Birthday & Collision Attacks
Apply the birthday paradox to hash collisions and hash-length extension.
The Birthday Paradox
In a group of 23 people, the probability that two share a birthday exceeds 50%. With 70 people, it exceeds 99.9%. Mathematically: in a set of size N, collision probability exceeds 50% after ~√N samples. This is the birthday bound.
Birthday Bound for Hash Functions
For an n-bit hash function: a collision (H(m1) = H(m2), m1 ≠ m2) can be found with ~2^{n/2} random trials. For SHA-256 (256-bit), collision requires ~2^{128} work — computationally infeasible. For MD5 (128-bit), ~2^{64} — borderline feasible.