Hash function security summary

From Wikipedia, the free encyclopedia
Jump to navigation Jump to 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 a reduced version 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]

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 263.1 2017-02-23 Paper.[2]
SHA256 2128 31 of 64 rounds (265.5) 2013-05-28 Two-block collision.[3]
SHA512 2256 24 of 80 rounds (232.5) 2008-11-25 Paper.[4]
BLAKE2s 2128 2.5 of 10 rounds (2112) 2009-05-26 Paper.[5]
BLAKE2b 2256 2.5 of 12 rounds (2224) 2009-05-26 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.[7]
SHA256 2128
SHA512 2256
BLAKE2s 2128
BLAKE2b 2256

Preimage resistance[edit]

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

Less common hash functions[edit]

Collision resistance[edit]

Hash function Security claim Best attack Publish date Comment
GOST 2128 2105 2008-08-18 Paper.[12]
HAVAL-128 264 27 2004-08-17 Collisions originally reported in 2004,[13] followed up by cryptanalysis paper in 2005.[14]
MD2 264 263.3 time, 252 memory 2009 Slightly less computationally expensive than a birthday attack,[15] 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.[16]
PANAMA 2128 26 2007-04-04 Paper,[17] improvement of an earlier theoretical attack from 2001.[18]
RIPEMD (original) 264 218 time 2004-08-17 Collisions originally reported in 2004,[13] followed up by cryptanalysis paper in 2005.[19]
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.[20]
RIPEMD-160 280 48 of 80 rounds (251 time) 2006 Paper.[21]
SHA-0 280 233.6 time 2008-02-11 Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC.[22]
Streebog 2256 9.5 rounds of 12 (2176 time, 2128 memory) 2013-09-10 Rebound attack.[23]
Whirlpool 2256 4.5 of 10 rounds (2120 time) 2009-02-24 Rebound attack.[24]

Preimage resistance[edit]

Hash function Security claim Best attack Publish date Comment
GOST 2256 2192 2008-08-18 Paper.[12]
MD2 2128 273 time, 273 memory 2008 Paper.[25]
MD4 2128 2102 time, 233 memory 2008-02-10 Paper.[26]
RIPEMD (original) 2128 35 of 48 rounds 2011 Paper.[27]
RIPEMD-128 2128 35 of 64 rounds
RIPEMD-160 2160 31 of 80 rounds
Streebog 2512 2266 time, 2259 data 2014-08-29 The paper presents two second-preimage attacks with variable data requirements.[28]
Tiger 2192 2188.8 time, 28 memory 2010-12-06 Paper.[29]

See also[edit]

References[edit]

  1. ^ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". 
  2. ^ Marc Stevens; Elie Bursztein; Pierre Karpman; Ange Albertini; Yarik Markov (2017-02-23). "The first collision for full SHA-1" (PDF). 
  3. ^ Florian Mendel; Tomislav Nad; Martin Schläffer (2013-05-28). Improving Local Collisions: New Attacks on Reduced SHA-256. Eurocrypt 2013. 
  4. ^ Somitra Kumar Sanadhya; Palash Sarkar (2008-11-25). New Collision Attacks against Up to 24-Step SHA-2. Indocrypt 2008. 
  5. ^ a b c d LI Ji; XU Liangyu (2009-05-26). "Attacks on Round-Reduced BLAKE". 
  6. ^ Marc Stevens; Arjen Lenstra; Benne de Weger (2009-06-16). "Chosen-prefix Collisions for MD5 and Applications" (PDF). 
  7. ^ Marc Stevens (2012-06-19). "Attacks on Hash Functions and Applications" (PDF). PhD thesis. 
  8. ^ Yu Sasaki; Kazumaro Aoki (2009-04-27). Finding Preimages in Full MD5 Faster Than Exhaustive Search. Eurocrypt 2009. 
  9. ^ Christophe De Cannière; Christian Rechberger (2008-08-17). Preimages for Reduced SHA-0 and SHA-1. Crypto 2008. 
  10. ^ a b Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki; Lei Wang (2009-12-10). Preimages for Step-Reduced SHA-2. Asiacrypt 2009. 
  11. ^ Yu Sasaki; Lei Wang; Kazumaro Aoki (2008-11-25). "Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512". 
  12. ^ a b Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008-08-18). Cryptanalysis of the GOST Hash Function. Crypto 2008. 
  13. ^ a b Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (2004-08-17). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". 
  14. ^ Xiaoyun Wang; Dengguo Feng; Xiuyuan Yu (October 2005). "An attack on hash function HAVAL-128" (PDF). Science in China Series F: Information Sciences. 48 (5): 545–556. doi:10.1360/122004-107. 
  15. ^ Lars R. Knudsen; John Erik Mathiassen; Frédéric Muller; Søren S. Thomsen (January 2010). "Cryptanalysis of MD2". Journal of Cryptology. 23 (1): 72–90. doi:10.1007/s00145-009-9054-1. 
  16. ^ Yu Sasaki; Yusuke Naito; Noboru Kunihiro; Kazuo Ohta (2007-03-22). "Improved Collision Attacks on MD4 and MD5". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E90-A (1): 36–47. doi:10.1093/ietfec/e90-a.1.36. 
  17. ^ Joan Daemen; Gilles Van Assche (2007-04-04). Producing Collisions for Panama, Instantaneously. FSE 2007. 
  18. ^ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle (2001). Producing Collisions for PANAMA. FSE 2001. 
  19. ^ Xiaoyun Wang; Xuejia Lai; Dengguo Feng; Hui Chen; Xiuyuan Yu (2005-05-23). Cryptanalysis of the Hash Functions MD4 and RIPEMD. Eurocrypt 2005. 
  20. ^ Thomas Fuhr; Thomas Peyrin (2008-12-04). Cryptanalysis of RadioGatun. FSE 2009. 
  21. ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). On the Collision Resistance of RIPEMD-160. ISC 2006. 
  22. ^ Stéphane Manuel; Thomas Peyrin (2008-02-11). Collisions on SHA-0 in One Hour. FSE 2008. 
  23. ^ Zongyue Wang; Hongbo Yu; Xiaoyun Wang (2013-09-10). "Cryptanalysis of GOST R hash function". Information Processing Letters. 114 (12): 655–662. doi:10.1016/j.ipl.2014.07.007. 
  24. ^ Florian Mendel; Christian Rechberger; Martin Schläffer; Søren S. Thomsen (2009-02-24). The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl (PDF). FSE 2009. 
  25. ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". 
  26. ^ Gaëtan Leurent (2008-02-10). MD4 is Not One-Way (PDF). FSE 2008. 
  27. ^ Chiaki Ohtahara; Yu Sasaki; Takeshi Shimoyama (2011). Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160. ISC 2011. 
  28. ^ Jian Guo; Jérémy Jean; Gaëtan Leurent; Thomas Peyrin; Lei Wang (2014-08-29). The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function. SAC 2014. 
  29. ^ 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. pp. 12–17. 

External links[edit]