Hash functions

The toolbox on the first page listed “a fingerprint of some data”: a short value, the same size whatever went in, that changes completely if the data changes at all. That’s a hash function. A cryptographic one is the workhorse of the field: it checks that a download is the file it should be, names every commit in Git, stores passwords, and is what actually gets signed when a document is signed. This page builds up what such a function has to do, looks inside the one most used today, SHA-256, and follows how its predecessors were broken.

(Hashes turn up in signal processing too: Shazam’s are the friendly kind, designed so that similar sounds give the same hash. A cryptographic hash wants the opposite: nobody should be able to make two different inputs give the same one.)

1 · A fingerprint for data

A first idea for a fingerprint is a check value such as a CRC, the remainder after dividing the message by a fixed polynomial (the DSP site’s LFSR page builds one). It’s excellent at catching accidents: a burst of noise on a wire never happens to leave the CRC unchanged. But it was never meant to stand up to someone trying.

A CRC is linear, in arithmetic where adding is XOR: change some bits of the message, and the CRC changes by an amount that depends only on which bits changed, not on the rest of the message. So Mallory can change Alice’s message however they like, then add four bytes chosen to put the CRC back. Each of the 32 bits in those four bytes changes the CRC in its own fixed way; finding which of them to flip to make up the difference is 32 equations in 32 unknowns, solved by elimination, as on the Randomness page.

Alice’s message, Mallory’s change (edit it), and the same change with four bytes added (in hex) chosen so its CRC-32 is Alice’s again. Whatever Mallory writes, the CRCs match (checked in the tests for 50 random messages and targets). SHA-256 can’t be fixed up like this: its fingerprints of the three messages have nothing in common.

So a fingerprint that has to resist people needs to be anything but linear. That’s what makes a hash cryptographic.

2 · What a cryptographic hash must resist

There are three things an attacker might try, each harder to defend against than the one before:

Finding a preimage. Given a hash value, find any message that has it. (A password database stores hashes; finding a preimage would give a password that works.)
Finding a second preimage. Given a message, find a different one with the same hash. That’s what Mallory just did to the CRC.
Finding a collision. Find any two messages with the same hash, choosing both.

A collision sounds harmless (Mallory chooses both messages, so who cares if they match?), but it’s the dangerous one in practice. Mallory writes two documents with the same hash: a harmless one, which Alice signs (signing really signs the hash), and a harmful one, which now carries Alice’s signature too.

For all three to be hard, the output must look unrelated to the input: no part of the hash should follow any part of the message in a way that could be steered. The visible sign of that is the avalanche: change one bit of the input, and about half the output bits change, which ones being impossible to predict. It’s the same property block ciphers need (Block ciphers).

SHA-256 of a message, and the same with one bit flipped (choose which with the slider). The grid is the 256 output bits after the flip, 32 to a row; the changed ones are coloured. Below, the measured average over 1,000 random flips of this message. Over 2,000 flips, the average is within one bit of 128, half of 256 (pinned in the tests).

3 · The birthday bound

How hard is each attack by brute force? For a preimage, with a 256-bit hash, Mallory has to try messages until one hits the given value, and each try succeeds with a chance of 1 in 2²⁵⁶. A collision is far easier, for a reason that surprises nearly everyone the first time: the birthday problem.

How many people need to be in a room for an even chance that two share a birthday? The answer is 23. It seems far too few, because it’s natural to think of one person matching you. But a match between any two will do, and 23 people make 23 × 22 / 2 = 253 pairs, each with a 1 in 365 chance. The exact chance takes a little more care. Work out the chance that nobody shares, one person at a time: the second person must miss the first (364 of 365 days will do), the third must miss both (363 of 365), and so on:

\text{chance nobody shares} = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{343}{365} \approx 0.493

So the chance that someone does is 50.7%.

The chance that at least two people in a room share a birthday (365 equally likely days), as the room fills up. It passes 50% (dashed) at 23 people; by 50 it’s 97%, and by 70, 99.9% (all pinned in the tests). Drag the slider: the pairs, n(n − 1)/2, grow with the square of the number of people.

