THE FOLD / CHEAT / THE BACKDOOR / THE BIRTHDAY ATTACK
THE BIRTHDAY ATTACK
half the bits, all the security
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Finding a collision is enormously easier than finding a collision with a particular value. Hunting a specific hash takes about N tries; hunting any coincidental pair takes about √N, because the number of pairs grows quadratically. That square root is why a 128-bit digest offers 64 bits of collision resistance, why MD5 fell in 2004, and why doubling the output length is the only fix.
LIT verified live: with 365 slots, 23 draws collide with probability 0.5072972343 from the exact product formula, and 60,000 simulated trials give 0.508683 — 0.68 standard errors away. The half-chance threshold divided by √N converges to √(2 ln 2) = 1.177410, measured at 1.203875, 1.187500, 1.179688, 1.177734, 1.177490 for N from 365 up to 16,777,216. Multiplying the space by 256 multiplies the work by only 15.970199. The mean number of draws to a first collision is 24.605 against √(πN/2) + 2/3 = 24.611.
LIT verified live: with 365 slots, 23 draws collide with probability 0.5072972343 from the exact product formula, and 60,000 simulated trials give 0.508683 — 0.68 standard errors away. The half-chance threshold divided by √N converges to √(2 ln 2) = 1.177410, measured at 1.203875, 1.187500, 1.179688, 1.177734, 1.177490 for N from 365 up to 16,777,216. Multiplying the space by 256 multiplies the work by only 15.970199. The mean number of draws to a first collision is 24.605 against √(πN/2) + 2/3 = 24.611.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE BACKDOOR: the square root is not a flaw in any hash function, it is a door in the shape of the problem.
AVAN (AI) asserted the threshold was 1.1774√N “at every scale” and the sweep refused it: at N = 365 the ratio is 1.2039, and demanding 1.1774 there fails on arithmetic that is entirely correct. The constant is a limit, and it is exactly √(2 ln 2) rather than a decimal worth memorising. The right test is monotone convergence toward it, which the measurements show cleanly. A second correction followed: the expected wait to a first collision is not √(πN/2) but that plus 2/3, and the measured 24.605 sits on the corrected value rather than the leading term. Both errors were the same shape — treating an asymptotic form as an identity.
AVAN (AI) asserted the threshold was 1.1774√N “at every scale” and the sweep refused it: at N = 365 the ratio is 1.2039, and demanding 1.1774 there fails on arithmetic that is entirely correct. The constant is a limit, and it is exactly √(2 ln 2) rather than a decimal worth memorising. The right test is monotone convergence toward it, which the measurements show cleanly. A second correction followed: the expected wait to a first collision is not √(πN/2) but that plus 2/3, and the measured 24.605 sits on the corrected value rather than the leading term. Both errors were the same shape — treating an asymptotic form as an identity.
3 ONE DIMENSION
Collision probability against the number of draws. The rise is sharper than it looks it should be.
4 TWO DIMENSIONS · INTERACTIVE
Grow the space by a factor and watch the work grow by its square root.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: draws as points, and the pairs between them.
AVAN’s addition (the inverse-companion): the forward reading is “collisions are easier than you expect.” The inverse is that the expectation was formed by counting the wrong objects. Intuition counts people and the problem is about pairs, and k people carry k(k−1)/2 pairs — so the quantity that matters is already quadratic before any probability is involved. Read backwards, the birthday paradox is not a fact about coincidence but about which set you were implicitly enumerating, and the square root is simply that quadratic seen from the other side.
LIT with 365 slots, 23 draws collide with probability 0.5072972343 from the exact product formula, and 60,000 simulated trials give 0.508683, which is 0.68 standard errors away; the half-chance threshold divided by sqrt(N) converges to sqrt(2 ln 2) = 1.177410, measured at 1.203875, 1.187500, 1.179688, 1.177734, 1.177490 for N from 365 up to 16,777,216; multiplying the space by 256 multiplies the work by only 15.970199; and the mean draws to a first collision is 24.605 against sqrt(pi N / 2) + 2/3 = 24.611
FIG The threshold was asserted to be 1.1774 sqrt(N) 'at every scale' and the sweep refused it: at N = 365 the ratio is 1.2039, and demanding 1.1774 there fails on arithmetic that is entirely correct. The constant is a LIMIT, and it is exactly sqrt(2 ln 2) rather than a decimal worth memorising; the right test is monotone convergence toward it. A second correction followed: the expected wait to a first collision is not sqrt(pi N / 2) but that plus 2/3, and the measured 24.605 sits on the corrected value rather than the leading term. Both errors were the same shape - treating an asymptotic form as an identity.
FIG The threshold was asserted to be 1.1774 sqrt(N) 'at every scale' and the sweep refused it: at N = 365 the ratio is 1.2039, and demanding 1.1774 there fails on arithmetic that is entirely correct. The constant is a LIMIT, and it is exactly sqrt(2 ln 2) rather than a decimal worth memorising; the right test is monotone convergence toward it. A second correction followed: the expected wait to a first collision is not sqrt(pi N / 2) but that plus 2/3, and the measured 24.605 sits on the corrected value rather than the leading term. Both errors were the same shape - treating an asymptotic form as an identity.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE BACKDOOR · David Lee Wise (ROOT0), with AVAN