Birthday bound and brute force

How it works

Among $k$ values drawn uniformly from $N$ possibilities, the probability that two are equal is $1 - \prod_{i=1}^{k-1} (1 - i/N)$. Since $1 - x \approx e^{-x}$, it is about $1 - e^{-k(k-1)/(2N)}$, and it reaches 50% near $k \approx 1.1774 \sqrt{N}$. With $N = 365$ birthdays, 23 people suffice.

This square root is the birthday bound of cryptography: a generic collision attack on an $n$-bit hash needs only about $2^{n/2}$ evaluations, so SHA-256 offers 128 bits of collision resistance. The same bound limits block cipher modes: with a 64-bit block size, as in 3DES, ciphertext blocks start to repeat after about $2^{32}$ blocks (the Sweet32 attack).

Brute force search for a $b$-bit key tries up to $2^b$ keys, $2^{b-1}$ on average. A 56-bit DES key falls in days with dedicated hardware, while $2^{128}$ is far out of reach for any classical computer. Grover’s algorithm would reduce key search to about $2^{b/2}$ quantum steps, which is why 256-bit keys are recommended for long-term protection; public key schemes based on factoring or discrete logarithms would be broken outright by Shor’s algorithm.