Hash Collision

A hash collision occurs when two distinct inputs produce the same fixed-length hash output. Since hash functions map infinite possible inputs to a finite output space, collisions are mathematically guaranteed to exist. The security question is not whether collisions exist — they always do — but whether an attacker can find them. When finding collisions becomes computationally feasible, the hash function is considered broken.

Collision Resistance

A cryptographic hash function must be collision resistant: finding any two inputs m1 ≠ m2 such that hash(m1) = hash(m2) should be computationally infeasible.

The birthday bound sets a probabilistic limit: for an n-bit hash, you need approximately 2^(n/2) evaluations to find a collision with 50% probability. For SHA-256 (256-bit output), that is 2^128 operations — computationally infeasible.

Real-World Collision Attacks

MD5 (Broken 2004)

The first practical MD5 collision was demonstrated in 2004. By 2008, researchers produced two different PDF files with the same MD5 hash, enabling the creation of a fraudulent CA certificate. MD5 collisions now take seconds on consumer hardware.

SHA-1 (Broken 2017)

Google's SHAttered attack (2017) produced the first practical SHA-1 collision — two different PDF files with identical SHA-1 hashes — at a cost of approximately $110,000 in cloud computing time. Browser vendors and certificate authorities had already been phasing out SHA-1.

SHA-256 (Currently Secure)

No practical collision attack exists against SHA-256. The 256-bit output provides 128 bits of collision resistance — current quantum and classical computers cannot approach this.

Second Pre-image vs Collision

These are distinct properties:

• Collision attack: find any two different inputs with the same hash (attacker chooses both)
• Second pre-image attack: given a specific input and its hash, find a different input with the same hash (attacker must match a specific hash)
• Pre-image attack: given only a hash, find any input that produces it

Second pre-image resistance is harder to break than collision resistance. An algorithm can be collision-broken while still being second-pre-image resistant.

Impact of Collision Attacks

Collision attacks matter when:

• Digital signatures over documents: an attacker can create two documents with the same hash, get one signed, and the signature applies to both
• Certificate fingerprints: collision attacks allowed the MD5 CA certificate forgery
• Hash-based deduplication: false duplicates if collisions are found

Collision attacks do not help with password cracking (you need a pre-image, not just any collision).

Safe Algorithms

For collision resistance in new projects, use SHA-256, SHA-3-256, or BLAKE3. Do not use MD5 or SHA-1 for any purpose where collision resistance matters.