What are KDFs? What are their main purposes? How they can be used, in other words, what's their drill in a cryptography scheme?
Key derivation functions (KDF): What are they, what are their main purposes and how they can be used?
2$\begingroup$ ...uhm, to derive keys from secrets? $\endgroup$– SEJPMOct 17, 2016 at 18:02
1$\begingroup$ A common use of a KDF is to take a human readable text password and turn it into the bits and bytes to be used as the key to a cryptographic algorithm. Maarten describes Password Based Key Derivation Functions below. The KDF means the human doesn't have to remember an exactly 32-byte hex password for an AES-256 key, or an 8-byte hex password for a DES key. $\endgroup$– John DetersOct 17, 2016 at 21:22
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:
- 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.
- 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.
- 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.
1$\begingroup$ how come CSPRNG are not uniform (discrete, finite, uniform and independent random)? I thought one of the characteristics of something being a CSPRNG is for it to be discrete, finite, uniform and independent random. So why is a KDF needed with output of CSPRNG? $\endgroup$ Nov 10, 2021 at 3:09
$\begingroup$ @FinlayWeber CSPRNG are uniform. Even non-CS halfway decent PRNGs are uniform. A KDF can be used as a building block inside a CSPRNG. It's the random events that are not uniform. $\endgroup$ Jun 13, 2022 at 11:27
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:
- a binary encoded secret or key;
- other information to derive a specific key (optional);
- output size (if configurable).
- 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.
$\begingroup$ For PBKDF in the last paragraph, could you please be more explicit about strengthening? My understanding is that the problem to solve here about password is its inadequate entropy rather than non-uniformity. Does this mean a randomly generated salt must be used in this case (to provide the additional entropy)? What if we simply want the output keying material as secure as the password (even if it doesn't have enough entropy to qualify a cryptographic key) - can we simply use a constant salt or no salt? $\endgroup$– CykerJul 14, 2018 at 6:15
3$\begingroup$ @Cyker No, a salt is to avoid comparison of the derived key material and against rainbow tables. It does not increase the entropy simply because the salt is supposed to be known by all (a secret salt, if used, is also called a pepper, but it requires you to have a pre-established key). The strengthening is basically just a amount of work that needs to be performed for each password hash. This slows the attacker down that tries a dictionary attack on the password, but it also slows down the regular user. And it only slows down attacks by a constant amount. $\endgroup$– Maarten Bodewes ♦Jul 14, 2018 at 10:34