Hash Collisions and Weak Preimages — truncated tags and broken functions that fall to brute force or known tooling

A collision is two distinct inputs that hash to the same digest; a preimage is a single input matching a target digest. In CTFs neither needs a real cryptanalytic break most of the time — the hash is *truncated*, the input space is *tiny or structured*, or the function is a *known-broken* one (MD5/SHA-1) with public collision tooling, so brute force or an off-the-shelf tool wins in practical time.

The signal that betrays it

- The tag/digest is short. A handful of bytes, a 32- or 64-bit "checksum", or a hash deliberately truncated (hashlib.sha256(x).digest()[:k]) — the shorter the output, the sooner a collision is reachable. Check feasibility with the birthday bound (see Birthday Attack — the square-root speedup that governs any collision search) before writing any code: for an m-bit tag, expect a hit near 2^(m/2) tries. - The challenge phrasing gives it away: "find two files/messages with the same hash", "forge a token whose hash equals X", "the server only checks the first N bytes of the digest". - The input space is small or heavily constrained — a short PIN, a filename from a known dictionary, a value with a fixed prefix/suffix — so a direct preimage search over that space (not the whole digest space) is what's actually cheap. - The hash function itself is MD5 or SHA-1 and the task hands you two *attacker-chosen, semantically different* prefixes to make collide (rogue cert / good-file-vs-evil-file pattern) — that's a stronger, distinct case; route to Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal instead of reimplementing anything here. - Type-juggling smell in a web/PHP context: loose comparison (==) between a stored hash and a user-supplied one, or a digest displayed/logged as a bare string that could be misread as a number — that's not a cryptographic collision at all, it's PHP's "magic hash" bug (see below), but it gets confused with real hash collisions often enough to flag here.

How it's exploited

1. Truncated hash → birthday brute force. Confirm the *effective* output width first (truncation, not nominal digest size, is what matters — see Birthday Attack — the square-root speedup that governs any collision search for the general bound), then just search: ``python import hashlib seen = {} while True: x = random_input() h = hashlib.sha256(x).digest()[:k] # k-byte truncation is the real search space if h in seen and seen[h] != x: print("collision:", seen[h], x); break seen[h] = x ` A dict-based search like this is fine up to roughly 2^32`-ish digests on ordinary hardware; past that, the memory-light Floyd/Brent cycle-detection variant in Birthday Attack — the square-root speedup that governs any collision search is the move, not a bigger dict.

2. Small/structured preimage → enumerate directly. If the input space is the actual constraint (a 6-digit PIN, a dictionary word, a fixed-format token), don't think in terms of 2^(hash bits) at all — enumerate the constrained space directly and hash-check each candidate. The size of the *input* space, not the digest space, sets the cost here; this is the case people most often over-estimate as "infeasible" by reasoning about digest size instead of input size.

3. Chosen-prefix collisions (MD5/SHA-1) → use proven tooling, don't reimplement. This is a distinct, harder primitive from a same-prefix birthday collision — see Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal for the full workflow. The field-tested rule: never attempt to hand-roll differential cryptanalysis under time pressure; hashclash (cpc.sh) for MD5 is the practical default, SHA-1 chosen-prefix tooling (sha-mbles) exists but is expensive enough that a CTF is more likely to want MD5.

4. Magic-hash / type-juggling bypass. Distinct mechanism, same "==" symptom as a collision check: in PHP, a digest whose hex string looks like 0e followed only by digits (e.g. md5("240610708") → 0e462097431906509019562988736854) is parsed by loose (==) comparison as scientific notation for 0, so any two such "magic hashes" compare equal to each other and to the literal 0. If a login/token check uses == against an MD5/SHA1 hex digest, search a wordlist (or brute force short inputs) for one whose digest matches the ^0e[0-9]+$ pattern — no actual hash collision with the target is needed, you just need *your own* digest to also start with 0e followed only by digits. Known worked example pairs exist for MD5 (e.g. 240610708 and QNKCDZO both hash to 0e... values) — treat those as reference points to test your own harness against, not as reusable payloads for a real target.

Overall priority rule (field-tested): pick the cheapest axis before brute forcing anything. Check truncation width, then input-space size, then whether the function is a known-broken one with existing tooling — in that order — before spending compute on raw search.

What does NOT work

- Running a birthday-style random search against a full, untruncated modern hash (SHA-256, SHA-3) expecting a collision. At 128-bit effective security the 2^(n/2) bound is astronomically out of reach for a CTF timebox — if the challenge doesn't truncate or otherwise weaken the function, the vulnerability is elsewhere (protocol misuse, not the primitive itself). Don't burn compute confirming the obvious. - Reimplementing MD5/SHA-1 differential cryptanalysis from scratch for a chosen-prefix task. This is exactly the mistake the Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal tooling exists to avoid — hashclash is proven, fast, and the field-tested default; hand-rolling the near-collision/differential-block search is a multi-week research project, not a CTF-timeboxed one. - Confusing a truncated-tag birthday collision with a preimage requirement. If the check is "your hash must equal *this specific* target value" rather than "any two values you control must match", the birthday speedup does not apply — that's a preimage search at the *full* cost of the constrained space, not 2^(n/2). Re-read the challenge check carefully before picking the attack. - Assuming a PHP `==` magic-hash bypass is a real cryptographic collision. It is a parser/type-coercion bug specific to loose comparison against numeric-looking strings, not a weakness in the hash function. It doesn't generalize past PHP's == semantics, and PHP 8's saner string-to-number comparison rules close it — check the PHP version/target language before reaching for this technique. - Trying to brute-force a preimage by iterating the full digest space instead of the actual constrained input space. When the input is small/structured (a PIN, a dictionary word), the tractable search is over inputs, not over 2^(digest bits) outputs — conflating the two wastes the entire time budget on an intractable search when a trivial one was available.

Related

Birthday Attack — the square-root speedup that governs any collision search Chosen-Prefix Collision — forcing two attacker-chosen, meaningfully different prefixes to hash equal Hash Length Extension — forge H(secret‖msg‖extra) from a digest alone 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 Sponge Construction — why length-extension does NOT work on SHA-3/Keccak Encoding and Decoding Layers — peel base64/hex/URL/compression first or you attack the wrong plaintext Cryptanalysis Methodology — classify the family before you reach for an attack