Breaking MD5 with Collision Attacks

Breaking MD5 with Collision Attacks

Introduction

A hash function’s job is to make finding two inputs with the same output infeasible. The MD5 guide covers the algorithm and calls it broken. This post shows two different ways to break it, and they are not the same attack.

The first is generic. Any hash function, no matter how well designed, falls to a birthday attack eventually, since a large enough set of random outputs is bound to repeat. This post runs that attack for real, live, against real MD5.

The second is specific to MD5. In 2004, Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu published a way to find full 128-bit MD5 collisions. It exploits an actual structural weakness in MD5’s compression function, at a cost far below what the birthday bound alone would predict. This post verifies their real, published collision directly, computing both hashes live rather than asking you to trust the claim.

Table of Contents

• Two Different Attacks
• The Birthday Attack
• A Worked Example
• Wang’s Real Collision
• Python Implementation
• Interactive Visualizer
• Birthday Bound vs. Wang’s Attack
• Limitations of This Post
• FAQ
• References

Two Different Attacks

It’s easy to conflate “MD5 is broken” with “any two inputs can be made to collide easily.” Neither attack here supports that stronger claim, and the difference matters.

The birthday attack works against any hash function, including a perfect one. It says nothing about MD5’s internals. It just exploits the fact that comparing many random outputs against each other, rather than against one fixed target, needs far fewer tries than intuition suggests. It finds collisions in a truncated digest, a small number of output bits, not the full 128.

Wang’s attack is specific to MD5. It exploits a real flaw in how MD5’s compression function propagates certain bit differences across its 64 rounds. It finds a genuine full 128-bit collision, at a cost dramatically below the roughly 2⁶⁴ operations a birthday attack against the full digest would need.

Both of these matter. The birthday attack is why every hash function needs a large output. Wang’s attack is why MD5 specifically needed replacing, years before its output size alone would have been the problem.

The Birthday Attack

Suppose you hash random messages and only look at the first N bits of each digest. How many messages do you need before two of them share those N bits?

Not 2ᴺ, despite that being how many distinct N-bit values exist. You’re not checking each new hash against one fixed target. You’re checking it against every hash you’ve already seen. That’s the birthday paradox: with 23 random people, there’s a better-than-even chance two share a birthday, even though there are 365 possible birthdays. The number of pairs you’re implicitly checking grows much faster than the number of people.

For an N-bit space, the expected number of tries before the first collision is:

expected tries ≈ 1.25 × √(2ᴺ)

For N = 32, that’s about 82,000 tries, not 4.3 billion. Doubling N roughly quadruples the expected tries, since the square root of 2ᴺ scales that way. This is why cryptographic hash outputs need to be twice as many bits as the attack you’re defending against actually costs. A 128-bit digest doesn’t give 128 bits of collision resistance. It gives 64, because of exactly this attack.

The Attack, Step by Step

1. Pick a truncation width N. This is the number of leading bits of the digest you’ll compare.
2. Hash a random message. Keep its full digest, but only the top N bits matter for comparison.
3. Check a table. Look up those N bits against a table of every truncated digest already seen. If it’s a fresh value, store it and try another message.
4. Stop at the first repeat. The two different messages producing that repeat are a genuine collision in the truncated digest, found in roughly 1.25 × √(2ᴺ) tries.

Nothing here is specific to MD5. The same attack, with the same expected try count, works identically against SHA-256 truncated to N bits. That’s the point: this is a property of hash functions in general, not a flaw in any one of them.

A Worked Example

The visualizer’s default settings truncate to 24 bits and seed the random messages with 2026, so this runs identically here, in the visualizer, and in the Python script below.

1. Expected tries. 1.25 × √(2²⁴) = 1.25 × 4096 ≈ 5,120.
2. Search. Random 8-byte messages are hashed one at a time, each checked against a table of every 24-bit truncated digest seen so far.
3. Match. After 6,746 tries, message 39172a6284a2ac7b and message 50a84dc4ff81c698 produce digests 04522229d07d67bdba6c29b05efbadd7 and 0452223ce6a1f51748257c89abf745e5.
4. Verify. Both digests begin 045222, the same 24 bits (6 hex digits). The remaining bits differ completely, since nothing constrained them.

6,746 is higher than the 5,120 expected, which is normal. The birthday bound is an average, not a guarantee, and a single run has real variance. Across several truncation widths, the pattern still holds:

Each step up roughly quadruples the expected count, and the actual counts track that trend despite the noise in any one run.

Wang’s Real Collision

