When is your birthday? The Math Behind Hash Collisions
The birthday paradox scales into cryptography and hash table design. Von Mises’s 1939 occupancy probability reframes collision math in ways still directly relevant to SHA-256 security estimates.
What Matters
- 23 people in a room yields ~50% chance of a shared birthday; exact formula: 365!/(365²³ × 342!).
- Insurance math bureau employees in the 1930s computed triple-birthday probability as ~0.0006—correct question, wrong frame.
- Richard von Mises (1939, Istanbul University) reframed it as occupancy probability: watch all 365 boxes, not one pre-chosen day.
- Von Mises’s expected-value formula gives E(x₃)≈0.22 for 60 people, meaning one triple-shared birthday per ~4–5 such groups.
- The math bureau’s framing predicts triple-match once per 1,500–2,000 groups; von Mises’s predicts once per ~4.5—a 300–400× difference.
- Birthday Attack in cybersecurity exploits this: generate random inputs until any two hash identically, requiring only √n attempts instead of n.
- SHA-256 has 2²⁵⁶ outputs; birthday attack needs ~2¹²⁸ attempts—collision resistance depends entirely on output space size.
