Birthday attack

From Wikipedia, the free encyclopedia

A birthday attack is a type of cryptographic attack which exploits the mathematics behind the birthday paradox, making use of a space-time tradeoff. Specifically, if a function $f (x)$ yields any of $H$ different outputs with equal probability and $H$ is sufficiently large, then after evaluating the function for about $1.2 \cdot \sqrt H$ different arguments we expect to obtain a pair of different arguments $x 1$ and $x 2$ with $f (x 1) = f (x 2)$ , known as a collision.

1 The mathematics
2 See also
3 References
4 External links

[edit] The mathematics

To show this, we start with the Taylor series approximation to the probability of two people having the same birthday. In this case, replace the number of days in a year with the number of unique outputs, $H$ :

$p(n) = 1-\bar p(n) \approx 1 - e^{-(n(n-1))/2 \cdot H} \approx 1-e^{-n^2/{2 \cdot H}},$

where $n$ is the number of attempts at a collision. Inverting this expression,

$n(p)\approx \sqrt{2\cdot H\cdot\ln\left({1 \over 1-p}\right)},$

and assigning a 0.5 probability of collision we arrive at

$n(0.5) = 1.1774 \sqrt 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 and for n-bit codes it could be computed as $2 n / 2$ .^[1] Other examples are as follows:

Bits	Possible outputs	Desired probability of random collision
Bits	Possible outputs	10^-12	10^-9	10^-6	0.1%	1%	25%	50%	75%
64	1.8 × 10¹⁹	6.1 × 10³	1.9 × 10⁵	6.1 × 10⁶	1.9 × 10⁸	6.1 × 10⁸	3.3 × 10⁹	5.1 × 10⁹	7.2 × 10⁹
128	3.4 × 10³⁸	2.6 × 10¹³	8.2 × 10¹⁴	2.6 × 10¹⁶	8.3 × 10¹⁷	2.6 × 10¹⁸	1.4 × 10¹⁹	2.2 × 10¹⁹	3.1 × 10¹⁹
256	1.2 × 10⁷⁷	4.8 × 10³²	1.5 × 10³⁴	4.8 × 10³⁵	1.5 × 10³⁷	4.8 × 10³⁷	2.6 × 10³⁸	4.0 × 10³⁸	5.7 × 10³⁸
384	3.9 × 10¹¹⁵	8.9 × 10⁵¹	2.8 × 10⁵³	8.9 × 10⁵⁴	2.8 × 10⁵⁶	8.9 × 10⁵⁶	4.8 × 10⁵⁷	7.4 × 10⁵⁷	1.0 × 10⁵⁸
512	1.3 × 10¹⁵⁴	1.6 × 10⁷¹	5.2 × 10⁷²	1.6 × 10⁷⁴	5.2 × 10⁷⁵	1.6 × 10⁷⁶	8.8 × 10⁷⁶	1.4 × 10⁷⁷	1.9 × 10⁷⁷

Table shows number of hashes needed to achieve the given probability of success, assuming all hashes are equally likely. For comparison, the uncorrectable bit error rate of a typical hard disk is 10^-18 to 10^-15.^{[citation needed]}

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 $m$ is typically signed by first computing $f (m)$ , where $f$ is a cryptographic hash function, and then using some secret key to sign $f (m)$ . Suppose Alice wants to trick Bob into signing a fraudulent contract. Alice prepares a fair contract $m$ and a fraudulent one $m'$ . 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'$ . 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 (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 -- in other words, Alice compares the new fair hash is compared to all previous fraudulent hashes, and the new fraudulent contract to all previous fair hashes -- Alice doesn't bother comparing fair-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. It has also been recommended (Schneier, p. 430) that Bob cosmetically modify any contract presented to him before signing.

The birthday attack can also be used to speed up the computation of discrete logarithms. Suppose $x$ and $y$ are elements of some group and $y$ is a power of $x$ . We want to find the exponent of $x$ that gives $y$ . A birthday attack computes $x r$ for many randomly chosen integers $r$ and computes $y x - s$ for many randomly chosen integers $s$ . After a while, a match will be found: $x r = y x - s$ which means $y = x r + s$ .

If the group has $n$ elements, then the naive method of trying out all exponents takes about $n / 2$ steps on average; the birthday attack is considerably faster and takes fewer than $2 \sqrt n$ steps on average.

Techniques based on repeated iteration, such as rainbow tables, can greatly reduce the storage requirements of birthday attacks.

[edit] See also

Meet-in-the-middle attack

[edit] 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

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

[edit] 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

Cryptographic hash functions and Message authentication codes (MACs) v • d • e
Hash algorithms: Gost-Hash \| HAS-160 \| HAS-V \| HAVAL \| MDC-2 \| MD2 \| MD4 \| MD5 \| N-Hash \| RadioGatún \| RIPEMD \| SHA family \| Snefru \| Tiger \| VEST \| WHIRLPOOL \| crypt(3) DES
MAC algorithms: DAA \| CBC-MAC \| HMAC \| OMAC/CMAC \| PMAC \| UMAC \| Poly1305-AES \| VEST
Authenticated encryption modes: CCM \| EAX \| GCM \| OCB \| VEST Attacks: Birthday attack \| Collision attack \| Preimage attack \| Rainbow table \| Brute force attack
Standardization: CRYPTREC \| NESSIE Misc: Avalanche effect \| Hash collision \| Hash functions based on block ciphers
Cryptography v • d • e
History of cryptography \| Cryptanalysis \| Cryptography portal \| Topics in cryptography
Symmetric-key algorithm \| Block cipher \| Stream cipher \| Public-key cryptography \| Cryptographic hash function \| Message authentication code \| Random numbers