# Birthday attack

Birthday attack

A birthday attack is a type of cryptographic attack, so named because it exploits the mathematics behind the birthday problem in probability theory. Given a function "f", the goal of the attack is to find two inputs $x_1,x_2$ such that $f\left(x_1\right)=f\left(x_2\right)$. Such a pair $x_1,x_2$ is called a collision. The method used to find a collision is to simply evaluate the function "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 paradox this method can be rather efficient. Specifically, if a function $f\left(x\right)$ yields any of $H$ different outputs with equal probability and $H$ is sufficiently large, then we expect to obtain a pair of different arguments $x_1$ and $x_2$ with $f\left(x_1\right) = f\left(x_2\right)$ after evaluating the function for about $1.25 cdot sqrt H$ different arguments on average.

The mathematics

We consider the following experiment. From a set of $H$ values we choose $n$ values uniformly at random thereby allowing repetitions.Let $p\left(n;H\right)$ be the probability that during this experiment at least one value is chosen more than once. This probability can be approximated as ::$p\left(n;H\right) approx 1 - e^\left\{-\left(n\left(n-1\right)\right)/2 cdot H\right\} approx 1-e^\left\{-n^2/\left\{2 cdot H,$

Let $n\left(p;H\right)$ be the smallest number of values we have to choose, such that the expected probability for finding a collision is at least $p$.By inverting this expression above, we find the following approximation

::$n\left(p;H\right)approx sqrt\left\{2cdot Hcdotlnleft\left(\left\{1 over 1-p\right\} ight\right)\right\},$

and assigning a 0.5 probability of collision we arrive at ::$n\left(0.5;H\right) approx 1.1774 sqrt H$.

Let $Q\left(H\right)$ be the expected number of values we have to choose before finding the first collision. This number can be approximated by

::$Q\left(H\right)approx sqrt$piover 2}H}.

As 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.1 × 109 attempts to generate a collision using brute force. This value is called birthday bound [See upper and lower bounds.] and for n-bit codes it could be computed as $2^\left\{n/2\right\}$. [cite paper
author = Jacques Patarin, Audrey Montreuil
title = Benes and Butterfly schemes revisited
version =
publisher = Université de Versailles
date = 2005
url = http://eprint.iacr.org/2005/004
format = PostScript, PDF
accessdate = 2007-03-15
] Other examples are as follows: ::"Table shows number of hashes" n(p) "needed to achieve the given probability of success, assuming all hashes are equally likely. For comparison, 10−18 to 10−15 is the uncorrectable bit error rate of a typical hard disk [http://arxiv.org/abs/cs/0701166] . In theory, MD5, 128 bits, should stay within that range until about 820 billion documents, even if its possible outputs are many more."

