Hash function security summary

From Wikipedia, the free encyclopedia
Jump to: navigation, search

This article summarizes publicly known attacks against cryptographic hash functions. Note that not all entries may be up to date. For a summary of other hash function parameters, see comparison of cryptographic hash functions.

Table color key[edit]

  No known successful attacks — attack only breaks part of the hash
  Theoretical break — attack breaks all rounds and has lower complexity than security claim
  Attack demonstrated in practice

Common hash functions[edit]

Collision resistance[edit]

Main article: Collision attack
Hash function Security claim Best attack Publish date Comment
MD5 264 218 time 2013-03-25 This attack takes seconds on a regular PC. Two-block collisions in 218, single-block collisions in 241.[1]
SHA-1 280 260.3 ... 265.3 2012-06-19 Paper.[2] Attack is feasible with large amounts of computation power.[3]
SHA256 2128 31 of 64 rounds (265.5) 2013-05-28 Two-block collision.[4]
SHA512 2256 24 of 80 rounds (232.5) 2008-11-25 Paper.[5]

Chosen prefix collision attack[edit]

Hash function Security claim Best attack Publish date Comment
MD5 264 239 2009-06-16 This attack takes hours on a regular PC.[6]
SHA-1 280 277.1 2012-06-19 Paper.[2]
SHA256 2128
SHA512 2256

Preimage resistance[edit]

Main article: Preimage attack
Hash function Security claim Best attack Publish date Comment
MD5 2128 2123.4 2009-04-27 Paper.[7]
SHA-1 2160 45 of 80 rounds 2008-08-17 Paper.[8]
SHA256 2256 43 of 64 rounds (2254.9 time, 26 memory) 2009-12-10 Paper.[9]
SHA512 2512 46 of 80 rounds (2511.5 time, 26 memory) 2008-11-25 Paper,[10] updated version.[9]

Less common hash functions[edit]

Collision resistance[edit]

Hash function Security claim Best attack Publish date Comment
GOST 2128 2105 2008-08-18 Paper.[11]
HAVAL-128 264 27 2004-08-17 Collisions originally reported in 2004,[12] followed up by cryptanalysis paper in 2005.[13]
MD2 264 263.3 time, 252 memory 2009 Slightly less computationally expensive than a birthday attack,[14] but for practical purposes, memory requirements make it more expensive.
MD4 264 3 operations 2007-03-22 Finding collisions almost as fast as verifying them.[15]
PANAMA 2128 26 2007-04-04 Paper,[16] improvement of an earlier theoretical attack from 2001.[17]
RIPEMD (original) 264 218 time 2004-08-17 Collisions originally reported in 2004,[12] followed up by cryptanalysis paper in 2005.[18]
RadioGatún 2608 * 2704 2008-12-04 For a word size w between 1-64 bits, the hash provides a collision security claim of 28.5w. For any value, the attack can find a collision in 211w time.[19]
RIPEMD-160 280 48 of 80 rounds (251 time) 2006 Paper.[20]
SHA-0 280 233.6 time 2008-02-11 Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC.[21]
Whirlpool 2256 4.5 of 10 rounds (2120 time) 2009-02-24 Rebound attack.[22]

Preimage resistance[edit]

Hash function Security claim Best attack Publish date Comment
GOST 2256 2192 2008-08-18 Paper.[11]
MD2 2128 273 time, 273 memory 2008 Paper.[23]
MD4 2128 2102 time, 233 memory 2008-02-10 Paper.[24]
RIPEMD (original) 2128 35 of 48 rounds 2011 Paper.[25]
RIPEMD-128 2128 35 of 64 rounds
RIPEMD-160 2160 31 or 80 rounds
Tiger 2192 2188.8 time, 28 memory 2010-12-06 Paper.[26]

See also[edit]

References[edit]

  1. ^ Tao Xie, Fanbao Liu, Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". 
  2. ^ a b Marc Stevens (2012-06-19). "Attacks on Hash Functions and Applications". PhD thesis. 
  3. ^ Bruce Schneier (2012-10-05). "When Will We See Collisions for SHA-1?". 
  4. ^ Florian Mendel, Tomislav Nad, Martin Schläffer (2013-05-28). "Improving Local Collisions: New Attacks on Reduced SHA-256". Eurocrypt 2013. 
  5. ^ Somitra Kumar Sanadhya, Palash Sarkar (2008-11-25). "New Collision Attacks against Up to 24-Step SHA-2". Indocrypt 2008. 
  6. ^ Marc Stevens, Arjen Lenstra, Benne de Weger (2009-06-16). "Chosen-prefix Collisions for MD5 and Applications". 
  7. ^ Yu Sasaki, Kazumaro Aoki (2009-04-27). "Finding Preimages in Full MD5 Faster Than Exhaustive Search". Eurocrypt 2009. 
  8. ^ Christophe De Cannière, Christian Rechberger (2008-08-17). "Preimages for Reduced SHA-0 and SHA-1". Crypto 2008. 
  9. ^ a b Kazumaro Aoki, Jian Guo, Krystian Matusiewicz, Yu Sasaki, Lei Wang (2009-12-10). "Preimages for Step-Reduced SHA-2". Asiacrypt 2009. 
  10. ^ Yu Sasaki, Lei Wang, and Kazumaro Aoki (2008-11-25). "Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512". 
  11. ^ a b Florian Mendel, Norbert Pramstaller, Christian Rechberger, Marcin Kontak, Janusz Szmidt (2008-08-18). "Cryptanalysis of the GOST Hash Function". Crypto 2008. 
  12. ^ a b Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu (2004-08-17). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". 
  13. ^ Xiaoyun Wang, Dengguo Feng, Xiuyuan Yu (October 2005). "An attack on hash function HAVAL-128". Science in China Series F: Information Sciences 48 (5): 545–556. 
  14. ^ Lars R. Knudsen, John Erik Mathiassen, Frédéric Muller, Søren S. Thomsen (January 2010). "Cryptanalysis of MD2". Journal of Cryptology 23 (1): pages 72–90. 
  15. ^ Yu Sasaki, et al. (2007-03-22). "Improved Collision Attacks on MD4 and MD5". 
  16. ^ Joan Daemen, Gilles Van Assche (2007-04-04). "Producing Collisions for Panama, Instantaneously". FSE 2007. 
  17. ^ Vincent Rijmen, Bart Van Rompay, Bart Preneel, Joos Vandewalle. "Producing Collisions for PANAMA". FSE 2001. 
  18. ^ Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu (2005-05-23). "Cryptanalysis of the Hash Functions MD4 and RIPEMD". Eurocrypt 2005. 
  19. ^ Thomas Fuhr, Thomas Peyrin (2008-12-04). "Cryptanalysis of RadioGatun". FSE 2009. 
  20. ^ Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen (2006). "On the Collision Resistance of RIPEMD-160". ISC 2006. 
  21. ^ Stéphane Manuel, Thomas Peyrin (2008-02-11). "Collisions on SHA-0 in One Hour". FSE 2008. 
  22. ^ Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen (2009-02-24). "The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl". FSE 2009. 
  23. ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". 
  24. ^ Gaëtan Leurent (2008-02-10). "MD4 is Not One-Way". FSE 2008. 
  25. ^ Chiaki Ohtahara, Yu Sasaki, Takeshi Shimoyama (2011). "Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160". ISC 2011. 
  26. ^ Jian Guo, San Ling, Christian Rechberger, Huaxiong Wang (2010-12-06). "Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2". Asiacrypt 2010. p. 12-17. 

External links[edit]