The birthday paradox explains why collisions in a finite output space appear sooner than intuition suggests. With 365 possible birthdays, only 23 people create a greater-than-50% chance that two share a birthday. section 6.2
Hash functions must map unbounded inputs to fixed-size outputs, so collisions are unavoidable in principle. For an ideal N-bit hash, roughly 2^(N/2) computations give an attacker a greater-than-50% chance of finding some collision. section 6.2 section 6.5
The birthday bound changes how hash security properties should be interpreted:
- Finding any two inputs with the same digest is a collision attack; matching a predetermined digest requires substantially more work and is a second-preimage attack. section 6.2
- A 128-bit MD5 digest would offer an idealized 2^64-step birthday bound, although practical attacks reduced collision-finding work to about 2^18 steps. section 6.2
- A hash is considered broken when collisions can be found more efficiently than the naive birthday attack. section 6.5
Different files, identical digest
A collision attack can produce two PDFs with radically different displayed contents but the same hash digest by exploiting format-specific file internals. section 6.5
Figure 6.4 Security properties of hash functions
Use the figure to compare collision resistance with the other security properties of hash functions. section 6.2
