Key Derivation Functions: Turning a Low-Entropy Password Into a Cryptographic Key

The core idea: buy an asymmetric cost, not a secret

A KDF answers a precise problem. You have a secret with low entropy — a human password carries maybe 20–40 bits, not the 128+ bits a cipher key needs — and you need a key that behaves as if it had full entropy. Naively hashing the password (K = SHA-256(password)) fixes the length but not the entropy: an attacker who guesses your password still recovers K, and each guess costs one cheap hash.

The KDF's job is to widen the gap between the defender's per-key cost and the attacker's per-guess cost. It does this with three ingredients, and the invariant that ties them together is: every candidate password an attacker tries must pay the full derivation cost, with no shortcut and no precomputation.

• Salt — a unique random value (≥16 bytes) stored alongside the output. It makes each derivation distinct, so an attacker cannot precompute a rainbow table or amortize one cracking run across many users. Salt does not need to be secret; it needs to be unique per password.
• Stretching (work factor) — the KDF repeats a hash or fills memory so a single derivation costs a chosen amount of time/space. Tune it so a legitimate login is ~50–250 ms and an attacker's billion-guess run becomes economically absurd.
• Pseudorandomness — the output is indistinguishable from random even though the input was structured, so K is a safe cipher/MAC key.

Note the vocabulary trap: a password hash (verify a login) and a password-based KDF (produce a key to encrypt a disk) are the same construction used two ways. Argon2 and scrypt serve both roles; the difference is whether you store the output for comparison or feed it to AES.

PBKDF2: iterated PRF, the workhorse standard

PBKDF2 (Password-Based Key Derivation Function 2), defined by Burt Kaliski in PKCS#5 v2.0 (2000) and re-published as RFC 8018, is the simplest surviving design. It applies a keyed pseudorandom function — almost always HMAC-SHA-256 — c times, chaining the outputs with XOR.

To produce a dkLen-byte key it derives one HMAC-sized block at a time. For block index i (1-based), let the salt be extended with the big-endian counter INT(i):

U₁ = HMAC(password, salt ∥ INT(i))
U₂ = HMAC(password, U₁)
...
U_c = HMAC(password, U_{c-1})
T_i = U₁ ⊕ U₂ ⊕ … ⊕ U_c        // XOR-fold all c iterations
DK  = T₁ ∥ T₂ ∥ … ∥ T_⌈dkLen/hLen⌉   // truncate to dkLen

• The chaining is strictly sequential: U_{j} depends on U_{j-1}, so an attacker cannot parallelize within one guess. The XOR-fold ensures every intermediate contributes, preventing a shortcut to U_c.
• The password is the HMAC key, so it is re-absorbed every iteration — you cannot precompute a hash state and skip the password.

PBKDF2's fatal weakness is that HMAC-SHA-256 needs only a few hundred bytes of state. That makes it cheap on GPUs and trivial on ASICs/FPGAs, where thousands of cores each run the sequential chain in parallel across different guesses. It has no memory-hardness knob at all. OWASP's 2023 guidance is 600,000 iterations for PBKDF2-HMAC-SHA-256 — and even then it is the weakest acceptable choice, kept alive mainly by FIPS 140 compliance and hardware support.

Memory-hardness: why scrypt and Argon2 win

An attacker's real advantage is silicon: a custom ASIC can compute SHA-256 orders of magnitude more cheaply per hash than your server's CPU. Iteration count alone does not close this gap, because it scales the same on both sides. The countermeasure, formalized by Colin Percival's scrypt (2009), is memory-hardness: force the derivation to use a large, unpredictable amount of RAM, because on-chip SRAM is the one resource ASICs cannot cheaply multiply.

scrypt's engine is ROMix over a large array V[0…N-1] of hash-block-sized elements:

• Fill phase — compute V[0]=X, then V[i]=BlockMix(V[i-1]) for i=1…N-1. This costs O(N) time and O(N) space.
• Mix phase — do N more steps where each reads V[j] at a data-dependent index j = integerify(X) mod N, i.e. an index the attacker cannot predict without holding the whole array.

The invariant that gives memory-hardness its teeth is the time–memory trade-off (TMTO) bound: an attacker who stores only N/k of the array must recompute the missing entries on demand, paying Θ(k) extra time per lookup. The product time × memory stays Ω(N²), so shrinking memory buys you nothing overall. That N² area-time cost is what a hardware attacker actually pays for.

Argon2 — winner of the 2015 Password Hashing Competition, standardized in RFC 9106 — refines this with three cost parameters (memory m in KiB, passes t, parallelism p) and three variants: Argon2d (data-dependent addressing, max ASIC resistance), Argon2i (data-independent, resistant to cache-timing side channels), and Argon2id (first half of the first pass independent, rest dependent) — the recommended default. RFC 9106's first recommended option is m = 2 GiB, t = 1, p = 4 (with a lighter m = 64 MiB, t = 3, p = 4 option for constrained contexts).

Complexity analysis: the cost is the feature

For a KDF, high complexity is intentional — you are buying attacker work — so the analysis is about the exact knob-to-cost relationship, not about being fast.

