Editing Birthday attack (section)

{{short description|Type of cryptographic attack}}
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 ([[pigeonhole principle|pigeonhole]]s). Let <math display="inline">H </math> be the number of possible values of a hash function, with <math display="inline"> H=2^l</math>. With a birthday attack, it is possible to find a [[hash collision|collision of a hash function]] with <math display="inline">50%</math> chance in <math display="inline">\sqrt{2^l} = 2^{l / 2},</math>  where <math display="inline"> l </math> is the bit length of the hash output,<ref>{{Cite web |title=Avoiding collisions, Cryptographic hash functions |url=https://cs.wellesley.edu/~cs310/lectures/15_hash_functions_slides_handouts.pdf |website=Foundations of Cryptography, Computer Science Department, Wellesley College}}</ref><ref name=":0" />  and with <math display="inline">2^{l-1}</math> being the classical [[preimage resistance]] security with the same probability.<ref name=":0">{{Cite report |url=http://dx.doi.org/10.6028/nist.sp.800-107r1 |title=Recommendation for applications using approved hash algorithms |last=Dang |first=Q H |date=2012 |publisher=National Institute of Standards and Technology |location=Gaithersburg, MD|doi=10.6028/nist.sp.800-107r1 }}</ref> There is a general (though disputed<ref>{{cite web|url=http://cr.yp.to/hash/collisioncost-20090823.pdf|title=Cost analysis of hash collisions : Will quantum computers make SHARCS obsolete?|author=Daniel J. Bernstein|website=Cr.yp.to|access-date=29 October 2017}}</ref>) [[BHT algorithm|result]] that quantum computers can perform birthday attacks, thus breaking collision resistance, in <math display="inline">\sqrt[3]{2^l} = 2^{l / 3}</math>.<ref>{{cite book|first1=Gilles|title = LATIN'98: Theoretical Informatics|volume = 1380|last1=Brassard|first2=Peter|last2=HØyer|first3=Alain|last3=Tapp| chapter=Quantum cryptanalysis of hash and claw-free functions |date=20 April 1998|publisher=Springer, Berlin, Heidelberg|pages=163–169|doi=10.1007/BFb0054319|series = Lecture Notes in Computer Science|isbn = 978-3-540-64275-6|arxiv = quant-ph/9705002|s2cid = 118940551}}</ref>

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]].{{Ref RFC|4949|notes=no|rp=36}}