Hash collisions
A collision is two different inputs producing the same digest. With 256-bit output there are astronomically many possible digests, so finding a collision by accident is hopeless — but by design it is a different story.
In this lesson
- Define a hash collision
- Explain why collisions matter for signatures and certificates
- Estimate the birthday bound for a 256-bit digest
Prerequisites
- required What is hashing?
Two inputs, one digest
Because a hash maps a huge input space onto a smaller output space, collisions must exist — the question is whether anyone can find them. For SHA-256 the fastest known approach costs roughly 2128 operations (the birthday bound), far beyond any current or planned hardware.
| Hash | Fastest known collision attack | Verdict |
|---|---|---|
| MD5 | Seconds on a laptop | Useless for security |
| SHA-1 | ~2<sup>63</sup> operations (SHAttered) | Deprecated |
| SHA-256 | ~2<sup>128</sup> operations | Secure for the foreseeable future |
Example · The SHAttered attack (2017)
Researchers produced two different PDF files with the same SHA-1 digest and used them to bypass file-type checks. Google and the CA/Browser Forum moved to SHA-256 within weeks. The lesson: a hash that can be collided can be used to swap one document for another, undetectably.
Collisions matter most where a hash stands in for the data itself:
- Code signing — if malware collides with a signed binary, the signature transfers to it.
- Certificates — a forged certificate with the CA's SHA-1 fingerprint would be trusted by browsers.
- Integrity checks — an attacker swaps your file for one with the same digest.
Hashing passwords is not about collisions
For passwords you care about preimage resistance (recovering the input) and slowness, which is why Argon2/bcrypt are used instead of SHA-256.
Search for a collision (you will lose)
Try to find two inputs with the same 64-character digest in the lab — then read the numbers above again.
Can collisions happen by accident?
For 256-bit digests, the odds are astronomically small for any realistic number of inputs — you would need roughly 2^128 hashes.
What is a second preimage attack?
Given one input, find a different input with the same digest. It is much harder than a plain collision (~2^256 for SHA-256), which is why hashes stay safe for file verification.
What is a collision?
Practice · server-graded