Birthday attack
A birthday attack is a type of cryptographic 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). With a birthday attack, it is possible to find a collision of a hash function in , with being the classical preimage resistance security. There is a general (though disputed[1]) result that quantum computers can perform birthday attacks, thus breaking collision resistance, in .[2]
Although there are some digital signature vulnerabilities associated with the birthday attack, it cannot be used to break an encryption scheme any faster than a brute-force attack.[3]: 36
Understanding the problem
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Birthday_attack_vs_paradox.svg/220px-Birthday_attack_vs_paradox.svg.png)
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 .[4]
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 , 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.
Mathematics
Given a function , the goal of the attack is to find two different inputs such that . Such a pair is called a collision. The method used to find a collision is simply to evaluate the function 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 yields any of different outputs with equal probability and is sufficiently large, then we expect to obtain a pair of different arguments and with after evaluating the function for about 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
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
and assigning a 0.5 probability of collision we arrive at
Let Q(H) be the expected number of values we have to choose before finding the first collision. This number can be approximated by
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 billion attempts (5.38×109) to generate a collision using brute force.[6] This value is called birthday bound[7] and for n-bit codes it could be approximated as 2n/2.[8] Other examples are as follows:
Bits Possible outputs (H) Desired probability of random collision
(2 s.f.) (p)10−18 10−15 10−12 10−9 10−6 0.1% 1% 25% 50% 75% 16 216 (~6.5 x 104) <2 <2 <2 <2 <2 11 36 190 300 430 32 232 (~4.3×109) <2 <2 <2 3 93 2900 9300 50,000 77,000 110,000 64 264 (~1.8×1019) 6 190 6100 190,000 6,100,000 1.9×108 6.1×108 3.3×109 5.1×109 7.2×109 128 2128 (~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 2256 (~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 2384 (~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 2512 (~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−18 to 10−15 is the uncorrectable bit error rate of a typical hard disk.[9] 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.[10]
The subexpression in the equation for is not computed accurately for small 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.[11] 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
which can also be written as
- .
or
- .
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 () and want the chance of a collision to be at most one in a million (), how many documents could we have at the most?
which is close to the correct answer of 93.
Digital signature susceptibility
Digital signatures can be susceptible to a birthday attack. A message is typically signed by first computing , where is a cryptographic hash function, and then using some secret key to sign . Suppose Mallory wants to trick Bob into signing a fraudulent contract. Mallory prepares a fair contract and a fraudulent one . She then finds a number of positions where 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 which are all fair contracts.
In a similar manner, Mallory also creates a huge number of variations on the fraudulent contract . 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, . 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. The birthday problem equations apply where is the number of pairs. The number of hashes Mallory actually generates is .
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.
See also
Notes
- ^ 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). 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.
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