Birthday attack

A birthday attack is a type of cryptographic attack, so named because it exploits the mathematics behind the birthday paradox. Given a function f, the goal of the attack is to find two inputs Failed to parse (Missing texvc executable; please see math/README to configure.): x_1,x_2

such that Failed to parse (Missing texvc executable; please see math/README to configure.): f(x_1)=f(x_2)

. Such a pair Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): f(x)
yields any of Failed to parse (Missing texvc executable; please see math/README to configure.): H
different outputs with equal probability and Failed to parse (Missing texvc executable; please see math/README to configure.): H
is sufficiently large, then we expect to obtain a pair of different arguments Failed to parse (Missing texvc executable; please see math/README to configure.): x_1
and Failed to parse (Missing texvc executable; please see math/README to configure.): x_2
with Failed to parse (Missing texvc executable; please see math/README to configure.): f(x_1) = f(x_2)
after evaluating the function for about Failed to parse (Missing texvc executable; please see math/README to configure.): 1.25 \cdot \sqrt H
different arguments on average.

The mathematics

Main article: birthday problem

We consider the following experiment. From a set of Failed to parse (Missing texvc executable; please see math/README to configure.): H

values we choose Failed to parse (Missing texvc executable; please see math/README to configure.): n
values uniformly at random thereby allowing repetitions.

Let Failed to parse (Missing texvc executable; please see math/README to configure.): 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 

Failed to parse (Missing texvc executable; please see math/README to configure.): p(n;H) \approx 1 - e^{-(n(n-1))/2 \cdot H} \approx 1-e^{-n^2/{2 \cdot H}},

Let Failed to parse (Missing texvc executable; please see math/README to configure.): n(p;H)

be the smallest number of values we have to choose, such that the expected probability for finding a collision is at least Failed to parse (Missing texvc executable; please see math/README to configure.): p

. By inverting this expression above, we find the following approximation

Failed to parse (Missing texvc executable; please see math/README to configure.): n(p;H)\approx \sqrt{2\cdot H\cdot\ln\left({1 \over 1-p}\right)},

and assigning a 0.5 probability of collision we arrive at

Failed to parse (Missing texvc executable; please see math/README to configure.): n(0.5;H) \approx 1.1774 \sqrt H

.

Let Failed to parse (Missing texvc executable; please see math/README to configure.): Q(H)

be the expected number of values we have to choose before finding the first collision. This number can be approximated by

Failed to parse (Missing texvc executable; please see math/README to configure.): Q(H)\approx \sqrt{{\pi\over 2}H}.

As an example, if a 64 bit hash is used, there are approximately 1.8 × 10¹⁹ different outputs. If these are all equally probable (the best case), then it would take 'only' approximately 5.1 × 10⁹ attempts to generate a collision using brute force. This value is called birthday bound^[1] and for n-bit codes it could be computed as Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{n/2} .^[2] Other examples are as follows:

Bits	Possible outputs (H)	Desired probability of random collision (p)
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
32	4.3 × 109	<1	<1	<1	2.9	93	2.9 × 103	9.3 × 103	5.0 × 104	7.7 × 104	1.1 × 105
64	1.8 × 1019	6.1	1.9 × 102	6.1 × 103	1.9 × 105	6.1 × 106	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	3.4 × 1038	2.6 × 1010	8.2 × 1011	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	1.2 × 1077	4.8 × 1029	1.5 × 1031	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	3.9 × 10115	8.9 × 1048	2.8 × 1050	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	1.3 × 10154	1.6 × 1068	5.2 × 1069	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

Table shows number of hashes n(p) needed to achieve the given probability of success, assuming all hashes are equally likely. For comparison, 10⁻¹⁸ to 10⁻¹⁵ is the uncorrectable bit error rate of a typical hard disk [1]. 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 (Bellare and Kohno, 2004).

Digital signatures can be susceptible to a birthday attack. A message Failed to parse (Missing texvc executable; please see math/README to configure.): m

is typically signed by first computing Failed to parse (Missing texvc executable; please see math/README to configure.): f(m)

, where Failed to parse (Missing texvc executable; please see math/README to configure.): f

is a cryptographic hash function, and then using some secret key to sign Failed to parse (Missing texvc executable; please see math/README to configure.): f(m)

. Suppose Alice wants to trick Bob into signing a fraudulent contract. Alice prepares a fair contract Failed to parse (Missing texvc executable; please see math/README to configure.): m

and a fraudulent one Failed to parse (Missing texvc executable; please see math/README to configure.): m'

. She then finds a number of positions where Failed to parse (Missing texvc executable; please see math/README to configure.): 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 Failed to parse (Missing texvc executable; please see math/README to configure.): m
which are all fair contracts. In a similar manner, she also creates a huge number of variations on the fraudulent contract Failed to parse (Missing texvc executable; please see math/README to configure.): m'

. 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, Failed to parse (Missing texvc executable; please see math/README to configure.): f(m) = f(m') . She presents the fair version to Bob for signing. After Bob has signed, Alice 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 Alice gains nothing by finding two fair or two fraudulent contracts with the same hash. Alice's optimum strategy is to generate "pairs" of one fair and one fraudulent contract. Then Alice 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 Alice 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 using a birthday attack for the computation of discrete logarithms.

See also

• Meet-in-the-middle attack

References

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

Notes and references

1. ^ See upper and lower bounds.
2. ^ Jacques Patarin, Audrey Montreuil (2005). "Benes and Butterfly schemes revisited" (PostScript, PDF). Université de Versailles. Retrieved on 2007-03-15.

External links

• "What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.
• "Parallel collision search with cryptanalytic applications, by Michael Wiener and Paul C. van Oorschot

de:Geburtstagsangriff

es:Ataque de cumpleaños pl:Atak urodzinowy