Chapter 2 · Cryptography·Advanced·~16 min

Hashing & MACs

Inside the constructions: sponge security arguments, BLAKE3's parallel tree, KMAC, hash differential cryptanalysis, and SHAttered.

You will learn

  • The sponge construction's capacity-as-security argument
  • BLAKE3's compression tree and why it parallelizes
  • KMAC vs HMAC, and what cSHAKE gives you
  • Differential cryptanalysis that broke MD5 and SHA-1
  • Why a 2-block SHA-1 collision was a 6500-CPU-year computation

Sponge security

A sponge has state of r + c bits, where r is the rate (bits absorbed per step) and c is the capacity (security parameter, never exposed externally). The argument: as long as the inner permutation behaves like a random permutation, the sponge is indistinguishable from a random oracle up to 2^(c/2) queries.

For Keccak-256 (SHA-3-256): rate = 1088 bits, capacity = 512 bits. Collision resistance: 128 bits (capacity/2). Pre-image resistance: 256 bits (output length). The capacity choice is what makes length extension impossible: the inner state is never exposed.

BLAKE3's compression tree

BLAKE3 (Aumasson, Neves, Wilcox-O'Hearn, O'Connor, 2020) compresses the input by chunking into 1024-byte segments, hashing each independently, then combining via a Merkle tree of compression-function calls.

Properties:

  • Parallelizable: chunks process on independent cores. Multi-GB/s on modern x86.
  • Single algorithm for hash, MAC (key the root), KDF, XOF (extendable output).
  • Pre-computed prefixes: incremental updates only re-hash affected subtrees, useful for content-addressable storage and incremental file systems.

The compression function itself is derived from BLAKE2s. Security argument inherits from BLAKE2's analysis.

KMAC and cSHAKE

KMAC (NIST SP 800-185) is a MAC built directly on SHA-3 / Keccak, not via HMAC. Construction: prepend the key and a customization string to the message, feed through cSHAKE (customizable SHAKE). The customization string provides domain separation for free; you can use the same key for different purposes by varying the string.

Advantages over HMAC-SHA-3:

  • Single sponge call, not two nested hashes. Faster.
  • Built-in domain separation (no need to engineer it via labels).
  • Variable output length (XOF mode).

Where the ecosystem allows SHA-3, KMAC is the modern boring choice. HMAC-SHA-256 remains the universal-compatibility default.

Differential cryptanalysis on MD5 and SHA-1

Both are Merkle-Damgard with a compression function that mixes message blocks into chaining state through bit-rotations, XORs, and additions. Differential cryptanalysis tracks how differences in input propagate through these operations.

Wang's 2004 attack on MD5: a chosen-prefix collision needed about 2^39 operations. Trivial today; demonstrated by the 2008 MD5-based rogue CA certificate (Sotirov et al). 2012 Flame malware used a chosen-prefix MD5 collision to forge a Microsoft code-signing certificate.

SHA-1: Wang et al's 2005 theoretical attack at 2^63 operations. The SHAttered result (Stevens et al, 2017) demonstrated the first actual SHA-1 collision: two PDFs with the same SHA-1 hash. Cost: ~6,500 CPU years and 110 GPU years, ~$110K of cloud compute. Chosen-prefix collisions were demonstrated in 2019 (Leurent and Peyrin), making SHA-1 unsafe for any signature.

Where hash CVEs come from in modern code

  • Algorithm choice: still finding MD5 and SHA-1 in long tails of legacy code.
  • Truncation: using a 64-bit prefix of a hash where 128 bits is needed.
  • Variable-time MAC comparison: every few years a major library ships a regression. Constant-time comparison is non-negotiable.
  • Wrong KDF: using a hash directly where a memory-hard KDF is needed (Argon2, scrypt). Caused real bcrypt-vs-MD5 password breaches.
  • Hash flooding DoS: hash table implementations with predictable hash functions hit by adversarial inputs. The 2003 attacks led to SipHash and randomized hash seeds.
Take the quizBack to intermediate