Password-Based Key Derivation and What Iteration Counts Buy

A password is not a key. It is a short, low-entropy, human-chosen string, often fewer than 40 bits of real uncertainty and frequently drawn from a set of a few thousand strings that appear in every leaked corpus. Turning it into a key means running a function that is deliberately expensive, so that each guess costs the attacker measurable work rather than a single hash. The parameters of that function are the entire defence, and their effect is arithmetic rather than magical.

Why hashing once is not derivation

If a key is the SHA-256 digest of a password, an attacker with a candidate list tries each password, hashes it, and compares against the target. A general-purpose hash is designed to be fast: hardware evaluates billions of SHA-256 compressions per second across a single device, and far more across a rack of them. The per-guess cost is so low that the password’s own entropy becomes the only barrier, and a few tens of bits of entropy fall quickly.

Derivation functions change the cost per guess in three ways. They iterate a mixing function many times, so each guess costs that many invocations. They add a per-credential salt, so the work cannot be shared across a set of targets. They may require a large memory allocation, so parallel hardware cannot be saturated cheaply.

Salt is the cheapest and most important of the three. A salt is a random value, typically 16 bytes or more, stored alongside the derived output and fed into the function. Without it, two users with the same password derive the same key, and an attacker who precomputes a table of digests for a dictionary recovers every matching password at once. With a distinct salt per credential, the precomputation must be repeated per target, and the cost of the table multiplies by the number of targets. Salt does not make any individual guess harder; it removes the amortization.

The iteration chain in PBKDF2

PKCS #5 version 2.1, published as RFC 8018, defines PBKDF2. The construction takes the password, the salt, an iteration count, and a desired output length, and produces blocks by repeatedly applying a pseudorandom function — HMAC with a chosen hash — and XORing the results:

import hashlib, hmac

def pbkdf2_block(password: bytes, salt: bytes, iterations: int, index: int,
                 dklen: int = 32) -> bytes:
    # U1 = PRF(password, salt || INT_32_BE(index)); U2 = PRF(password, U1); ...
    u = hmac.new(password, salt + index.to_bytes(4, 'big'), hashlib.sha256).digest()
    acc = bytearray(u)
    for _ in range(iterations - 1):
        u = hmac.new(password, u, hashlib.sha256).digest()
        for i, b in enumerate(u):
            acc[i] ^= b
    return bytes(acc)

The loop is inherently serial: each iteration depends on the previous HMAC output, so a single derivation cannot be parallelized across cores. That is the point. An attacker’s advantage comes from running many independent guesses in parallel, and each guess remains a chain of dependent operations.

The weakness is the ratio between the defender’s cost and the attacker’s cost. PBKDF2 with HMAC-SHA-256 needs only a few dozen bytes of state per guess, so custom silicon can run enormous numbers of chains concurrently. Raising the iteration count raises the attacker’s cost linearly and the defender’s cost linearly, and the attacker’s hardware is better suited to the work. Iteration counts in the hundreds of thousands are a common recommendation; the correct number is whatever makes one derivation take a noticeable but tolerable fraction of a second on the defender’s hardware, and it must be raised as hardware improves, which means storing the count with each credential and re-deriving on the next successful login when the stored count is below the current target.

Memory hardness changes the trade

If each guess must allocate and touch a large buffer, an attacker cannot multiply concurrency without multiplying memory. Memory is the expensive resource in parallel cracking hardware: a chip with thousands of cores has a fixed bandwidth and a fixed amount of fast memory, and a function that requires 64 MiB per guess limits concurrency to the number of 64 MiB regions the hardware can hold.

Argon2, specified in RFC 9106, is built around this constraint. It fills a memory array of a configurable size with pseudorandom data derived from the password and salt, then makes a second pass over that array with data-dependent reads, so the access pattern depends on the password and cannot be predicted or precomputed. The RFC defines two variants: Argon2d uses data-dependent addressing and is suited to settings where side-channel resistance is not required, while Argon2i uses data-independent addressing to resist side-channel attacks at some cost in cracking resistance. A hybrid, Argon2id, uses data-independent addressing for the first half of the first pass and data-dependent addressing afterwards, and is the recommended default.

The three cost parameters — memory size, number of passes, and degree of parallelism — trade against each other. Memory size is the primary lever against parallel hardware. Passes increase time without increasing memory. Parallelism declares how many lanes the function may use, and it changes the defender’s latency and the attacker’s achievable occupancy. RFC 9106 gives recommended configurations in the tens of MiB range for interactive logins, with the note that the choice should be calibrated to the deployment.

The scrypt function takes a different route to the same goal: it builds a large array from the password and then reads it back in an order determined by the password, so an attacker who wants to reduce memory must recompute entries, paying time instead. The two are not equivalent — Argon2’s memory filling is more directly resistant to time-memory tradeoffs — but both make the cost curve steeper than linear in the wrong direction for the attacker.

The honest limit: memory hardness raises the cost per guess but does not raise the password’s entropy. A password from a list of ten thousand common choices is recovered by ten thousand guesses, whatever the per-guess cost. Derivation parameters buy time, and the time bought is only useful if the password is changed after a breach is discovered.

Deriving an encryption key rather than a verifier

There are two distinct uses, and they want different properties. A password verifier is stored so that a later login can be checked; it must be expensive to compute and must not reveal the password. A password-derived encryption key must be reproduced exactly at decryption time, so it cannot be stored at all in a form that yields the key.

For the verifier, the derived value is stored with its salt and parameters, and comparison is a constant-time equality check on the derived bytes. Because the derived output is long and random-looking, storing it directly is acceptable, though storing a hash of it is common so that a database leak does not hand over a value that can be replayed against a different system.

For the encryption key, the salt must be stored but the derived key must not be. The usual design stores the salt and parameters in a header, derives the key at unlock, and uses it once. That header is also the place to bind the derivation: feeding the parameters into the derivation as associated data prevents an attacker from lowering the iteration count in the stored header to make a later brute-force cheaper.

Key derivation is also the mechanism behind the hierarchy in envelope encryption, where a master secret is expanded into per-context wrapping keys rather than stored in each context. There the input has full entropy, so the cost parameters can be minimal; the expensive settings exist specifically to compensate for a low-entropy input.

Parameters, upgrades, and mistakes

The parameters must be stored per credential, because they will change. A system that hard-codes one iteration count cannot raise it without invalidating every existing verifier. Storing salt, algorithm identifier, and cost parameters alongside the output lets old verifiers remain valid while new ones use current settings, and lets a successful login trigger re-derivation at the higher cost.

Several failure modes recur. Truncating the salt to a few bytes, or deriving it from the username, defeats the anti-amortization purpose. Comparing derived values with an early-exit equality check leaks timing. Applying the derivation once and then using the output as a key for a fast hash to obtain more bytes, instead of requesting the full length from the function, throws away the work. Reusing one salt across all credentials in a migration is a common shortcut with the same effect as no salt at all.

A subtler error is choosing parameters by benchmark rather than by threat. The relevant question is how long a single derivation takes on the hardware that will actually run it, and how many concurrent logins that hardware must serve. A cost that makes one login take half a second caps throughput at two logins per second per core, and the queue that forms under load becomes a denial-of-service vector. The parameters are a capacity decision as much as a cryptographic one, and the same arithmetic governs the key-stretching that protects long-lived secrets described in protecting key material in memory and at rest.