Hash function security summary
See also: Security level

From Wikipedia the free encyclopedia

Top View

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]
See also: Security level
  No attack successfully demonstrated — attack only breaks a reduced version of the hash or requires more work than the claimed security level of the hash
  Attack demonstrated in theory — attack breaks all rounds and has lower complexity than security claim
  Attack demonstrated in practice — complexity is low enough to be actually used

Common hash functions

[edit]

Collision resistance

[edit]
Main article: Collision attack

Hash function Security claim Best attack Publish date Comment
MD5 2 2 time 2013-03-25 This attack takes seconds on a regular PC. Two-block collisions in 2, single-block collisions in 2.
SHA-1 2 2 2020-01-08 Paper by Gaëtan Leurent and Thomas Peyrin
SHA256 2 31 of 64 rounds (2) 2013-05-28 Two-block collision.
SHA512 2 24 of 80 rounds (2) 2008-11-25 Paper.
SHA-3 Up to 2 6 of 24 rounds (2) 2017 Paper.
BLAKE2s 2 2.5 of 10 rounds (2) 2009-05-26 Paper.
BLAKE2b 2 2.5 of 12 rounds (2) 2009-05-26 Paper.

Chosen prefix collision attack

[edit]

Hash function Security claim Best attack Publish date Comment
MD5 2 2 2009-06-16 This attack takes hours on a regular PC.
SHA-1 2 2 2020-01-08 Paper by Gaëtan Leurent and Thomas Peyrin
SHA256 2
SHA512 2
SHA-3 Up to 2
BLAKE2s 2
BLAKE2b 2

Preimage resistance

[edit]
Main article: Preimage attack

Hash function Security claim Best attack Publish date Comment
MD5 2 2 2009-04-27 Paper.
SHA-1 2 45 of 80 rounds 2008-08-17 Paper.
SHA256 2 43 of 64 rounds (2 time, 2 memory) 2009-12-10 Paper.
SHA512 2 46 of 80 rounds (2 time, 2 memory) 2008-11-25 Paper, updated version.
SHA-3 Up to 2
BLAKE2s 2 2.5 of 10 rounds (2) 2009-05-26 Paper.
BLAKE2b 2 2.5 of 12 rounds (2) 2009-05-26 Paper.

Length extension

[edit]
Main article: Length extension attack

  • Vulnerable: MD5, SHA1, SHA256, SHA512
  • Not vulnerable: SHA384, SHA-3, BLAKE2

Less-common hash functions

[edit]

Collision resistance

[edit]

Hash function Security claim Best attack Publish date Comment
GOST 2 2 2008-08-18 Paper.
HAVAL-128 2 2 2004-08-17 Collisions originally reported in 2004, followed up by cryptanalysis paper in 2005.
MD2 2 2 time, 2 memory 2009 Slightly less computationally expensive than a birthday attack, but for practical purposes, memory requirements make it more expensive.
MD4 2 3 operations 2007-03-22 Finding collisions almost as fast as verifying them.
PANAMA 2 2 2007-04-04 Paper, improvement of an earlier theoretical attack from 2001.
RIPEMD (original) 2 2 time 2004-08-17 Collisions originally reported in 2004, followed up by cryptanalysis paper in 2005.
RadioGatún Up to 2 2 2008-12-04 For a word size w between 1-64 bits, the hash provides a security claim of 2. The attack can find a collision in 2 time.
RIPEMD-160 2 48 of 80 rounds (2 time) 2006 Paper.
SHA-0 2 2 time 2008-02-11 Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC.
Streebog 2 9.5 rounds of 12 (2 time, 2 memory) 2013-09-10 Rebound attack.
Whirlpool 2 4.5 of 10 rounds (2 time) 2009-02-24 Rebound attack.

Preimage resistance

[edit]

Hash function Security claim Best attack Publish date Comment
GOST 2 2 2008-08-18 Paper.
MD2 2 2 time, 2 memory 2008 Paper.
MD4 2 2 time, 2 memory 2008-02-10 Paper.
RIPEMD (original) 2 35 of 48 rounds 2011 Paper.
RIPEMD-128 2 35 of 64 rounds
RIPEMD-160 2 31 of 80 rounds
Streebog 2 2 time, 2 data 2014-08-29 The paper presents two second-preimage attacks with variable data requirements.
Tiger 2 2 time, 2 memory 2010-12-06 Paper.

