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
[edit] 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]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]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]- 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]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".
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ 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).
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ 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".
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ 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) - ^ 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".
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ 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.2014.07.007.
- ^ 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.