Password-Based Key Derivation Function 2

cryptography security

Definition

Password-Based Key Derivation Function 2

PBKDF2 is a password-based key derivation function defined in PKCS #5 / RFC 2898. It derives a cryptographic key of arbitrary length from a password by iterating a pseudorandom function.

For password-based authentication, the derived key is used as the stored “hash” of the password.

Parameters

Pseudorandom Function $\text{PRF}$

A keyed function with two parameters and fixed output length $hLen$ (for example, HMAC-SHA256).

Password $P$

The user-provided secret.

Salt $S$

A random per-user value.

Iteration Count $c$

The number of iterations; typically $10^4$ to $10^6$.

Desired Key Length $kLen$

The number of bytes to output.

Algorithm

For each block $i=1,2,\dots ,\lceil kLen/hLen\rceil$:

$$\begin{array}{rl}{U}_1& =\text{PRF}(P,S\Vert {\text{INT}}_{32}(i))\\ U_j& =\text{PRF}(P,U_{j-1})\text{for }j=2,\dots ,c\\ & \\ T_i& =U_1\oplus U_2\oplus \cdots \oplus U_c\end{array}$$

The derived key is the concatenation truncated to $kLen$ bytes:

$$\text{DK}=(T_1\Vert T_2\Vert \cdots \Vert T_{\lceil kLen/hLen\rceil }{)}_{[0\dots kLen-1]}$$

¹

Security

Work Factor

An attacker must perform $c\cdot \lceil kLen/hLen\rceil$ evaluations of the PRF per guess. The iteration count $c$ directly scales the attacker’s cost.

Parallelisability

PBKDF2 can be configured to arbitrarily increase computation time. However, it requires little memory and can be easily parallelised. ASICs and GPUs can therefore be used for highly parallelised offline attacks.

Not Memory-Hard

Modern alternatives — scrypt, Argon2, yescrypt — are memory-hard: they derive the key from a large array whose computation is time-intensive. Elements are accessed depending on the password characters. Parallelising an offline attack then requires either huge memory availability (to store the array) or large computation time (to recompute array elements on the fly).

PBKDF2 is not memory-hard. An attacker can evaluate many PRF calls in parallel on GPUs or ASICs. For new systems, memory-hard alternatives are preferred.

Footnotes

1. 192.019 Introduction to Security ↩