How can bcrypt have built-in salts

Question

Coda Hale s article  quot How To Safely Store a Password quot  claims that   bcrypt has salts built-in to prevent rainbow table attacks   He cites this paper  which says that in OpenBSD s implementation of bcrypt   OpenBSD generates the 128-bit bcrypt salt from an arcfour  arc4random 3   key stream  seeded with random data the kernel collects from device timings   I don t understand how this can work  In my conception of a salt   It needs to be different for each stored password  so that a separate rainbow table would have to be generated for each It needs to be stored somewhere so that it s repeatable  when a user tries to log in  we take their password attempt  repeat the same salt-and-hash procedure we did when we originally stored their password  and compare  When I m using Devise  a Rails login manager  with bcrypt  there is no salt column in the database  so I m confused  If the salt is random and not stored anywhere  how can we reliably repeat the hashing process  In short  how can bcrypt have built-in salts

User · Answer

This is from PasswordEncoder interface documentation from Spring Security,

 * @param rawPassword the raw password to encode and match
 * @param encodedPassword the encoded password from storage to compare with
 * @return true if the raw password, after encoding, matches the encoded password from
 * storage
 */
boolean matches(CharSequence rawPassword, String encodedPassword);

Which means, one will need to match rawPassword that user will enter again upon next login and matches it with Bcrypt encoded password that's stores in database during previous login/registration.

User · Answer

This is bcrypt   Generate a random salt  A  cost  factor has been pre-configured  Collect a password   Derive an encryption key from the password using the salt and cost factor  Use it to encrypt a well-known string  Store the cost  salt  and cipher text  Because these three elements have a known length  it s easy to concatenate them and store them in a single field  yet be able to split them apart later   When someone tries to authenticate  retrieve the stored cost and salt  Derive a key from the input password  cost and salt  Encrypt the same well-known string  If the generated cipher text matches the stored cipher text  the password is a match   Bcrypt operates in a very similar manner to more traditional schemes based on algorithms like PBKDF2  The main difference is its use of a derived key to encrypt known plain text  other schemes  reasonably  assume the key derivation function is irreversible  and store the derived key directly     Stored in the database  a bcrypt  hash  might look something like this       2a 10 vI8aWBnW3fID ZQ4 zo1G q1lRps 9cGLcZEiGDMVr5yUP1KUOYTa   This is actually three fields  delimited by        2a identifies the bcrypt algorithm version that was used  10 is the cost factor  210 iterations of the key derivation function are used  which is not enough  by the way  I d recommend a cost of 12 or more   vI8aWBnW3fID ZQ4 zo1G q1lRps 9cGLcZEiGDMVr5yUP1KUOYTa is the salt and the cipher text  concatenated and encoded in a modified Base-64  The first 22 characters decode to a 16-byte value for the salt  The remaining characters are cipher text to be compared for authentication    This example is taken from the documentation for Coda Hale s ruby implementation

User · Answer

To make things even more clearer   Registeration Login direction -   The password   salt is encrypted with a key generated from the  cost  salt and the password  we call that encrypted value the cipher text  then we attach the salt to this value and encoding it using base64  attaching the cost to it and this is the produced string from bcrypt    2a COST BASE64  This value is stored eventually   What the attacker would need to do in order to find the password     other direction  lt -    In case the attacker got control over the DB  the attacker will decode easily the base64 value  and then he will be able to see the salt  the salt is not secret  though it is random  Then he will need to decrypt the cipher text   What is more important   There is no hashing in this process  rather CPU expensive encryption - decryption  thus rainbow tables are less relevant here

User · Answer

I believe that phrase should have been worded as follows      bcrypt has salts built into the generated hashes to prevent rainbow table attacks    The bcrypt utility itself does not appear to maintain a list of salts  Rather  salts are generated randomly and appended to the output of the function so that they are remembered later on  according to the Java implementation of bcrypt   Put another way  the  hash  generated by bcrypt is not just the hash  Rather  it is the hash and the salt concatenated

[security] How can bcrypt have built-in salts?

Examples related to security

Examples related to hash

Examples related to internals

Examples related to bcrypt