Key Derivation Functions, in depth: PBKDF2 from scratch, memory-hard scrypt and Argon2id, HKDF extract-and-expand and choosing between them

Why passwords need slow functions

A random 256-bit key cannot be brute-forced. A human password can: realistic passwords come from a space of perhaps a few billion likely candidates once an attacker applies wordlists and mutation rules. The defence cannot make that space bigger, so it makes each guess cost more.

Suppose an attacker's rig computes R = 10^10 SHA-256 compressions per second (an illustrative figure) and works through 10^9 candidates against one stolen hash. With unsalted SHA-256 the search takes 0.1 seconds, and one precomputed table covers every user. With a per-user salt the table is useless and each hash must be attacked separately. With PBKDF2-HMAC-SHA256 at 600,000 iterations, each guess costs about 1.2 million compressions (two per HMAC once the padded key states are cached), so the rig manages about 8,300 guesses a second and the same search takes about 33 hours per user. The salt removes amortisation; the work factor multiplies cost. You need both.

Iteration count alone has a weakness: it costs computation but no memory, and computation is exactly what GPUs and custom chips provide cheaply in parallel. That is why memory-hard functions exist, and why PBKDF2 is now the choice mainly when a FIPS-validated primitive is required.

PBKDF2 from scratch

PBKDF2 (RFC 8018) is defined over a pseudorandom function, in practice HMAC with SHA-256 or SHA-512. For output block i it computes U1 = PRF(P, salt || INT(i)), then Uj = PRF(P, Uj-1) for j up to the iteration count c, and XORs all the U values together. Blocks are concatenated until enough bytes exist. The implementation is short enough to check against the standard library:

import hashlib, hmac, os