The birthday attack above never touches MD5’s internal structure. It would work exactly the same way against a hash function with no flaws at all. Wang’s attack is different. It targets MD5’s compression function directly, and it finds a genuine collision on the full 128-bit output, not a truncated one.

The technique, at a high level, works over MD5’s 64-round compression function:

1. Find a differential path. A specific pattern of tiny differences between two input blocks (individual bits, flipped in specific words) that has a good chance of canceling out completely by the end of all 64 rounds, despite MD5’s rounds being designed to scramble input differences unpredictably.
2. Derive sufficient conditions. A long list of bit-level constraints on the intermediate state, at each round, that must hold for the difference to actually cancel out as predicted.
3. Modify the message to satisfy them. The first roughly 32 rounds’ conditions can be forced to hold directly, by choosing specific message bits. The remaining conditions are left to chance.
4. Search. Try message variants until the unconstrained conditions happen to hold too. Because message modification already satisfies most conditions deterministically, this final search is fast, historically well under a minute on ordinary hardware, not the years a generic 2⁶⁴ birthday attack over the full digest would take.

The published result of applying this technique is a pair of two-block (128-byte) messages that produce the identical MD5 digest 79054025255fb1a26e4bc422aef54eb4. This post doesn’t run that search itself. Building and debugging a correct implementation of Wang’s differential path and message-modification technique is a substantially larger undertaking than reusing it, and getting the sufficient conditions subtly wrong tends to fail silently rather than loudly. Instead, this post verifies the real, published result directly: both message blocks are hashed live, right here, with the exact same MD5 implementation this site’s base MD5 guide uses.

Verifying the Real Bytes

The two messages differ in exactly 6 of their 128 bytes. Every one of those 6 differences is the byte’s value XOR-ed with 0x80, a single flipped bit, sitting exactly where Wang’s differential path predicts a difference should propagate to.

offset  19: 0x87 -> 0x07
offset  45: 0x71 -> 0xf1
offset  59: 0xf2 -> 0x72
offset  83: 0xb4 -> 0x34
offset 109: 0xa8 -> 0x28
offset 123: 0x2b -> 0xab

Both full messages hash, via genuine unmodified MD5, to 79054025255fb1a26e4bc422aef54eb4. That’s not a truncated match like the birthday attack above. Every one of the 128 bits agrees.

Python Implementation

This site’s own MD5 guide already has a from-scratch, verified MD5 implementation. The script below reuses it, unmodified, for both attacks: the live birthday search, and verifying Wang’s published collision.

Key Features

• Self-contained. The MD5 function below is copied directly from the base guide, so this script runs with no other files needed.
• A real birthday search. Random messages are generated from a small seeded generator (mulberry32), so this script’s numbers match the visualizer’s exactly for the same seed.
• A real verification, not an assertion. The Wang collision bytes are hashed with this same from-scratch MD5, not hardcoded as already-equal.

Code

# md5_collision_breaker.py
#
# Two independent attacks against MD5:
#
# 1. A generic birthday attack against N bits of the digest. Works against
#    any hash function; says nothing about MD5's internal structure.
# 2. Verification of a real, published full 128-bit MD5 collision, found
#    in 2004 by Wang, Feng, Lai, and Yu using an actual structural flaw
#    in MD5's compression function.
#
# The MD5 implementation below is the base MD5 guide's own code, copied
# in so this script needs no other files.

import math


S = [7,12,17,22, 7,12,17,22, 7,12,17,22, 7,12,17,22,
     5, 9,14,20, 5, 9,14,20, 5, 9,14,20, 5, 9,14,20,
     4,11,16,23, 4,11,16,23, 4,11,16,23, 4,11,16,23,
     6,10,15,21, 6,10,15,21, 6,10,15,21, 6,10,15,21]

K = [int(abs(math.sin(i + 1)) * 2**32) & 0xFFFFFFFF for i in range(64)]


def left_rotate(x, c):
    return ((x << c) | (x >> (32 - c))) & 0xFFFFFFFF