• PBKDF2: to derive an hLen-byte key costs exactly c HMAC calls → Θ(c) time. For a longer key of ℓ blocks it is Θ(c · ℓ) hash calls. Space is O(1) — a few hundred bytes — which is precisely the flaw: constant space means an ASIC packs millions of cores.
• scrypt: with array size N, block factor r, parallelism p, time is Θ(N · r · p) and memory is Θ(N · r). The defender's cost is linear in N; the attacker's area-time cost is Θ(N²) when memory is minimized. Doubling N quadruples the attacker's silicon cost while only doubling yours.
• Argon2: time is Θ(t · m) memory operations (t passes over an m-block array); memory is Θ(m); the p lanes give up to Θ(p) parallel speedup on your multicore server. Its area-time lower bound against reduced-memory attackers is likewise super-linear, tunable independently of time via m.

The design goal, stated as an inequality: choose parameters so that cost_defender ≈ 100 ms per derivation while cost_attacker = cost_defender × (guesses needed) exceeds their budget. If a password has ~40 bits of entropy (≈10¹² guesses) and each guess costs 100 ms of GPU-equivalent work, a full search costs on the order of thousands of GPU-years — which is the whole point.

HKDF (RFC 5869) is the odd one out: it is O(1)-ish and deliberately fast. It is not for passwords. Its two phases are PRK = HKDF-Extract(salt, IKM) (concentrate entropy from already-high-entropy input material, e.g. a Diffie-Hellman shared secret) and OKM = HKDF-Expand(PRK, info, L) (stretch to L bytes with a per-context info label). Use HKDF when the input is already random; use Argon2/scrypt/PBKDF2 when the input is a human password.

Choosing and tuning a KDF in practice

Which KDF and which numbers? Decide by threat model and constraints, then benchmark on your real hardware.

• New systems, server-side: use Argon2id. Start from RFC 9106 (m = 64 MiB, t ≥ 2, p = 1 is a common practical floor; more memory if you can afford it), then raise m until derivation takes ~100–500 ms under peak login load. Memory is your strongest lever — it is what ASICs cannot cheaply scale.
• FIPS-only or embedded/legacy hardware: use PBKDF2-HMAC-SHA-256 with c ≥ 600,000, accepting that it is GPU-friendly. It is the compliance and interoperability choice, not the security-optimal one.
• bcrypt remains a solid default in ecosystems that ship it (it has a small 4 KiB working set that thwarts naive GPU attacks), but note its 72-byte password truncation and lack of a memory knob.
• Deriving a key from a high-entropy secret (TLS 1.3 traffic keys, an X25519 shared secret, splitting a master key into sub-keys): use HKDF, not a password KDF — you do not need stretching, you need clean pseudorandom expansion with domain-separating info labels.

Where these run at scale: 1Password and Bitwarden derive vault keys with PBKDF2/Argon2; LUKS/dm-crypt full-disk encryption uses Argon2id (and formerly PBKDF2) for the key-slot KDF; Signal, WhatsApp, and TLS 1.3 use HKDF throughout their key schedules; WireGuard uses HKDF (BLAKE2s). Storage formats encode the parameters inline — e.g. $argon2id$v=19$m=65536,t=3,p=4$salt$hash — so you can raise cost over time and re-derive on next login without breaking old records.

Pitfalls, edge cases, and attacks

KDFs fail in the details. The common ways to get it wrong:

• No salt or a reused/static salt. This re-enables rainbow tables and lets one cracking run hit every user with the same password. Salt must be unique per credential and generated from a CSPRNG; ≥16 bytes.
• Cost parameters too low. Numbers from a 2010 tutorial (PBKDF2 with c=1,000; scrypt N=2¹⁴) are now cheap. Re-benchmark against current hardware and store the parameters so you can upgrade in place.
• DoS by over-tuning. Argon2 with 2 GiB per login is a self-inflicted memory-exhaustion attack — an unauthenticated flood of logins can OOM the server. Bound concurrency, and size memory to survive peak load.
• Side channels. Argon2d and scrypt use data-dependent memory addressing, so cache-timing leaks can aid an attacker who shares the machine. Use Argon2id to keep the first pass data-independent.
• Non-constant-time comparison. When a KDF output is used to verify a login, compare with a constant-time equality check; a byte-by-byte == leaks a timing oracle.
• Deriving multiple keys from one derivation. Do not reuse one KDF output as both an encryption key and a MAC key. Run a proper expansion (HKDF-Expand with distinct info labels) so sub-keys are independent — this is domain separation.
• bcrypt's 72-byte cap and null-byte truncation: long passwords are silently shortened, which has produced real vulnerabilities (e.g. pepper-prefix designs). Pre-hash to a fixed length if you must feed long inputs to bcrypt.

The overarching lesson mirrors the LinkedIn breach: a KDF is only as strong as its cost parameters and salt discipline. The algorithm choice matters, but a well-salted Argon2id with an out-of-date memory setting can still fall — the knob must track the attacker's hardware, forever.

Password-based KDFs and the extract-then-expand KDF, by cost model and resistance

KDF	Year / author	Cost knobs	GPU/ASIC resistance	Standard
PBKDF2	2000, Kaliski (RSA)	iteration count c	Weak (CPU-cheap, tiny memory)	RFC 8018 / PKCS#5
bcrypt	1999, Provos & Mazières	cost (log rounds)	Moderate (4 KB working set)	OpenBSD / de facto
scrypt	2009, Percival	N (mem), r, p	Strong (memory-hard, TMTO-bounded)	RFC 7914
Argon2id	2015, Biryukov et al.	m (KiB), t (passes), p (lanes)	Strongest (data-dep + indep)	RFC 9106 / PHC winner
HKDF	2010, Krawczyk	none (not password-hardening)	N/A — for high-entropy input	RFC 5869