World Library  
Flag as Inappropriate
Email this Article

Hash function security summary

Article Id: WHEBN0026774718
Reproduction Date:

Title: Hash function security summary  
Author: World Heritage Encyclopedia
Language: English
Subject: SIMD (hash function), VMAC, Lane (hash function), NaSHA, CWC mode
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Hash function security summary

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 part 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

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

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]
Whirlpool 2256 4.5 of 10 rounds (2120 time) 2009-02-24 Rebound attack.[22]

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.[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

References

  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. ^  
  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

  • 2010 summary of attacks against Tiger, MD4 and SHA-2: 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. 3. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.