def md5(message: bytes) -> bytes:
    a0, b0, c0, d0 = 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476

    msg = bytearray(message)
    orig_len_bits = (len(message) * 8) & 0xFFFFFFFFFFFFFFFF
    msg.append(0x80)
    while len(msg) % 64 != 56:
        msg.append(0)
    msg += orig_len_bits.to_bytes(8, 'little')

    for offset in range(0, len(msg), 64):
        chunk = msg[offset:offset + 64]
        M = [int.from_bytes(chunk[i:i+4], 'little') for i in range(0, 64, 4)]

        A, B, C, D = a0, b0, c0, d0
        for i in range(64):
            if i < 16:
                F = (B & C) | (~B & D); g = i
            elif i < 32:
                F = (D & B) | (~D & C); g = (5 * i + 1) % 16
            elif i < 48:
                F = B ^ C ^ D; g = (3 * i + 5) % 16
            else:
                F = C ^ (B | ~D); g = (7 * i) % 16

            F = (F + A + K[i] + M[g]) & 0xFFFFFFFF
            A, D, C = D, C, B
            B = (B + left_rotate(F, S[i])) & 0xFFFFFFFF

        a0 = (a0 + A) & 0xFFFFFFFF
        b0 = (b0 + B) & 0xFFFFFFFF
        c0 = (c0 + C) & 0xFFFFFFFF
        d0 = (d0 + D) & 0xFFFFFFFF

    return b''.join(v.to_bytes(4, 'little') for v in (a0, b0, c0, d0))


# ---- Attack 1: birthday attack on a truncated digest ----

def mulberry32(seed):
    a = seed & 0xFFFFFFFF
    while True:
        a = (a + 0x6D2B79F5) & 0xFFFFFFFF
        t = ((a ^ (a >> 15)) * (1 | a)) & 0xFFFFFFFF
        t = ((t + (((t ^ (t >> 7)) * (61 | t)) & 0xFFFFFFFF)) & 0xFFFFFFFF) ^ t
        yield (t ^ (t >> 14)) & 0xFFFFFFFF


def rand_bytes(rng, n):
    out = bytearray()
    while len(out) < n:
        out += next(rng).to_bytes(4, "little")
    return bytes(out[:n])


def birthday_search(bits, seed):
    rng = mulberry32(seed)
    nbytes = (bits + 7) // 8
    mask_bits = bits % 8
    seen = {}
    tries = 0
    while True:
        tries += 1
        msg = rand_bytes(rng, 8)
        digest = md5(msg)
        prefix = digest[:nbytes]
        if mask_bits:
            prefix = prefix[:-1] + bytes([prefix[-1] & (0xFF << (8 - mask_bits) & 0xFF)])
        if prefix in seen and seen[prefix] != msg:
            return seen[prefix], msg, tries, md5(seen[prefix]), digest
        seen[prefix] = msg


# ---- Attack 2: verify Wang, Feng, Lai, Yu's real 2004 collision ----

WANG_M1 = bytes.fromhex(
    "d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89"
    "55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b"
    "d8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0"
    "e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70"
)
WANG_M2 = bytes.fromhex(
    "d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89"
    "55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b"
    "d8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0"
    "e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70"
)


if __name__ == "__main__":
    m1, m2, tries, d1, d2 = birthday_search(bits=24, seed=2026)
    print("--- Birthday attack (24-bit truncation, seed 2026) ---")
    print(f"Message 1: {m1.hex()}  MD5: {d1.hex()}")
    print(f"Message 2: {m2.hex()}  MD5: {d2.hex()}")
    print(f"Matched on the first 24 bits after {tries:,} tries.")

    print("\n--- Verifying Wang, Feng, Lai, Yu (2004) ---")
    h1, h2 = md5(WANG_M1).hex(), md5(WANG_M2).hex()
    print(f"MD5(M1) = {h1}")
    print(f"MD5(M2) = {h2}")
    print(f"M1 == M2: {WANG_M1 == WANG_M2}   MD5(M1) == MD5(M2): {h1 == h2}")

Running this script produces the following output:

--- Birthday attack (24-bit truncation, seed 2026) ---
Message 1: 39172a6284a2ac7b  MD5: 04522229d07d67bdba6c29b05efbadd7
Message 2: 50a84dc4ff81c698  MD5: 0452223ce6a1f51748257c89abf745e5
Matched on the first 24 bits after 6,746 tries.

--- Verifying Wang, Feng, Lai, Yu (2004) ---
MD5(M1) = 79054025255fb1a26e4bc422aef54eb4
MD5(M2) = 79054025255fb1a26e4bc422aef54eb4
M1 == M2: False   MD5(M1) == MD5(M2): True

Both numbers match the visualizer and the worked example above exactly. This script’s own md5 function was independently checked against Python’s built-in hashlib.md5 on 500 random-length random inputs before being trusted for either attack.

For Fun: The Collision Check in 4 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning MD5 from. This version skips the birthday attack and only verifies the published collision, using hashlib instead of a from-scratch implementation.

