How can bcrypt have built-in salts?

Question

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?

Answer 1

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; 2¹⁰ 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.