How SHA-2 and SHA-3 Would Break: Merkle-Damgard Collisions, Length Extension, and the Sponge's Algebraic Frontier

1. Two Hashes, Two Deaths#

Here is something you can say about a machine before it has ever failed: which way it will fall. A structural engineer knows a bridge sways before it buckles and buckles before it snaps, because the failure mode is written into the truss, not painted onto the surface. Cryptographic hash functions are the same. We can already describe, mechanically and in detail, how SHA-2 and SHA-3 would break -- even though nobody has ever broken either one, and the two descriptions have almost nothing in common.

The two functions NIST standardized as the Secure Hash Standard and the SHA-3 Standard ^{[1, 2]} sit underneath an enormous amount of modern security: certificate chains, signed software updates, commitment schemes, the proof-of-work in a blockchain. They advertise the same guarantee. For a 256-bit digest, finding any two inputs that hash to the same value should cost about $2^{128}$ attempts. That number is easy to say and hard to feel. $2^{128} \approx 3.4 \times 10^{38}$, a 39-digit count -- far more than every grain of sand on Earth, yet far fewer than the atoms that make up the Earth. It is an enormous human-scale number that is still dwarfed by atomic-scale ones.

That $2^{128}$ figure is not a design target so much as a ceiling imposed by arithmetic. Feed roughly $2^{n/2}$ random messages into any $n$-bit hash and, by the birthday paradox, two of them almost certainly collide. So $2^{128}$ is simply the generic cost of a birthday search against a 256-bit digest -- the number every genuine attack has to beat to count as a break ^[1].

Now the strange part. SHA-256 and SHA3-256 keep that identical promise using almost none of the same parts. SHA-2 iterates a small compression function from a fixed starting value, folding the message in one block at a time -- the Merkle-Damgard design. SHA-3 does something else entirely: it stirs the message into a large public permutation and squeezes the digest back out -- the sponge. Two constructions, one guarantee.

And because the constructions differ, their deaths differ. A Merkle-Damgard hash does not die at its digest size; it dies when a carefully chosen difference in the input threads through the compression function and cancels at the output -- the method that felled MD5 and SHA-1. It also leaks: given a digest, you can often extend the message without knowing it. The sponge has neither trait. It hands an attacker a different target: the algebra of its one nonlinear step, chi, which has algebraic degree just two.

That is the whole argument in one sentence, and the rest of this article is its proof. One boundary before we begin.

To see why each death is pre-written, we have to go back to the 1989 bargain that made iterated hashing trustworthy in the first place -- and to the two debts it quietly signed on SHA-2's behalf.

2. The Merkle-Damgard Bargain of 1989#

In 1989 two people, an ocean apart and unaware of each other, answered the same question the same way -- and in doing so pre-wrote how SHA-2 would one day die. Ralph Merkle and Ivan Damgard each presented the result at CRYPTO 1989 ^{[3, 4]}.

The question was practical and deep at once: how do you hash a message of arbitrary length using only a fixed-size building block, and then prove the result is as hard to collide as that block? Their answer is the scaffolding under nearly every hash you have ever used.

The shape of the compression function they had in mind, and the one every hash in the SHA line uses, is Davies-Meyer.

flowchart LR
IV["IV (fixed start)"] --> F1["f"]
B1["Message block 1"] --> F1
F1 -->|"chaining value H1"| F2["f"]
B2["Message block 2"] --> F2
F2 -->|"chaining value H2"| F3["f"]
B3["Final block + length pad"] --> F3
F3 --> D["Digest = final chaining value"]

The proof is the reason the world trusted this design for two decades, and it is worth seeing rather than taking on faith -- because both of SHA-2's structural debts fall directly out of it.

That reduction is a genuine gift -- it lets designers focus all their effort on one small function -- but it comes with two debts written into the same clause.

The first debt: all of the hash's collision resistance now concentrates in $f$. An attacker cannot collide SHA-256 without colliding its 64-step compression function, so that function is the entire battlefield. Everything a would-be attacker does, and everything the last thirty-five years of cryptanalysis has done, targets exactly that object ^[5].

The second debt is subtler and, for a practitioner, more immediately dangerous. Look again at the chain: the digest that comes out is the final chaining value -- the complete internal state at the end of the computation. Nothing is hidden.

The strengthening step -- appending the message length before the final block -- is what makes the collision proof go through, closing the length-mismatch case above. The Davies-Meyer feed-forward and the length padding are two separate load-bearing details. The feed-forward stops an attacker running the block cipher backward from a chaining value; the length padding stops trivial collisions between messages of different lengths. Remove either and the reduction fails. But it does nothing to hide the state -- so it fixes the first debt's proof without touching the second debt at all.