import hashlib
m1 = bytes.fromhex("d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70")
m2 = bytes.fromhex("d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70")
print(m1 != m2, hashlib.md5(m1).hexdigest() == hashlib.md5(m2).hexdigest() == "79054025255fb1a26e4bc422aef54eb4")

Verified to print True True: the two messages are genuinely different, and both hash to the exact published digest.

Interactive Visualizer

Try the visualizer above. Step 1 runs the birthday attack live, at whatever truncation width you choose, and shows the two messages it finds along with how many tries it took against the expected count. Step 2 verifies Wang’s real collision live, computing both full MD5 digests in your browser with the same library this site’s base MD5 visualizer uses. Step 3 lets you flip one of the six crafted bytes back to its “wrong” value, so you can watch the collision break the instant the exact bit pattern is disturbed.

Birthday Bound vs. Wang’s Attack

The gap in that cost column is the whole story. A generic birthday attack against MD5’s full 128-bit output would need about 2⁶⁴ hashes, decisively out of reach. Wang’s attack reaches a full collision in well under a minute, precisely because it exploits MD5’s actual design rather than brute-forcing the birthday bound. That gap between “safe by the numbers” and “broken in practice” is exactly why MD5 was retired for anything security-sensitive, not merely resized.

Limitations of This Post

The birthday attack here is real and runs live, but it only ever produces a truncated collision. Extending it to a full 128-bit collision the generic way needs roughly 2⁶⁴ hashes, far beyond what any browser or script here attempts.

Wang’s collision is verified, not generated. This post confirms a real, historically significant result using genuine, unmodified MD5, computed twice independently (the base guide’s from-scratch Python, and CryptoJS in the browser). It doesn’t implement the differential path and message-modification search that originally found those bytes. That search involves dozens of interacting bit-level conditions across MD5’s 64 rounds, and a subtly wrong implementation tends to simply fail to find anything, rather than fail loudly. Klima’s message-modification refinements later cut the original attack’s runtime from about an hour to under a minute on ordinary 2006 hardware; reproducing that scale of engineering is out of scope here.

This is also an identical-prefix collision, not a chosen-prefix one. Both halves of Wang’s pair are forced by the differential path itself. Nobody gets to choose what those bytes look like, only that a valid pair exists for a given starting state. That’s very different from producing two meaningfully different documents, like two different X.509 certificates, that both hash the same way. That harder version, chosen-prefix collision, is what real-world attacks like the 2008 rogue certificate authority forgery and the 2012 Flame malware actually needed. It requires substantially more computation and specialized tooling (Marc Stevens’ HashClash), and it isn’t covered here.

FAQ

Does the birthday attack here break real MD5?

It doesn’t, because it finds two messages agreeing on a small number of digest bits you chose in advance, not a full 128-bit collision. It’s a demonstration of a generic property every hash function shares, not an MD5-specific weakness.

Is Wang’s collision faked or simulated?

It isn’t, because the two 128-byte messages are the real, published bytes from the 2004 paper. Both are hashed live with a real MD5 implementation, and the result is checked against the published digest, not assumed.

Why does flipping one byte break the collision?

The collision depends on an exact, carefully engineered bit pattern across all 128 bytes. It has nothing to do with any general property of “messages like this one.” Disturbing even one of the six crafted bytes removes the exact cancellation the differential path relies on.

Could this technique target SHA-256 the same way?

Not in the same form. Wang’s attack exploits weaknesses specific to MD5’s particular round functions and message schedule. SHA-256 has a different internal structure, and no comparable practical collision attack against it is currently known.

What’s the difference between this and a chosen-prefix collision?

Here, both colliding messages are dictated by the differential path itself; you don’t get to choose meaningful content for either one. A chosen-prefix collision lets you pick two different, meaningful starting messages, then find suffixes that bring them to the same hash. That version needs much more computation and specialized tooling, and it’s what makes forging two different meaningful documents with the same hash possible.

References

1. Wang, X., Feng, D., Lai, X., and Yu, H. “Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD.” IACR ePrint 2004/199.

2. Klima, V. “Tunnels in Hash Functions: MD5 Collisions Within a Minute.” IACR ePrint 2006/105.

3. Stevens, M. “HashClash: MD5 & SHA-1 Cryptanalysis Toolbox.” Available at: https://github.com/cr-marcstevens/hashclash

4. Wikipedia. “MD5.” Available at: https://en.wikipedia.org/wiki/MD5