Archivehashing
The Birthday Bound in Practice
Why 128-bit hashes are enough for most things and 64-bit hashes are not enough for anything adversarial.
- Published
- Reading time
- 1 min read
A collision needs roughly 2^(n/2) work for an n-bit hash. SHA-256 therefore offers about 128 bits of collision resistance, not 256. This is not a flaw; it is the price of asking "do any two inputs collide?" instead of "does this input match that one?".
Doing the arithmetic
| Digest | Collision work | Preimage work |
|---|---|---|
| 64-bit | 2^32 | 2^64 |
| 128-bit | 2^64 | 2^128 |
| 256-bit | 2^128 | 2^256 |
2^32 operations is minutes on a GPU. That is why 64-bit hashes (and short IDs like 8-hex-character commit prefixes) must never be used where an adversary can choose inputs.
Where it actually bites
- Deduplication keys: an attacker who can force a collision can make two different blobs share storage.
- Shard assignment: collisions are harmless, but predictable collisions are not.
- Random IDs: a 64-bit random identifier is fine for uniqueness at modest scale, but birthday collisions appear around 4 billion items.
Takeaway: size the hash for the adversary. Non-adversarial uniqueness can use short IDs; anything an attacker can grind needs at least 128 bits of collision resistance, i.e. a 256-bit digest.