Merkle-Damgard signs two debts at once: all collision resistance concentrates in one small function, and the digest is the whole internal state. The first is where the hash can be collided; the second is why it leaks.

A construction that concentrates all its collision resistance in one small function is only ever as safe as that function is hard to collide. For fifteen years, nobody could touch it. Then the mathematics of differences arrived, and MD5 fell in minutes.

3. How a Merkle-Damgard Hash Actually Dies#

The break, when it came, did not come from brute force. It came from the arithmetic of differences -- and once you see it, you cannot un-see why SHA-2 is built the way it is.

The idea starts with a question no birthday search ever asks: what if we do not treat the hash as a black box, but push a specific, carefully chosen difference between two messages through its internals and watch where the difference travels? If we can arrange for the difference to appear, ripple through a few steps, and then cancel itself out exactly at the output, the two messages collide -- and we never paid the $2^{n/2}$ birthday toll.

Florian Chabaud and Antoine Joux built the first working version of this against SHA-0 at CRYPTO 1998 ^[6]. Their tools were two ideas that still organize the whole subject.

By chaining local collisions along a differential characteristic so the total difference vanished at the output, Chabaud and Joux drove the estimated cost of a SHA-0 collision down to roughly $2^{61}$ -- comfortably below the $2^{80}$ birthday wall for a 160-bit digest ^[6]. It was an estimate, not a produced collision, but it was the first real crack in the black box.

Then Xiaoyun Wang turned the estimate into a scalpel. In 2004 and 2005, Wang, with Hongbo Yu and Yiqun Lisa Yin, announced results that stunned the field: full, practical collisions for MD5 -- Rivest's 1992 design ^[7] -- and a collision attack on the full SHA-1 ^[8], well below its birthday bound ^{[9, 10]}. The engine had two new parts. First, a hand-built nonlinear path through the hard early steps of the compression function, spliced onto a cheap linear trail for the rest. Second, and decisive:

flowchart TD
A["Choose a message difference"] --> B["Build a differential characteristic ending in zero output difference"]
B --> C["Derive per-step sufficient conditions on state bits"]
C --> D["Message-modify the early steps to force cheap conditions deterministically"]
D --> E["Search the residual probability for the hard late conditions"]
E --> F["Output a conforming colliding message pair"]

Why does modifying the message help so much? The answer is specific enough to work through, and it is exactly the mechanism the earlier hashes handed the attacker for free.

The consequence reset every intuition about hash security. Full MD5, whose 128-bit digest nominally promised $2^{64}$ collision work, collapsed to seconds on a PC ^[9]. Full SHA-1, nominally $2^{80}$, fell to an estimated $2^{69}$ -- a real break of the design, years before anyone spent the compute to exhibit an actual colliding pair ^[10].

A Merkle-Damgard hash does not die at its digest size. It dies when a differential characteristic plus message modification threads its compression function -- deterministically through the early steps, cheaply through the tail. Collision resistance was never really about the number of output bits; it was always about whether a path exists through $f$.

Those hand-built attacks were later paid out in full, practical collisions -- SHAttered in 2017 and SHAmbles in 2020 -- but those belong to the deployment story, not this one. SHAttered (Stevens, Karpman, Bursztein, Albertini, and Markov) produced the first identical-prefix SHA-1 collision at about $2^{63.1}$ ^[11]; SHAmbles (Gaetan Leurent and Thomas Peyrin, correcting a common misattribution to Marc Stevens) produced the first chosen-prefix SHA-1 collision at about $2^{63.4}$ and forged a PGP key ^{[12, 13]}. Both are evidence that the differential method pays out end to end; the empirical sibling article tells their story.

This is the pivotal fact of the whole subject. So the real question becomes: can that same scalpel reach SHA-2? The answer forced cryptography down two roads at once.

4. Two Lineages Diverge#

Start with the cleanest evidence in the whole story that patching a weak compression function only buys time. SHA-0, standardized in 1993, had a linear message expansion; it was withdrawn in 1995 and replaced by SHA-1, whose entire difference from SHA-0 was a single one-bit rotation added to that expansion. That one rotation held for about a decade. Then a Wang-style path walked straight through it ^[10]. A one-operation fix delayed the break; it did not prevent it.

The full six-generation lineage reads as a slow-motion argument, each break motivating the next design.

