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 different arguments we expect to obtain a pair of different arguments x₁ and x₂ with f(x₁) = f(x₂), known as a collision. The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write) is the study of message secrecy. ... Mathematics is commonly defined as the study of patterns of structure, change, and space; more informally, one might say it is the study of figures and numbers. Mathematical knowledge is constantly growing, through research and application, but mathematics itself is not usually considered a natural science. ... In probability theory, the birthday paradox states that given a group of 23 (or more) randomly chosen people, the probability is more than 50% that at least two of them will have the same birthday. ... In computer science, a space-time or time-memory trade-off is a situation where the programmer can reduce memory use at the cost of slower program execution, or can reduce computation time at the cost of increased memory use. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... In computer science, a hash collision is a situation that occurs when two distinct inputs into a hash function produce identical outputs. ...

The mathematics

To show this, we start with the Taylor series approximation to the probability p(n) of two people having the same birthday given n, the number of random people. In this case, replace the number of days in a year with the number of unique outputs, H, and consider n to be the number of random inputs: As the degree of the Taylor series rises, it approaches the correct function. ...

Inverting this expression, we find

and assigning a 0.5 probability of collision we arrive at

.

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 (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). In cryptography, MD5 (Message-Digest algorithm 5) is a widely used cryptographic hash function with a 128-bit hash value. ...

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; 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). In cryptography, a digital signature or digital signature scheme is a type of asymmetric cryptography used to simulate the security properties of a signature in digital, rather than written, form. ... In cryptography, a cryptographic hash function is a hash function with certain additional security properties to make it suitable for use as a primitive in various information security applications, such as authentication and message integrity. ... The names Alice and Bob are commonly used placeholders for archetypal characters in fields such as cryptography and physics. ...

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. The EFFs US$250,000 DES cracking machine contained over 1,800 custom chips and could brute force a DES key in a matter of days — the photograph shows a DES Cracker circuit board fitted with several Deep Crack chips. ...

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 yx ^{− s} for many randomly chosen integers s. After a while, a match will be found: x^r = yx ^{− s} which means y = x^{r + s}. In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. ... This picture illustrates how the hours in a clock form a group. ...

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 steps on average.

Techniques based on repeated iteration, such as rainbow tables, can greatly reduce the storage requirements of birthday attacks. A rainbow table is a special type of lookup table that is constructed by placing a plaintext password entry in a chain of keys and cyphertexts, generated by a one-way hash. ...

See also

• Meet-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. ...

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

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

Mihir Bellare is a cryptographer at the University of California, San Diego. ... Eurocrypt (or EUROCRYPT) is an important conference for cryptography research. ... Bruce Schneier Bruce Schneier (born January 15, 1963) is an American cryptographer, computer security specialist, and writer. ... Bruce Schneier Bruce Schneier (born January 15, 1963) is an American cryptographer, computer security specialist, and writer. ... 2005 (MMV) was a common year starting on Saturday of the Gregorian calendar. ... PostScript (PS) is a page description language and programming language used primarily in the electronic and desktop publishing areas. ... PDF is an abbreviation with several meanings: Portable Document Format Post-doctoral fellowship Probability density function There also is an electronic design automation company named PDF Solutions. ... 2007 (MMVII) is the current year, a common year starting on Monday of the Gregorian calendar and the AD/CE era. ... March 15 is the 74th day of the year in the Gregorian calendar (75th in leap years). ...

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