How Differential Cryptanalysis Broke SHA-1

SHA-1 compresses 512-bit blocks through 80 rounds and returns 160 bits, so the birthday bound places collision resistance at about 80 bits. For two decades the working assumption was that SHA-1 sat close to that bound. It did not. The collision published in 2017 was found at a cost on the order of 2^63 SHA-1 compressions, some 65,000 times cheaper than the generic figure, and it was obtained by constructing the collision rather than by searching for one. Following how requires descending from the round function into the differential path and back out.

The round function and where differences go

SHA-1’s 80 rounds each compute a new working variable from rotations and a nonlinear function of three of the five state words, add a round constant and a message word, and rotate the working set. The message schedule expands 16 32-bit words into 80 by XOR of four earlier words and a rotation, so every message bit influences many later rounds.

A differential attack fixes a difference pattern between two messages and asks where it propagates. Because the operations are addition modulo 2^32, rotation, and bitwise logic, a difference in one word produces a difference in later words in a partly controllable way. Addition is the awkward one: the difference that results from adding two words depends on their carries, so a given input difference can produce a set of output differences, each with a probability. Rotation moves bits to known positions and is free of probability. The bitwise functions are non-linear in the Boolean sense but have simple difference behaviour for their particular truth tables, which is why they carry most of the design weight.

The attacker’s goal is a difference pattern that is non-zero somewhere in the message and cancels to zero in all five state words after the last round. If the chaining values coincide at the end of a block, the remaining iteration is identical for both messages, and the two inputs collide.

The pattern is a characteristic: for each round, which bits of which words differ, and what each difference is assumed to be. Constructing one is the expensive part. It is done partly by search and partly by hand, working backwards from a zero final difference through the round constraints, with a cost model that penalises the unlikely conditions. The search space is large enough that the published characteristics took months of computation to find and were sharpened over several papers as the attack improved.

From characteristic to message pair

A characteristic says which differences are needed. It does not say which messages produce them, because the message words are free variables that have to be solved for. The attacker’s structure is a meet-in-the-middle: the first several rounds are worked forward from an arbitrary prefix, the last several are undone from the target chaining value, and the two meet at a set of constraints on the middle message words.

Message modification is the technique that turned theoretical characteristics into practical attacks. Most of the conditions a characteristic imposes are local: a particular bit of a particular word must have a particular value at a particular round. The attacker computes the state forward, and where a condition fails, perturbs the message word that feeds that round in a way that fixes the condition while preserving the conditions already satisfied in earlier rounds. Deterministic modifications handle early rounds and always succeed; probabilistic modifications handle later rounds and are applied in the hope that the remaining conditions hold.

This is why the attack’s cost is measured in trial-and-error on the last dozen rounds rather than in a search over the full message space. A well-constructed characteristic reaches round 60 or so with modifications, leaving the remainder to chance, and a small probability raised to the power of a dozen is a reachable number.

The second ingredient is the near-collision block. Rather than trying to cancel all differences in one block, the attack uses two: the first produces a small, specified difference in the chaining value, and the second cancels it. Splitting the work means each block only has to solve part of the problem, which makes each differential path shallower and the search for it tractable. It also means the colliding messages are longer than one block, which shapes what the attacker can produce.

The published collision and its construction

attack cost      2^63      SHA-1 compressions, order of magnitude for SHAttered
birthday bound   2^80      generic collision search on a 160-bit digest
ratio            ~2^17     gap between constructed and searched collision

What that cost bought was not a collision between arbitrary byte strings. The two colliding messages are PDF files that render differently, which was the point: a collision between random-looking binary garbage proves a weakness but not a practical threat. Publishing the pair made the result directly verifiable, and a digest utility run over either file returns the same 40 hexadecimal characters.

The step from that to certificate forgery is the chosen-prefix version, where the attacker fixes two meaningful prefixes before the attack begins. Stevens, Lenstra, and de Weger described a chosen-prefix attack against the full function in 2011 and estimated its cost as substantially higher than the plain collision attack. The practical consequence is a timeline: a function whose collision resistance is reduced by four orders of magnitude is not safe for any use where an attacker chooses both messages and takes value from their collision. Splitting a distinguishing-prefix collision into two near-collision blocks is what makes the difference between “a curiosity” and “a certificate”.

Why the margin was thinner than the bound suggested

The birthday bound is not a statement about SHA-1. It is a statement about the collision-finding problem in a random function of 160 bits. A real hash has structure, and differential cryptanalysis exploits the structure. For MD5 the gap between the bound and reality was so large that the function fell to ordinary hardware; for SHA-1 the gap was smaller and the attack needed substantial resources, but it was on the same side of the line.

The design rationale for SHA-1’s 80 rounds was partly margin against this class of attack. SHA-0, which differed in the message schedule expansion and nothing else, fell to collisions years earlier at a far lower cost. Adding the rotation to the schedule raised the attack cost by orders of magnitude without making the function behave like a random function. Extra rounds or a wider state move the attack cost; they do not close the gap, and there is no a priori reason to believe any particular number of rounds is beyond the reach of a better characteristic.

The general lesson is that collision resistance claims for a specific function come from cryptanalysis, not from the birthday bound. The bound says how low the cost can be. Cryptanalysis says how low it is for that function. A function with no published attack is not known to be at the bound; it is known to have resisted the attacks that have been tried, which is a different and weaker statement.

What replaced it and what that changed

The direct replacement is SHA-256, with a 256-bit digest and no published collision cheaper than the generic bound. The structural change that matters is the message schedule, which SHA-2’s designers strengthened with the benefit of watching SHA-0 and MD5 fall.

In practice the migration involved protocol changes rather than a function swap. Certificate authorities, version control systems, and signature schemes that identify a hash by an algorithm identifier had to add identifiers for the replacement while keeping old signatures verifiable for a transition period. That dual-verification window is where most real-world risk lived: an implementation that accepts both algorithms must reject a SHA-1 signature wherever a SHA-256 one is required, and the requirement belongs at the policy layer rather than in the parser, because a parser that accepts either cannot distinguish “the signer used SHA-1” from “the attacker downgraded the identifier”.

The other consequence is architectural. SHA-256 inherits the iterated structure, and with it length extension and Joux multicollisions, which SHA-3’s sponge was designed to avoid. The transition to SHA-3 is not driven by SHA-1’s collision weakness, since SHA-2 remains unbroken at the collision level; it is driven by the wish for a structurally different fallback, as described in the sponge construction. The same distinction between “resisted so far” and “proven” applies to every function in the replacement chain, and the honest way to size a margin is to assume the next characteristic is better than the last one.