gantt
title Two lineages, 1989 to 2024
dateFormat YYYY
axisFormat %Y
section Construction
Merkle-Damgard bargain :1989, 1990
MD5 (RFC 1321) :1992, 1993
SHA-1 (FIPS 180-1) :1995, 1996
SHA-2 standardized :2001, 2002
SHA-3 competition :2007, 2012
SHA-3 standard (FIPS 202) :2015, 2016
section Cryptanalysis
Chabaud-Joux on SHA-0 :1998, 1999
Wang breaks MD5 and SHA-1 :2004, 2006
Zero-sum full Keccak-f :2011, 2012
SHA-256 reduced-round records :2013, 2024
SHA-3 internal-differential records :2013, 2024

By 2005 the field had a decision to make, and it split into two philosophies. The first response was to harden the same construction. SHA-2, standardized in 2001 and still the workhorse, kept Merkle-Damgard and Davies-Meyer but gave the compression function a much larger state, a heavier message schedule, and modular-addition mixing designed to starve differential paths ^[1]. That is the road we return to in the next section, because it worked.

The second response was more radical. Stung by the 2004-2005 breaks, NIST announced the SHA-3 competition on November 2, 2007, and ran it until October 2, 2012, explicitly seeking a hash that would fail differently from the Merkle-Damgard family -- so that a single new cryptanalytic idea could not bring down every standardized hash at once ^[17]. The winner was Keccak, a sponge built on a large public permutation, designed from the start so that its hidden capacity removes length extension by construction ^[16].

The subtle and load-bearing point is what NIST did not do. It did not retire SHA-2.

Two lineages, two answers to the same failure. But an answer is only as good as the attack it survives -- so why has SHA-2 held for more than two decades, and what exactly did the sponge change?

5. Why SHA-2 Held, and What the Sponge Changed#

Two structural facts define the present. The first is that the same message-modification machinery that broke MD5 and SHA-1 stalls on SHA-2 -- and the reason is one design choice. The second is that the sponge removed the debts a differential attack needs, and put something entirely different in their place.

Why the scalpel stalls on SHA-2#

Recall the mechanism from the last section: message modification is cheap only because, in the early steps, each message word is a free variable entering the state at exactly one place. Break that "one free word per early step" structure and the trick loses its edge. SHA-2 breaks it on purpose.

In MD5 and SHA-1 the message schedule is essentially a permutation (and, later, a linear expansion) of the input words -- clean and separable. SHA-2's schedule is neither. From step 16 onward, each expanded word is built by

$W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16} \pmod{2^{32}}$

where $\sigma_0$ and $\sigma_1$ are XORs of rotations and a shift, and the additions are modular ^[1]. Those modular additions couple the words through carries: changing one bit of one word can ripple through carry chains into many others. The clean, separable structure that let an attacker solve each early condition by inverting a single word update is gone. Now solving one sufficient condition perturbs others, and the conditions can no longer be discharged by independent single-word inversion.

That carry-laden coupling is the structural reason the hand construction that felled MD5 and SHA-1 cannot be driven through SHA-2 by hand at all -- which is why the modern realization of the attack is an automated SAT/SMT solver managing the entangled condition system, and why even that tooling, in the record-holders' own words, "has reached the bottleneck" around 39 of 64 steps ^[15]. We return to that number in the next section. For now the point is qualitative: SHA-2 held because it made the compression function's internals too coupled for the differential scalpel to carve cleanly.

What the sponge deleted#

Keccak does not try to win the differential arms race. It changes the board.

flowchart LR
MSG["Message blocks"] -->|"XOR into rate"| RATE["Rate (r bits)"]
RATE --> F["Keccak-f[1600], 24 rounds"]
CAP["Capacity (c bits): never absorbed or squeezed"] --> F
F -->|"squeeze"| DIG["Digest, read from the rate only"]

Two debts vanish at once. Because the capacity is never emitted, the digest is not the full internal state -- so no attacker can resume the computation from it. Length extension is gone by construction, not by patch ^[19]. And because there is no keyed compression function -- just one fixed public permutation -- there is no keyed object to push a differential characteristic through to force a hash collision directly the way Wang did. The entire Merkle-Damgard attack surface is simply absent.

So what is left to attack? The permutation's algebra. And that turns on the single nonlinear step inside Keccak-f.

flowchart LR
S["State (1600 bits)"] --> T["theta: linear column mixing (degree 1)"]
T --> R["rho: bit rotations (degree 1)"]
R --> P["pi: lane permutation (degree 1)"]
P --> C["chi: the only nonlinear step (degree 2)"]
C --> I["iota: add round constant (degree 1)"]
I --> O["Next-round state"]

Here is the load-bearing fact of the sponge's exposure, and it is worth deriving rather than asserting, because one word in it does real work.

One round is the composition $R = \iota \circ \chi \circ \pi \circ \rho \circ \theta$. Four of those five steps are affine, degree 1; only chi is nonlinear, degree 2. Composing a degree-2 map with affine maps leaves the degree at 2, so a single round has $\deg(R) = 2$.

