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
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
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
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
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
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
^ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013).
"Fast Collision Attack on MD5" .
^
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) .
^ 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" .
^ Marc Stevens; Arjen Lenstra; Benne de Weger (2009-06-16).
"Chosen-prefix Collisions for MD5 and Applications" (PDF) .
^ 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" .
^
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