Cairn
algorithms · cryptography · O(c) time, c = iteration count — a deliberate, tunable cost knob, not a fixed one; O(1) space, one running 32-byte accumulator regardless of c

↩ back to Cryptography

PBKDF2

Both SHA-256's and HMAC's own Pitfalls sections name the same gap and leave it open: a fast hash is the wrong tool for storing passwords, because "fast" is exactly what lets an attacker try billions of guesses a second — real systems need something deliberately slow instead, "not built on this site." PBKDF2 (Password-Based Key Derivation Function 2, RFC 8018) is the simplest of the three real options those pages name, and the one that reuses machinery already here: it doesn't define a new hash, it just runs HMAC-SHA256 over and over — thousands to hundreds of thousands of times — and makes the repeat count the whole security knob. More repeats means more work for both a legitimate login check and an attacker's guess, equally, which is the entire point.

Try it

Pick a password, a salt, and an iteration count, then derive. This page's own implementation (see Reference implementation) is cross-checked against the browser's native crypto.subtle.deriveBits with the PBKDF2 algorithm — the same cross-check SHA-256's and HMAC's own demos already run against their own primitives. Derivation runs on click, not on every keystroke — at the higher presets it's slow on purpose, and that's the whole demo: watch the elapsed time below actually grow with the iteration count, measured live rather than only asserted.

Pick an iteration count and click Derive.

Same password, three different salts — a realistic stand-in for three different user accounts that happen to share a password. Watch the three derived keys share nothing in common, which is the entire reason a precomputed table built for one salt is useless against another.

Why it works

PBKDF2's core, for a derived key no longer than the underlying hash's own output (32 bytes here, so only a single block is ever needed):

U1 = HMAC-SHA256(password, salt ‖ INT32_BE(1))
U2 = HMAC-SHA256(password, U1)
U3 = HMAC-SHA256(password, U2)
...
Uc = HMAC-SHA256(password, Uc-1)

DK = U1 ⊕ U2 ⊕ U3 ⊕ ... ⊕ Uc

The password keys every call; the message each HMAC call hashes is the previous call's own output, chained c times. Each step depends on every step before it, so the chain can't be shortcut or parallelized away for a single guess the way, say, checking many passwords in parallel across cores can be — c sequential HMAC calls are c sequential HMAC calls, for attacker and defender alike. The final derived key is the XOR of every intermediate U value, not just the last one — a detail inherited from RFC 8018's general multi-block definition, kept here even though a single 32-byte block never needs the "concatenate multiple blocks" machinery the full spec provides for longer derived keys. The salt's only job is appended once, inside U1: it changes every subsequent U value for a fixed password, which is exactly why the three-salt demo above produces three unrelated keys from one password — nothing about the chain itself treats the salt as secret, it's stored right alongside the derived key, but it must be unique per record so no single precomputed table can target more than one.

Reference implementation

Built directly on top of HMAC's own hmacSha256 primitive — this page adds only the chaining and the XOR accumulation on top:

function pbkdf2Hmac256(passwordBytes, saltBytes, iterations, dkLenBytes) {
  const hLen = 32; // SHA-256's output size
  const blockIndex = new Uint8Array(4);
  writeUInt32BE(blockIndex, 0, 1);               // only block 1 — dkLenBytes is 32 here, never more

  let u = hmacSha256(passwordBytes, concatBytes(saltBytes, blockIndex)); // U1
  const t = u.slice();                            // running XOR accumulator, starts as U1
  for (let i = 1; i < iterations; i++) {
    u = hmacSha256(passwordBytes, u);              // Ui = HMAC(password, U(i-1))
    for (let k = 0; k < hLen; k++) t[k] ^= u[k];   // accumulate into T
  }
  return t.slice(0, dkLenBytes);
}

// hmacSha256(key, message) is exactly the function HMAC's own page already built and verified —
// copied here rather than imported, the same way HMAC's page copied SHA-256's own processBlocks
// and padMessage instead of linking to them; every page on this site is a standalone file.

Verified against four of Node's own crypto.pbkdf2Sync('password', 'salt', c, 32, 'sha256') outputs — c = 1 (120fb6cff…cb70be17b), c = 2, c = 4096, and c = 10000 — byte-for-byte matches on every one, before any of it reached the page above. Timing numbers in Pitfalls below were measured the same way: plain Node, not this page's own vm-sandboxed anything, per the standing lesson that cross-realm execution distorts wall-clock numbers non-uniformly.

Pitfalls

The iteration count is the entire defense, and it decays as hardware gets faster. A count picked for today's attacker hardware is a weaker count in five years purely because cheaper hardware ran the same number of guesses faster, with no change to the algorithm at all. OWASP's current guidance for PBKDF2-HMAC-SHA256 is a minimum of 600,000 iterations — measured directly on this VM in plain Node (not this page's own JavaScript, which has no native-code speedup and would take noticeably longer), that's about 380ms per single guess, scaling almost exactly linearly with the count: roughly 0.66ms at 1,000 iterations, 64ms at 100,000, 380ms at 600,000. Every login check or password-reset must pay that same cost deliberately — it's the whole mechanism, not overhead to optimize away.

PBKDF2 is time-hard, not memory-hard — and that's a real, not cosmetic, weakness. Every one of the c chained HMAC calls above needs only a single 32-byte running state; a GPU, FPGA, or custom ASIC can run thousands of independent PBKDF2 guesses side by side for roughly the cost of one, because none of them compete for scarce fast memory the way a CPU-only attacker does. That parallel-hardware shortcut is exactly what bcrypt and Argon2 — named on SHA-256's and HMAC's own pages alongside PBKDF2 — are designed to close, by deliberately requiring a large, hard-to-parallelize memory footprint per guess on top of the time cost. bcrypt's own page builds the first of the two and measures exactly how much memory footprint it actually buys; Argon2 itself remains unbuilt here, though its own internal hash function, BLAKE2b, now is. PBKDF2 is still a legitimate, standardized, widely-deployed choice (TLS 1.2's key derivation, WPA2, many disk-encryption tools all use it) — it's a genuine improvement over a bare hash, just not the strongest available option against an attacker with custom hardware to throw at the problem.

A salt that isn't unique per record defeats the entire point. The salt doesn't need to be secret — it's stored right next to the derived key — but it does need to be different for every password, generated fresh (a cryptographically random value, not a counter or a username) each time one is created. Reuse the same salt across every user and an attacker who precomputes one table of password → derived key pairs for that one salt can check it against every row in a breached database at once, collapsing straight back to the exact precomputed-table weakness salting exists to prevent — demonstrated live above: three salts, three completely unrelated keys, for the identical password.

Complexity

Time: O(c) HMAC-SHA256 calls — roughly 2c SHA-256 compressions, since HMAC's own Complexity section already puts one HMAC call at about two SHA-256 calls. Unlike SHA-256 or HMAC, whose costs are fixed by the input size alone, PBKDF2's cost is a deliberately chosen constant multiplier c on top of that — tunable upward as hardware improves, with no ceiling except how long a legitimate login is willing to wait. Space: O(1) — one 32-byte running HMAC state and one 32-byte XOR accumulator, regardless of c; the exact property the memory-hardness pitfall above turns into a real weakness against parallel hardware. Security: PBKDF2 introduces no new hardness assumption beyond HMAC's own, already reduced to SHA-256's own compression function — its resistance to brute force is entirely a function of c, chosen at design time, not a property of the construction itself the way length-extension resistance is for HMAC.