Now use the composition bound for Boolean functions, $\deg(f \circ g) \le \deg(f) \cdot \deg(g)$, across $r$ rounds: $\deg(R^2) \le 2 \cdot 2 = 4$, $\deg(R^3) \le 2 \cdot 4 = 8$, and in general each extra round multiplies the bound by at most 2. The degree doubles per round:

$1 \;\to\; 2 \;\to\; 4 \;\to\; 8 \;\to\; \cdots \;\to\; 2^r, \qquad \text{so} \qquad \deg(\text{Keccak-}f^{\,r}) \le 2^r.$

You can watch chi's degree-2 structure force a higher-order derivative to vanish directly. A degree-$d$ function summed (XORed) over any affine cube of dimension $d+1$ gives zero, so summing degree-2 chi over any 3-dimensional cube must vanish.

// chi on a 5-bit row: y[i] = x[i] XOR ((NOT x[i+1]) AND x[i+2]), indices mod 5.
function chi(x) {
let y = 0;
for (let i = 0; i < 5; i++) {
  const xi  = (x >> i) & 1;
  const xi1 = (x >> ((i + 1) % 5)) & 1;
  const xi2 = (x >> ((i + 2) % 5)) & 1;
  const bit = xi ^ ((xi1 ^ 1) & xi2);   // one AND term => algebraic degree 2
  y |= (bit << i);
}
return y;
}

// A degree-d function has a vanishing (d+1)-th order derivative:
// summing it over ANY affine cube of dimension d+1 gives 0.
// chi has degree 2, so summing over ANY 3-dimensional cube must XOR to 0.
function sumOverCube(base, d1, d2, d3) {
let acc = 0;
for (let m = 0; m < 8; m++) {
  let x = base;
  if (m & 1) x ^= d1;
  if (m & 2) x ^= d2;
  if (m & 4) x ^= d3;
  acc ^= chi(x);
}
return acc;
}

console.log("chi(0b10110)          =", chi(0b10110));
console.log("3-cube sum (should 0) =", sumOverCube(0b00000, 0b00001, 0b00010, 0b00100));
console.log("3-cube sum (should 0) =", sumOverCube(0b10101, 0b00011, 0b01100, 0b10000));

One honesty note keeps this from overclaiming. The bound $\deg \le 2^r$ is the elementary degree-doubling law, and it is only informative at low round counts. Keccak-f acts on 1600 bits, where any permutation has degree at most 1599; $2^r$ already exceeds 1599 at $r = 11$, so the elementary bound says nothing about the full 24 rounds. The full-round result in Section 8 -- a zero-sum partition of size $2^{1590}$ -- rests instead on the tighter degree bound of Boura, Canteaut, and De Canniere, which stays below the state size even at 24 rounds ^[20]. The elementary law is what caps the cube attack at a handful of rounds; the refined bound is what lets the zero-sum reach all 24. Keep them separate and the whole SHA-3 frontier stays legible.

Now the two constructions can be laid side by side.

SHA-2 keeps the differential attack surface and the length-extension debt. The sponge trades both away for an algebraic surface whose degree grows only as $2^r$. The two functions do not sit on one strength axis, a bigger lock on the same door -- they expose different attack surfaces, so they would die different deaths. Construction, not digest size, selects the failure mode.

So the two constructions hand an attacker two different problems: thread a carry-laden differential path through 64 steps, or break the low-degree algebra of 24 rounds. How far has anyone actually gotten on each?

6. The Best Published Attacks, With Margins#

Here is the scoreboard. After thirty-five years of cryptanalysis, where exactly does the deepest published structural attack stop on each function, and how far is that from the full thing? This is the article's quantitative core, and it comes with a reading rule that matters more than any single number.

The yardstick never changes. A structural break must beat the generic birthday cost of $2^{n/2}$ on the full function. On full SHA-256 and full SHA3-256, no published attack does; the best-known collision attack on either full function is still the generic one at $2^{128}$ ^{[15, 21]}. Every record below is progress on the method, measured against a full function that remains untouched.

The SHA-2 record board#

Against SHA-2, one avenue has all the reach: automated differential characteristic search -- the mechanized descendant of Wang's hand construction, driven by SAT and SMT solvers and steered by mixed-integer linear programming. Reading its records needs one distinction.

The current records, all practical (a real colliding pair verified on a PC, not merely a sub-birthday estimate), come from Mendel, Nad, and Schlaffer in 2013 and from Li, Liu, and Wang in 2024 ^{[22, 15]}:

