Math intuitions
The birthday paradox
In a room of 23 people the odds that two share a birthday are just over even, because the number of pairs grows with the square of the group.
A classic of elementary probability; the cryptographic birthday attack takes its name and its arithmetic from it.
Ask how many people must be in a room before two of them probably share a birthday and most people guess well over a hundred, reasoning from 365 days. The answer is 23. The calculation goes through the chance that nobody matches: the second person avoids the first's birthday with probability 364/365, the third avoids both with 363/365, and so on. Multiply the 22 fractions and you get 0.493, so the chance of at least one shared birthday among 23 people is 50.7 percent. With 41 people it is 90 percent, with 57 it is 99 percent, and with 70 it is 99.9 percent. The question people answer by instinct is a different one: how many people are needed before someone shares your birthday. That one really does take 253 people to pass even odds.
Intuition fails because it counts people when it should count pairs. Among n people there are n times (n minus 1) over 2 pairs, and every pair is a separate chance of a match: 23 people make 253 pairs and 57 make 1,596. Each pair matches with probability 1/365, so the expected number of matches among 23 people is 253/365, about 0.69, and the chance of none is about e to the minus 0.69, which is 0.50. The square in the pair count is the whole story: double the group and you quadruple the chances. The general rule is that with N equally likely values, a collision becomes more likely than not once you have drawn about the square root of 2 ln 2 times N items, roughly 1.4N; for N of 365 that is the square root of 506, which is 22.5.
The same arithmetic sets the limit on hash functions. A hash with 160 bits has 2 to the power 160 possible outputs, so nobody can forge a chosen digest, but a collision between some two inputs in a large set is expected after about 2 to the power 80 tries, the square root. That is the birthday attack, and it is why a hash's collision resistance is only half its bit length. SHA-1 was retired because cryptanalysis beat even that bound: on 23 February 2017 CWI Amsterdam and Google published two PDF files with the same SHA-1 digest after work equivalent to 2 to the power 63.1 compression calls, more than 100,000 times fewer than the birthday bound. The lesson runs both ways. Coincidences are far more common than they feel, and so are 'impossible' collisions among random identifiers once the system is large.
Example
On 23 February 2017 Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini and Yarik Markov, of CWI Amsterdam and Google, announced the first collision for the full SHA-1 hash function: two PDF files with different visible content and the same 160-bit digest, 38762cf7f55934b34d179ae6a4c80cadccbb7f0a. Their paper puts the work at the equivalent of 2 to the power 63.1 SHA-1 compression function calls, about 6,500 CPU-years and 100 GPU-years, and more than 100,000 times faster than a brute-force search, which the birthday bound sets at about 2 to the power 80. Browsers and certificate authorities stopped accepting SHA-1 signatures within months.
Where it applies
Any system that assigns random identifiers, shards by hash or deduplicates by fingerprint has a birthday bound: with 32-bit IDs, expect a duplicate after about 77,000 items, not 4 billion, so use 128 bits where collisions must never happen. And when two users report the same freak coincidence, count the pairs before calling it suspicious.
Think about it
Where in your systems or your life are you counting items when you should be counting pairs?
Applied it to something real? Log it.
Test yourselfWhy do 23 people give even odds of a shared birthday when 365 days seem to need far more?
Because 23 people make 253 pairs and each pair is a 1-in-365 chance: expected matches are 253/365, about 0.69, so the chance of none is e^-0.69, about 0.5. Chances grow with the square of the group.
Related models
- Exponential versus linear growthLinear growth adds the same amount each step; exponential growth multiplies by the same factor, and the two look alike only at the start.
- Probabilistic thinkingThink in odds rather than certainties: estimate how likely each outcome is, and judge a decision by those odds rather than by the single result that happened.
- Base ratesHow common something is to begin with matters as much as the evidence in front of you, and people routinely leave it out.