Chapter 2 · Cryptography· Intermediate· ~14 min

Hashing & MACs

Under the hood: Merkle-Damgard vs sponge constructions, length extension, the birthday bound, and HMAC vs the alternatives.

You will learn

  • Why SHA-2 inherits the length-extension property and SHA-3 does not
  • The birthday bound and why 256-bit hashes give you 128-bit collision resistance
  • HMAC's construction and why it survives length extension
  • Where Poly1305 fits and what an AEAD really is internally

Two constructions

Most hashes are built one of two ways:

  • Merkle-Damgard: process the message in fixed blocks, chain each block's output into the next. Used by MD5, SHA-1, SHA-2. Internal state at the end becomes the digest. Property: if you know H(m) and the length of m, you can compute H(m || padding || m') for any m' without knowing m.
  • Sponge: absorb the message into a large internal state, then squeeze out the digest. Used by SHA-3 (Keccak) and BLAKE3. The internal state is bigger than the output, so length extension does not apply.

Length extension, demonstrated

Server stores a secret k and validates messages with tag = H(k || msg). Client sends (msg, tag). Server recomputes and checks.

An attacker who sees (msg, tag) and knows len(k) can use SHA-256's resumability to compute the correct tag for (msg || padding || arbitrary_extension) without knowing k. This is real. It happened to Flickr's API in 2009.

The fix is HMAC, or switching to SHA-3, BLAKE2, or BLAKE3 (none of which have length extension).

HMAC, in one diagram

HMAC computes H((K' XOR opad) || H((K' XOR ipad) || msg)), where ipad and opad are fixed constants and K' is the key padded to block size. The double hash means an attacker who extends the inner message still cannot extend through the outer hash. It works even with vulnerable underlying hashes (HMAC-SHA-1 is still safe today because of this, though SHA-1 itself is collision-broken).

The birthday paradox

To find a collision in an n-bit hash you need about 2^(n/2) attempts on average, not 2^n. A 128-bit hash gives 64-bit collision resistance, which is reachable today (2^64 ~ 10^19 operations).

That is why SHA-1's 160-bit output is dead (80-bit collisions are easily computable now; Google demonstrated SHA-1 collisions in 2017) and why modern systems use 256-bit hashes for 128-bit collision resistance, which is comfortably out of reach.

From hash to MAC to AEAD

The progression of authentication primitives:

  • Hash: nobody can find a different message with the same digest. No key.
  • MAC: keyed. HMAC is one construction; CMAC (block-cipher-based) is another.
  • Polynomial MAC: GMAC, Poly1305. Very fast on modern hardware. Built on multiplication in a finite field.
  • AEAD: encryption plus MAC in one primitive. AES-GCM = AES-CTR + GMAC. ChaCha20-Poly1305 = ChaCha20 stream + Poly1305.

The progression reflects what production systems actually need: confidentiality and integrity together, computed in one pass over the data, with a single tag to verify.

Practical advice

  • For general-purpose hashing: SHA-256 (Merkle-Damgard, length-extension-vulnerable in raw form) or SHA-3 / BLAKE3 (sponge / tree, no length extension).
  • For MACs: HMAC-SHA-256 is the safe boring choice. Poly1305 paired with a counter is the fast modern choice (used inside ChaCha20-Poly1305).
  • Never roll your own MAC. H(secret || message) is the most common foot-cannon in this area.
  • Use constant-time comparison for tags. A loose == leaks timing.
Take the quiz Back to the beginner version