The 2024 paper set three firsts at once: the first practical semi-free-start collision for 39-step SHA-256 (improving the decade-old 38-step SFS record), the first practical free-start collision for 40-step SHA-224 where the prior best was a theoretic attack at time complexity $2^{110}$, and practical and theoretic collisions for reduced SHA-512 ^[15]. Impressive -- and then the same authors say where the road ends.

"The current advanced tool to search for SHA-2 characteristics has reached the bottleneck." -- Li, Liu, and Wang, on why the attack cannot climb past about 39 of 64 steps ^[15]

The modular-addition diffusion from Section 5 is exactly what makes longer characteristics effectively unfindable with today's encodings. The three record numbers for the same function are not a contradiction -- they are three different attacker games. From-IV is a true collision on the real hash. Semi-free-start hands the attacker the shared chaining value. Free-start additionally hands them a chosen difference in it. Each added freedom buys a few more steps of reach, which is why SHA-256 shows 31 (from-IV), 39 (SFS), and its sibling SHA-224 shows 40 (FS). The from-IV number is the one that measures the real hash.

The SHA-3 record board#

The sponge side has three attacks rather than one, and the next section is devoted to why they disagree about what "progress" means.

For the scoreboard, the reduced-round facts are these. Cube and cube-like algebraic attacks reach up to 9 of the 24 rounds in keyed Keccak modes, with the 6-round attacks fully practical on a desktop ^[21]. Internal-differential collision cryptanalysis holds the actual collision records: 5 of 24 rounds for SHA3-384 and 6 of 24 for SHAKE256 ^[23]. And a zero-sum distinguisher reaches all 24 rounds of the permutation while producing no collision at all ^[20] -- the row we unpack next.

The team that set the deepest keyed reach stated the bottom line directly.

"The security margin of Keccak remains large." -- Dinur, Morawiecki, Pieprzyk, Srebrny, and Straus, whose cube-attack-like cryptanalysis reached the deepest keyed rounds ^[21]

Now state the margins plainly, because they are the number a practitioner actually needs. For SHA-256, the deepest collision result leaves roughly 25 of 64 steps untouched in the semi-free-start model and about 33 untouched from the real IV. For a Keccak collision, roughly 18 of 24 rounds remain untouched. Those are not narrow escapes; they are the bulk of each function.

// A toy keyed function of public bits p0,p1 and secret key bits k0,k1.
// Algebraic degree 2 -- the product (p0 AND p1) is the only quadratic term.
function f(p0, p1, k0, k1) {
return ((p0 & p1) ^ (p1 & k0) ^ (p0 & k1) ^ k0) & 1;
}

// Cube over the single public variable p0: XOR f over p0 in {0,1}.
// The resulting "superpoly" is LINEAR in the key -- it equals p1 XOR k1.
function cubeSumOverP0(p1, k0, k1) {
return f(0, p1, k0, k1) ^ f(1, p1, k0, k1);
}

// The attacker cannot see the key. Say the hidden key is:
const K0 = 1, K1 = 0;

// Query with p1 = 0 and sum the cube: the quadratic term dies and k1 falls out.
const recovered = cubeSumOverP0(0, K0, K1);
console.log("cube superpoly at p1=0 recovers k1 =", recovered, "(true k1 =", K1, ")");

// The same reading discipline for any reduced-round headline:
function margin(reached, total, unit) {
return "reached " + reached + "/" + total + " " + unit +
       "  ->  " + (total - reached) + " " + unit + " still untouched";
}
console.log(margin(39, 64, "SHA-256 steps"));
console.log(margin(6, 24, "SHAKE256 rounds"));

One number on the SHA-3 side hides an argument, though. The deepest result of all -- the zero-sum -- reaches every one of Keccak's 24 rounds, and still breaks nothing. To see why, look at the three rival attacks on the sponge side by side.

7. The SHA-3 Fork the Thesis Holds Open#

SHA-2's story has one protagonist: differential collision search, with no rival of comparable reach. SHA-3's story has three, and they disagree about what the word "reach" even means. Pretending that one of them is the SHA-3 break would misrepresent the field, so this section keeps the fork open.

Method A: cube and cube-like attacks#

The cube attack, introduced by Itai Dinur and Adi Shamir in 2009, is the avenue the title of this article names the algebraic frontier, because it exploits the low degree that chi keeps small at low round counts ^[24].

The method is provably successful on random low-degree polynomials whenever the number of public variables exceeds $d + \log_d n$, and it runs in about $2^{d-1} n + n^2$ bit operations for degree $d$ over $n$ secret variables ^[24].

