PBKDF2, in depth: the block function, HMAC key caching, test vectors, WPA2, WebCrypto and JCA, iteration calibration and the long-password denial of service

What PBKDF2 computes

With a PRF of output length hLen bytes, PBKDF2 computes DK = T_1 || T_2 || ..., truncated to dkLen bytes, where each block is T_i = U_1 xor U_2 xor ... xor U_c, U_1 = PRF(P, S || INT(i)) and U_j = PRF(P, U_(j-1)). INT(i) is the block index as four big-endian bytes, starting at 1. The password is the HMAC key and never appears as message data.

Three consequences follow. Every output block costs c PRF calls, and the blocks are independent, so an attacker who can check a guess against the first block never computes the rest. The XOR of all intermediate values means the chain cannot be shortcut by stopping early. And because the work is pure hashing with a few dozen bytes of state, GPUs and ASICs run it in parallel very cheaply; PBKDF2 has no memory hardness at all, which is the main reason Argon2id is preferred where it is allowed.

What PBKDF2 computes

With a PRF of output length hLen bytes, PBKDF2 computes DK = T_1 || T_2 || ..., truncated to dkLen bytes, where each block is T_i = U_1 xor U_2 xor ... xor U_c, U_1 = PRF(P, S || INT(i)) and U_j = PRF(P, U_(j-1)). INT(i) is the block index as four big-endian bytes, starting at 1. The password is the HMAC key and never appears as message data.

Three consequences follow. Every output block costs c PRF calls, and the blocks are independent, so an attacker who can check a guess against the first block never computes the rest. The XOR of all intermediate values means the chain cannot be shortcut by stopping early. And because the work is pure hashing with a few dozen bytes of state, GPUs and ASICs run it in parallel very cheaply; PBKDF2 has no memory hardness at all, which is the main reason Argon2id is preferred where it is allowed.

Where the time goes: HMAC key caching

Each HMAC call is H((K xor opad) || H((K xor ipad) || m)). The two padded key blocks are the same for all c calls, so the hash state after absorbing each of them can be computed once and copied. A short message such as a 32-byte U value then costs two compression-function calls per HMAC instead of four. Attackers' cracking kernels always do this. A defender who does not pays roughly double the work for the same security, which means either halving the iteration count to keep logins fast or doubling the server bill.

Python's hmac module exposes the keyed state through copy():

import hashlib, hmac, struct