Attacks on hashed passwords

[edit]
Main article: Password cracking

Hashes described here are designed for fast computation and have roughly similar speeds. Because most users typically choose short passwords formed in predictable ways, passwords can often be recovered from their hashed value if a fast hash is used. Searches on the order of 100 billion tests per second are possible with high-end graphics processors. Special hashes called key derivation functions have been created to slow brute force searches. These include pbkdf2, bcrypt, scrypt, argon2, and balloon.

See also

[edit]

References

[edit]
  1. ^ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". IACR Cryptol. ePrint Arch.
  2. ^ Gaëtan Leurent; Thomas Peyrin (2020-01-08). SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust (PDF). USENIX Security Symposium. SEC'20. Vol. 29. USENIX Association. pp. 1839–1856. ISBN 978-1-939133-17-5.
  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. doi:10.1007/978-3-540-89754-5_8.
  5. ^ L. Song, G. Liao and J. Guo, Non-Full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak, CRYPTO, 2017
  6. ^ LI Ji; XU Liangyu (2009-05-26). "Attacks on Round-Reduced BLAKE". IACR Cryptol. ePrint Arch.
  7. ^ Marc Stevens; Arjen Lenstra; Benne de Weger (2012-07-12). "Chosen-prefix Collisions for MD5 and Applications" (PDF). International Journal of Applied Cryptography. 2 (4): 322–359. doi:10.1504/IJACT.2012.048084.
  8. ^ Yu Sasaki; Kazumaro Aoki (2009-04-27). Finding Preimages in Full MD5 Faster Than Exhaustive Search. Eurocrypt 2009. doi:10.1007/978-3-642-01001-9_8.
  9. ^ Christophe De Cannière; Christian Rechberger (2008-08-17). Preimages for Reduced SHA-0 and SHA-1. Crypto 2008.
  10. ^ Kazumaro Aoki; Jian Guo; Krystian Matusiewicz; Yu Sasaki; Lei Wang (2009-12-10). Preimages for Step-Reduced SHA-2. Asiacrypt 2009. doi:10.1007/978-3-642-10366-7_34.
  11. ^ Yu Sasaki; Lei Wang; Kazumaro Aoki (2008-11-25). "Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512". IACR Cryptol. ePrint Arch.
  12. ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008-08-18). Cryptanalysis of the GOST Hash Function. Crypto 2008.
  13. ^ Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (2004-08-17). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". Cryptology ePrint Archive.
  14. ^ Xiaoyun Wang; Dengguo Feng; Xiuyuan Yu (October 2005). "An attack on hash function HAVAL-128" (PDF). Science in China Series F. 48 (5): 545–556. CiteSeerX 10.1.1.506.9546. doi:10.1360/122004-107. Archived from the original (PDF) on 2017-08-09. Retrieved 2014-10-23.
  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. S2CID 2443076.
  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. Bibcode:2007IEITF..90...36S. 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. doi:10.1007/11426639_1.
  20. ^ RadioGatún is a family of 64 different hash functions. The security level and best attack in the chart are for the 64-bit version. The 32-bit version of RadioGatún has a claimed security level of 2 and the best claimed attack takes 2 work.
  21. ^ Thomas Fuhr; Thomas Peyrin (2008-12-04). Cryptanalysis of RadioGatun. FSE 2009.
  22. ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). On the Collision Resistance of RIPEMD-160. ISC 2006.
  23. ^ Stéphane Manuel; Thomas Peyrin (2008-02-11). Collisions on SHA-0 in One Hour. FSE 2008. doi:10.1007/978-3-540-71039-4_2.
  24. ^ 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.
  25. ^ 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.
  26. ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". Cryptology ePrint Archive.
  27. ^ Gaëtan Leurent (2008-02-10). MD4 is Not One-Way (PDF). FSE 2008.
  28. ^ Chiaki Ohtahara; Yu Sasaki; Takeshi Shimoyama (2011). Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160. ISC 2011. doi:10.1007/978-3-642-21518-6_13.
  29. ^ 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.
  30. ^ 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.
  31. ^ "ECRYPT Benchmarking of Cryptographic Hashes". Retrieved November 23, 2020.
  32. ^ "Mind-blowing GPU performance". Improsec. January 3, 2020.
  33. ^ Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica. Retrieved 2020-11-23.
[edit]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_function_security_summary&oldid=1292105386"