Against Keccak, Dinur, Morawiecki, Pieprzyk, Srebrny, and Straus reached up to 9 of the 24 rounds faster than exhaustive search, with the 6-round attacks fully practical ^[21]. But note precisely what it threatens: key recovery or forgery in keyed Keccak modes -- not a plain hash collision. The cube round counts come from keyed Keccak variants such as message authentication codes and the Keyak authenticated-encryption scheme, whose nominal round count is 12. In those modes a secret key exists to recover. Standard SHA3-256 hashing has no key, so the cube attack does not by itself produce a hash collision -- it is the deepest algebraic reach, in a different attack model. And because the degree doubles each round, the cube needed grows astronomically past a handful of rounds, which is exactly why it stalls at 9.

Method B: zero-sum distinguishers#

Take the same low-degree property but drop the key, and you get a statement about the raw permutation. Christina Boura, Anne Canteaut, and Christophe De Canniere used a refined bound on the degree of iterated permutations to build zero-sum partitions of size $2^{1590}$ for the full 24-round Keccak-f ^[20].

This is the deepest structural reach anyone has into Keccak -- it touches every round -- and it is also the least usable result in the subject. It distinguishes the permutation from an ideal one; it yields no collision, no preimage, nothing against the hash. Hold that paradox; the next section is built on it.

Method C: internal-differential collisions#

The record-holders work differently again -- and they are the avenue that produces the property that actually matters for a hash.

The line runs from Thomas Peyrin's generalized internal differentials in 2010, through Dinur, Dunkelman, and Shamir -- who produced actual collisions for 3-round Keccak, a 4-round Keccak-384 attack $2^{45}$ times faster than birthday, and collisions on 5 rounds of Keccak-256 ^[25] -- to Zhongyi Zhang, Chengan Hou, and Meicheng Liu, whose "probabilistic linearization" extended the records to 5 rounds of SHA3-384 and 6 of SHAKE256 ^[23]. This is the only avenue that delivers real collisions on the standardized instances.

Now put the three side by side. The decisive column is not "how many rounds" but "what property."

Third-party cryptanalysis of all three families is tracked publicly by the designers ^[26]. That middle row -- 24 rounds reached, nothing broken -- is not an accident of today's tooling. It is a provable wall, and understanding why forces us to the theoretical limits.

8. The Ideal, the Bounds, and the Distinguisher Trap#

Begin with the middle row from the last table, because it is the strangest fact in the subject. A zero-sum partition of size $2^{1590}$ reaches all 24 rounds of Keccak-f -- the deepest structural property anyone has ever proved about it -- and it yields no collision, no preimage, nothing usable against the hash ^[20]. How can the deepest result reach the whole function and still break nothing?

First, the wall that neither function's attackers have crossed. On the full SHA-256 and full SHA3-256, no published structural attack beats $2^{128}$ for a collision or $2^{256}$ for a preimage. Best-known equals generic on both, so the "beat the birthday bound" gap is not merely large -- it is open and uncrossed. Nobody has closed any of it on either full function ^{[1, 2]}. Everything in Section 6 is reduced-round evidence about how far away the break is.

Now the answer to the zero-sum paradox, which is a proof, not a hope.

Bertoni, Daemen, Peeters, and Van Assche proved in 2008 that a sponge calling a random permutation is indifferentiable from a random oracle: the success probability of any generic attack is at most its success probability against a true random oracle plus $N^2/2^{c-1}$, where $N$ is the number of queries to the permutation and $c$ is the capacity ^{[27, 19]}.

The strength of the claim is the clause "even when the distinguisher can query the permutation directly" -- a simulator can answer those permutation queries consistently with random-oracle outputs up to about $2^{c/2}$ work. Below $2^{c/2}$ in the hidden capacity, nothing separates the sponge from an ideal object.

That is what disarms the zero-sum. A zero-sum partition is a structural distinguisher of the permutation f alone -- a global property of how f maps XOR structure. The indifferentiability theorem runs in exactly one direction: any attack on the sponge F implies a distinguisher on f, but not the converse. Having a distinguisher on f does not hand you an attack on F. In the designers' own words:

"The existence of a structural distinguisher for f does not necessarily imply an attack or weakness in F." -- Bertoni, Daemen, Peeters, and Van Assche, on why a permutation property need not be a hash break ^[19]

Concretely, a collision requires steering the rate bits of two different messages so that their squeezed outputs coincide across the hidden capacity. The zero-sum gives an attacker no such steering: it certifies a global XOR property of the permutation, not a way to aim two chosen inputs at one output through the capacity. So it lies outside the class of exploitable structure that indifferentiability rules out, and a distinguisher whose success probability is zero below $2^{c/2}$, in the designers' phrase, "forms no threat" ^[19].

