Birthday attack

Last updated January 22, 2025

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,^[1]^[2] and with ${\textstyle 2^{l-1}}$ being the classical preimage resistance security with the same probability.^[2] There is a general (though disputed^[3]) result that quantum computers can perform birthday attacks, thus breaking collision resistance, in ${\textstyle {\sqrt[{3}]{2^{l}}}=2^{l/3}}$ .^[4]

Understanding the problem

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 $1-{\frac {365!}{(365-n)!\cdot 365^{n}}}$ .^[6]

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 $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.

Relation to the balls into bins problem

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.

Mathematics

Given a function $f$ , the goal of the attack is to find two different inputs $x_{1},x_{2}$ such that $f(x_{1})=f(x_{2})$ . Such a pair $x_{1},x_{2}$ is called a collision. The method used to find a collision is simply to 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 problem, this method can be rather efficient. Specifically, if a function $f(x)$ 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(x_{1})=f(x_{2})$ after evaluating the function for about $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

p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}

^[7]

where $n$ is the number of chosen values (inputs) and $H$ is the number of possible outcomes (possible hash outputs).

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

n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}

and assigning a 0.5 probability of collision we arrive at

n(0.5;H)\approx 1.1774{\sqrt {H}}

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

Q(H)\approx {\sqrt {{\frac {\pi }{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 billion attempts (5.38×10⁹) to generate a collision using brute force.^[8] This value is called birthday bound^[9] and it could be approximated as 2^l/2, where l is the number of bits in H.^[10] Other examples are as follows:

Bits	Possible outputs (H)	Desired probability of random collision (2 s.f.) (p)
Bits	Possible outputs (H)	10⁻¹⁸	10⁻¹⁵	10⁻¹²	10⁻⁹	10⁻⁶	0.1%	1%	25%	50%	75%
16	2¹⁶ (~6.5 x 10⁴)	<2	<2	<2	<2	<2	11	36	190	300	430
32	2³² (~4.3×10⁹)	<2	<2	<2	3	93	2900	9300	50,000	77,000	110,000
64	2⁶⁴ (~1.8×10¹⁹)	6	190	6100	190,000	6,100,000	1.9×10⁸	6.1×10⁸	3.3×10⁹	5.1×10⁹	7.2×10⁹
96	2⁹⁶ (~7.9×10²⁸)	4.0×10⁵	1.3×10⁷	4.0×10⁸	1.3×10¹⁰	4.0×10¹¹	1.3×10¹³	4.0×10¹³	2.1×10¹⁴	3.3×10¹⁴	4.7×10¹⁴
128	2¹²⁸ (~3.4×10³⁸)	2.6×10¹⁰	8.2×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¹⁹
192	2¹⁹² (~6.3×10⁵⁷)	1.1×10²⁰	3.7×10²¹	1.1×10²³	3.5×10²⁴	1.1×10²⁶	3.5×10²⁷	1.1×10²⁸	6.0×10²⁸	9.3×10²⁸	1.3×10²⁹
256	2²⁵⁶ (~1.2×10⁷⁷)	4.8×10²⁹	1.5×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	2³⁸⁴ (~3.9×10¹¹⁵)	8.9×10⁴⁸	2.8×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	2⁵¹² (~1.3×10¹⁵⁴)	1.6×10⁶⁸	5.2×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 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.^[11] In theory, MD5 hashes or UUIDs, being roughly 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 could be found even faster. The notion of 'balance' of a hash function quantifies the resistance of the function to birthday attacks (exploiting uneven key distribution.) However, determining the balance of a hash function will typically require all possible inputs to be calculated and thus is infeasible for popular hash functions such as the MD and SHA families.^[12] The subexpression $\ln {\frac {1}{1-p}}$ in the equation for $n(p;H)$ is not computed accurately for small $p$ when directly translated into common programming languages as log(1/(1-p)) due to loss of significance. When log1p is available (as it is in C99) for example, the equivalent expression -log1p(-p) should be used instead.^[13] If this is not done, the first column of the above table is computed as zero, and several items in the second column do not have even one correct significant digit.

Simple approximation

A good rule of thumb which can be used for mental calculation is the relation

p(n)\approx {n^{2} \over 2H}

which can also be written as

H\approx {n^{2} \over 2p(n)}

.

or

n\approx {\sqrt {2H\times p(n)}}

.

This works well for probabilities less than or equal to 0.5.

This approximation scheme is especially easy to use when working with exponents. For instance, suppose you are building 32-bit hashes ( $H=2^{32}$ ) and want the chance of a collision to be at most one in a million ( $p\approx 2^{-20}$ ), how many documents could we have at the most?

n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5

which is close to the correct answer of 93.

Digital signature susceptibility

Digital signatures can be susceptible to a birthday attack or more precisely a chosen-prefix collision 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 Mallory wants to trick Bob into signing a fraudulent contract. Mallory 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, Mallory 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, Mallory takes the signature and attaches it to the fraudulent contract. This signature then "proves" that Bob signed the fraudulent contract.

The probabilities differ slightly from the original birthday problem, as Mallory gains nothing by finding two fair or two fraudulent contracts with the same hash. Mallory's strategy is to generate pairs of one fair and one fraudulent contract. For a given hash function $2^{l}$ is the number of possible hashes, where $l$ is the bit length of the hash output. The birthday problem equations do not exactly apply here. For a 50% chance of a collision, Mallory would need to generate approximately $2^{(l/2)+1}$ hashes, which is twice the number required for a simple collision under the classical birthday problem.

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.

Besides using a larger bit length, the signer (Bob) can protect himself by making some random, inoffensive changes to the document before signing it, and by keeping a copy of the contract he signed in his own possession, so that he can at least demonstrate in court that his signature matches that contract, not just the fraudulent one.

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

Reverse attack

The same fraud is possible if the signer is Mallory, not Bob. Bob could suggest a contract to Mallory for a signature. Mallory could find both an inoffensively-modified version of this fair contract that has the same signature as a fraudulent contract, and Mallory could provide the modified fair contract and signature to Bob. Later, Mallory could produce the fraudulent copy. If Bob doesn't have the inoffensively-modified version contract (perhaps only finding their original proposal), Mallory's fraud is perfect. If Bob does have it, Mallory can at least claim that it is Bob who is the fraudster.

Notes

↑ "Avoiding collisions, Cryptographic hash functions" (PDF). Foundations of Cryptography, Computer Science Department, Wellesley College.
1 2 Dang, Q H (2012). Recommendation for applications using approved hash algorithms (Report). Gaithersburg, MD: National Institute of Standards and Technology.
↑ Daniel J. Bernstein. "Cost analysis of hash collisions : Will quantum computers make SHARCS obsolete?" (PDF). Cr.yp.to. Retrieved 29 October 2017.
↑ Brassard, Gilles; HØyer, Peter; Tapp, Alain (20 April 1998). "Quantum cryptanalysis of hash and claw-free functions". LATIN'98: Theoretical Informatics. Lecture Notes in Computer Science. Vol. 1380. Springer, Berlin, Heidelberg. pp. 163–169. arXiv: quant-ph/9705002 . doi:10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID 118940551.
↑ R. Shirey (August 2007). Internet Security Glossary, Version 2. Network Working Group. doi: 10.17487/RFC4949 . RFC 4949.Informational.
↑ "Birthday Problem". Brilliant.org. Brilliant_(website) . Retrieved 28 July 2023.
↑ Bellare, Mihir; Rogaway, Phillip (2005). "The Birthday Problem". Introduction to Modern Cryptography (PDF). pp. 273–274. Retrieved 2023-03-31.
↑ Flajolet, Philippe; Odlyzko, Andrew M. (1990). "Random Mapping Statistics". In Quisquater, Jean-Jacques; Vandewalle, Joos (eds.). Advances in Cryptology — EUROCRYPT '89. Lecture Notes in Computer Science. Vol. 434. Berlin, Heidelberg: Springer. pp. 329–354. doi:10.1007/3-540-46885-4_34. ISBN 978-3-540-46885-1.
↑ See upper and lower bounds.
↑ Jacques Patarin, Audrey Montreuil (2005). "Benes and Butterfly schemes revisited" (PostScript, PDF). Université de Versailles. Retrieved 2007-03-15.{{cite journal}}: Cite journal requires |journal= (help)
↑ Gray, Jim; van Ingen, Catharine (25 January 2007). "Empirical Measurements of Disk Failure Rates and Error Rates". arXiv: cs/0701166 .
↑ "CiteSeerX". Archived from the original on 2008-02-23. Retrieved 2006-05-02.
↑ "Compute log(1+x) accurately for small values of x". Mathworks.com. Retrieved 29 October 2017.

Related Research Articles

In physics, the Maxwell–Boltzmann distribution, or Maxwell(ian) distribution, is a particular probability distribution named after James Clerk Maxwell and Ludwig Boltzmann.

In probability theory and statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is

<span class="mw-page-title-main">Central limit theorem</span> Fundamental theorem in probability theory and statistics

In probability theory, the central limit theorem (CLT) states that, under appropriate conditions, the distribution of a normalized version of the sample mean converges to a standard normal distribution. This holds even if the original variables themselves are not normally distributed. There are several versions of the CLT, each applying in the context of different conditions.

In quantum computing, Grover's algorithm, also known as the quantum search algorithm, is a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just $evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.$

In probability theory, the birthday problem asks for the probability that, in a set of $n$ randomly chosen people, at least two will share the same birthday. The birthday paradox refers to the counterintuitive fact that only 23 people are needed for that probability to exceed 50%.

In probability theory and statistics, a Gaussian process is a stochastic process, such that every finite collection of those random variables has a multivariate normal distribution. The distribution of a Gaussian process is the joint distribution of all those random variables, and as such, it is a distribution over functions with a continuous domain, e.g. time or space.

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. This has nothing to do with whether the function is one-to-one; finding any one input with the desired image is considered a successful inversion.

A commitment scheme is a cryptographic primitive that allows one to commit to a chosen value while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes are binding. Commitment schemes have important applications in a number of cryptographic protocols including secure coin flipping, zero-knowledge proofs, and secure computation.

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

In cryptography, collision resistance is a property of cryptographic hash functions: a hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b). The pigeonhole principle means that any hash function with more inputs than outputs will necessarily have such collisions; the harder they are to find, the more cryptographically secure the hash function is.

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.

In cryptography, the Rabin signature algorithm is a method of digital signature originally proposed by Michael O. Rabin in 1978.

<span class="mw-page-title-main">Fast inverse square root</span> Root-finding algorithm

Fast inverse square root, sometimes referred to as Fast InvSqrt or by the hexadecimal constant 0x5F3759DF, is an algorithm that estimates $, the reciprocal of the square root of a 32-bit floating-point number in IEEE 754 floating-point format. The algorithm is best known for its implementation in 1999 in Quake III Arena, a first-person shooter video game heavily based on 3D graphics. With subsequent hardware advancements, especially the x86 SSE instruction rsqrtss, this algorithm is not generally the best choice for modern computers, though it remains an interesting historical example.$

In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra, and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per $log(n)$ message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.

The elliptic curve only hash (ECOH) algorithm was submitted as a candidate for SHA-3 in the NIST hash function competition. However, it was rejected in the beginning of the competition since a second pre-image attack was found.

In cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the fast Fourier transform (FFT). SWIFFT is not the first hash function based on the FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction algorithm. It can be shown that finding collisions in SWIFFT is at least as difficult as finding short vectors in cyclic/ideal lattices in the worst case. By giving a security reduction to the worst-case scenario of a difficult mathematical problem, SWIFFT gives a much stronger security guarantee than most other cryptographic hash functions.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

Badger is a message authentication code (MAC) based on the idea of universal hashing and was developed by Boesgaard, Scavenius, Pedersen, Christensen, and Zenner. It is constructed by strengthening the ∆-universal hash family MMH using an ϵ-almost strongly universal (ASU) hash function family after the application of ENH, where the value of ϵ is $. Since Badger is a MAC function based on the universal hash function approach, the conditions needed for the security of Badger are the same as those for other universal hash functions such as UMAC.$

Network coding has been shown to optimally use bandwidth in a network, maximizing information flow but the scheme is very inherently vulnerable to pollution attacks by malicious nodes in the network. A node injecting garbage can quickly affect many receivers. The pollution of network packets spreads quickly since the output of honest node is corrupted if at least one of the incoming packets is corrupted.

HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the exact cardinality of the distinct elements of a multiset requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. Probabilistic cardinality estimators, such as the HyperLogLog algorithm, use significantly less memory than this, but can only approximate the cardinality. The HyperLogLog algorithm is able to estimate cardinalities of > 10⁹ with a typical accuracy (standard error) of 2%, using 1.5 kB of memory. HyperLogLog is an extension of the earlier LogLog algorithm, itself deriving from the 1984 Flajolet–Martin algorithm.

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

External links

"What is a digital signature and what is authentication?" from RSA Security's crypto FAQ.
"Birthday Attack" X5 Networks Crypto FAQs

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Avoiding collisions, Cryptographic hash functions" (PDF). Foundations of Cryptography, Computer Science Department, Wellesley College.

[:0-2] 1 2 Dang, Q H (2012). Recommendation for applications using approved hash algorithms (Report). Gaithersburg, MD: National Institute of Standards and Technology.

[3] Daniel J. Bernstein. "Cost analysis of hash collisions : Will quantum computers make SHARCS obsolete?" (PDF). Cr.yp.to. Retrieved 29 October 2017.

[4] Brassard, Gilles; HØyer, Peter; Tapp, Alain (20 April 1998). "Quantum cryptanalysis of hash and claw-free functions". LATIN'98: Theoretical Informatics. Lecture Notes in Computer Science. Vol. 1380. Springer, Berlin, Heidelberg. pp. 163–169. arXiv: quant-ph/9705002 . doi:10.1007/BFb0054319. ISBN 978-3-540-64275-6. S2CID 118940551.

[rfc4949-5] R. Shirey (August 2007). Internet Security Glossary, Version 2. Network Working Group. doi: 10.17487/RFC4949 . RFC 4949.Informational.

[6] "Birthday Problem". Brilliant.org. Brilliant_(website) . Retrieved 28 July 2023.

[7] Bellare, Mihir; Rogaway, Phillip (2005). "The Birthday Problem". Introduction to Modern Cryptography (PDF). pp. 273–274. Retrieved 2023-03-31.

[8] Flajolet, Philippe; Odlyzko, Andrew M. (1990). "Random Mapping Statistics". In Quisquater, Jean-Jacques; Vandewalle, Joos (eds.). Advances in Cryptology — EUROCRYPT '89. Lecture Notes in Computer Science. Vol. 434. Berlin, Heidelberg: Springer. pp. 329–354. doi:10.1007/3-540-46885-4_34. ISBN 978-3-540-46885-1.

[9] See upper and lower bounds.

[10] Jacques Patarin, Audrey Montreuil (2005). "Benes and Butterfly schemes revisited" (PostScript, PDF). Université de Versailles. Retrieved 2007-03-15.{{cite journal}}: Cite journal requires |journal= (help)

[11] Gray, Jim; van Ingen, Catharine (25 January 2007). "Empirical Measurements of Disk Failure Rates and Error Rates". arXiv: cs/0701166 .

[12] "CiteSeerX". Archived from the original on 2008-02-23. Retrieved 2006-05-02.

[13] "Compute log(1+x) accurately for small values of x". Mathworks.com. Retrieved 29 October 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]