Key derivation functions (KDF): What are they, what are their main purposes and how they can be used?

Question

What are KDFs? What are their main purposes? How they can be used, in other words, what's their drill in a cryptography scheme?

Answer 1

The HKDF paper provides as good a summary as any:

A Key derivation function (KDF) is a basic and essential component of cryptographic systems: Its goal is to take a source of initial keying material, usually containing some good amount of randomness, but not distributed uniformly or for which an attacker has some partial knowledge, and derive from it one or more cryptographically strong secret keys.

Here it's important that you understand how the term "random" is used in probability theory vs. how it's (ab)used by computer people. Very informally:

• When us computer folks say "random" we more often that not implicitly assume that we're talking about a discrete, finite, uniform and independent random variable—one that takes on any value drawn from a finite set with equal probability as all the others, and earlier outcomes do not influence later ones, the way coin flips or dice rolls behave.
• When statisticians say random, they aren't assuming as much. For a statistician, for example, a stereotypical random variable has a normal distribution ("bell curve"), where values cluster around a mean and disperse according to a standard deviation—the way, for example, that inexact physical measurements have random errors that cluster around the true value.

So reading the quote with that in mind, a KDF is a cryptographically strong function that takes input that is random in the statistician's sense and produces output that is pseudorandom in the cryptographer's (preferred) sense. This is useful in various contexts:

1. Diffie-Hellman key exchange with randomly selected keys produces a shared secret that is random in the statistician's sense, but its output is not uniformly distributed. So to use this secret as a symmetric key you pass it through some KDF.
2. Cryptographic random number generators refresh themselves periodically from the values obtained by measuring random events like oscillator states, network packet timing, mouse movements or key presses. These events are also not uniform, so a KDF can be used to fix that.
3. Passwords are also not uniform, so to turn passwords into keys we use KDFs. But in that case we use specialized password-based KDFs that also add a work factor to slow down brute force guesses.

Answer 2

KDF's or Key Derivation Functions are functions or schemes to derive key or output keying material (OKM) from other secret information, the input keying material (IKM). That information may be another key or, for instance a password. It is important that the secret contains enough randomness to generate keys, without an attacker to be able to perform attacks using information about the input.

A KDF has the following possible use cases:

• the extraction of entropy from the given IKM;
• the expansion of the extracted entropy to OKM of the right size;
• strengthening of a the IKM such as a password (in case of Password Based KDF's or PBKDFs);
• the one-way generation of multiple OKM's from a single IKM.

---

There are many forms of KDF's, and not all functions used as KDF are explicitly named as KDF's. For instance, the KDF of TLS is simply called "the PRF" for Pseudo-Random-Functions, which is a much more generic term.

Some KDF's have input limitations, some have output limitations and not all KDF's have the same configuration parameters.

The base construction of a KDF is:

input:

• a binary encoded secret or key;
• other information to derive a specific key (optional);
• output size (if configurable).

output:

• a derived key or derived keying material.

Furthermore, there are many different parameters possible:

• a salt;
• work factor (for PBKDF's);
• memory usage (for PBKDF's);
• parallelism (for PBKDF's).

The output of programming interfaces could also contain additional configuration or input parameters such as attributes of the output key. It's for instance logical to also include the type of the key such as "AES", so that the OKF can be stored in a container for AES keys.

---

Now the idea of a KDF is that it is one way, and that the output is indistinguishable from random. It should be hard to brute force the input keying material, if the input material contains a certain amount of randomness. KDF's are therefore usually build from one-way hashes or PRF's such as Message Authentication Codes (MAC algorithms).

Furthermore, the KDF should be deterministic. That means that the KDF itself is also a PRF.

---

So finally, the use cases:

• they are used as "password hashes", which perform strengthening of the IKF to create a OKF: the password hash which can be stored in a database (to prevent the actual passwords to be computed by an attacker that obtains a copy of the database);
• they are used to "concentrate" the entropy of the IKM, for instance the output of Diffie-Hellman key exchange is not 100% well distributed;
• they are used to derive multiple keys (of possibly different length / types) from the same IKM by specifying a specific info parameter for each key;
• they are used to expand the key material, while maintaining the security strength of the IKM.

As an example of the last point, you could retrieve a 192 bit triple DES key and IV from a single 128 bit source key as IKM by splitting the output OKM.

---

As indicated, there are many types and constructions of KDF's. On the one hand there are block cipher based KDF's that require a specific key size and output precisely one block size of keying material. On the other hand HKDF (probably the most advanced KDF right now) can work on any input size and it has a large output size.

---

There are basically two families of KDFs. The already mentioned PBKDF's such as PBKDF1, PBKDF2, bcrypt, scrypt, Argon2 take passwords that need to be strengthened as input keying material and then perform strengthening. KBKDF's - Key Based Key Derivation Functions - take key material that already contains enough entropy as input.