A permutation distinguisher is not a hash break. "Reaches all 24 rounds" and "produces a collision" are provably different statements, separated by the capacity's $2^{c/2}$ indifferentiability margin -- not merely by the current state of tooling. Depth of reach into the permutation is not nearness to a break of the hash. The capacity stands between them by design, and the standing between is a theorem.

Two more limits complete the picture, one on each construction. On the sponge side, the full-round zero-sum exists only because of the refined degree bound, not the elementary one. Recall from Section 5 that the elementary law $\deg \le 2^r$ goes vacuous by round 11 against a 1600-bit state. The 24-round zero-sum instead rests on Boura, Canteaut, and De Canniere's tighter bound for permutations whose nonlinear layer is parallel small S-boxes, which stays below the state size all the way to round 24 ^[20]. The elementary law caps the cube attack; the refined law powers the distinguisher. On the Merkle-Damgard side, length extension is not a bug that a better implementation could remove -- it is a provable inevitability of the untruncated construction. Because the SHA-2 digest is the whole final chaining value, anyone with $H(m)$ and $|m|$ can resume the iteration, full stop ^[5]. The only cures are to stop emitting the whole state (the sponge), hide enough of it (sufficient truncation), or wrap the hash (HMAC).

So the limits cut both ways. The sponge is closer to the ideal object -- indifferentiable up to the capacity, no length extension -- while SHA-2 is closer to the ideal margin in practice, with the bulk of its steps untouched by any differential path. Neither is anywhere near falling. One scope marker remains, because readers always ask about it.

The limits leave exactly one question standing: if neither function is close to falling, where would the next round of progress even come from?

9. Where the Next Round Would Come From#

If either function is ever broken, the break will arrive through one of a small, nameable set of open problems. Naming them turns you from spectator into forecaster.

flowchart TD
Q["Where would a break come from?"] --> A["SHA-2: differential search"]
Q --> B["SHA-3: three avenues"]
A --> A1["OP-1: past ~40 of 64 steps? Stalled at 39"]
B --> B1["Cube: 9 of 24, keyed only"]
B --> B2["Internal-differential: 6 of 24 collisions"]
B --> B3["Zero-sum: 24 of 24, distinguisher only"]
B2 --> OP2["OP-2: close the ~18-round gap?"]
B3 --> OP4["OP-4: cross the capacity barrier?"]
A1 --> OP3["OP-3: beat 2^128 on a full function, THE break, none known"]
OP2 --> OP3
OP4 --> OP3

OP-1: Can differential characteristic search push SHA-256 past about 40 steps? The full-function margin depends entirely on how far this single leading avenue can climb, and the 2024 record paper reports the tooling "has reached the bottleneck" -- modular-addition diffusion makes longer characteristics effectively unfindable with current encodings. Whether that is a fundamental barrier or an artifact of today's solvers is itself open ^[15].

OP-2: Can any SHA-3 avenue close the roughly 18-round gap to a full-Keccak collision? The best collision reach is 6 of 24 rounds, and the two leading avenues advance a round or two per decade, neither clearly out-reaching the other on its target property ^{[23, 21]}.

OP-3: Is there any structural attack that beats the birthday bound on either full family? This is the break -- and today the answer is a clean no. Best-known equals generic on both full functions; everything else in this article is reduced-round evidence about how far away this remains ^{[1, 2]}.

OP-4: Why is the permutation-distinguisher / hash-collision divide so hard to cross? The deepest reach into Keccak-f, the 24-round zero-sum, currently yields nothing usable against the hash. Section 8 argued the reason is structural: indifferentiability makes the capacity a genuine barrier, not merely a reduction nobody has found yet ^{[20, 27]}.

None of these problems is close to solved -- which is exactly why the practical answer to "what should I ship?" is calm and specific.

10. What the Margins Mean on Monday Morning#

So: should you change anything you shipped last week? Almost certainly not -- but there is exactly one structural gotcha worth ten minutes of your attention.

Start with the reassurance. Both full functions are sound for their advertised properties. Every record in Section 6 is reduced-round; 39 of 64 steps of SHA-256 and 6 of 24 rounds of SHAKE256 do not threaten the full functions, which remain safe for collision, preimage, and second-preimage resistance ^{[15, 23]}. Nothing in this article is a reason to rip out SHA-256.

The one gotcha is length extension, and it is a property of the construction, not a defect to be patched. If you ever compute a keyed digest as $H(\text{secret} \,\|\, \text{message})$ with a plain Merkle-Damgard hash and treat it as a MAC, an attacker who sees that digest can forge a valid one for a longer message without knowing the secret.

The decision guide fits in one table.