def pbkdf2_fast(name, password, salt, iterations, dklen):
    """Keys HMAC once, then copies the keyed inner/outer state for each call."""
    keyed = hmac.new(password, None, name)   # the ipad/opad blocks are absorbed here, once
    hlen = keyed.digest_size
    def prf(msg):
        h = keyed.copy()
        h.update(msg)
        return h.digest()
    out = b""
    for i in range(1, -(-dklen // hlen) + 1):
        u = prf(salt + struct.pack(">I", i))
        t = int.from_bytes(u, "big")
        for _ in range(iterations - 1):
            u = prf(u)
            t ^= int.from_bytes(u, "big")
        out += t.to_bytes(hlen, "big")
    return out[:dklen]

A textbook version that calls hmac.new(password, u, name) inside the loop produces identical output. In pure Python the difference at 20,000 iterations was modest, 77 ms against 59 ms, because interpreter overhead dominates. The difference that matters is with long keys: HMAC first hashes any key longer than the hash block size, and the naive loop repeats that every iteration. With a 1 MB password and only 200 iterations the naive version took 189 ms and the cached one 2 ms. Scale the naive figure to 600,000 iterations and a single login attempt costs about ten minutes of CPU. Production code should call the platform implementation (hashlib.pbkdf2_hmac, OpenSSL, the JCA or WebCrypto), all of which cache the keyed state; the pure-Python version is for understanding and tests.

Prove it with test vectors

Never ship a KDF you have not checked against published vectors. RFC 6070 gives vectors for PBKDF2-HMAC-SHA1; the WPA2 specification gives one for its pre-shared key derivation. Both of these passed with the code above and with hashlib:

assert pbkdf2_fast("sha1", b"password", b"salt", 1, 20).hex() == \
    "0c60c80f961f0e71f3a9b524af6012062fe037a6"            # RFC 6070, c = 1
assert pbkdf2_fast("sha1", b"password", b"salt", 4096, 20).hex() == \
    "4b007901b765489abead49d926f721d065a429c1"            # RFC 6070, c = 4096
assert hashlib.pbkdf2_hmac("sha1", b"password", b"IEEE", 4096, 32).hex() == \
    "f42c6fc52df0ebef9ebb4b90b38a5f902e83fe1b135a70e23aed762e9710a12e"  # WPA2 PSK
assert pbkdf2_fast("sha256", b"pw", b"saltsaltsaltsalt", 1000, 64) == \
    hashlib.pbkdf2_hmac("sha256", b"pw", b"saltsaltsaltsalt", 1000, 64)  # two blocks

For SHA-256 and SHA-512 there is no RFC vector set, so cross-check your implementation against a second independent one, as the last line does, and make sure at least one case has dkLen larger than hLen so the block counter is exercised. Include an empty password, a password longer than the hash block size, and a non-ASCII password encoded as UTF-8.

Case study: WPA2-Personal

WPA2-Personal derives its 256-bit pairwise master key as PBKDF2-HMAC-SHA1(passphrase, SSID, 4096, 32 bytes). It is a useful case study because it gets two things wrong by today's standards and one thing instructively right.

• The salt is the network name. Salts should be random and unique. Using the SSID means every network called by a router vendor's default name shares a salt, so attackers can precompute tables for common SSIDs and common passphrases once and reuse them.
• 4,096 iterations was chosen for 2004 hardware. A captured four-way handshake lets an attacker test guesses offline at whatever rate their GPUs allow.
• The output is two SHA-1 blocks. 32 bytes is more than SHA-1's 20, so each guess costs 2 x 4,096 HMAC calls. Here the second block is not wasted defender work, because the whole 32-byte key feeds the next derivation step and the attacker must compute it too. Contrast that with splitting one long PBKDF2 output into a verifier and a key, where the attacker only needs the verifier block.

The lesson for your own designs: random 16-byte salts per secret, an iteration count sized to current hardware and revisited, and never more PBKDF2 output than one block unless every byte is needed to test a guess. Derive extra keys with HKDF from one block instead.

PBKDF2 in the browser and on the JVM

In the browser, WebCrypto exposes PBKDF2 through deriveBits or deriveKey. The password is imported as a raw key that can only be used for derivation:

const enc = new TextEncoder();
const base = await crypto.subtle.importKey(
  "raw", enc.encode(password), "PBKDF2", false, ["deriveBits"]);
const bits = await crypto.subtle.deriveBits(
  { name: "PBKDF2", salt, iterations: 600000, hash: "SHA-256" },
  base, 256);                       // length in bits: one SHA-256 block

On the JVM, the JCA provides it as a SecretKeyFactory. The password is a char[] so it can be wiped, and the key length is in bits:

PBEKeySpec spec = new PBEKeySpec(password, salt, 600_000, 256);
SecretKeyFactory f = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA256");
byte[] dk = f.generateSecret(spec).getEncoded();
spec.clearPassword();

Two portability traps: normalise passwords to the same Unicode form (NFC or NFKC) on every client before encoding to UTF-8, or the same typed password derives different keys on different platforms; and check how each API counts length, bits in WebCrypto and the JCA, bytes in hashlib and OpenSSL.

Calibrating iterations and login capacity

The OWASP Password Storage Cheat Sheet recommends at least 600,000 iterations for PBKDF2-HMAC-SHA256 and 220,000 for PBKDF2-HMAC-SHA512. NIST SP 800-132 sets far lower floors, at least 1,000 iterations and a salt of at least 128 bits, which are minimums for compliance, not targets. Treat the OWASP numbers as a floor and calibrate upward from your own hardware and login rate:

import hashlib, os, time

def calibrate(name="sha256", target_ms=250, probe=100_000):
    salt = os.urandom(16)
    t = time.perf_counter()
    hashlib.pbkdf2_hmac(name, b"calibration", salt, probe)
    per_iter = (time.perf_counter() - t) / probe
    return int(target_ms / 1000 / per_iter)

# Test laptop, SHA-256 at 600,000: about 390 ms idle, over 1,100 ms with other jobs running.

Calibrate under realistic load: the same call was nearly three times slower on a busy machine than on an idle one. Then size capacity. If one verification costs 386 ms of one core, a 16-core login tier sustains about 16 / 0.386, roughly 41 verifications per second, before queueing. Peak login traffic after an outage or a forced logout can be ten times normal, so plan for that or put verification behind its own pool with a bounded queue so a login storm cannot starve the rest of the service.

Long passwords as a denial-of-service lever

In September 2013 Django disclosed CVE-2013-1443: its authentication framework would hash arbitrarily long passwords, and a one-megabyte password took roughly a minute to check with the PBKDF2 hasher. Repeated submissions tied up servers. The fix was to fail authentication for any password longer than 4,096 bytes before hashing it.

The general rule is that a slow hash is an amplifier the attacker controls, so put limits in front of it: cap password length (a few kilobytes is generous), rate-limit attempts per account and per source address, run verification in a bounded worker pool, and fail fast with the same response time shape whether or not the account exists, by verifying against a dummy hash for unknown users so timing does not leak which usernames are real.

A production verifier with upgrades

A production verifier stores the algorithm, iteration count, salt and hash together, compares in constant time, and upgrades old records when the user next logs in:

import base64, hashlib, hmac, os

ITER = 600_000
MAX_PW = 4096

def make(pw: str) -> str:
    salt = os.urandom(16)
    dk = hashlib.pbkdf2_hmac("sha256", pw.encode(), salt, ITER)
    b64 = lambda b: base64.b64encode(b).decode()
    return f"pbkdf2_sha256${ITER}${b64(salt)}${b64(dk)}"

def verify(pw: str, stored: str):
    """Returns (ok, replacement_record_or_None)."""
    if len(pw.encode()) > MAX_PW:
        return False, None
    algo, iters, salt, dk = stored.split("$")
    if algo != "pbkdf2_sha256":
        raise ValueError("unknown hasher")
    got = hashlib.pbkdf2_hmac("sha256", pw.encode(), base64.b64decode(salt), int(iters))
    ok = hmac.compare_digest(got, base64.b64decode(dk))
    return ok, (make(pw) if ok and int(iters) < ITER else None)

The upgrade path only reaches users who log in. For dormant accounts, wrap the old hash: store the result of the new function applied to the old hash and mark the record, as described in the KDF article. Plain hashes such as unsalted SHA-256 should be wrapped immediately; see the SHA family for why a fast hash on its own is never a password store, and bcrypt for the main legacy alternative and its 72-byte limit.

Failure modes

• Iteration count frozen in config. Values chosen years ago become cheap; review them yearly and rely on rehash-on-login.
• Fixed or short salts. A constant salt allows one precomputation for all users; WPA2's SSID salt shows the cost at scale.
• Multi-block output used as a verifier plus key. The attacker checks one block, the defender pays for all of them.
• No length cap. Long passwords turn the KDF into a CPU amplifier, as CVE-2013-1443 showed.
• Non-constant-time comparison. Use hmac.compare_digest or the platform equivalent.
• Unicode mismatch. Different normalisation on different clients locks users out.
• Client-side only hashing. If a browser derives the key and the server stores it directly, the derived value becomes the password. Hash again on the server.

What to do next

1. Run the RFC 6070 and WPA2 vectors against every PBKDF2 implementation you ship.
2. Measure verification time on production hardware and set iterations from your latency budget, no lower than the OWASP floor.
3. Compute peak verifications per second for your login tier and isolate verification in a bounded pool.
4. Add a password length cap before hashing and per-account rate limits.
5. Store parameters with each hash, implement rehash-on-login and wrap legacy records.
6. If you are not bound by FIPS, plan a migration to Argon2id.