The same holds for any set of N equally likely values. After k tries there are about k²/2 pairs, each matching with a chance of 1 in N, so a match becomes likely once k²/2 is around N: when k is around the square root of N. That’s the birthday bound. For a hash of n bits, N = 2ⁿ, and √N = 2ⁿᐟ²: a collision takes about 2ⁿᐟ² tries, not 2ⁿ. (The Debian OpenSSL bug used the same arithmetic to spot machines with the same key.)

press Find a collision

SHA-256 cut down to its first few bits, so that collisions are within reach. The search hashes “message number 0”, “message number 1”, … remembering every value, until one repeats. The messages are always the same, so the results are too: 581 tries for 16 bits (√N = 256), 4,987 for 24 bits (√N = 4,096), and 20,294 for 32 bits (√N = 65,536), pinned in the tests. Each is within a small factor of √N; trying for a particular value instead would take around N.

So a hash’s strength against collisions is half its length in bits. SHA-256 gives 128 bits of it: as far out of reach as trying every 128-bit key (see What we want). A 128-bit hash such as MD5 would give only 64, which a determined attacker can reach by brute force alone, and that was before MD5 was broken outright (section 5).

4 · Inside SHA-256

A hash has to take any amount of data, but the mixing inside works on fixed-size pieces. SHA-256 bridges the two with a design known as Merkle–Damgård, after Ralph Merkle and Ivan Damgård, who each showed in 1989 that it works:

Pad the message: add a 1 bit (the byte 80 in hex), then zeros, then the message’s length in bits as a 64-bit number, so that the total is a whole number of 64-byte blocks.
Start from a fixed state of 256 bits (eight 32-bit words, from the square roots of the first eight primes: numbers with nothing up their sleeve).
For each block, mix it into the state with the compression function, which takes 256 bits of state and 512 bits of block and returns a new 256-bit state.
The final state is the hash.

Putting the length in the padding matters: without it, messages that differ only in how many zeros they end with could pad to the same blocks. Merkle and Damgård showed that, padded this way, a collision in the whole hash would mean a collision in the compression function, so it’s enough to make that one function strong.

41 message 80 the 1 bit 00 zeros 00 the length, in bits

A message padded and cut into 64-byte blocks (in hex: the message’s bytes, the 1 bit, zeros, and the length), with the state after each. Each state is the compression function of the one before and the next block; the last is the hash, and it matches the site’s SHA-256 (checked against FIPS 180-4’s examples). Type a longer message to add blocks, and use the slider to pick one out.

The compression function works in 64 rounds. Eight working words, a to h, start as the state. Each round takes one word of the block (the 16 words of the block are stretched into 64 by mixing earlier ones), mixes it with a few of the working words using additions, rotations and bitwise choices, and shifts the words along one place:

t1 = h + Σ1(e) + choose(e, f, g) + k[i] + w[i]     # choose: each bit of e picks f's bit or g's
t2 = Σ0(a) + majority(a, b, c)                      # majority: the bit most of a, b, c have
h, g, f, e, d, c, b, a = g, f, e, d + t1, c, b, a, t1 + t2

Here Σ0 and Σ1 XOR together three rotations of a word, and k[i] is a fixed constant for each round (from the cube roots of the first 64 primes). At the end the working words are added to the state it started from.

Additions carry between bits, rotations move bits across the word, and choose and majority aren’t linear at all, so a difference in one bit soon touches everything:

The 256 working bits (a to h, 32 each) through the 64 rounds of compressing Alice’s dinner message, compared with the same message with one bit flipped: a dot wherever the two differ, with the count every eight rounds on the right. Nothing differs until the round that first uses the changed word. A flip in the first character shows 3 different bits after round 1 and over 100 by round 5; averaged over random flips, half the bits differ by round 16 (all pinned in the tests). Move the flipped bit later in the message and the spreading starts later, when its word comes in.

One consequence of the design is worth flagging. The hash is the final state. So anyone who knows the hash of a message can carry on from it, hashing more blocks on the end, without knowing the message. That’s no problem for a fingerprint, but it breaks the obvious way of making a keyed check value from a hash, and it’s the length extension attack on MACs and authenticated encryption.

5 · How MD5 and SHA-1 fell

