Hash function security summary: Difference between revisions

From HandWiki
imported>Rtextdoc
linkage
 
Jport (talk | contribs)
0 edits
fix
 
Line 3: Line 3:


== Table color key ==
== Table color key ==
{{See also|Security level}}
{{legend|#f9f9f9|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}}
{{legend|#f9f9f9|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}}
{{legend|#ffff90|Attack demonstrated in theory — attack breaks all rounds and has lower complexity than security claim}}
{{legend|#ffff90|Attack demonstrated in theory — attack breaks all rounds and has lower complexity than security claim}}
Line 24: Line 25:
| 2<sup>18</sup> time
| 2<sup>18</sup> time
| 2013-03-25
| 2013-03-25
| This attack takes seconds on a regular PC. Two-block collisions in 2<sup>18</sup>, single-block collisions in 2<sup>41</sup>.<ref>{{cite journal |author1=Tao Xie |author2=Fanbao Liu |author3=Dengguo Feng |date=25 March 2013 |title=Fast Collision Attack on MD5 |url=https://eprint.iacr.org/2013/170 }}</ref>
| This attack takes seconds on a regular PC. Two-block collisions in 2<sup>18</sup>, single-block collisions in 2<sup>41</sup>.<ref>{{cite journal |author1=Tao Xie |author2=Fanbao Liu |author3=Dengguo Feng |date=25 March 2013 |title=Fast Collision Attack on MD5 |url=https://eprint.iacr.org/2013/170 |journal=IACR Cryptol. ePrint Arch.  }}</ref>
|- style="background: #ff9090; color: black"
|- style="background: #ff9090; color: black"
| [[SHA-1]]
| [[SHA-1]]
Line 30: Line 31:
| 2<sup>61.2</sup>
| 2<sup>61.2</sup>
| 2020-01-08
| 2020-01-08
| Paper by Gaëtan Leurent and Thomas Peyrin<ref name=sha1-shambles>{{cite journal |author1=Gaëtan Leurent |author2=Thomas Peyrin |date=2020-01-08 |title=SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust |url=https://eprint.iacr.org/2020/014.pdf }}</ref>
| Paper by Gaëtan Leurent and Thomas Peyrin<ref name=sha1-shambles/>
|-
|-
| SHA256
| SHA256
Line 54: Line 55:
| 2.5 of 10 rounds (2<sup>112</sup>)
| 2.5 of 10 rounds (2<sup>112</sup>)
| 2009-05-26
| 2009-05-26
| Paper.<ref name=attacks-on-reduced-round-blake>{{cite journal |author1=LI Ji |author2=XU Liangyu |date=2009-05-26 |title=Attacks on Round-Reduced BLAKE |url=https://eprint.iacr.org/2009/238 }}</ref>
| Paper.<ref name=attacks-on-reduced-round-blake>{{cite journal |author1=LI Ji |author2=XU Liangyu |date=2009-05-26 |title=Attacks on Round-Reduced BLAKE |url=https://eprint.iacr.org/2009/238|journal=IACR Cryptol. ePrint Arch.  }}</ref>
|-
|-
| [[BLAKE (hash function)#BLAKE2|BLAKE2b]]
| [[BLAKE (hash function)#BLAKE2|BLAKE2b]]
Line 77: Line 78:
| 2<sup>39</sup>
| 2<sup>39</sup>
| 2009-06-16
| 2009-06-16
| This attack takes hours on a regular PC.<ref>{{cite journal |author1=Marc Stevens |author2=Arjen Lenstra |author3=Benne de Weger |date=2009-06-16 |title=Chosen-prefix Collisions for MD5 and Applications |url=https://documents.epfl.ch/users/l/le/lenstra/public/papers/lat.pdf }}</ref>
| This attack takes hours on a regular PC.<ref>{{cite journal |author1=Marc Stevens |author2=Arjen Lenstra |author3=Benne de Weger |date=2012-07-12 |title=Chosen-prefix Collisions for MD5 and Applications |url=https://documents.epfl.ch/users/l/le/lenstra/public/papers/lat.pdf | journal=International Journal of Applied Cryptography| volume=2| issue=4 | pages=322–359 |doi=10.1504/IJACT.2012.048084}}</ref>
|- style="background: #ff9090; color: black"
|- style="background: #ff9090; color: black"
| [[SHA-1]]
| [[SHA-1]]
Line 83: Line 84:
| 2<sup>63.4</sup>
| 2<sup>63.4</sup>
| 2020-01-08
| 2020-01-08
| Paper by Gaëtan Leurent and Thomas Peyrin<ref name=sha1-shambles>{{cite journal |author1=Gaëtan Leurent |author2=Thomas Peyrin |date=2020-01-08 |title=SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust |url=https://eprint.iacr.org/2020/014.pdf }}</ref>
| Paper by Gaëtan Leurent and Thomas Peyrin<ref name=sha1-shambles>{{cite conference |author1=Gaëtan Leurent |author2=Thomas Peyrin |date=2020-01-08 |title=SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust|url=https://eprint.iacr.org/2020/014.pdf|conference=USENIX Security Symposium|volume=29|pages=1839–1856|isbn=978-1-939133-17-5|series=SEC'20|publisher=USENIX Association}}</ref>
|-
|-
| SHA256
| SHA256
Line 149: Line 150:
| 46 of 80 rounds (2<sup>511.5</sup> time, 2<sup>6</sup> memory)
| 46 of 80 rounds (2<sup>511.5</sup> time, 2<sup>6</sup> memory)
| 2008-11-25
| 2008-11-25
| Paper,<ref>{{cite journal |author1=Yu Sasaki |author2=Lei Wang |author3=Kazumaro Aoki |date=2008-11-25 |title=Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 |url=https://eprint.iacr.org/2009/479 }}</ref> updated version.<ref name=sha2-preimage />
| Paper,<ref>{{cite journal |author1=Yu Sasaki |author2=Lei Wang |author3=Kazumaro Aoki |date=2008-11-25 |title=Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 |url=https://eprint.iacr.org/2009/479|journal=IACR Cryptol. ePrint Arch. }}</ref> updated version.<ref name=sha2-preimage />
|-
|-
| [[SHA-3]]
| [[SHA-3]]
Line 245: Line 246:
| 9.5 rounds of 12 (2<sup>176</sup> time, 2<sup>128</sup> memory)
| 9.5 rounds of 12 (2<sup>176</sup> time, 2<sup>128</sup> memory)
| 2013-09-10
| 2013-09-10
| [[Rebound attack]].<ref>{{cite journal |author=Zongyue Wang |author2=Hongbo Yu |author3=Xiaoyun Wang |date=2013-09-10 |title=Cryptanalysis of GOST R hash function |journal=Information Processing Letters |volume=114 |issue=12 |pages=655–662 |url=https://eprint.iacr.org/2013/584 |doi=10.1016/j.ipl.2014.07.007}}</ref>
| [[Rebound attack]].<ref>{{cite journal |author=Zongyue Wang |author2=Hongbo Yu |author3=Xiaoyun Wang |date=2013-09-10 |title=Cryptanalysis of GOST R hash function |journal=Information Processing Letters |volume=114 |issue=12 |pages=655–662 |url=https://eprint.iacr.org/2013/584 |doi=10.1016/j.ipl.2014.07.007|url-access=subscription }}</ref>
|-
|-
| [[Whirlpool (hash function)|Whirlpool]]
| [[Whirlpool (hash function)|Whirlpool]]

Latest revision as of 04:54, 23 May 2026

Short description: Publicly known attacks against cryptographic hash functions

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

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

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 261.2 2020-01-08 Paper by Gaëtan Leurent and Thomas Peyrin[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]
SHA-3 Up to 2512 6 of 24 rounds (250) 2017 Paper.[5]
BLAKE2s 2128 2.5 of 10 rounds (2112) 2009-05-26 Paper.[6]
BLAKE2b 2256 2.5 of 12 rounds (2224) 2009-05-26 Paper.[6]

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.[7]
SHA-1 280 263.4 2020-01-08 Paper by Gaëtan Leurent and Thomas Peyrin[2]
SHA256 2128
SHA512 2256
SHA-3 Up to 2512
BLAKE2s 2128
BLAKE2b 2256

Preimage resistance

Main article: Preimage attack
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]
SHA-3 Up to 2512
BLAKE2s 2256 2.5 of 10 rounds (2241) 2009-05-26 Paper.[6]
BLAKE2b 2512 2.5 of 12 rounds (2481) 2009-05-26 Paper.[6]

Length extension

Main article: Length extension attack
  • Vulnerable: MD5, SHA1, SHA256, SHA512
  • Not vulnerable: SHA384, SHA-3, BLAKE2

Less-common hash functions

Collision resistance

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 Up to 2608[20] 2704 2008-12-04 For a word size w between 1-64 bits, the hash provides a security claim of 29.5w. The attack can find a collision in 211w time.[21]
RIPEMD-160 280 48 of 80 rounds (251 time) 2006 Paper.[22]
SHA-0 280 233.6 time 2008-02-11 Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC.[23]
Streebog 2256 9.5 rounds of 12 (2176 time, 2128 memory) 2013-09-10 Rebound attack.[24]
Whirlpool 2256 4.5 of 10 rounds (2120 time) 2009-02-24 Rebound attack.[25]

Preimage resistance

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

Attacks on hashed passwords

Main article: Password cracking

Hashes described here are designed for fast computation and have roughly similar speeds.[31] 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.[32][33] Special hashes called key derivation functions have been created to slow brute force searches. These include pbkdf2, bcrypt, scrypt, argon2, and balloon.

See also

References

  1. ↑ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". IACR Cryptol. ePrint Arch.. https://eprint.iacr.org/2013/170. 
  2. ↑ 2.0 2.1 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". USENIX Security Symposium. 29. USENIX Association. pp. 1839–1856. ISBN 978-1-939133-17-5. https://eprint.iacr.org/2020/014.pdf. 
  3. ↑ Florian Mendel; Tomislav Nad; Martin Schläffer (2013-05-28). "Improving Local Collisions: New Attacks on Reduced SHA-256". Eurocrypt 2013. https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=69018. 
  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. ↑ 6.0 6.1 6.2 6.3 LI Ji; XU Liangyu (2009-05-26). "Attacks on Round-Reduced BLAKE". IACR Cryptol. ePrint Arch.. https://eprint.iacr.org/2009/238. 
  7. ↑ Marc Stevens; Arjen Lenstra; Benne de Weger (2012-07-12). "Chosen-prefix Collisions for MD5 and Applications". International Journal of Applied Cryptography 2 (4): 322–359. doi:10.1504/IJACT.2012.048084. https://documents.epfl.ch/users/l/le/lenstra/public/papers/lat.pdf. 
  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. https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=36848. 
  10. ↑ 10.0 10.1 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.. https://eprint.iacr.org/2009/479. 
  12. ↑ 12.0 12.1 Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008-08-18). "Cryptanalysis of the GOST Hash Function". Crypto 2008. https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=36649. 
  13. ↑ 13.0 13.1 Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (2004-08-17). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". Cryptology ePrint Archive. https://eprint.iacr.org/2004/199. 
  14. ↑ 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. doi:10.1360/122004-107. http://www.infosec.sdu.edu.cn/uploadfile/papers/An%20attack%20on%20hash%20function%20HAVAL-128.pdf. 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. 
  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. Bibcode: 2007IEITF..90...36S. 
  17. ↑ Joan Daemen; Gilles Van Assche (2007-04-04). "Producing Collisions for Panama, Instantaneously". FSE 2007. http://radiogatun.noekeon.org/panama/. 
  18. ↑ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle (2001). "Producing Collisions for PANAMA". FSE 2001. https://www.cosic.esat.kuleuven.be/publications/article-81.ps. 
  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 2304 and the best claimed attack takes 2352 work.
  21. ↑ Thomas Fuhr; Thomas Peyrin (2008-12-04). "Cryptanalysis of RadioGatun". FSE 2009. https://eprint.iacr.org/2008/515. 
  22. ↑ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). "On the Collision Resistance of RIPEMD-160". ISC 2006. https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=17675. 
  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. https://eprint.iacr.org/2013/584. 
  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". FSE 2009. https://www.iacr.org/archive/fse2009/56650270/56650270.pdf. 
  26. ↑ Søren S. Thomsen (2008). "An improved preimage attack on MD2". Cryptology ePrint Archive. https://eprint.iacr.org/2008/089. 
  27. ↑ Gaëtan Leurent (2008-02-10). "MD4 is Not One-Way". FSE 2008. https://who.rocq.inria.fr/Gaetan.Leurent/files/MD4_FSE08.pdf. 
  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. https://eprint.iacr.org/2014/675. 
  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. https://eprint.iacr.org/2010/016. 
  31. ↑ "ECRYPT Benchmarking of Cryptographic Hashes". https://bench.cr.yp.to/results-hash.html. 
  32. ↑ "Mind-blowing GPU performance". Improsec. January 3, 2020. https://improsec.com/tech-blog/mind-blowing-gpu-performance. 
  33. ↑ Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica. https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/. 



Retrieved from "https://handwiki.org/wiki/index.php?title=Hash_function_security_summary&oldid=4347775"