Cairn
algorithms · cryptography · O(n) time, a constant amount of extra work (one key-block pass, two nested hashes) on top of hashing the message once; forging a valid tag without the key is believed as hard as breaking SHA-256 itself, not easier

↩ back to Cryptography

HMAC

SHA-256's own Pitfalls section showed why SHA-256(secret‖message) is unsafe as a message-authentication code: anyone who knows the secret's byte length — not its contents — can resume the compression function from a published hash and forge a valid hash for the secret plus attacker-chosen appended data, without ever reading the secret. HMAC is the fix real systems use: not a different hash function, but a specific way of nesting an existing one — SHA-256 here, though the construction works with any hash — so that the weakness above can't be exploited. This page builds HMAC-SHA256 from scratch on top of this site's own SHA-256 implementation, then runs the exact same length-extension attack that broke the naive construction against this one, live, to watch it fail.

Try it

Type a key and a message — the tag updates on every keystroke, computed two independent ways: this page's own hand-written HMAC-SHA256 (see Reference implementation), and the browser's native crypto.subtle, via importKey/sign with the HMAC algorithm. They're checked against each other on every keystroke, the same cross-check SHA-256's own demo runs for plain hashing.

Changing a single character of the key changes the tag completely, same avalanche behavior as plain SHA-256 — but changing the key is something only someone who already holds the key can do. A visitor with only the message and the tag, no key, is exactly the attacker this page's second demo plays.

The setup below mirrors SHA-256's own length-extension demo as closely as possible — same hidden 32-byte secret, same "public request / attacker forges an extension" shape — except the server now computes HMAC-SHA256(secret, request) instead of SHA-256(secret‖request). The attacker tries the identical trick: treat the published tag as if it were a raw SHA-256 internal state, and resume compression from it with the standard glue padding plus whatever extra data they want appended.

Server-side setup: a 32-byte secret (hidden) keys HMAC-SHA256 over a request string.

Attacker's view — knows only the published tag above and the request string. Tries the exact length-extension technique that worked against naive SHA-256(secret‖message) on SHA-256's own page.

Why it works

HMAC's definition, independent of which hash it wraps:

HMAC(key, message) = H( (key' ⊕ opad) ‖ H( (key' ⊕ ipad) ‖ message ) )

H is the underlying hash (SHA-256 here). key' is the key adjusted to exactly one block: if the key is longer than the hash's 64-byte block size it's hashed down to 32 bytes first (itself safe, since a hash's output is no easier to predict than a shorter key would be); if it's shorter, it's zero-padded up to 64 bytes. ipad and opad are two fixed, public 64-byte constants — the byte 0x36 and the byte 0x5c repeated — chosen only so the inner and outer calls never see the same padded key value, keeping the two hash computations properly independent (any two distinct constants would do; FIPS 198 is specific about which two).

The construction is nested: an inner hash runs over key'⊕ipad followed by the real message, and its 32-byte output — not the message — is what the outer hash actually processes, prefixed with key'⊕opad. This is exactly what defeats length extension. The naive attack works because a hash's output is its internal state after the last block, with no further processing — so resuming compression from a published digest and feeding it more blocks produces a value that's provably the hash of the original input with those blocks appended. HMAC's published tag is the outer hash's final state, but the outer hash was never run over the attacker-visible message at all — it was run over key'⊕opad followed by the inner digest. Resuming compression from the published tag and appending more blocks, the way the demo above tries, produces H(key'⊕opad ‖ inner_digest ‖ glue ‖ extra) — a real, validly-padded SHA-256 computation, just not HMAC(key, message‖extra), which would require recomputing the inner hash over key'⊕ipad ‖ message‖extra from scratch. Nothing published lets an outsider do that: key'⊕ipad depends on the secret key, and the tag alone never reveals it. The forged and true values the demo computes are different numbers for an inherent structural reason, not by luck of the specific secret chosen.

Reference implementation

Built directly on top of SHA-256's own processBlocks/padMessage primitives — this page adds only the key handling and the ipad/opad nesting on top:

const BLOCK_SIZE = 64; // bytes — SHA-256's block size

