Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal

Given two prefixes P1 and P2 that the ATTACKER picked freely (not just two random inputs, and not two blobs sharing a common head), find suffixes S1, S2 such that H(P1||S1) = H(P2||S2) — this is the collision class that actually breaks real formats, because the meaningful, semantically-differing content (a "good" cert vs a "rogue" one, a benign PDF vs a malicious one) is fixed in advance and only the padding suffix is under attacker control. Demonstrated practically against MD5 (rogue CA certificate, CRYPTO 2009) and SHA-1 (SHAmbles, 2020).

The signal that gives it away

- The challenge hands you (or asks you to produce) two semantically different documents/headers/certificates that must end up with the identical hash — not two arbitrary random-looking blobs. If the two things you need to collide already share a long common prefix and only differ near the end, that's the weaker *identical-prefix* case (Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling), not this one. - Framing like "forge a certificate", "make a good file and an evil file with the same hash", "the verifier only checks the hash of the uploaded document, not its content" — anywhere the difference between the two payloads has to be attacker-meaningful (different issuer field, different executable behavior, different visible content), not incidental. - The hash in play is MD5 or SHA-1. Both are structurally broken at the differential-cryptanalysis level (Merkle-Damgard, see Merkle–Damgård Construction — the digest IS the internal state) and have published, tooled attacks. A chosen-prefix claim against SHA-256/SHA-3 is not something you reimplement in a CTF timeframe — no practical break of that shape is public. - You've already ruled out — or the challenge explicitly rules out — that identical-prefix / truncated-hash brute force (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 enough, because the two prefixes genuinely diverge from byte zero.

How to exploit it

Don't reimplement the cryptanalysis. Use proven tooling.

- MD5 is the practical default: [hashclash](https://github.com/cr-marcstevens/hashclash)'s cpc.sh script takes two arbitrary prefix files and produces colliding suffix blocks for both, no differential-path math required on your end. ``bash # birthday/near-collision phase aligns the internal chaining state of the two # prefixes, then differential ("collision") blocks merge them: ./cpc.sh prefix1.bin prefix2.bin # -> prefix1.bin.coll, prefix2.bin.coll ` Field detail worth knowing before you run it: hashclash expects each prefix file's length to be a multiple of 64 bytes (optionally plus 1–3 bytes, or a small multiple of 4), which it uses as forced message words in the first near-collision block — pad your prefixes to that boundary yourself rather than debugging why the tool's output looks wrong. The published construction behind it (Stevens et al., CRYPTO 2009) gets down to about three pairs of near-collision blocks and roughly 2^49` MD5 compression calls, and was demonstrated end-to-end by forging a rogue CA certificate signed as if it were a legitimate one. - SHA-1 has a real chosen-prefix break too — SHAmbles (Leurent & Peyrin, 2020), the follow-up to the 2017 SHAttered identical-prefix result, used to forge colliding PGP keys with different user IDs. Field note, confirmed by the public cost estimates: this is usually out of CTF scope. SHAmbles-class attacks are dramatically more expensive than the MD5 case (originally estimated in the tens of thousands of dollars of cloud GPU time in the paper) — if the challenge gives you a choice of which hash to target, or the flag is achievable via MD5 anywhere in the pipeline, prefer MD5 every time. - After alignment, append a common suffix to BOTH files. Because Merkle-Damgard finalization only depends on the current chaining state (see Merkle–Damgård Construction — the digest IS the internal state), once the two colliding blocks bring both inputs to the *same* internal state, anything appended afterward — identical bytes — keeps the digests equal. This is what lets you attach a shared trailer (the rest of a cert, the rest of a PDF) without touching the collision machinery again. - Exploit format leniency to hide the differing bytes. The collision blocks themselves are unstructured near-random data; you need a place in the target format that tolerates opaque bytes without altering what a viewer/verifier considers the "meaning" of the file — comments, length-prefixed blobs, unused PDF objects, image/JPEG segments a renderer skips, an X.509 certificate's serial number or validity-period fields. The rogue-CA demonstration hid the divergence inside fields a CA would populate predictably (serial number, validity period), which is exactly why those had to be *predicted*, not just chosen.

What does NOT work

- Reimplementing the differential path search yourself. This is published, hard cryptanalysis (finding the near-collision blocks is the actual research contribution) — there is no shortcut version worth hand-rolling under CTF time pressure. Always reach for hashclash (MD5) or the SHAmbles tooling (SHA-1) rather than trying to rediscover the attack. - Treating this as the same problem as an identical-prefix collision. SHAttered-style identical-prefix collisions need the two inputs to already share a long common prefix and only search for a divergence near the end — useless when you need two *independently meaningful* documents (different headers, different semantics) from byte zero. If the two payloads must genuinely differ from the start, identical-prefix tooling and reasoning (Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling) won't get you there; you need the chosen-prefix construction specifically. - Mixing MD5 tooling with SHA-1 targets or vice versa. The differential paths, block layout, and cost model are specific to each hash's internal round structure — hashclash's MD5 machinery does not transfer to SHA-1 targets and the reverse is equally true. - Assuming the target format has a spot to hide arbitrary bytes. The whole attack depends on format leniency: a parser/verifier that ignores or under-checks some region (a comment, an unused field, a padding block). If the format canonicalizes input or strictly validates every byte's semantics before hashing, the collision blocks either get stripped or make the file invalid — confirm a genuine hiding spot exists before investing compute in generating the collision. - Reaching for chosen-prefix collisions against SHA-256, SHA-3, or other modern hashes. No practical collision attack of this shape is public against full-round SHA-256; and SHA-3's sponge design structurally resists the length-extension/state-leak family of tricks that chosen-prefix constructions build on for Merkle-Damgard hashes (see Sponge Construction — why length-extension does NOT work on SHA-3/Keccak) — if the challenge names a modern hash, this technique is the wrong direction entirely. - Ignoring the compute budget on the SHA-1 side. Unlike MD5 (roughly a day or so of compute is commonly cited for hashclash runs), a SHA-1 chosen-prefix run is a real expense in time and money. Don't commit to the SHA-1 path inside a CTF without first checking whether the challenge actually forces it, or whether an MD5-based route to the same flag exists.

Related

Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling Merkle–Damgård Construction — the digest IS the internal state Multicollision Attack — Joux's trick: 2^t colliding messages for the price of t single-block collisions Birthday Attack — the square-root speedup that governs any collision search Sponge Construction — why length-extension does NOT work on SHA-3/Keccak