The Birthday Problem: Why 23 Strangers Probably Share a Birthday
Walk into a room with 22 strangers — 23 people total, counting yourself — and there's a better than 50-50 chance two of them share a birthday. Not a birth year. Not a birth decade. The exact same month and day. Most people's gut says that's absurd; with 365 days to choose from, surely you'd need close to 183 people, half the calendar, before the odds tip in favor of a match. The gut is wrong, and the reason it's wrong is one of the most useful lessons in all of probability: our intuition is built for counting things, not counting pairs.
This is the birthday problem (often called the birthday paradox, though it isn't a logical paradox at all — just a wildly counterintuitive true fact). It shows up in classrooms as a party trick, and it shows up in cryptography as a genuine security threat. Both come from the same piece of math.
The Concept
Here's the trap: when people estimate this problem, they instinctively ask "what are the odds someone shares my birthday?" That's the wrong question. The actual question is "what are the odds any two of the 23 people share a birthday with each other." That distinction changes everything, because it's not about one comparison — it's about all of them.
With 23 people, the number of possible pairs isn't 23. It's every person compared against every other person: 23 choose 2, which works out to (23 × 22) / 2 = 253 distinct pairs. Two hundred fifty-three separate chances for a match, all drawn from a pool of just 365 days. Suddenly 50-50 odds don't sound so strange.
The cleanest way to compute it is backwards: find the probability that nobody shares a birthday, then subtract from 1. For the first person, any birthday is fine — probability 365/365. The second person just needs to avoid the first person's day: 364/365. The third needs to avoid two taken days: 363/365. And so on, down through the 23rd person, who needs to avoid the 22 birthdays already claimed: 343/365. Multiply that whole chain together:
(365/365) × (364/365) × (363/365) × ... × (343/365) ≈ 0.4927
That's the probability of no shared birthday among 23 people — just under 49.3%. Subtract from 1, and the probability that at least two people do share a birthday is about 50.7%. Cross 23 people and you've crossed the halfway point. At 30 people, the odds climb to about 71%. At 50 people, it's over 97%. At 70, it's effectively certain — better than 99.9%.
The curve is brutally steep near the start precisely because the number of pairs grows quadratically while the pool of days stays fixed at 365. Each new person doesn't just add one more chance for a match; they add a chance against everyone already in the room.
Why It Matters
The birthday problem is famous as a classroom curiosity, but its real teeth are in computer security, where it has a name: the birthday attack.
Cryptographic hash functions take any input — a document, a password, a piece of software — and compress it into a short fixed-length fingerprint. A good hash function should make it computationally infeasible to find two different inputs that produce the same fingerprint (a "collision"). Naively, you might think that with a 160-bit hash (like the once-ubiquitous SHA-1, which produces 2^160 possible outputs), you'd need to try close to 2^160 inputs before finding a collision by luck. But that's the same mistake as guessing 183 people for the birthday problem. Thanks to the same pairwise-comparison math, you actually only need to try roughly the square root of that number — about 2^80 attempts — before two random inputs are more likely than not to collide. Squaring the search space down to its square root sounds like a technicality, but it turns "impossible" into merely "very expensive."
That's exactly what happened to SHA-1. On February 23, 2017, researchers from Google and the Dutch research institute CWI Amsterdam announced "SHAttered," the first publicly demonstrated real-world SHA-1 collision: two different PDF files, visually distinct, that hashed to the identical SHA-1 fingerprint. Producing it took about 9,223,372,036,854,775,808 (nine quintillion) SHA-1 computations — roughly 6,500 CPU-years plus about 110 GPU-years of computation. Expensive, but very much achievable for a well-resourced attacker, and nowhere close to the 2^160 brute-force estimate naive intuition would suggest. The result: SHA-1, which had underpinned digital signatures, TLS certificates, and Git commit hashes for two decades, was formally declared broken for collision-resistance and industry has since moved to SHA-256 and SHA-3.
The birthday problem also quietly governs things far outside cryptography. It explains why hash tables in software start accumulating collisions well before they're full, why random unique IDs (like UUIDs) are deliberately made astronomically long to keep collision odds negligible even across trillions of entries, and why "surprising" coincidences — two people at a wedding with the same rare last name, two students in a lecture hall with the same phone number's last four digits — are actually the expected outcome of enough pairwise comparisons, not evidence of anything mystical.
The Details
It's worth being precise about which birthday question you're asking, because there are two very different versions and conflating them is exactly what fuels the "paradox" feeling.
Question 1 (the classic birthday problem): How many random people do you need before it's more likely than not that some two of them share a birthday? Answer: 23.
Question 2 (the "birthmate" problem): How many random people do you need before it's more likely than not that someone shares your specific birthday? This is a completely different calculation — you're now checking everyone against one fixed target day, not against each other — and the answer balloons to 253 people. That 253, interestingly, is the same number as the pair-count at 23 people (23 choose 2 = 253), a coincidence that trips up even people who've studied the problem before.
The gap between "23" and "253" is the entire lesson of the birthday problem in miniature: fixing one point of comparison (your birthday, a specific target hash) is combinatorially much harder to match than letting any pair match. Attackers exploit this constantly — a birthday attack doesn't try to forge a collision with one specific existing signed document (that's as hard as the 253-person problem, essentially a full brute-force search); it generates a large batch of malicious variants and a large batch of legitimate-looking variants and looks for any collision between the two batches, which is the much easier 23-person-style problem.
The math generalizes cleanly beyond 365 days too. The general formula for the probability of at least one collision among k items drawn from n equally likely categories is:
P(collision) ≈ 1 − e^(−k²/2n)
(This uses the exponential approximation e^(−x) ≈ 1 − x for small x, which holds well here.) Set the target probability to 50% and solve for k, and you get the useful rule of thumb k ≈ 1.1774 × √n. Plug in n = 365 and you get k ≈ 22.49, rounding up to the familiar 23. Plug in n = 2^160 (SHA-1's output space) and you get k ≈ 2^80 — the birthday-attack collision estimate. Same formula, wildly different real-world settings, from party trick to cryptographic vulnerability.
One more twist: the birthday problem is remarkably robust to the assumption that birthdays are uniformly distributed across the year, which they aren't — actual human birth dates cluster somewhat in September in the U.S. (roughly nine months after winter holidays), and are also skewed by hospital scheduling around weekends and holidays. You might expect this to change the answer significantly. It doesn't, much. Non-uniformity in the underlying distribution only ever increases the chance of a collision compared to the perfectly uniform case — clustering makes matches easier to find, never harder — so 23 remains a solid, slightly conservative real-world estimate.
The problem is generally attributed to the English mathematician Harold Davenport, who worked it out informally around 1927 but didn't bother publishing it — by his own account, he assumed something so simple must already be known. The first formal publication of a version of the problem came over a decade later, in 1939, from the Austrian mathematician and philosopher Richard von Mises, who framed a related question about expected numbers of birthday matches in a paper on partition and occupancy probabilities.
Takeaways
- With 23 people, the odds that some two share a birthday cross 50% — not because any one match is likely, but because 23 people generate 253 independent chances for a match.
- Human intuition badly underestimates problems that scale with the number of pairs (which grows roughly as n²) rather than the number of individuals (which grows linearly).
- This same math, scaled up, is the "birthday attack" in cryptography: finding any collision in a hash function takes roughly the square root of the naive brute-force estimate, which is why SHA-1 fell to a real, budgeted attack in 2017.
- Targeting one specific match (your birthday, a specific hash) is a fundamentally harder problem than finding any match among a group — 253 people vs. 23 people is the difference in miniature.
- The formula k ≈ 1.1774 × √n turns this from a party trick into a general-purpose estimation tool for any "how many tries until a coincidence" question.
Resources: - Birthday problem — Wikipedia - CWI & Google: SHAttered, the first SHA-1 collision