Why is Bcrypt called a Key Derivation Function? 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:


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?

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?
It's called a key derivation function because that's what you'd typically use its output for &mdash; 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:


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