function hmacSha256(keyBytes, messageBytes) {
  let key = keyBytes;
  if (key.length > BLOCK_SIZE) key = sha256Bytes(key);       // longer than a block: hash it down
  if (key.length < BLOCK_SIZE) {                              // shorter: zero-pad up to a block
    const padded = new Uint8Array(BLOCK_SIZE);
    padded.set(key, 0);
    key = padded;
  }

  const ipad = new Uint8Array(BLOCK_SIZE), opad = new Uint8Array(BLOCK_SIZE);
  for (let i = 0; i < BLOCK_SIZE; i++) {
    ipad[i] = key[i] ^ 0x36;
    opad[i] = key[i] ^ 0x5c;
  }

  const inner = sha256Bytes(concatBytes(ipad, messageBytes));  // H(key'⊕ipad ‖ message)
  return sha256Bytes(concatBytes(opad, inner));                 // H(key'⊕opad ‖ inner)
}

// sha256Bytes(bytes) runs SHA-256's own processBlocks(padMessage(bytes), H0) and returns the
// 32-byte digest as bytes rather than hex — same compression function, same padding, as the
// SHA-256 page's own sha256Hex, just returning raw bytes so it can be fed into a second hash.

Verified against four independent RFC 4231 test vectors — including a key shorter than one block, the classic key="Jefe" case (HMAC-SHA256("Jefe", "what do ya want for nothing?") = 5bdcc146bf60754e6a042426089575c75a003f089d2739839dec58b964ec3843), and a key longer than one block to exercise the hash-the-key-down branch — every one matching Node's crypto.createHmac('sha256', …) exactly, before any of it reached the page above.

Pitfalls

Concatenating key and message plainly is still unsafe, even nested wrong. HMAC's security comes from the specific nesting above, not from "hash it twice" in general. A naive H(H(secret‖message)) — nesting without the ipad/opad separation or without feeding the key into both layers — doesn't carry the same proof and isn't what any standard calls HMAC. The two fixed constants aren't decoration; they're what keeps the inner and outer computations from degenerating into equivalent or related calls an attacker could exploit.

A verifier that compares tags byte-by-byte with a naive loop leaks timing. A comparison that returns as soon as it finds a mismatched byte takes measurably less time to reject a tag that's wrong in its first byte than one that's wrong in its last — and across enough network requests, that timing difference lets an attacker recover a valid tag one byte at a time without ever seeing the key. The fix is a constant-time comparison (XOR every byte pair and OR the results together, only branching once at the very end) — a different, narrower pitfall than the length-extension attack this whole page is otherwise about, and one that bites the verifier's code even when the HMAC computation itself is flawless.

HMAC authenticates; it still doesn't make a fast hash slow. Like plain SHA-256, running HMAC costs roughly two hash computations — fast by design, which is exactly right for checking a request wasn't tampered with in transit. It's still the wrong tool for storing passwords: a per-guess cost of two fast hashes is not meaningfully more expensive to brute-force than SHA-256's own single hash, and deliberately slow, salted key-derivation functions — bcrypt, Argon2, or PBKDF2, which chains this very page's own HMAC-SHA256 thousands of times as its building block — remain the right choice there. PBKDF2's own page builds that chain, and bcrypt's own page builds the memory-hard alternative; Argon2 itself remains unbuilt here, though its own internal hash function, BLAKE2b, now is.

Complexity

Time: O(n) in the message length — one pass to (maybe) hash an over-length key, then two SHA-256 calls over roughly block-sized and message-sized inputs respectively; a constant multiple of plain SHA-256's own cost, not a different order. Space: O(1) beyond the message, same as SHA-256 itself — the key, after the fixed-size adjustment above, never grows with input size. Security: HMAC is proven secure (as a pseudorandom function, and hence unforgeable without the key) as long as the underlying compression function has certain standard properties — a proof that holds for SHA-256 and does not depend on SHA-256 being collision-resistant in the stronger sense SHA-256's own Complexity section discusses. No attack against HMAC-SHA256 beats generic brute force over the key space as of this writing, and — the entire point of this page — the specific length-extension shortcut that works against naive keyed hashing does not carry over, demonstrated above rather than only asserted.