Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions

In an iterated Merkle-Damgard hash, finding 2^t messages that ALL share one digest costs only ~t single-block collision searches, not the ~2^((t-1)n/2) you'd expect from brute-forcing a 2^t-way collision directly — because each stage's collision is found starting from the CURRENT chaining state, and any combination of the t binary choices lands on the same final state.

The signal that gives it away

- The target is a classic iterated/Merkle-Damgard hash (Merkle–Damgård Construction — the digest IS the internal state) — MD5, SHA-1, SHA-2 all qualify structurally. - The challenge wants many colliding messages, not just one pair — "produce N messages with the same hash", "defeat a hash-based proof-of-uniqueness/proof-of-distinctness check", "show the hash accepts exponentially many preimages of a value cheaply". - The design under attack concatenates or cascades two independent hashes, H1(m) || H2(m), on the assumption that the combination is stronger than either half. That assumption is exactly what this technique breaks — it's the signature "gotcha" scenario for this page. - You've already ruled out that a single ordinary collision (Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling, Birthday Attack — the square-root speedup that governs any collision search) is what's being asked for — the challenge specifically wants a *set* of colliding inputs, or wants you to defeat a construction that combines multiple hashes.

How it's exploited

Chain t independent single-block collisions, each starting from the previous stage's output state — never restart from the same fixed state each time.

``python def collision_block(state): # birthday-search a pair colliding from state seen = {} while True: b = os.urandom(BLOCK) s = f(state, b) # one compression step if s in seen: return seen[s], b, s # (b0, b1) both take state to the same s seen[s] = b ``

1. Start from the hash's IV (or whatever chaining state the challenge fixes). Run collision_block to get a pair of blocks (b_1^0, b_1^1) that both drive the state from IV to the same next state s_1. 2. Repeat from s_1 to get (b_2^0, b_2^1) landing on s_2. Continue for t stages. 3. Now every one of the `2^t` messages formed by picking one block from each pair — b_1^{c_1} || b_2^{c_2} || ... || b_t^{c_t} for any bit string c — drives the chaining value through the exact same sequence of intermediate states and lands on the same final digest. You built 2^t colliding messages with only t birthday searches, each costing Θ(2^(n/2)) (Joux's original bound: expected complexity Θ(r·2^(n/2)) for a 2^r-multicollision — dramatically cheaper than the naive expectation for a 2^r-way collision found by brute birthday search). 4. Break a cascaded/concatenated hash `H1(m) || H2(m))`: build a 2^(n/2)-way multicollision in H1 alone (cost ~(n/2)·2^(n/2), using the chaining trick above with t = n/2 stages). You now have 2^(n/2) distinct messages that all share ONE H1 digest. Birthday-search *inside that set* (Birthday Attack — the square-root speedup that governs any collision search) for a pair that also collides under H2 — with 2^(n/2) candidates, an H2 collision among them is expected. Total cost stays polynomial-ish in n beyond the 2^(n/2) set-building step, instead of the 2^n-ish cost the concatenation was supposed to force. This is the concrete mechanism behind Joux's headline result: concatenating two Merkle-Damgard hashes is barely stronger than the weaker of the two, not their combined strength. 5. In CTF practice, you rarely need to hand-derive the complexity bound — recognizing "iterated hash + wants many colliding messages, or wants a concatenated-hash break" is enough to reach for the chained-collision-block construction directly.

Related

Merkle–Damgård Construction — the digest IS the internal state Birthday Attack — the square-root speedup that governs any collision search Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling

What does NOT work

- Searching for each stage's collision from the SAME fixed starting state instead of the state reached by the previous stage. That collapses back to finding one ordinary collision repeatedly — it does not compose into an exponential multicollision. The entire trick is that stage i+1's search starts from s_i, the state the previous stage's pair both already reach. - Treating the multicollision as giving you an attacker-CHOSEN target digest, or two attacker-meaningful distinct documents. It doesn't. The random birthday search lands on whatever digest it happens to land on, and every message in the resulting 2^t family is built from the SAME random collision blocks — you don't get to pick two independently meaningful payloads (a "good" file vs a "rogue" file) this way. That's a different, harder problem — see Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal — which needs proven differential tooling, not this chaining trick. - Expecting this to break a single hash's own collision resistance cheaper than an ordinary birthday search. It doesn't — the per-stage cost is still one full Θ(2^(n/2)) birthday search; the payoff of the technique is specifically in the *cascaded/concatenated-hash* scenario (or wherever you need MANY colliding messages instead of one pair), not in beating one hash's bound. - Applying it directly against HMAC or a sponge-based hash (SHA-3/Keccak). The construction needs an attacker-controlled entry point into the FULL chaining state that carries block-to-block, which is exactly the Merkle-Damgard property. HMAC's nested key wrapping means the attacker doesn't control the state the message blocks actually chain from; a sponge never exposes its full internal state as the visible output (only the "rate" portion is), so the same chaining trick has no equivalent handle to grab. Field-tested, not yet cross-referenced to a public source for the sponge case specifically — treat as a strong prior, not a proven impossibility, if a challenge ever puts a sponge hash in front of you. - Assuming a small number of stages `t` gets you an unreasonably large multicollision for free. Each stage still costs a real birthday search (Θ(2^(n/2)), not free); the win is t searches for 2^t messages, not zero searches for infinite messages. Budget t searches, not t seconds.