Why is Bcrypt called a Key Derivation Function?

Question

I am trying to understand why is bcrypt called a Key Derivation Function?

I looked up the details of Ekfblowfish on Usenix article.

After reading it, I understood that:

1. The password is the encryption key. The length of the password can vary and so the length of the encryption key can vary (max is 56 bytes or 448 bits).
2. 128 bit salt, it does not provide the details about how this salt is generated? It only says, that the 128 bit salt along with the variable length encryption key is used to modify the S Boxes and the P Array.
3. When it says, Key Schedule, it refers to both, S Boxes and P Arrays. The Key Schedule keeps changing using the bits of 128 bit salt and the encryption key.

Now, what key are we deriving here? It is not clear, why is bcrypt called a Key Derivation Function?

So, does it mean that at the end of Expensive Key Schedule, we have a unique value for S boxes and P array contents which are further used to encrypt "OrpheanBeholderScryDoubt" using ECB mode.

So, aren't we deriving the Key Schedule (S boxes + P Arrays) instead of the Encryption Key (which is the same as the password that was supplied as an argument in the starting)?

Which key has been derived using Eksblowfish?

Answer 1

It's called a key derivation function because that's what you'd typically use its output for — as a key for some other cryptographic algorithm. (Of course, you can also use the output of Bcrypt for other purposes, e.g. storing it in a database as a password hash, but that's really a secondary use case.)

In general, key derivation functions (KDFs) serve a number of purposes:

• Key separation: This is the most basic use case for KDFs. Basically, you have one key, but need several. This might be e.g. because you're a server that needs to communicate with multiple clients using distinct keys for each, or simply because the algorithms you're using together (e.g. a cipher and a MAC) have only been proven secure under the assumption that they each have separate and independent keys. You can solve this problem by using a KDF (with different salts) to derive multiple (quasi-)independent subkeys from your original key.

• Key expansion: Related to the above, some algorithms may require rather long keys for practical reasons, even though the desired security level against brute force guessing could be met with a shorter key. In such cases, you can use a KDF to effectively extend the length of your key.

• Key whitening: Many encryption algorithms, such as block ciphers, require a key that consist of a fixed number of (effectively) random bytes. If you have a key that is not in the required format (such as an arbitrary-length passphrase, or a Diffie-Hellman shared secret), you can use a KDF that accepts arbitrary input key material to hash it into a byte string of suitable size.

• Key stretching: This is the specific use case for which Bcrypt (and other "password-based" KDFs like PBKDF2 or scrypt) are designed for. Basically, say you have a user-entered passphrase that may have a relatively small amount of entropy (say, from 20 to 40 bits), in addition to all the other issues mentioned above (too short / too long, wrong format), and you want to use it to encrypt/decrypt some data (or to authenticate the user) while making it hard to break the encryption by guessing the passphrase by brute force.

  The solution is to use a deliberately slow (and possibly memory-hungry) KDF, like Bcrypt, to derive an encryption key from the passphrase. By making the derivation process deliberately take a very long time (say, a whole second, which might be a million times more than a simple non-stretching key derivation would take), you can slow down any brute force attacks by the same factor. The reason it's called "key stretching" is, presumably, because you're taking a "short" (low-entropy) key and effectively making it as resistant to brute force attacks as a "longer" (higher-entropy) one.

Now, that's a whole bunch of jobs, and indeed one might argue against lumping all functions designed for some or all of these tasks under the single label "KDF", but that's how the established terminology works. There is some justification for it, since systems that require the latter properties often also require the former.

Still, different KDFs do have different strengths; for example, Bcrypt is pretty good for key stretching, but somewhat awkwardly limited in other respects. If I wanted a Bcrypt-based system that handled all of the points above, I might consider e.g. combining Bcrypt with HKDF (from RFC 5869), like this:

1. Use HKDF-Extract to whiten the input key material / passphrase, avoiding the input length limits of Bcrypt.
2. Feed the pseudorandom key generated by HKDF-Extract through Bcrypt to stretch it against brute force attacks.
3. Use the output of Bcrypt as the PRK for HKDF-Expand, to provide efficient key separation and expansion.

Answer 2

BCrypt is not a key derivation function, it is a password hashing algorithm.

If you needed to derive a key from a password, bcrypt has no capability to generate a 256-bit key.

