Birthday 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 (pigeonholes). Let be the number of possible values of a hash function, with . With a birthday attack, it is possible to find a collision of a hash function with chance in where is the bit length of the hash output,[1][2] and with 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 .[4]

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.[5]: 36 

  1. ^ "Avoiding collisions, Cryptographic hash functions" (PDF). Foundations of Cryptography, Computer Science Department, Wellesley College.
  2. ^ a b 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.
  5. ^ R. Shirey (August 2007). Internet Security Glossary, Version 2. Network Working Group. doi:10.17487/RFC4949. RFC 4949. Informational.