MD5 (Ron Rivest, 1991, 128 bits) and SHA-1 (published by NIST in 1995, 160 bits) are built just like SHA-256: Merkle–Damgård around a compression function of rounds. For years they were the standard hashes. Both fell to the same idea as differential cryptanalysis: find a path of differences through the rounds that cancels out with a useful probability, and steer the message words to make it happen.

MD5 collisions (2004). Xiaoyun Wang and colleagues published the first: two different messages with the same MD5. Improved methods soon found MD5 collisions in seconds on an ordinary computer.
A forged certificate authority (2008). A team including Alexander Sotirov and Marc Stevens used a chosen-prefix collision, two different starts given the same hash by carefully computed endings, to make a certificate that a real certificate authority had signed (for an innocent-looking website certificate) also valid for a certificate authority of their own. They used around 200 games consoles to compute it.
Flame (2012). Malware found in the Middle East carried a code-signing certificate that appeared to come from Microsoft, made with a chosen-prefix MD5 collision of a new kind, so it could pose as a Windows update. Whoever built it had their own cryptanalysis.
SHAttered (2017). CWI Amsterdam and Google published two different PDF files with the same SHA-1, the first SHA-1 collision, after about 2⁶³ SHA-1 computations. Chosen-prefix collisions for SHA-1 followed in 2020.

A hash doesn’t fail all at once: collisions come first, years before anyone finds a preimage (none has been found in practice for MD5 or SHA-1 even now). But collisions are enough to forge signatures and certificates, as the examples show, so each was retired once collisions appeared. SHA-256, from the same family as SHA-1 but larger and with more careful mixing, has no known attack better than the birthday bound.

6 · SHA-3 and the sponge

In 2007 NIST opened a competition for a new hash, not because SHA-256 was broken, but so that a hash of a quite different design would be ready if it ever was. The winner, in 2012, was Keccak, by Guido Bertoni, Joan Daemen (one of the two designers of AES), Michaël Peeters and Gilles Van Assche. It became SHA-3 (FIPS 202) in 2015.

SHA-3 isn’t Merkle–Damgård. It’s a sponge: a large state of 1,600 bits, split into two parts. The rate (1,088 bits for SHA3-256) is where the message goes in and the hash comes out; the capacity (the other 512 bits) is never touched directly by either.

Absorbing: XOR the next block of message into the rate, then scramble the whole state with a fixed permutation, f (24 rounds of mixing). Repeat for every block.
Squeezing: read the hash out of the rate (for SHA3-256, its first 256 bits).

SHA3-256 as a sponge: each 136-byte block of the (padded) message XORed into the rate, then the permutation f over the whole state; the hash is the first 256 bits of the rate at the end. Type more than 135 bytes to add a block. Its result for “abc” matches FIPS 202’s example (pinned in the tests), and SHA-256’s result is shown beside it: two entirely different functions.

Because the hash shows only 256 of the 1,600 bits, nobody can pick up the state from the hash and carry on: the capacity stays hidden. So SHA-3 can’t be extended the way SHA-256 can, and keying it is as simple as hashing the key followed by the message. The capacity also sets its strength: an attack has to find a collision in those hidden 512 bits, which by the birthday bound takes about 2²⁵⁶ tries, so the 256-bit output, at 2¹²⁸ for a collision, is the limit.

Summary

A hash function turns any data into a short, fixed-size fingerprint. A CRC isn’t a safe one: it’s linear, so four chosen bytes can give any CRC.
A cryptographic hash must resist finding a preimage, a second preimage and a collision, and shows the avalanche: one flipped input bit changes about half the output bits.
The birthday bound: with N possible values, a match comes after about √N tries (23 people for a shared birthday). An n-bit hash resists collisions only up to about 2ⁿᐟ² work.
SHA-256 pads the message and feeds it, block by block, through a compression function of 64 rounds (Merkle–Damgård); the hash is the final state, which allows length extension.
MD5 and SHA-1 fell to differential attacks: collisions, then chosen-prefix collisions, enough to forge certificates (2008, Flame in 2012) and documents (SHAttered, 2017).
SHA-3 is a sponge: the message goes into the rate, the capacity stays hidden, and length extension is impossible.