Fingerprints of data

A cryptographic hash function $H$ maps an input of any length to an output of fixed length $n$, typically 256 bits, called the digest. There is no key. It must be fast to compute and, in a precise sense, impossible to steer: the digest of SHA-256 for “abc” is ba7816bf…, and for “abd” something with no visible relation to it. Hashes are the most used cryptographic primitive of all: they identify Git commits, the blocks of Bitcoin's chain, the files of software updates; they are inside every signature, every password database and every TLS handshake.

§Three kinds of resistance

Collisions must exist, since infinitely many inputs share $2^n$ outputs; the requirement is that nobody can find one. For an ideal $n$-bit hash, finding a preimage takes about $2^n$ tries. Finding a collision takes far fewer.

§The avalanche

A good hash behaves like a random function: every output bit depends on every input bit, and changing the input flips each output bit with probability one half, independently of the others.

§The birthday paradox

In a room of 23 people, the probability that two share a birthday is more than one half. The paradox, which is not a paradox, is that we compare pairs, and 23 people make 253 pairs. The same arithmetic governs collisions.

Proof of the approximation

The $i$-th draw avoids the $i-1$ earlier ones with probability $1-(i-1)/N$, so no collision happens with probability $\prod _{i=1}^{q-1}(1-i/N)$. Using $1-x\le e^{-x}$, this is at most $\exp (-\sum _{i}i/N)=e^{-q(q-1)/2N}$, and for $q\ll N$ the approximation is tight. Setting it to $1/2$ gives $q^2\approx 2N\ln 2$, that is $q\approx 1.18\sqrt{N}$.

So a 128-bit hash offers only 64 bits of collision resistance, within reach of a large computation; that is why modern hashes have at least 256 bits. The same bound limits 64-bit block ciphers (Sweet32) and random nonces.

§Merkle–Damgård

How do you hash an input of any length with a function of fixed size? Ralph Merkle (in his 1979 thesis) and Ivan Damgård (1989) independently found the construction behind MD5, SHA-1 and SHA-2. Take a compression function $f$ that maps a chaining value and a message block to a new chaining value. Pad the message (with its length at the end), cut it into blocks $m_1,\dots ,m_{\ell }$, and iterate:

Proof

Suppose $H(m)=H(m^{\prime })$ with $m\ne m^{\prime }$. If their lengths differ, the last blocks differ (they encode the lengths), and $f(h_{\ell -1},m_{\ell })=f(h_{{\ell }^{\prime }-1}^{\prime },m_{{\ell }^{\prime }}^{\prime })$ is already a collision of $f$. Otherwise walk back from the end: at the first step $i$ (from the end) where $(h_{i-1},m_i)\ne (h_{i-1}^{\prime },m_i^{\prime })$ but $f$ of both is equal, we have a collision of $f$. Such a step exists because the inputs differ somewhere.

The construction has a quirk: $H(m)$ is the internal state after processing $m$, so anyone who knows $H(m)$ and the length of $m$, but not $m$ itself, can compute $H(m\Vert \mathit{pad}\Vert x)$ for any $x$. This length-extension attack breaks the naive authentication tag $H(k\Vert m)$, as Flickr's API learned in 2009, and is the reason for HMAC.

§The fall of MD5 and SHA-1

Ron Rivest designed MD5 in 1992; the NSA designed SHA-1 (160 bits) in 1995. In August 2004 the Chinese cryptographer Xiaoyun Wang and her team presented collisions for MD5 and several related hashes, computed in hours; a year later they showed that SHA-1 was much weaker than its 80-bit birthday bound. The consequences took years to play out:

• 2008: Marc Stevens, Alexander Sotirov and colleagues used an MD5 collision to create a rogue certificate authority trusted by every browser.
• 2012: the Flame malware, attributed to state actors, forged a Microsoft code-signing certificate with a new MD5 collision attack and spread through Windows Update.
• 2017: Google and CWI Amsterdam announced SHAttered, two different PDF files with the same SHA-1, after $2^{63.1}$ SHA-1 computations (about 6,500 CPU-years and 110 GPU-years).
• 2020: Gaëtan Leurent and Thomas Peyrin's “SHA-1 is a Shambles” produced a chosen-prefix collision for about $45,000 of GPU time, enough to impersonate PGP keys.

Git, which identified everything by SHA-1, added collision detection in 2017 and supports SHA-256 repositories since 2020. The desktop app keeps MD5 and SHA-1 for checking old checksums, marked as broken.

§SHA-2, SHA-3 and BLAKE

SHA-2 (2001: SHA-224, SHA-256, SHA-384, SHA-512) is also Merkle–Damgård, with a much stronger compression function, and remains unbroken. But after Wang's attacks NIST wanted a backup built on different principles, and in 2007 opened another public competition. Sixty-four candidates were submitted; in 2012 NIST chose Keccak, by Guido Bertoni, Joan Daemen (co-designer of AES), Michaël Peeters and Gilles Van Assche, published as SHA-3 in FIPS 202 (2015).

Keccak is a sponge. Its state of 1,600 bits is split into a rate of $r$ bits and a capacity of $c$ bits. In the absorbing phase each $r$-bit block of the message is XORed into the rate part and the whole state is permuted by a fixed permutation $f$; in the squeezing phase the output is read $r$ bits at a time from the rate part, permuting in between. The capacity is never touched directly by the input or the output.

Because the capacity is hidden, a sponge has no length extension. Keccak's structure also gives extendable-output functions (SHAKE128, SHAKE256), used inside the post-quantum standards. BLAKE2 (2012), derived from the SHA-3 finalist BLAKE by Jean-Philippe Aumasson and colleagues, is faster than MD5 in software and as secure as SHA-3; BLAKE3 (2020) organises the computation as a Merkle tree, so it hashes in parallel on every core.

§HMAC: a hash with a key

A hash proves nothing about who made a message: anyone can recompute it. A message authentication code mixes in a secret key, so only those who know the key can produce or check the tag. Mihir Bellare, Ran Canetti and Hugo Krawczyk designed HMAC in 1996 to be safe with Merkle–Damgård hashes:

with two fixed constants $\mathit{ipad}=\text{0x36}\dots$ and $\mathit{opad}=\text{0x5c}\dots$. The outer hash hides the inner state, which defeats length extension, and the construction is provably a pseudorandom function if the compression function is. HMAC authenticates TLS records, JSON Web Tokens (HS256), AWS API requests and one-time passwords (TOTP). Verification must compare tags in constant time, or the time taken reveals how many bytes matched; the desktop app does.

§Further reading

1. Ralph Merkle, Secrecy, Authentication and Public Key Systems, PhD thesis, Stanford (1979); Ivan Damgård, “A Design Principle for Hash Functions”, CRYPTO 1989.
2. Xiaoyun Wang and Hongbo Yu, “How to Break MD5 and Other Hash Functions”, EUROCRYPT 2005.
3. Marc Stevens et al., “The first collision for full SHA-1”, CRYPTO 2017 (shattered.io).
4. Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, “On the Indifferentiability of the Sponge Construction”, EUROCRYPT 2008.
5. Mihir Bellare, Ran Canetti, Hugo Krawczyk, “Keying Hash Functions for Message Authentication”, CRYPTO 1996.