A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties. The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes), as described in the birthday problem/paradox.

Understanding the problem
As an example, consider the scenario in which a teacher with a class of 30 students asks for everybody's birthday, to determine whether any two students have the same birthday (corresponding to a hash collision as described below [for simplicity, ignore February 29]). Intuitively, this chance may seem small. If the teacher picked a specific day (say September 16), then the chance that at least one student was born on that specific day is, about 7.9%. However, the probability that at least one student has the same birthday as any other student is around 70% (using the formula for n = 30).

The Mathematics
Given a function, the goal of the attack is to find two different inputs such that a pair is called a collision. The method used to find a collision is simply to evaluate the function for different input values that may be chosen randomly or pseudorandomly until the same result is found more than once. Because of the birthday problem, this method can be rather efficient. Specifically, if a function yields any of different outputs with equal probability and is sufficiently large, then we expect to obtain a pair of different arguments. Then we look to evaluating the function for about different arguments on average. We consider the following experiment. From a set of H values we choose n values uniformly at random thereby allowing repetitions. Let p (n; H) be the probability that during this experiment at least one value is chosen more than once. This probability can be approximated as Let n (p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. By inverting this expression above, we find the following approximation and assigning a 0.5 probability of collision we arrive at let Q (H) be the expected number of values we have to choose before finding the first collision. This number can be approximated, for an example, if a 64-bit hash is used, there are approximately 1.8 × 1019 different outputs. If these are all equally probable (the best case), then it would take 'only' approximately 5 billion attempts (5.1 × 109 ) to generate a collision using brute force. This value is called birthday bound [1] and for n-bit codes it could be computed as 2n/2.

Now if you see that if the outputs of the function are distributed unevenly, then a collision could be found even faster. The notion of 'balance' of a hash function quantifies the resistance of the function to birthday attacks (exploiting uneven key distribution) and allows the vulnerability of popular hashes such as MD and SHA to be estimated (Bellare and Kohno, 2004 [3]). The sub expression in the equation for is not computed accurately for small when directly translated into common programming languages as log (1/ (1-p)) due to loss of significance. When log1p is available (as it is in ANSI C) for example, the equivalent expression -log1p (-p) should be used instead. If this is not done, the first column of the above table is computed as zero, and several items in the second column do not have even one correct significant digit.

References
• Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks. EUROCRYPT
2004: pp401–418
• Applied Cryptography, 2nd ed. by Bruce Schneierms in the second column do not have even one correct significant digit.