Birthday bound
Hash collisions become likely at √(output space).
Origin
The classic birthday paradox dates to Richard von Mises (1939). Applied to hash collisions, it tells you a 256-bit hash gives only ~128 bits of collision resistance — which is why MAC tags below 128 bits are considered unsafe.
Where it shows up in production
- GCM-SIV nonce limits AES-GCM-SIV caps usage at 2^32 messages per key to stay safely below the birthday bound.
- Git SHA-1 collision (2017) SHAttered demonstrated a real-world collision; the underlying limit was birthday-bound on the 160-bit output.
On Semicolony
Sources & further reading
Found this useful?