It is easy to see that if the outputs of the function are distributed unevenly, then a collision can be found even faster. The notion of 'balance' of a hash function quantifies the resistance of the function to birthday attacks and allows the vulnerability of popular hashes such as MD and SHA to be estimated ( [http://citeseer.ist.psu.edu/bellare02hash.html Bellare and Kohno, 2004] ).

Digital signatures can be susceptible to a birthday attack. A message $m$ is typically signed by first computing $f\left(m\right)$, where $f$ is a cryptographic hash function, and then using some secret key to sign $f\left(m\right)$. Suppose Mary wants to trick Bob into signing a fraudulent contract. Mary prepares a fair contract $m$ and a fraudulent one $m\text{'}$. She then finds a number of positions where $m$ can be changed without changing the meaning, such as inserting commas, empty lines, one versus two spaces after a sentence, replacing synonyms, etc. By combining these changes, she can create a huge number of variations on $m$ which are all fair contracts. In a similar manner, she also creates a huge number of variations on the fraudulent contract $m\text{'}$. She then applies the hash function to all these variations until she finds a version of the fair contract and a version of the fraudulent contract which have the same hash value, $f\left(m\right) = f\left(m\text{'}\right)$. She presents the fair version to Bob for signing. After Bob has signed, Mary takes the signature and attaches it to the fraudulent contract. This signature then "proves" that Bob signed the fraudulent contract. This differs slightly from the original birthday problem, as Mary gains nothing by finding two fair or two fraudulent contracts with the same hash. Mary's optimum strategy is to generate "pairs" of one fair and one fraudulent contract.Then Mary compares each freshly-generated pair to all other pairs; that is, she compares the new fair hash to all previous fraudulent hashes, and the new fraudulent contract to all previous fair hashes (but doesn't bother comparing fair hashes to fair or fraudulent to fraudulent). The birthday problem equations apply where "n" is the number of pairs. (The number of hashes Mary actually generates is 2n.)

To avoid this attack, the output length of the hash function used for a signature scheme can be chosen large enough so that the birthday attack becomes computationally infeasible, i.e. about twice as many bits as are needed to prevent an ordinary brute force attack.

Pollard's rho algorithm for logarithms is an example for an algorithm usinga birthday attack for the computation of discrete logarithms.

ee also

* Meet-in-the-middle attack

References

* Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp401&ndash;418
* "Applied Cryptography, 2nd ed." by Bruce Schneier

Notes and references

* [http://www.rsasecurity.com/rsalabs/node.asp?id=2182 "What is a digital signature and what is authentication?"] from RSA Security's crypto FAQ.
* [http://www.certainkey.com/dnet/acmccs94.pdf "Parallel collision search with cryptanalytic applications] , by Michael Wiener and Paul C. van Oorschot

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• birthday attack — noun A method of code decryption which exploits the so called birthday paradox …   Wiktionary

• Birthday problem — In probability theory, the birthday problem, [This is not a paradox in the sense of leading to a logical contradiction, but is called a paradox because the mathematical truth contradicts naïve intuition: most people estimate that the chance is… …   Wikipedia

• Birthday — For other uses, see Birthday (disambiguation). Candles spell out the traditional English birthday greeting A birthday is a day or anniversary where a person celebrates his or her date of birth. Birthdays are celebrated in numerous cultures, often …   Wikipedia

• Attack of the Killer Kung-Fu Wolf Bitch — Infobox Boondocks Episode Title = Attack of the Killer Kung Fu Wolf Bitch Caption = Robert s date, Luna, going against Huey in a friendly sparring match . Airdate = November 19, 2007 Season no. = 2 Episode no. = 21 Production no. = 207 Writer =… …   Wikipedia

• Birthday Cake Interview — The Birthday Cake Interview refers to a famous political interview in Australia that was carried out between interviewer Mike Willesee and Liberal Party Opposition Leader Dr John Hewson shortly before the 1993 federal election. It is remembered… …   Wikipedia

• Collision attack — In cryptography, a collision attack on a cryptographic hash tries to find two arbitrary inputs that will produce the same hash value, i.e. a hash collision. In contrast to a preimage attack, neither the hash value nor one of the inputs is… …   Wikipedia

• Meet-in-the-middle attack — Not to be confused with man in the middle attack. The meet in the middle attack is a cryptographic attack which, like the birthday attack, makes use of a space time tradeoff. While the birthday attack attempts to find two values in the domain of… …   Wikipedia

• Preimage attack — In cryptography, a preimage attack on a cryptographic hash is an attempt to find a message that has a specific hash value. There are two types of preimage attacks:* First preimage attack : given a hash h , find a message m such that hash(m) = h …   Wikipedia

• Correlation attack — In cryptography, correlation attacks are a class of known plaintext attacks for breaking stream ciphers whose keystream is generated by combining the output of several linear feedback shift registers (called LFSRs for the rest of this article)… …   Wikipedia

• Stream cipher attack — Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive or operation (xor), can be very secure if used properly. However they are vulnerable to attack if certain precautions are not followed:*keys must never be… …   Wikipedia