Sponge Construction — why length-extension does NOT work on SHA-3/Keccak

SHA-3/Keccak, SHAKE, and Ascon all build on a b = r + c bit state (rate r, capacity c) that alternates ABSORB (XOR an r-bit block in, apply permutation f) and SQUEEZE (read r bits out, apply f, repeat) — and because the capacity portion of the state is never written to output, generic security sits at roughly c/2 bits and the classic Merkle–Damgård length-extension trick simply has no state to resume from.

The signal that gives it away

- The hash in play is SHA-3-256/384/512, SHAKE128/256, Keccak, or Ascon — anything described as "sponge", or with visible "rate/capacity/absorb/squeeze" terminology in the challenge source. - A challenge *tempts* you toward Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone (a naive-MAC pattern H(secret ‖ msg), a known (msg, tag) pair, a goal of appending privileged data) but the digest function is SHA-3/SHAKE/Keccak, not MD5/SHA-1/SHA-2 — that attack fails here, full stop. Recognizing *which* hash family you're looking at is the whole signal; five seconds spent confirming this saves an hour of debugging an exploit that can never work. - The challenge instead hands you a custom sponge with a deliberately small capacity (e.g. c set to something like 32-64 bits while r is large) — that's not a length-extension setup, it's an invitation to a Birthday Attack — the square-root speedup that governs any collision search on collisions/preimages, because security has been engineered down to ~2^(c/2). - The challenge exposes a duplex/AEAD-style API (interleaved absorb of associated data + squeeze of ciphertext/tag, or a nonce that gets reused across sessions) — that's a different exploitation path than length-extension, closer in flavor to stream-cipher keystream reuse. - You're handed a SHAKE128/256 output and the challenge cares about squeezing *more* bytes than the "obvious" digest length — that's a hint you're meant to use it as an XOF, not a fixed-length hash.

How it's exploited

Confirm the primitive first, then route to the actual weakness — the sponge itself is not the target, what surrounds it is:

1. Rule out state-resumption attacks immediately once you see SHA-3/SHAKE/Keccak/Ascon. The digest never exposes the full b-bit internal state — only r bits of it are ever written to output at any point, and the c-bit capacity stays hidden for the life of the computation. There is no "load the digest as the internal state" move like Merkle–Damgård Construction — the digest IS the internal state permits. If a naive-MAC pattern (H(secret ‖ msg)) is built on SHA-3 instead of MD5/SHA-1/SHA-2, do not spend time on padding reconstruction or hashpumpy-style tooling — pivot to a different angle: oracle/timing leaks, key reuse across messages, or a weak/predictable secret. 2. If it's a custom sponge, audit the capacity first. c is the actual security parameter (not the digest length, which is a squeeze-phase choice). A standards-compliant sponge with generic security bound N²/2^(c-1) behaves like a random oracle only against attackers making N < 2^(c/2) calls to the permutation — so a deliberately small c (say c = 32 or c = 64 in a homebrew scheme) collapses collision/preimage resistance to something brute-forceable, and that's a straight Birthday Attack — the square-root speedup that governs any collision search, not a sponge-specific trick. 3. If the hash is used as an XOF (SHAKE), exploit the arbitrary-length squeeze rather than assuming a fixed digest. SHAKE128/SHAKE256 let you request as many output bytes as you want: ``python import hashlib out = hashlib.shake_128(data).digest(64) # squeeze 64 bytes, not the "usual" fixed size `` If a challenge's check only compares a truncated prefix of a SHAKE output, or derives multiple keys/values from the same absorbed input at different squeeze lengths, that's the actual exploitable surface — not the sponge's internal permutation. 4. For duplex/AEAD misuse, reason about absorbed/squeezed positions the way you would about stream-cipher keystream reuse. A reused nonce or a message replayed into the same duplex state can put predictable data at a squeezed position, effectively producing a "keystream" you can XOR out — same underlying logic as Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge, just wrapped in sponge terminology. 5. When unsure which attacks transfer from Merkle–Damgård designs, compare the two constructions structurally rather than guessing. Merkle–Damgård Construction — the digest IS the internal state chains a compression function where the digest *is* the last internal state — that's the single fact every MD attack (length-extension, some multicollision/fixed-point tricks) leans on. The sponge's absorb/squeeze split with a hidden capacity is the specific design choice that breaks that assumption; walk through *why* an attack needs full-state visibility before assuming it does or doesn't apply to a sponge.

What does NOT work

- Length-extension against SHA-3/SHAKE/Keccak. This is the single most common wasted hour on this family: there is no raw post-secret internal state to resume hashing from, because the capacity bits behind any squeeze are never revealed — the security argument (N < 2^(c/2) calls behave like a random oracle) depends specifically on that. No amount of padding-reconstruction cleverness fixes this; the primitive structurally forecloses it. If you catch yourself reaching for hashpumpy or manual MD-style padding math against a SHA-3/Keccak digest, stop and look for a different bug class instead. - Treating the digest length as the security parameter. SHA-3-256 truncates its squeeze to 256 bits, but its capacity is 512 bits (rate 1088, b=1600 for the standard permutation) — the *output* length and the *security* level are set independently by r/c, unlike a naive "digest bits = security bits" assumption. Don't estimate collision resistance from the advertised hash name alone in a custom/modified sponge; check what c the challenge actually configured. - Assuming squeezing further reveals the pre-permutation state. Each additional r-bit block you squeeze out of a XOF comes after another application of f — you can't reconstruct earlier squeezed blocks' relationship to the hidden capacity by squeezing more, and squeezing more bytes doesn't leak anything about the capacity itself; it only gives you more rate-bits of *output*, not state. - Assuming a small-rate, large-capacity sponge is the vulnerable configuration. It's the opposite: shrinking capacity is what weakens a sponge (security ≈ c/2). A challenge that looks "unusual" because it squeezes slowly (small r) is not thereby weaker — check c, not r, before concluding there's a shortcut.

Related

Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone Merkle–Damgård Construction — the digest IS the internal state Birthday Attack — the square-root speedup that governs any collision search Stream-Cipher Keystream Reuse — the umbrella break behind every reused-keystream challenge HMAC Fundamentals — the nested MAC that tells you when to STOP trying length-extension