up vote 361 down vote favorite
134

Coda Hale's article "How To Safely Store a Password" 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?

share|improve this question
up vote 475 down vote accepted

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. 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 in 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.

share|improve this answer
1  
Would you have more details as to why cost factor of 10 would not be enough? In Grails, I noticed that 10 is the default value for cost factor/log rounds for bcrypt so it might be worth updating given your suggestion. – paul_sns May 14 '12 at 22:52
    
@erickson a cost of 16 takes almost 10 seconds on my host .. I can't have that every time someone's logging in. Is my hardware really just that crappy? – Explosion Pills Jun 21 '12 at 0:54
    
@ExplosionPills what language and library are you using? If an interpreter is executing most of the algorithm it could appear much slower. – erickson Jun 21 '12 at 2:26
    
@erickson php with crypt (CRYPT_BLOWFISH). Am I screwed? – Explosion Pills Jun 21 '12 at 2:43
36  
The cost factor for bcrypt is exponential, or rather, a cost factor of 10 means 2^10 rounds (1024), a cost factor of 16 would mean 2^16 rounds (65536). It's natural then that it would take 5-10 seconds. It should take about 64 times as long as a cost factor of 10 does. To clear up other misinformation, PHP's crypt function uses the unix crypt library which is implemented in c. – thomasrutter Jul 3 '12 at 13:02
up vote 104 down vote

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.

share|improve this answer
    
Related: stackoverflow.com/questions/5881169/… – Gumbo Jul 26 '11 at 15:40
6  
OK, so I sign up for a site and choose a the password "foo". Bcrypt adds a random salt of "akd2!*", resulting in "fooakd2!*", which is hashed and stored. Later, I try to sign in with password "bar". To see if I'm correct, it needs to hash "barakd2!*". If the salt was generated randomly to start with, how does it know how to add it back to "bar" before hashing and comparing? – Nathan Long Jul 26 '11 at 15:40
26  
@Nathan: bcrypt knows how to extract the salt back out of the generated output (which is stored in the database). When it comes time to authenticate, bcrypt separates the original output into its hash and salt components. The salt component is applied to the incoming password typed by the user. – Adam Paynter Jul 26 '11 at 15:46
7  
To answer Nathan Long's comment, a good way of thinking of this is that salts are not meant to be secret. This is why the salt is included in the output from the bcrypt function as one of the answers pointed out above. The salt is there to prevent rainbow tables, which are lists of common passwords, or just brute force, etc... of different passwords but hashed. Without salt, the hash for a password in database A would be the same as a hash for a password in database B. Salt merely changes up the hash values making it harder for someone who stole the database to decrypt (unhash) passwords. – Joseph Astrahan Jan 5 '16 at 16:28
2  
@Nathan but can an attacker just remove the known salts in all passwords and then create a table with them? – Oscar Aug 11 '16 at 22:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.