def pbkdf2_sha256(password: bytes, salt: bytes, iterations: int, dklen: int) -> bytes:
    hlen = 32
    blocks = -(-dklen // hlen)                      # ceiling division
    out = b""
    for i in range(1, blocks + 1):
        u = hmac.new(password, salt + i.to_bytes(4, "big"), hashlib.sha256).digest()
        acc = int.from_bytes(u, "big")
        for _ in range(iterations - 1):
            u = hmac.new(password, u, hashlib.sha256).digest()
            acc ^= int.from_bytes(u, "big")
        out += acc.to_bytes(hlen, "big")
    return out[:dklen]

salt = os.urandom(16)
mine = pbkdf2_sha256(b"correct horse", salt, 1000, 48)
assert mine == hashlib.pbkdf2_hmac("sha256", b"correct horse", salt, 1000, dklen=48)

Two properties of this construction cause real bugs. First, every output block costs the full iteration count, but an attacker can test a guess against the first block alone. Asking PBKDF2-HMAC-SHA256 for 64 bytes, then using the first half as a verifier and the second half as an encryption key, doubles the defender's cost and leaves the attacker's unchanged. Derive hLen bytes once and expand them with HKDF instead. Second, HMAC hashes any key longer than the hash's block size (64 bytes for SHA-256) before use, so a password over 64 bytes and its SHA-256 digest produce the same PBKDF2 output. That is a curiosity rather than a break, but it surprises people who test for distinct inputs.

For parameters, the OWASP Password Storage Cheat Sheet currently recommends at least 600,000 iterations for PBKDF2-HMAC-SHA256 when FIPS-140 compliance is required. Salts should be at least 16 random bytes per password.

Memory-hard functions: scrypt and Argon2id

A memory-hard function forces each guess to fill and read back a large buffer. Memory bandwidth and capacity do not scale with chip area the way arithmetic does, so attackers lose much of their parallel advantage. scrypt does this with a large array of salsa20-mixed blocks; Argon2, the winner of the Password Hashing Competition and specified in RFC 9106, does it with a matrix of 1 KiB blocks. Argon2id mixes data-independent passes (resisting side channels) with data-dependent ones (resisting trade-offs of time for memory) and is the default choice.

The standard library exposes scrypt, but OpenSSL caps its memory by default, so realistic parameters fail unless you raise the limit explicitly:

key = hashlib.scrypt(b"correct horse", salt=os.urandom(16),
                     n=2**17, r=8, p=1, maxmem=256 * 1024 * 1024, dklen=32)

For Argon2id in Python, the argon2-cffi package handles salts, encoding and verification. Pass parameters explicitly rather than relying on library defaults, so the code documents the policy:

from argon2 import PasswordHasher
from argon2.exceptions import VerifyMismatchError

ph = PasswordHasher(time_cost=2, memory_cost=19456, parallelism=1)   # memory in KiB

def register(password: str) -> str:
    return ph.hash(password)   # "$argon2id$v=19$m=19456,t=2,p=1$<salt>$<hash>"

def login(stored: str, password: str):
    try:
        ph.verify(stored, password)
    except VerifyMismatchError:
        return False, stored
    if ph.check_needs_rehash(stored):     # parameters older than current policy
        stored = ph.hash(password)        # upgrade while the plaintext is in hand
    return True, stored

The stored string is in the PHC format: algorithm, version, parameters, salt and hash in one self-describing value. That is what makes upgrades possible: each record says how it was made, so raising the policy only changes what new hashes look like, and old ones are rehashed at the next successful login. Legacy PBKDF2 or bcrypt records can be wrapped (Argon2id applied over the old hash) to protect dormant accounts immediately.

HKDF: extract, then expand

When the input is already strong, slowness buys nothing. What is needed is a way to turn a secret that may not be uniformly random, such as an X25519 or Diffie-Hellman shared value, into keys that are, and to derive many independent keys from one. HKDF (RFC 5869) does this in two steps. Extract computes PRK = HMAC(salt, IKM), concentrating the input's entropy into one pseudorandom key. Expand computes T(1) = HMAC(PRK, info || 0x01), T(i) = HMAC(PRK, T(i-1) || info || i), and concatenates up to 255 blocks:

def hkdf_extract(salt: bytes, ikm: bytes) -> bytes:
    return hmac.new(salt or bytes(32), ikm, hashlib.sha256).digest()   # empty salt = 32 zero bytes

def hkdf_expand(prk: bytes, info: bytes, length: int) -> bytes:
    if length > 255 * 32:
        raise ValueError("HKDF-SHA256 output is limited to 8160 bytes")
    okm, t, i = b"", b"", 1
    while len(okm) < length:
        t = hmac.new(prk, t + info + bytes([i]), hashlib.sha256).digest()
        okm += t
        i += 1
    return okm[:length]

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF

ikm, salt, info = os.urandom(32), os.urandom(16), b"myapp/v1/session-enc"
ref = HKDF(algorithm=hashes.SHA256(), length=42, salt=salt, info=info).derive(ikm)
assert hkdf_expand(hkdf_extract(salt, ikm), info, 42) == ref

The info string is the key-separation mechanism. Two calls with different labels give keys that are independent for practical purposes, so one master secret can safely yield an encryption key, a MAC key and a nonce prefix. Include a protocol name, a version and the purpose in every label. TLS 1.3 builds its whole key schedule from HKDF in this way. Ed25519 solves a similar problem more simply, splitting one SHA-512 output of the seed into the signing scalar and the nonce prefix.

Choosing a KDF by input entropy

The last row surprises people. A server-generated token with 128 or more random bits cannot be guessed, so a single fast hash is enough and keeps lookups cheap. Slowness is protection only for secrets humans choose.

Worked example: sizing a login service

A login service peaks at 300 logins a second. Benchmarking Argon2id at m = 19 MiB, t = 2, p = 1 on the production instance type gives, say, 40 ms per hash on one core. Concurrency is rate times latency: 300 x 0.04 = 12 hashes in flight, needing 12 cores and 12 x 19 MiB, about 230 MiB of memory, plus headroom. Raising memory to 64 MiB would cost about 770 MiB at peak and longer latency; whether that is worth it depends on the threat model and the budget, and it is a decision to make with numbers like these rather than defaults.

The same arithmetic exposes a denial-of-service risk. An attacker sending 3,000 bogus logins a second asks for 120 cores of KDF work. Rate-limit per account and per source before the KDF runs, and reject oversized password inputs early.

Failure modes

• Fast hash for passwords. SHA-256 or MD5 with or without salt. Every leaked database of this kind has been cracked at scale. Migrate by wrapping existing hashes.
• HKDF on passwords. HKDF adds no work factor, so the result is as guessable as the password. Stretch first.
• Long PBKDF2 outputs. More than hLen bytes multiplies only the defender's cost, as shown above.
• Reused derived keys. The same HKDF output used for encryption and authentication, or empty info labels everywhere. Separate by label.
• No upgrade path. Parameters hard-coded and not stored with the hash, so they can never be raised. Use self-describing formats and rehash on login.
• Non-constant-time comparison. Comparing derived values with == leaks timing. Use hmac.compare_digest or the library's verify call.
• Secrets in logs. Passwords appear in request logs before they reach the KDF. Scan for them with tooling such as the secret scanners used for LLM pipelines.

Trade-offs

Every unit of password-KDF cost is paid by the defender on each login and by the attacker on each guess, so the parameters set a budget, not a guarantee. Argon2id gives the best ratio of attacker to defender cost but is not available in every FIPS environment, where PBKDF2 with a high count is the compliant option. A server-side pepper (an HMAC key held in an HSM or KMS and applied before the KDF) protects a leaked database whose application secrets did not leak, at the price of a key that must be rotated carefully. HKDF is cheap and simple, but it protects nothing when its input is weak.

What to do next

1. Inventory every place your systems derive or store keys and passwords, and classify each input as low or high entropy.
2. Store new password hashes with Argon2id at or above the OWASP minimum, in PHC format, with parameters set explicitly in code.
3. Add rehash-on-login and wrap legacy fast hashes so dormant accounts are protected now.
4. Benchmark the KDF on production hardware and size cores and memory for peak login rate plus abuse.
5. Replace ad-hoc key splitting with HKDF and versioned info labels; never request more than hLen bytes from PBKDF2.
6. Use constant-time comparison everywhere derived values are checked, and rate-limit before the KDF runs.