bcrypt

from Wikipedia, the free encyclopedia

bcrypt is a cryptological hash function that was specially developed for hashing and storing passwords . The function based on the Blowfish algorithm was designed by Niels Provos and David Mazières and presented to the public at the USENIX conference in 1999.

background

To provide users with an application or website authentication is generally used a combination of username or e-mail address and a password. The website has to save the password for this, but saving the password in unencrypted form is a considerable security risk. If the password and user name become known to a third party (e.g. if the website is hacked), they can authenticate themselves to the website. Since many users use the same combination of user name and password for many services, this can also affect other services.

This problem is usually circumvented using cryptographic hash functions. A hash value of the password is determined and stored with such a function. Such functions are characterized by the fact that the original password cannot be restored. To authenticate the user, the user's input is hashed with the same function and the two hash values ​​are compared - if the original passwords are the same, the hash values ​​are also the same.

The hash functions MD5 and the Secure Hash Algorithm (SHA1 etc.) have been developed with the aim of hashing the data as efficiently as possible, as they are also used to verify large files, for example. On the other hand, this efficiency makes it easier to guess the passwords using brute force attacks or to create so-called rainbow tables , which is why they should no longer be used for hashing passwords.

design

Password hashing methods such as PBKDF2 , scrypt and also bcrypt were developed in contrast to regular hashing methods with the aim of making hashing as complex as possible. For normal application purposes, this effort is negligible compared to other factors, only if the calculation is to be carried out frequently in succession (such as in a brute force attack) does it slow down considerably.

The presentation by bcrypt introduced some design criteria for password-based key derivation functions for this purpose:

  • Bcrypt has a cost factor that can be set depending on the purpose of the application and that defines the workload involved in calculating hash values. This factor can also increase the effort, if the performance of the computers continues to develop in the future.
  • The function should be optimized for the context for which it was designed. Performance advantages for hardware implementations and other programming languages ​​should turn out to be slight, since such advantages benefit an attack.
    • A (moderate) memory requirement limits the benefit of hardware optimizations. Bcrypt requests 4 KB of RAM.
    • Software implementations should be based on operations that are optimized for CPUs, such as exclusive-or, addition or shift operations.

The NIST recommendation from 2010 for PBKDF2 only takes the first criterion into account. However, these criteria have been included and expanded in the key derivation function scrypt and by the Password Hashing Competition .

functionality

Bcrypt only differs from Blowfish block encryption in a few ways. The slowdown mainly takes place within the password-dependent calculation of the round key and the S-boxes . These are modified in several rounds depending on the salt and the password by the EksBlowfishSetup function . The number of these rounds is 2 to the power of the cost parameter. Then the 192-bit value “OrpheanBeholderScryDoubt” is encrypted 64 times in ECB mode with the round keys and S-boxes generated in this way .

The result of the bcrypt reference implementation is a 60-character string that has been adapted to the requirements of the original application, the user authentication of OpenBSD . The character string is introduced with the "$" character and the version number, cost factor and a character string consisting of salt and hash value are separated. Salt and hash value are mapped with a special Base64 coding; the actual hash value is contained in the last 31 characters. This format is also adopted by other implementations.

safety

The length of the password is limited to 56 bytes with bcrypt, even if most passwords do not exceed this limit. The memory requirement of 4 KB does not meet the requirement to limit hardware implementations, for example in FPGAs and ASICs . Taking into account the energy efficiency and the costs for the hardware, bcrypt can be attacked primarily by parallel computing FPGAs ( dictionary attack or brute force method ). An attack scenario with special ASICs would be even more promising. Still, bcrypt often scores better than most other password-based key derivation functions, apart from scrypt, when it comes to attacks with specialized hardware .

Further development

With Pufferfish by Jeremi Gosney, an algorithm is taking part in the Password Hashing Competition that is heavily based on bcrypt. The yescrypt algorithm , which is based on scrypt , also adopts the mechanism of fast, random access, which makes the algorithm GPU-resistant.

Web links

Individual evidence

  1. ↑ Meltem Sonmez Turan; Elaine B. Barker; William E. Burr; Lidong Chen: Recommendation for Password-Based Key Derivation Part I: Storage Applications . NIST SP - 800-132, 2010.
  2. ↑ Password Hashing Competition: Call for submissions ( Memento of the original from September 2, 2013 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. . Criteria for password-based key derivation functions. @1@ 2Template: Webachiv / IABot / password-hashing.net
  3. ↑ Katja Malvoni, Solar Designer, Josip Knezovic: Are Your Passwords Safe: Energy-Efficient Bcrypt Cracking with Low-Cost Parallel Hardware . Investigation into the performance of hardware for breaking bcrypt hash values ​​(pdf). (English)
  4. ↑ Energy-efficient bcrypt cracking: Takeaways . Presentation at openwall. (English)
  5. ↑ Wiemer, F., Zimmermann, R .: High-speed implementation of bcrypt password search using special-purpose hardware . In 2014 International Conference on Reconfigurable Computing and FPGAs (ReCoFig), 2014.
  6. ^ Colin Percival: Stronger Key Derivation via Sequential Memory-Hard Functions . Presentation at the BSDCan'09. On page 14, the cost of breaking different functions is compared.
  7. ↑ European Union Agency for Network and Information Security: Algorithms, key size and parameters report - 2014. P. 53. (pdf)
  8. ↑ http://www.openwall.com/presentations/Passwords12-The-Future-Of-Hashing/ Contains a comparison of FPGAs / ASICs and GPUs on pages 45 and 46.
  9. ↑ Markus Dürmuth and Thorsten Kranz: On Password Guessing with GPUs and FPGAs . 2014 (pdf).
  10. ↑ Wiki of the Password Hashing Competition: Pufferfish. (English)
  11. ↑ Wiki of the Password Hashing Competition: yescrypt. (English)