Jump to content

Hash function security summary: Difference between revisions

Edit links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→Collision resistance: Superscript, since RadioGatún’s strength against collision attacks is the same as a 608-bit-long hash
Citation bot (talk | contribs)
Bots
5,283,300 edits
m Add: citeseerx, journal. Removed parameters. You can use this bot yourself. Report bugs here. | User-activated.
Line 42: Line 42:
| 24 of 80 rounds (2<sup>32.5</sup>)
| 24 of 80 rounds (2<sup>32.5</sup>)
| 2008-11-25
| 2008-11-25
| Paper.<ref name=sha2-collision>{{cite conference |author1=Somitra Kumar Sanadhya |author2=Palash Sarkar |date=2008-11-25 |title=New Collision Attacks against Up to 24-Step SHA-2 |conference=Indocrypt 2008 |url=https://link.springer.com/chapter/10.1007%2F978-3-540-89754-5_8 }}</ref>
| Paper.<ref name=sha2-collision>{{cite conference |author1=Somitra Kumar Sanadhya |author2=Palash Sarkar |date=2008-11-25 |title=New Collision Attacks against Up to 24-Step SHA-2 |conference=Indocrypt 2008 |doi=10.1007/978-3-540-89754-5_8 }}</ref>
|-
|-
| [[SHA-3]]
| [[SHA-3]]
Line 83: Line 83:
| 2<sup>77.1</sup>
| 2<sup>77.1</sup>
| 2012-06-19
| 2012-06-19
| Paper.<ref name=stevens-sha1>{{cite journal |author=Marc Stevens |date=2012-06-19 |title=Attacks on Hash Functions and Applications |work=PhD thesis |url=https://marc-stevens.nl/research/papers/PhD%20Thesis%20Marc%20Stevens%20-%20Attacks%20on%20Hash%20Functions%20and%20Applications.pdf }}</ref>
| Paper.<ref name=stevens-sha1>{{cite journal |author=Marc Stevens |date=2012-06-19 |title=Attacks on Hash Functions and Applications |journal=PhD Thesis |url=https://marc-stevens.nl/research/papers/PhD%20Thesis%20Marc%20Stevens%20-%20Attacks%20on%20Hash%20Functions%20and%20Applications.pdf }}</ref>
|-
|-
| [[SHA256]]
| [[SHA256]]
Line 131: Line 131:
| 2<sup>123.4</sup>
| 2<sup>123.4</sup>
| 2009-04-27
| 2009-04-27
| Paper.<ref>{{cite conference |author1=Yu Sasaki |author2=Kazumaro Aoki |date=2009-04-27 |title=Finding Preimages in Full MD5 Faster Than Exhaustive Search |conference=Eurocrypt 2009 |url=https://link.springer.com/chapter/10.1007%2F978-3-642-01001-9_8 }}</ref>
| Paper.<ref>{{cite conference |author1=Yu Sasaki |author2=Kazumaro Aoki |date=2009-04-27 |title=Finding Preimages in Full MD5 Faster Than Exhaustive Search |conference=Eurocrypt 2009 |doi=10.1007/978-3-642-01001-9_8 }}</ref>
|-
|-
| [[SHA-1]]
| [[SHA-1]]
Line 143: Line 143:
| 43 of 64 rounds (2<sup>254.9</sup> time, 2<sup>6</sup> memory)
| 43 of 64 rounds (2<sup>254.9</sup> time, 2<sup>6</sup> memory)
| 2009-12-10
| 2009-12-10
| Paper.<ref name=sha2-preimage>{{cite conference |author1=Kazumaro Aoki |author2=Jian Guo |author3=Krystian Matusiewicz |author4=Yu Sasaki |author5=Lei Wang |date=2009-12-10 |title=Preimages for Step-Reduced SHA-2 |conference=Asiacrypt 2009 |url=https://link.springer.com/chapter/10.1007%2F978-3-642-10366-7_34 }}</ref>
| Paper.<ref name=sha2-preimage>{{cite conference |author1=Kazumaro Aoki |author2=Jian Guo |author3=Krystian Matusiewicz |author4=Yu Sasaki |author5=Lei Wang |date=2009-12-10 |title=Preimages for Step-Reduced SHA-2 |conference=Asiacrypt 2009 |doi=10.1007/978-3-642-10366-7_34 }}</ref>
|-
|-
| [[SHA512]]
| [[SHA512]]
Line 192: Line 192:
| 2<sup>7</sup>
| 2<sup>7</sup>
| 2004-08-17
| 2004-08-17
| Collisions originally reported in 2004,<ref name=collisions2004>{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xuejia Lai |author4=Hongbo Yu |date=2004-08-17 |title=Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD |url=https://eprint.iacr.org/2004/199 }}</ref> followed up by cryptanalysis paper in 2005.<ref>{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xiuyuan Yu |date=October 2005 |title=An attack on hash function HAVAL-128 |journal=Science in China Series F: Information Sciences |volume=48 |issue=5 |pages=545–556 |url=http://www.infosec.sdu.edu.cn/uploadfile/papers/An%20attack%20on%20hash%20function%20HAVAL-128.pdf |doi=10.1360/122004-107}}</ref>
| Collisions originally reported in 2004,<ref name=collisions2004>{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xuejia Lai |author4=Hongbo Yu |date=2004-08-17 |title=Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD |url=https://eprint.iacr.org/2004/199 }}</ref> followed up by cryptanalysis paper in 2005.<ref>{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xiuyuan Yu |date=October 2005 |title=An attack on hash function HAVAL-128 |journal=Science in China Series F: Information Sciences |volume=48 |issue=5 |pages=545–556 |url=http://www.infosec.sdu.edu.cn/uploadfile/papers/An%20attack%20on%20hash%20function%20HAVAL-128.pdf |doi=10.1360/122004-107|citeseerx=10.1.1.506.9546 }}</ref>
|-
|-
| [[MD2 (cryptography)|MD2]]
| [[MD2 (cryptography)|MD2]]
Line 198: Line 198:
| {{nowrap| 2<sup>63.3</sup> time, 2<sup>52</sup> memory }}
| {{nowrap| 2<sup>63.3</sup> time, 2<sup>52</sup> memory }}
| 2009
| 2009
| Slightly less computationally expensive than a birthday attack,<ref>{{cite journal |author1=Lars R. Knudsen |author2=John Erik Mathiassen |author3=Frédéric Muller |author4=Søren S. Thomsen |date=January 2010 |title=Cryptanalysis of MD2 |journal=Journal of Cryptology |volume=23 |issue=1 |pages=72–90 |url=https://link.springer.com/article/10.1007%2Fs00145-009-9054-1 |doi=10.1007/s00145-009-9054-1}}</ref> but for practical purposes, memory requirements make it more expensive.
| Slightly less computationally expensive than a birthday attack,<ref>{{cite journal |author1=Lars R. Knudsen |author2=John Erik Mathiassen |author3=Frédéric Muller |author4=Søren S. Thomsen |date=January 2010 |title=Cryptanalysis of MD2 |journal=Journal of Cryptology |volume=23 |issue=1 |pages=72–90 |doi=10.1007/s00145-009-9054-1}}</ref> but for practical purposes, memory requirements make it more expensive.
|- style="background: #ff9090; color: black"
|- style="background: #ff9090; color: black"
| [[MD4]]
| [[MD4]]
Line 216: Line 216:
| 2<sup>18</sup> time
| 2<sup>18</sup> time
| 2004-08-17
| 2004-08-17
| Collisions originally reported in 2004,<ref name=collisions2004 /> followed up by cryptanalysis paper in 2005.<ref>{{cite conference |author=Xiaoyun Wang |author2=Xuejia Lai |author3=Dengguo Feng |author4=Hui Chen |author5=Xiuyuan Yu |date=2005-05-23 |title=Cryptanalysis of the Hash Functions MD4 and RIPEMD |conference=Eurocrypt 2005 |url=https://link.springer.com/chapter/10.1007%2F11426639_1 }}</ref>
| Collisions originally reported in 2004,<ref name=collisions2004 /> followed up by cryptanalysis paper in 2005.<ref>{{cite conference |author=Xiaoyun Wang |author2=Xuejia Lai |author3=Dengguo Feng |author4=Hui Chen |author5=Xiuyuan Yu |date=2005-05-23 |title=Cryptanalysis of the Hash Functions MD4 and RIPEMD |conference=Eurocrypt 2005 |doi=10.1007/11426639_1 }}</ref>
|-
|-
| [[RadioGatún]]
| [[RadioGatún]]
Line 234: Line 234:
| 2<sup>33.6</sup> time
| 2<sup>33.6</sup> time
| 2008-02-11
| 2008-02-11
| Two-block collisions using [[boomerang attack]]. Attack takes estimated 1 hour on an average PC.<ref>{{cite conference |author1=Stéphane Manuel |author2=Thomas Peyrin |date=2008-02-11 |title=Collisions on SHA-0 in One Hour |conference=FSE 2008 |url=https://link.springer.com/chapter/10.1007%2F978-3-540-71039-4_2 }}</ref>
| Two-block collisions using [[boomerang attack]]. Attack takes estimated 1 hour on an average PC.<ref>{{cite conference |author1=Stéphane Manuel |author2=Thomas Peyrin |date=2008-02-11 |title=Collisions on SHA-0 in One Hour |conference=FSE 2008 |doi=10.1007/978-3-540-71039-4_2 }}</ref>
|-
|-
| [[Streebog]]
| [[Streebog]]
Line 281: Line 281:
| 35 of 48 rounds
| 35 of 48 rounds
| rowspan=3 | 2011
| rowspan=3 | 2011
| rowspan=3 | Paper.<ref>{{cite conference |author= Chiaki Ohtahara |author2= Yu Sasaki |author3= Takeshi Shimoyama |date=2011 |title=Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160 |conference=ISC 2011 |url=https://link.springer.com/chapter/10.1007%2F978-3-642-21518-6_13 }}</ref>
| rowspan=3 | Paper.<ref>{{cite conference |author= Chiaki Ohtahara |author2= Yu Sasaki |author3= Takeshi Shimoyama |date=2011 |title=Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160 |conference=ISC 2011 |doi= 10.1007/978-3-642-21518-6_13 }}</ref>
|-
|-
| RIPEMD-128
| RIPEMD-128

Revision as of 14:31, 20 November 2018

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

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 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]
SHA-3 Up to 2512 6 of 25 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 277.1 2012-06-19 Paper.[8]
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.[9]
SHA-1 2160 45 of 80 rounds 2008-08-17 Paper.[10]
SHA256 2256 43 of 64 rounds (2254.9 time, 26 memory) 2009-12-10 Paper.[11]
SHA512 2512 46 of 80 rounds (2511.5 time, 26 memory) 2008-11-25 Paper,[12] updated version.[11]
SHA-3 Up to 2512
BLAKE2s 2256 2.5 of 10 rounds (2241) 2009-05-26 Paper.[6]
BLAKE2b 2256 2.5 of 12 rounds (2481) 2009-05-26 Paper.[6]

Less-common hash functions

Collision resistance

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

Preimage resistance

Hash function Security claim Best attack Publish date Comment
GOST 2256 2192 2008-08-18 Paper.[13]
MD2 2128 273 time, 273 memory 2008 Paper.[27]
MD4 2128 2102 time, 233 memory 2008-02-10 Paper.[28]
RIPEMD (original) 2128 35 of 48 rounds 2011 Paper.[29]
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.[30]
Tiger 2192 2188.8 time, 28 memory 2010-12-06 Paper.[31]

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. ^ Marc Stevens; Elie Bursztein; Pierre Karpman; Ange Albertini; Yarik Markov (2017-02-23). "The first collision for full SHA-1" (PDF). {{cite journal}}: Cite journal requires |journal= (help)
  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. ^ a b c d LI Ji; XU Liangyu (2009-05-26). "Attacks on Round-Reduced BLAKE". {{cite journal}}: Cite journal requires |journal= (help)
  7. ^ 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)
  8. ^ Marc Stevens (2012-06-19). "Attacks on Hash Functions and Applications" (PDF). PhD Thesis.
  9. ^ 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.
  10. ^ Christophe De Cannière; Christian Rechberger (2008-08-17). Preimages for Reduced SHA-0 and SHA-1. Crypto 2008.
  11. ^ a b 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.
  12. ^ 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)
  13. ^ a b Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008-08-18). Cryptanalysis of the GOST Hash Function. Crypto 2008.
  14. ^ a b Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (2004-08-17). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". {{cite journal}}: Cite journal requires |journal= (help)
  15. ^ 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. CiteSeerX 10.1.1.506.9546. doi:10.1360/122004-107.
  16. ^ 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.
  17. ^ 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.
  18. ^ Joan Daemen; Gilles Van Assche (2007-04-04). Producing Collisions for Panama, Instantaneously. FSE 2007.
  19. ^ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle (2001). Producing Collisions for PANAMA. FSE 2001.
  20. ^ 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.
  21. ^ 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.
  22. ^ Thomas Fuhr; Thomas Peyrin (2008-12-04). Cryptanalysis of RadioGatun. FSE 2009.
  23. ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). On the Collision Resistance of RIPEMD-160. ISC 2006.
  24. ^ 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.
  25. ^ 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.
  26. ^ 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.
  27. ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". {{cite journal}}: Cite journal requires |journal= (help)
  28. ^ Gaëtan Leurent (2008-02-10). MD4 is Not One-Way (PDF). FSE 2008.
  29. ^ 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.
  30. ^ 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.
  31. ^ 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_function_security_summary&oldid=869809278"