Hash Collisions Explained: The Birthday Paradox & Why MD5 Is Dead

Collisions Must Exist: Pigeonhole Principle

A hash function compresses arbitrary-length input into fixed-length output. SHA-256 always emits 256 bits — only 2²⁵⁶ possible outputs — while possible inputs are infinite.

Infinite inputs mapped into finite outputs guarantee multiple inputs share one output. That is the pigeonhole principle; no deep math required. The good news: "exists" is not "findable" — a 2²⁵⁶ output space makes random collisions vanishingly rare. The bad news is the next section.

---

The Birthday Paradox: Collisions Arrive Much Earlier Than Intuition

「How many random inputs until a collision is more likely than not?」 Intuition says half the output space, but the real answer is far smaller — the birthday paradox: among 23 people, two share a birthday with over 50% probability (365 possible days).

For a b-bit hash, the input count where collision probability crosses 50% is about 2^(b/2), not 2^b. Verify with a real calculation:

import math
def collision_prob(bits, n):
    N = 2 ** bits
    return 1 - math.exp(-n * (n - 1) / (2 * N))

# 32-bit truncation (e.g. the first 8 hex characters of a SHA-256 digest)
for n in (10_000, 50_000, 77_000, 100_000):
    print(n, f'{collision_prob(32, n)*100:.1f}%')
# 10000 → 1.2%   50000 → 25.3%   77000 → 49.9%   100000 → 68.8%

77,000 random inputs push a 32-bit hash past a 50% collision chance — the birthday bound lands right at 2^(32/2) = 65536, matching theory. A 64-bit truncation crosses at about 5×10⁹, and MD5's 128-bit space needs only about 2⁶⁴ operations by the same bound — no longer out of reach for distributed compute, which is exactly how SHA-1 got its real collision.

---

A Hands-On Experiment: Build a Collision Yourself

Probability tables are abstract; a runnable experiment is not. Truncate SHA-256 to its first 2 hex characters (8 bits — only 256 possible values) and brute-force the birthday paradox in seconds:

import hashlib
seen = {}
for i in range(1_000_000):
    s = f'oltool-{i}'
    h = hashlib.sha256(s.encode()).hexdigest()[:2]
    if h in seen:
        print(f'collision: {seen[h]!r} and {s!r} share prefix {h!r} (hit #{i})')
        break
    seen[h] = s
# collision: 'oltool-21' and 'oltool-24' share '7b' (hit #24)

Verify the full hashes of the two "collisions": 7b3f71f6… and 7bf43201… — identical prefix, completely different overall. The experiment demonstrates precisely how truncated hashes fail: the fewer bits compared, the faster the collision. It also explains why "take the first N digits as a short fingerprint" requires N to be chosen by collision-probability math, not gut feeling.

---

MD5 and SHA-1: Collisions You Can Order

MD5's status is no longer theoretical: chosen-prefix collision attacks have been practical since 2004, letting attackers craft two different files with the same MD5 — real-world forgeries include a rogue CA certificate (2008) and Flash-file impersonation. SHA-1 got its real collision in 2017 (SHAttered, ~2⁶³ operations, about $110k of GPU time), followed by a public PDF-forgery proof of concept.

This changes the threat model: you no longer worry about "happening to collide"; you worry about "someone builds a pair on purpose". An attacker crafts two budget sheets — one for you to read, one for you to sign — and a signing system using MD5/SHA-1 gives both the same hash, making it impossible to prove later which one you signed.

Cryptography answers this with length and structure: SHA-256 emits 256 bits with a birthday bound near 2¹²⁸, far beyond feasible compute; and constructing a collision requires breaking the internal compression structure, for which no method is known.

---

Two Scenarios, Two Different Impacts

Row two is often mixed up: in the password threat model, "crafting two colliding passwords" is pointless — trying common passwords is faster. That is why 「MD5 collisions are broken」 is not the main reason 「MD5 for passwords is unsafe」 (the real reason is speed). The two get conflated constantly.

Full algorithm comparison and selection guidance: the hash algorithm reference and choosing a text hash tool.

---

Reproducible Results

Three groups of output, all really run (terminal-ready):

Birthday bound (32-bit truncation, where collision probability crosses 50%):

import math
def collision_prob(bits, n):
    N = 2 ** bits
    return 1 - math.exp(-n * (n - 1) / (2 * N))
print(collision_prob(32, 77_000))   # → 0.499… (≈ 50%)
print(collision_prob(64, 5 * 10**9)) # → 0.492  (64-bit birthday bound ≈ 5e9)

Truncated collision experiment (first 2 hex digits of SHA-256 = 8 bits):

import hashlib
seen = {}
for i in range(1_000_000):
    s = f'oltool-{i}'.encode()
    h = hashlib.sha256(s).hexdigest()[:2]
    if h in seen:
        print(f'{seen[h]!r} vs {s!r}: share {h!r}, hit #{i}')
        break
    seen[h] = s
# 'oltool-21' vs 'oltool-24': both start '7b', hit #24
# Full SHA-256: 7b3f71f6… ≠ 7bf43201… (truncated equal ≠ overall equal)

Determinism on the same input (the foundation of integrity checking):

import hashlib
hashlib.sha256(b'hello world').hexdigest()
# → b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9 (any machine, any time, same result)

The last one is why file verification works at all: deterministic algorithm + large enough output space ⇒ 「equal hash」 is an engineering equivalent of 「equal content」.

---

Takeaways

• Collisions must exist (pigeonhole), but their timing is computable (birthday paradox: 2^(b/2));
• MD5 / SHA-1 collisions are constructible on demand — retire them from every security-relevant path;
• Start at SHA-256 for integrity verification, with hashes sourced from official channels;
• Password storage faces brute-force enumeration, not collisions — salt + slow hash is the answer;
• For truncated fingerprints, choose N by collision-probability math, never by gut feeling.

This site's text hash tool supports all mainstream algorithms, and the hash algorithm reference has the full comparison and selection advice.