What is a collision attack (birthday attack), and how does it differ from a pre-image attack in both approach and complexity?
A collision attack finds any two documents with the same hash — the attacker modifies both documents and only needs $\sqrt{2^n} = 2^{n/2}$ operations.
* Because Eve varies both documents, the birthday paradox cuts the work to only ~2^(n/2). *
* The collision bar is always half the height — which is exactly why a hash needs twice the bits of its target security level. *
Key difference from pre-image attack:
| Pre-image Attack | Collision Attack | |
|---|---|---|
| Target | Weak collision resistance | Strong collision resistance |
| What's modified | Only the forged document | Both original and forged |
| Realism | More realistic scenario | Less realistic (original is also altered) |
| Complexity | $O(2^n)$ | $O(2^{n/2})$ — square root! |
Why is it easier? The birthday paradox — when you can choose both values freely, you exploit the combinatorial explosion of pairs. With $2^{n/2}$ random documents, you're likely to find a matching pair.
For n = 256 bits: Pre-image needs $2^{256}$, collision needs $2^{128}$. Still infeasible, but the gap is dramatic.
Tip: This is why hash functions that resist collision attacks must have output sizes at least double what you'd think — a 128-bit hash only gives $2^{64}$ collision security.
Go deeper:
Collision attack (Wikipedia) — classical vs chosen-prefix collisions and the real-world MD5/SHA-1 breaks.- Birthday attack (Wikipedia) — the probability argument behind the $2^{n/2}$ cost.