Birthday Bound
The birthday bound is the attack-complexity floor fixed by the birthday paradox: finding a collision in a set of N elements takes about sqrt(N) samples.
Purpose
It sets the security ceiling for hash functions and block-cipher modes: an n-bit hash offers only 2^(n/2) collision resistance, and CBC/CTR modes of an n-bit block repeat after 2^(n/2) blocks.
Mechanism
By the birthday paradox, random sampling from an N-element set repeats with high probability after about sqrt(N) draws. Hence an n-bit hash collision needs 2^(n/2) operations, and SHA-256 provides 128-bit collision resistance.
Use cases
- Hash-function security strength assessment
- Block-count ceilings for block-cipher modes
- Choosing signature hash lengths