Hash function security summary
From Wikipedia, the free encyclopedia
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
[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 | 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
[edit ]| 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
[edit ]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
[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 | 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
[edit ]| 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
[edit ]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
[edit ]- Comparison of cryptographic hash functions
- Cryptographic hash function
- Collision attack
- Preimage attack
- Length extension attack
- Cipher security summary
References
[edit ]- ^ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". IACR Cryptol. ePrint Arch.
- ^ a b 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.
- ^ Florian Mendel; Tomislav Nad; Martin Schläffer (2013年05月28日). Improving Local Collisions: New Attacks on Reduced SHA-256. Eurocrypt 2013.
- ^ 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.
- ^ L. Song, G. Liao and J. Guo, Non-Full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak, CRYPTO, 2017
- ^ a b c d LI Ji; XU Liangyu (2009年05月26日). "Attacks on Round-Reduced BLAKE". IACR Cryptol. ePrint Arch.
- ^ 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.
- ^ 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 .
- ^ Christophe De Cannière; Christian Rechberger (2008年08月17日). Preimages for Reduced SHA-0 and SHA-1. Crypto 2008.
- ^ 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 .
- ^ 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.
- ^ a b Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008年08月18日). Cryptanalysis of the GOST Hash Function. Crypto 2008.
- ^ a b Xiaoyun Wang; Dengguo Feng; Xuejia Lai; Hongbo Yu (2004年08月17日). "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD". Cryptology ePrint Archive.
- ^ 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. Archived from the original (PDF) on 2017年08月09日. Retrieved 2014年10月23日.
- ^ 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.
- ^ 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.
- ^ Joan Daemen; Gilles Van Assche (2007年04月04日). Producing Collisions for Panama, Instantaneously. FSE 2007.
- ^ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle (2001). Producing Collisions for PANAMA. FSE 2001.
- ^ 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 .
- ^ 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.
- ^ Thomas Fuhr; Thomas Peyrin (2008年12月04日). Cryptanalysis of RadioGatun. FSE 2009.
- ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). On the Collision Resistance of RIPEMD-160. ISC 2006.
- ^ 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 .
- ^ 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.201407007.
- ^ 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.
- ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". Cryptology ePrint Archive.
- ^ Gaëtan Leurent (2008年02月10日). MD4 is Not One-Way (PDF). FSE 2008.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ "ECRYPT Benchmarking of Cryptographic Hashes" . Retrieved November 23, 2020.
- ^ "Mind-blowing GPU performance". Improsec. January 3, 2020.
- ^ Goodin, Dan (2012年12月10日). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica . Retrieved 2020年11月23日.
External links
[edit ]- 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.