What is a birthday attack?

A birthday attack is a name used to refer to a class of brute-force attacks. It gets its name from the surprising result that the probability that two or more people in a group of 23 share the same birthday is greater than 1/2; such a result is called a birthday paradox.

If some function, when supplied with a random input, returns one of k equally-likely values, then by repeatedly evaluating the function for different inputs, we expect to obtain the same output after about 1.2k^1/2. For the above birthday paradox, replace k with 365.

Birthday attacks are often used to find collisions of hash functions (see Question 96).

| Question 96|