1. Introduction

In this tutorial, we’ll define Key Derivation Functions (KDFs) and present their purposes.

Then, we’ll explain the properties that characterize them and introduce their different types. Last but not least, we’ll talk about their applications.

2. Definition and Purpose

A KDF is a cryptographic algorithm designed to generate a secure secret key from a single key value. Its primary purpose is to protect sensitive data by miscarrying the attacker’s temptations to predict or decrypt the used keys.

Generally, a KDF takes as input a secret key, which can be a password, a master key, or some secret value. However, it may also take other inputs depending on the specific KDF used, such as a salt value, a difficulty level, and a key size.

A typical formulation of a KDF is:

Visually:

The salt is a randomly generated value stored alongside the secret key to strengthen the resilience to rainbow tables attacks.

Then, the Difficulty level indicates the computational efforts required to compute the derived key, generally referring to the number of iterations to run the function. This determines how secure the KDF is against brute-force attacks.

The Key size specifies the desired length of the output key. It depends on the specific application and security requirements.

3. KDF Techniques

We usually use KDFs for these operations:

• Key stretching
• Key whitening
• Salting
• Key separation

3.1. Key Stretching

In key stretching, we apply a one-way function that iteratively processes the secret key, using the output of each iteration as the input for the next. Specifically, it’s a mathematical function that is easy to calculate but computationally infeasible to invert. This technique increases the computational difficulty, i.e., the time and resources required for the key derivation process.

Key stretching protects against brute-force attacks, where the adversary exhaustively tries all possible key combinations to guess the key.

3.2. Key Whitening

Key whitening is a security measure that involves adding a fixed, secret value to the input key before passing it through a KDF.

This value, known as the whitening key, is only shared between the parties involved in the key exchange. The goal is to increase the unpredictability of the input key, making it more secure against attacks.

3.3. Salting

On the other hand, salting involves appending a random value to the input key. The value is specific to each password or user.

We call it salt and append it to the key to increase the length. We store it alongside the KDF output key to use during authentication or decryption. The purpose of salting is to resist attacks that exploit situations when two users have the same password.

3.4. Key Separation

Key separation is a method of generating multiple keys from a single master key.

Typically, it divides the input key into subkeys and uses them to generate a list of output keys. This technique helps ensure the generated keys aren’t related, as we use different parameters and KDFs for each input.

This approach offers a higher level of security and flexibility in key management. If an attacker compromises one key, it won’t affect the other keys’ security, making key separation a valuable technique in many security applications.

4. Properties of a KDF

There are several properties that a KDF should have to be secure and efficient:

• Determinism: when passing the same input to the function, we should always get the same output
• No collisions: when passing two different input keys to the KDF, it should be almost impossible to obtain the same output keys
• Key independence: no matter the input and his weakness level, a KDF should behave similarly and generate an output of the same size
• One-way process: it should be hard or impossible to compute the input key from the output key
• Resistance to brute-force attacks: it should be computationally impossible for an adversary to guess the key by trying every possible combination of characters

5. Classification

Key derivation functions (KDFs) can be classified based on their algorithm and input type.

One common approach to KDFs is to use hash functions, such as SHA-256 and SHA-3, to generate keys. KDFs that utilize hash functions are KDF1, KDF2, and PBKDF2.

Another technique is to use Message Authentication Codes (MACs) to derive a key from input data, such as the HKDF algorithm, which is based on the H-MAC algorithm.

KDFs can also be categorized based on the type of input they accept. Password-based KDFs, including PBKDF2, bcrypt, scrypt, and Argon2, take passwords as input to generate keys. We often use these KDFs in password storage applications to protect user passwords against attacks.

On the other hand, key-agreement KDFs use shared secret values generated by key agreement protocols like Diffie-Hellman and Elliptic Curve Diffie-Hellman to derive output keys. Examples of such KDFs include HKDF and KDF2, which are commonly used in secure communication systems.

6. Applications in Cryptography

KDFs have various applications in cryptography. One such application is disk encryption, which involves converting data stored on a computer’s hard disk into a code difficult for unauthorized attackers to decrypt. KDFs use the user’s password or other secret values to generate the encryption key.

We also use KDFs in key exchange protocols like the Diffie-Hellman algorithm. This protocol allows two parties to establish a shared secret key over an insecure communication channel using public keys and random values. We use a KDF on the Diffie-Hellman output key to derive a uniformly distributed key that can be adapted for authentication, encryption, or other cryptographic operations.

Furthermore, KDFs can also be used to store passwords securely. Due to low entropy, user passwords are often the weakest element in digital systems. Here, KDFs turn passwords into cryptographic keys that are more efficient and secure against attacks.

Generally, KDFs are resource-intensive in terms of computing and memory, making it harder for adversaries to break them since they have to run the KDF many times. Meanwhile, a legitimate user will only need to run it once.