The mechanism is worth seeing once, because it explains why "just hash the secret with the message" fails.

sequenceDiagram
participant D as Defender
participant A as Attacker
D->>D: hash secret then message into digest t
D->>A: publish digest t and the message length
Note over A: attacker never learns the secret
A->>A: resume internal state from t
A->>A: append glue padding then an evil suffix
A->>D: send forged message plus a new digest
Note over D: the new digest verifies as a valid hash

// A toy Merkle-Damgard hash where the state IS the digest.
// This shows the STRUCTURE of length extension, not real SHA-256 output.
function compress(state, ch) {
// stand-in mixing; a real f is Davies-Meyer over a block cipher
return (((state << 5) ^ (state >>> 2) ^ ch) >>> 0);
}
function hash(state, message) {
for (let i = 0; i < message.length; i++) {
  state = compress(state, message.charCodeAt(i));
}
return state >>> 0;
}

const IV = 0x9e3779b9;

// Defender hashes a secret-prefixed message and publishes only the digest.
const secretPrefixed = "SECRET-user=guest";
const digest = hash(IV, secretPrefixed);

// Attacker never learns the secret, but the digest IS the state,
// so they resume from it and append a chosen suffix.
const suffix = "&admin=true";
const forged = hash(digest, suffix);

// In a real hash the attacker also splices in the glue padding,
// producing H(m || pad || suffix). Here (no padding) it lands exactly:
const legitimate = hash(IV, secretPrefixed + suffix);

console.log("forged   =", forged);
console.log("expected =", legitimate);
console.log("match    =", forged === legitimate);

A worked forgery for SHA-256 and SHA-512 is exactly what the hash_extender tool automates ^[29]. But truncation is where the naive intuition "any truncation stops extension" quietly fails, and SHA-224 is the trap.

Two smaller notes round out the practical picture. First, a naming hazard that bites developers. Ethereum's "Keccak-256" is not SHA3-256. Ethereum froze the original Keccak submission before FIPS 202 added its domain-separation padding, so the two functions append different bits before permuting and therefore produce different digests on the same input ^[2]. Code that assumes they are interchangeable will compute the wrong hash. This is a padding difference, not a security difference -- but it is a real bug source. Second, the quantum question again: if you are hedging against a future quantum adversary, the move is a longer digest -- SHA-384, SHA-512, or SHAKE256 at a longer output -- not a migration to a different construction, because Grover is a generic speedup that a bigger output absorbs ^[18].

Every one of these recommendations is a corollary of a single idea -- the construction decides the failure mode. A few common misconceptions fall out of the same idea, and they are worth clearing up directly.

11. Misconceptions the Structural View Corrects#

Six questions whose honest answers are all the same idea in disguise: the construction, not the digest size, decides the failure mode.

Every answer traces back to the same sentence. It is worth stating that sentence one last time, with all the evidence now behind it.

12. The Construction Writes the Obituary#

We opened with a claim that should have sounded like a bluff: that we could describe, mechanically, how each of these functions would fall before either has ever fallen. Now the description is complete, and the two obituaries share nothing but a date that has not arrived.

SHA-2 would die the way MD5 and SHA-1 died -- a Wang-style differential collision threaded through its compression function, deterministic in the early steps and cheap through the tail. It survives today only because its carry-laden schedule keeps that path unfindable past about 39 of 64 steps, and it carries length extension as a structural debt from the 1989 bargain ^[15].

SHA-3 would die a different death entirely, on the algebra of a single degree-2 step: the cube frontier that stalls at 9 keyed rounds, and the internal-differential collisions that hold the records at 6 ^[23]. Its deepest known property reaches all 24 rounds and still breaks nothing, because the capacity provably stands between a permutation distinguisher and a hash collision.

And the margins are the payoff. Roughly 25 to 33 of SHA-256's 64 steps, and roughly 18 of Keccak's 24 rounds, remain entirely untouched after thirty-five years of the best cryptanalysis in the world ^{[15, 23, 21]}. The construction writes the obituary; the cryptanalysis only fills in the date, and the date is nowhere close.

The construction writes the obituary. A hash does not die at its digest size -- it dies where its construction is thinnest, and no two constructions are thin in the same place.

That is the through-line, and it hands off cleanly. How these functions have actually failed people in the field -- Flame's rogue certificate, the long death of SHA-1 in the browser -- is a different kind of story, told by the empirical sibling to this piece, "How the Hash Functions Broke in Real Life."

And it points forward: if a hash's construction predicts its structural death, the natural next question for this series is whether the same is true for the ciphers and signature schemes still to come -- whether, for every primitive, the shape of the thing already names the way it would break.