Jump to content

Hash function security summary

Edit links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 5.158.154.232 (talk) at 10:50, 17 November 2016. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

  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

Collision resistance

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

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

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

Collision resistance

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]
Streebog 2256 9.5 rounds of 12 (2176 time, 2128 memory) 2013-09-10 Rebound attack.[22]
Whirlpool 2256 4.5 of 10 rounds (2120 time) 2009-02-24 Rebound attack.[23]

Preimage resistance

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.[24]
MD4 2128 2102 time, 233 memory 2008-02-10 Paper.[25]
RIPEMD (original) 2128 35 of 48 rounds 2011 Paper.[26]
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.[27]
Tiger 2192 2188.8 time, 28 memory 2010-12-06 Paper.[28]

See also

References

  1. ^ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". {{cite journal}}: Cite journal requires |journal= (help)
  2. ^ a b Marc Stevens (2012-06-19). "Attacks on Hash Functions and Applications" (PDF). PhD thesis.
  3. ^ Bruce Schneier (2012-10-05). "When Will We See Collisions for SHA-1?".
  4. ^ Improving Local Collisions: New Attacks on Reduced SHA-256. Eurocrypt 2013. 2013-05-28. {{cite conference}}: Unknown parameter |authors= ignored (help)
  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" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
  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; Kazumaro Aoki (2008-11-25). "Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512". {{cite journal}}: Cite journal requires |journal= (help)
  11. ^ a b Cryptanalysis of the GOST Hash Function. Crypto 2008. 2008-08-18. {{cite conference}}: Unknown parameter |authors= ignored (help)
  12. ^ a b "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". 2004-08-17. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |authors= ignored (help)
  13. ^ "An attack on hash function HAVAL-128" (PDF). Science in China Series F: Information Sciences. 48 (5): 545–556. October 2005. {{cite journal}}: Unknown parameter |authors= ignored (help)
  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): 72–90. doi:10.1007/s00145-009-9054-1.
  15. ^ "Improved Collision Attacks on MD4 and MD5". IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E90-A (1): 36–47. 2007-03-22. doi:10.1093/ietfec/e90-a.1.36. {{cite journal}}: Unknown parameter |authors= ignored (help)
  16. ^ Producing Collisions for Panama, Instantaneously. FSE 2007. 2007-04-04. {{cite conference}}: Unknown parameter |authors= ignored (help)
  17. ^ Producing Collisions for PANAMA. FSE 2001. 2001. {{cite conference}}: Unknown parameter |authors= ignored (help)
  18. ^ Cryptanalysis of the Hash Functions MD4 and RIPEMD. Eurocrypt 2005. 2005-05-23. {{cite conference}}: Unknown parameter |authors= ignored (help)
  19. ^ Thomas Fuhr; Thomas Peyrin (2008-12-04). Cryptanalysis of RadioGatun. FSE 2009.
  20. ^ On the Collision Resistance of RIPEMD-160. ISC 2006. 2006. {{cite conference}}: Unknown parameter |authors= ignored (help)
  21. ^ Stéphane Manuel; Thomas Peyrin (2008-02-11). Collisions on SHA-0 in One Hour. FSE 2008.
  22. ^ "Cryptanalysis of GOST R hash function". Information Processing Letters. 114 (12): 655–662. 2013-09-10. doi:10.1016/j.ipl.2014.07.007. {{cite journal}}: Unknown parameter |authors= ignored (help)
  23. ^ The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl (PDF). FSE 2009. 2009-02-24. {{cite conference}}: Unknown parameter |authors= ignored (help)
  24. ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". {{cite journal}}: Cite journal requires |journal= (help)
  25. ^ Gaëtan Leurent (2008-02-10). MD4 is Not One-Way (PDF). FSE 2008.
  26. ^ Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160. ISC 2011. 2011. {{cite conference}}: Unknown parameter |authors= ignored (help)
  27. ^ The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function. SAC 2014. 2014-08-29. {{cite conference}}: Unknown parameter |authors= ignored (help)
  28. ^ Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2. Asiacrypt 2010. 2010-12-06. pp. 12–17. {{cite conference}}: Unknown parameter |authors= ignored (help)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_function_security_summary&oldid=750016632"