On the other hand, people do use actual key derivation functions, e.g.:

• pbkdf2
• scrypt
• argon2

as the basis for their own password hashing algorithms.

These key derivation functions all:

• accept a password
• accept a "cost"
• accept the number of bytes you'd like generated
• and derive a key of the requested number of bytes

But bcrypt cannot do that. Bcrypt always and only ever generates 24 bytes.

The internal implementation detail of bcrypt is that it encrypts the text:

OrpheanBeholderScryDoubt (24 characters)

and encrypts it 64 times.

The resulting 24 bytes is then returned to you in a special serialized string form (along with other stuff):

$2a$10$Ro0CUfOqk6cXEKf3dyaM7OhSCvnwM9s4wIX9JeLapehKK5YdLxKcm
\___________________________/\_____________________________/
              |                            |
          other stuff             24-bytes of "strong" data

And while you can be clever enough and abuse bcrypt - ripping out the final 24-bytes of the base-64 encoded data:

hSCvnwM9s4wIX9JeLapehKK5YdLxKcm (24-bytes of base64 encoded data)

But you didn't derive a key.

• Not only because nowhere was a parameter passed asking how many bytes you'd like to derive
• but because it's only 192-bits
• if you wanted to derive a 256-bit key
• you're out of luck
• because bcrypt is not a key-derivation function

It's a password hashing algorithm

Abuse bcrypt to use it as KDF

And perhaps you can be clever, and use the output from bcrypt as the basis to build a key derivation function:

//Derive 256-bit key using bcrypt output as the "salt":
String password = "correct battery horse staple";
String salt = bcrypt(password, 14);
Byte[] key = PBKDF2(password, salt, 32, 1);

This, incidentally is how scrypt works:

//Derive 256-bit key using BlockMix/ROMix/Sasls8 output as the "salt":
String password = "correct battery horse staple";
String salt = ROMix(password, GetRandom(16), 14, 8, 1);
Byte[] key PBKDF2(password, salt, 32, 1);

But bcrypt in and of itself is not a key derivation function; it's a password hashing algorithm.

Answer 3

It's called key derivation because it is used to obtain a "strong" key based on a key you own and is not so strong. Suppose a user has a password 12345 and an online service needs authentication. In order to verify the correctness the server doesn't store 12345 but it stores bcrypt(12345+salt) which further makes is more difficult for an attacker to break its one-wayness.

Answer 4

In addition to Ilmari's excellent answer I would like to address your questions and clarify some points for you:

I am trying to understand why is bcrypt called a Key Derivation Function?

Because it derives a key from given input. This key is then used as unique value for a password in the case it is used for password hashing. bcrypt is a Password Based KDF. This means that the key is derived from a password (together with the salt and iteration count of course, the password is the principal input though).

...

After reading it, I understood that:

the password is the encryption key. The length of the password can vary and so the length of the encryption key can vary (max is 56 bytes or 448 bits). 128 bit salt, it does not provide the details about how this salt is generated? It only says, that the 128 bit salt along with the variable length encryption key is used to modify the S Boxes and the P Array. When it says, Key Schedule, it refers to both, S Boxes and P Arrays. The Key Schedule keeps changing using the bits of 128 bit salt and the encryption key.

Now, what key are we deriving here? It is not clear, why is bcrypt called a Key Derivation Function?

The password is used as input for the key for the Eksblowfish algorithm. This should be considered an implementation detail.

So, does it mean that at the end of Expensive Key Schedule, we have a unique value for S boxes and P array contents which are further used to encrypt "OrpheanBeholderScryDoubt" using ECB mode?

So, aren't we deriving the Key Schedule (S boxes + P Arrays) instead of the Encryption Key (which is the same as the password that was supplied as an argument in the starting)?

First the key schedule for which the password is used as part of the input parameters, then the encryption which results in the derived key. The derived key is just a bunch of bytes (the ctext` from your article).

Of course you should not directly store the ctext directly if you want to use it as (base for a) key. Storing Concatenate(cost, salt, ctext) is mainly useful for using it as a password hash. If it is a string starting with $2y$ then the concatenation is stored as a crypt compatible string.

Which key has been derived using Eksblowfish?

The output ctext. You can use this output for any cipher or as password hash. Your confusion arises from mixing the output with the implementation.