Two different inputs producing the same digest is a hash collision. Engineering only cares about three questions: must a collision exist, how soon will one appear, and can one be constructed on purpose. The answers are the pigeonhole principle, the birthday paradox, and the current state of MD5 and SHA-1 — together they decide which algorithm a checksum or a password store should use.
Collisions Must Exist: Pigeonhole Principle
A hash compresses arbitrary-length input into fixed-length output: SHA-256 always emits 256 bits, so only 2²⁵⁶ outputs exist while inputs are infinite. Mapping infinity onto a finite set guarantees that several inputs share one output — no advanced mathematics required.
"Exists" is not "reachable by luck". A 2²⁵⁶ output space makes accidental collisions vanishingly rare, so the real risk is never bad luck; it is deliberate construction. The next section makes the arithmetic concrete.
The Birthday Paradox: From "Impossible" to "Computable"
How many random inputs until a collision is more likely than not? Intuition says half the output space; the real answer is far smaller. Among 23 people, two share a birthday with over 50% probability, out of only 365 days. For a b-bit hash the count is about 2^(b/2), not 2^b.
import math
def collision_prob(bits, n):
N = 2 ** bits
return 1 - math.exp(-n * (n - 1) / (2 * N))
# 32-bit truncation (the first 8 hex characters of a SHA-256 digest, say)
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%
At 77,000 random inputs a 32-bit hash passes a 50% collision chance, landing right around 2^(32/2) = 65536. Watch how the probability grows: from 10,000 to 77,000 inputs — under eight times more — the chance climbs from 1.2% to 49.9%. It scales with n²/N, not linearly. "I only store a few tens of thousands of fingerprints, so nothing will collide" is simply wrong at 32 bits.
A 64-bit truncation needs about 5×10⁹; MD5's 128 bits need roughly 2⁶⁴ operations under the same bound. That is within reach of dedicated hardware, and it is exactly the road SHA-1 travelled to a real collision.
Building a Collision Yourself
Truncate SHA-256 to its first two hex characters (8 bits, 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 {h!r} (hit #{i})')
break
seen[h] = s
# collision: 'oltool-21' and 'oltool-24' share '7b' (hit #24)
The full digests of those two "collisions" are 7b3f71f6… and 7bf43201…: identical prefix, otherwise unrelated. Truncation costs collision resistance, not one-wayness — you still cannot recover the input, but manufacturing a matching short fingerprint is easy.
The engineering consequence is direct: given m items and a tolerated probability p, scan different bit widths with the collision_prob function above until p falls under the threshold. Never pick eight or sixteen characters because they "look long enough". Short fingerprints collide much sooner than intuition suggests.
MD5 and SHA-1: Collisions You Can Order
MD5's situation is not theoretical. Chosen-prefix collision attacks have been practical since 2004, letting an attacker build two different files with the same MD5 — real forgeries include a rogue CA certificate in 2008 and disguised Flash files. SHA-1 got a real collision in 2017 through SHAttered (about 2⁶³ operations, roughly 110k dollars of GPU time), followed by a public PDF-forgery proof of concept.
The threat model changes accordingly: stop worrying about accidental collisions and start worrying about deliberately built pairs. An attacker prepares two budget sheets, one for you to read and one for you to sign; a signing system on MD5/SHA-1 gives them identical digests, so nobody can later prove which one you signed.
SHA-256 closes that path with output length and internal structure: 256 bits put the birthday bound near 2¹²⁸, far beyond feasible compute, and constructing a collision means breaking the compression structure itself, for which no method is known.
Two Scenarios, Two Threat Models
| Scenario | Collision impact | Requirement |
|---|---|---|
| File integrity verification | An attacker can craft a matched pair: a malicious file plus the hash you expect | Use an unbroken algorithm (SHA-256 or better); source the hash from an independent trusted channel |
| Password storage | Collisions are irrelevant — plain enumeration is cheaper | Unrelated to collisions: needs salt + slow hash (bcrypt/argon2) |
The second row gets conflated constantly. In password storage, "crafting two colliding passwords" is pointless because simply trying common passwords wins. "MD5 collisions are broken" is therefore not the main reason MD5 is unsafe for passwords; the real reason is speed.
A related question: if two files share a digest, are they identical? With an unbroken algorithm, engineering treats that as equivalent; logically it is "overwhelmingly likely". That is the entire foundation of verification — determinism plus a large enough output space:
import hashlib
hashlib.sha256(b'hello world').hexdigest()
# -> b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9 (same on any machine, any time)
Four Engineering Boundaries
- Collisions must exist (pigeonhole), but their timing is computable (birthday bound 2^(b/2)), which makes probability a manageable parameter rather than superstition.
- MD5 and SHA-1 are out of every adversarial use, including file signing, certificates, and tamper-evident identifiers; they remain usable for dedup and cache keys, though there is no reason not to use SHA-256.
- Trust in verification comes from the channel: the algorithm is only a necessary condition, and the digest must come from an independent trusted source. Workflow in file integrity checks.
- Password storage defends against enumeration, not collisions: salt plus a slow hash, with parameters and migration in the password hashing guide.
- Choose truncated fingerprint width from item count and tolerated probability, never by gut feeling.
Quick reference and selection: hash algorithm reference and the text hash tool.