birthday: one construct, many systems

The birthday problem is the classic probability result that in a group of only twenty-three people it is more likely than not that two share a birthday, because what matters is the number of pairs, which grows with the square of the group size rather than linearly. More generally, drawing items uniformly from a set of N possibilities, a repeat becomes likely once the number of draws approaches the square root of N. Feller's An Introduction to Probability Theory and Its Applications develops this coincidence counting. The referent is the combinatorics of collisions among random draws from a finite space, the same mathematics that bounds hash collisions in cryptography.[1]

Unit

The probability that two of k random draws from N categories coincide

Recovery means

Not applicable

Measured by

Computed from the number of pairs; a repeat is likely once draws approach the square root of N

A birthday attack applies exactly the birthday problem against a hash function: because collisions become likely after about the square root of the output space, an attacker expects to find two inputs with the same n-bit digest after roughly 2 to the power n/2 evaluations, far fewer than the 2 to the n a naive search would suggest. This birthday bound is why collision resistance demands digests twice as long as the security level sought. Menezes, van Oorschot, and Vanstone's Handbook of Applied Cryptography presents the attack and its bound. It is the identical collision-counting construct as the birthday problem, realised in the system of hash functions.[2]

Unit

Expected work to find a hash collision, about 2^(n/2) for an n-bit digest

Recovery means

Not applicable

Measured by

Quantified by the birthday bound relating collision probability to the number of hash evaluations