Security of Hash Functions and MACs: The Birthday Attack

Read five things out of that run.

The birthday probabilities cross one half between 22 and 23 people, and the run prints both so the reader can see it happen. At 57 people a match is almost certain.

The prediction for each digest width. A 16-bit digest collides after about 2 to the power 8.3 tries, a 128-bit digest after 2 to the power 64.3, and a 256-bit digest after 2 to the power 128.3. Those exponents are the security levels, and they are half the digest length plus a small constant.

And the measurement. At 16, 20, 24 and 28 bits, real collisions in truncated SHA-256 were found after 374, 1,701, 7,858 and 22,141 tries against predictions of 320, 1,283, 5,133 and 20,534. Ratios of 1.17, 1.33, 1.53 and 1.08. A single draw lands within about half a factor of the prediction, which is exactly what the distribution says: the birthday bound is a median, not a guarantee.

Contrast this with the previous chapter's toy hash, which collided in 53 tries against a prediction of 320. A ratio near 1 is evidence the function behaves randomly; a ratio far below 1 is evidence it does not. That comparison is the practical use of the bound.

The security table. MD5's 128 bits give 64 bits of collision resistance; SHA-1's 160 give 80; SHA-256's 256 give 128. A 64-bit search is feasible and an 80-bit one was feasible with effort, which is the whole history of those two functions in one line.

The attack on a signature scheme, step by step

This is what the birthday bound is actually used for, and it is the form an examination question takes.

Step 1. The attacker prepares two documents: one the victim is willing to sign, such as an ordinary letter, and one the attacker wants signed, such as an authorisation to pay.

Step 2. The attacker generates about 2 to the power n/2 variations of each, by making changes that do not alter the meaning: extra spaces, a line break moved, a synonym, an invisible character, a different date format.

Step 3. By the birthday bound, among those two sets of 2 to the power n/2 variations there is very likely a pair, one from each set, with the same digest.

Step 4. The attacker presents the innocent variation for signature. The victim signs it. The signature is over the digest, so the same signature is valid on the fraudulent variation. The attacker attaches it there.

Note what the attack needs: a collision, chosen freely by the attacker. It does not need a preimage and it does not need a second preimage of a document somebody else wrote. That is why collision resistance is the property a signature scheme depends on, and why a published collision breaks signatures while leaving password storage alone.

And the defence. A digest long enough that 2 to the power n/2 is infeasible, which today means at least 256 bits. Plus, in some schemes, randomising the digest so that the signer contributes a value the attacker cannot predict.

What this means for a MAC

For a MAC the arithmetic is different and the chapter title names both, so both are asked.

An attacker attacking a MAC has two routes. Guess the key, which costs 2 to the power k for a k-bit key. Or guess the tag, which costs 2 to the power n for an n-bit tag, and each guess needs the verifier to test it, so the attacker cannot do it offline.

So a MAC's strength is min(k, n), and the birthday bound does not halve it, because the attacker cannot mount an offline birthday search: they do not hold the key, so they cannot compute tags themselves. That is the difference from a hash and it is examinable.

But it halves in one case. If the attacker can obtain tags for messages of their choosing, they can look for an internal collision in the MAC's chaining value, and for a MAC built on an iterated construction that costs about 2 to the power n/2 queries. So a MAC's tag should still be long enough that 2 to the power n/2 queries are infeasible, and that is why 128-bit tags are preferred over 64-bit ones.

Distinctions that carry marks

What beginners get wrong here

Saying an n-bit hash gives n bits of security. It gives n against preimages and n/2 against collisions, and which matters depends on the use.

Thinking the birthday attack needs to hit a given digest. It does not. The attacker chooses both documents, which is what makes it cheap.

Counting comparisons wrongly. With 23 people there are 253 pairs, not 22. That miscount is why the result seems paradoxical.

Treating the bound as exact. It is a median. The run's four measurements came in at 1.08 to 1.53 times the prediction.

