A birthday attack is a bruteforce collision 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). Let ${\textstyle H}$ be the number of possible values of a hash function, with ${\textstyle H=2^{l}}$. With a birthday attack, it is possible to find a collision of a hash function with ${\textstyle 50\%}$ chance in ${\textstyle {\sqrt {2^{l}}}=2^{l/2},}$ where ${\textstyle l}$ is the bit length of the hash output, and with ${\textstyle 2^{l-1}}$ being the classical preimage resistance security with the same probability. There is a general (though disputed) result that quantum computers can perform birthday attacks, thus breaking collision resistance, in ${\textstyle {\sqrt[{3}]{2^{l}}}=2^{l/3}}$.

Although there are some digital signature vulnerabilities associated with the birthday attack, it cannot be used to break an encryption scheme any faster than a brute-force attack.

As an example, consider the scenario in which a teacher with a class of 30 students (n = 30) asks for everybody's birthday (for simplicity, ignore leap years) to determine whether any two students have the same birthday (corresponding to a hash collision as described further). Intuitively, this chance may seem small. Counter-intuitively, the probability that at least one student has the same birthday as any other student on any day is around 70% (for n = 30), from the formula ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$.

If the teacher had picked a specific day (say, 16 September), then the chance that at least one student was born on that specific day is ${\displaystyle 1-(364/365)^{30}}$, about 7.9%.

In a birthday attack, the attacker prepares many different variants of benign and malicious contracts, each having a digital signature. A pair of benign and malicious contracts with the same signature is sought. In this fictional example, suppose that the digital signature of a string is the first byte of its SHA-256 hash. The pair found is indicated in green – note that finding a pair of benign contracts (blue) or a pair of malicious contracts (red) is useless. After the victim accepts the benign contract, the attacker substitutes it with the malicious one and claims the victim signed it, as proven by the digital signature.

The birthday attack can be modelled as a variation of the balls into bins problem, where balls (hash function inputs) are randomly placed into bins (hash function outputs). A hash collision occurs when at least two balls are placed into the same bin.

Given a function ${\displaystyle f}$, the goal of the attack is to find two different inputs ${\displaystyle x_{1},x_{2}}$ such that ${\displaystyle f(x_{1})=f(x_{2})}$. Such a pair ${\displaystyle x_{1},x_{2}}$ is called a collision. The method used to find a collision is simply to evaluate the function ${\displaystyle f}$ 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 ${\displaystyle f(x)}$ yields any of ${\displaystyle H}$ different outputs with equal probability and ${\displaystyle H}$ is sufficiently large, then we expect to obtain a pair of different arguments ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ with ${\displaystyle f(x_{1})=f(x_{2})}$ after evaluating the function for about ${\displaystyle 1.25{\sqrt {H}}}$ 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