Halving a MAC's strength by the birthday bound. The attacker cannot compute tags offline. A MAC's strength is the smaller of the key length and the tag length, with a separate query bound for internal collisions.

Quick revision

• Birthday paradox: 23 people give a better than even chance of a shared birthday, because there are 253 pairs, not 22 comparisons.
• General rule: a repeat becomes likely after about the square root of pi N / 2 draws from N possibilities.
• Collision resistance of an n-bit hash is n/2 bits. Preimage and second preimage remain n.
• MD5 128 bits gives 64; SHA-1 160 gives 80; SHA-256 gives 128. Hence 256 bits is the modern floor.
• Measured: collisions in truncated SHA-256 at 16, 20, 24, 28 bits after 374, 1,701, 7,858 and 22,141 tries against predictions of 320, 1,283, 5,133 and 20,534. Ratios 1.08 to 1.53.
• A ratio near 1 is evidence the hash behaves randomly. The previous chapter's toy hash collided at a ratio of 0.17, which is evidence it does not.
• The signature attack: 2 to the power n/2 variations of each of two documents, find a colliding pair, get the innocent one signed, attach the signature to the other. It needs a collision, not a preimage.
• A MAC's strength is min(key bits, tag bits), not halved, because the attacker cannot compute tags offline; but internal collisions cost about 2 to the power n/2 queries.

Test yourself

1. State the birthday paradox and explain why the answer is 23. That among 23 randomly chosen people the probability that two share a birthday exceeds one half, despite there being 365 possible birthdays. The reason is that the relevant count is of pairs, not of people: 23 people give 23 times 22 divided by 2, that is 253 pairs, each matching with probability 1 in 365, so a match becomes likely far sooner than intuition suggests.

2. Give the birthday bound and its consequence for hash functions. A repeat among draws from N possibilities becomes more likely than not after about the square root of pi N / 2 draws. For an n-bit digest N is 2 to the power n, so a collision is found in about 2 to the power n/2 operations, which means an n-bit hash offers only n/2 bits of collision resistance while retaining n bits of preimage resistance.

3. How many operations are needed to find a collision in MD5, SHA-1 and SHA-256, ideally? About 2 to the power 64 for MD5's 128-bit digest, 2 to the power 80 for SHA-1's 160-bit digest, and 2 to the power 128 for SHA-256's 256-bit digest. In practice cryptanalysis reduced the first two well below those figures.

4. Describe the birthday attack on a digital signature scheme. The attacker prepares an innocent document and a fraudulent one, then generates about 2 to the power n/2 meaning-preserving variations of each by altering whitespace, wording or invisible characters. By the birthday bound a pair with the same digest, one from each set, is very likely to exist. The attacker obtains the victim's signature on the innocent variation and attaches it to the fraudulent one; since the signature is computed over the digest, it verifies on both.

5. Which resistance property does that attack defeat, and why does that matter? Collision resistance, because the attacker chooses both documents freely rather than having to match one they were given. It matters because it means a published collision immediately breaks signature schemes using that hash, while leaving uses that depend only on preimage resistance, such as password storage, unaffected.

6. Why does the birthday bound not halve a MAC's strength? Because the attacker has no key and therefore cannot compute tags offline. To search for a collision they must obtain tags from the verifier, one query at a time, so the search is bounded by what the verifier will answer rather than by their own computing power. A MAC's strength is the smaller of its key length and its tag length, although an internal collision in an iterated MAC still costs about 2 to the power n/2 queries, which is why longer tags are preferred.

7. Four measured collision searches came in at 1.08 to 1.53 times the predicted number of tries. What does that tell you, and what would a ratio of 0.17 tell you? That the bound is being met: it is a median rather than a guarantee, and single draws scatter around it by a factor of about a half either way, so ratios near 1 are evidence that the function's outputs are uniformly distributed. A ratio of 0.17 would say collisions are arriving far sooner than chance allows, which is evidence that the outputs are clustered and the function is measurably worse than random.