Hash function security summary

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]

1. ^ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". IACR Cryptol. ePrint Arch.
2. ^ 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.
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". IACR Cryptol. ePrint Arch.
7. ^ 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.
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.
10. ^ 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.
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.
12. ^ a b Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008-08-18). Cryptanalysis of the GOST Hash Function. Crypto 2008.
13. ^ 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.
14. ^ Xiaoyun Wang; Dengguo Feng; Xiuyuan Yu (October 2005). "An attack on hash function HAVAL-128" (PDF). Science in China Series F. 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.
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. S2CID 2443076.
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\. Bibcode:2007IEITF..90...36S. doi:10.1093/ietfec/e90-a.1.36.
17. ^ Joan Daemen; Gilles Van Assche (2007-04-04). Producing Collisions for Panama, Instantaneously. FSE 2007.
18. ^ Vincent Rijmen; Bart Van Rompay; Bart Preneel; Joos Vandewalle (2001). Producing Collisions for PANAMA. FSE 2001.
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.
22. ^ Florian Mendel; Norbert Pramstaller; Christian Rechberger; Vincent Rijmen (2006). On the Collision Resistance of RIPEMD-160. ISC 2006.
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.
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 (PDF). FSE 2009.
26. ^ Søren S. Thomsen (2008). "An improved preimage attack on MD2". Cryptology ePrint Archive.
27. ^ Gaëtan Leurent (2008-02-10). MD4 is Not One-Way (PDF). FSE 2008.
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.
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.
31. ^ "ECRYPT Benchmarking of Cryptographic Hashes". Retrieved November 23, 2020.
32. ^ "Mind-blowing GPU performance". Improsec. January 3, 2020.
33. ^ 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.

* v
* t
* e

Cryptographic hash functions and message authentication codes

* List
* Comparison
* Known attacks

Common functions|

* MD5 (compromised)
* SHA-1 (compromised)
* SHA-2
* SHA-3
* BLAKE2

SHA-3 finalists|

* BLAKE
* Grøstl
* JH
* Skein
* Keccak (winner)

Other functions|

* BLAKE3
* CubeHash
* ECOH
* FSB
* Fugue
* GOST
* HAS-160
* HAVAL
* Kupyna
* LSH
* Lane
* MASH-1
* MASH-2
* MD2
* MD4
* MD6
* MDC-2
* N-hash
* RIPEMD
* RadioGatún
* SIMD
* SM3
* SWIFFT
* Shabal
* Snefru
* Streebog
* Tiger
* VSH
* Whirlpool

Password hashing/
key stretching functions|

* Argon2
* Balloon
* bcrypt
* Catena
* crypt
* LM hash
* Lyra2
* Makwa
* PBKDF2
* scrypt
* yescrypt

General purpose
key derivation functions|

* HKDF
* KDF1/KDF2

MAC functions|

* CBC-MAC
* DAA
* GMAC
* HMAC
* NMAC
* OMAC/CMAC
* PMAC
* Poly1305
* SipHash
* UMAC
* VMAC

Authenticated
encryption modes|

* CCM
* ChaCha20-Poly1305
* CWC
* EAX
* GCM
* IAPM
* OCB

Attacks|

* Collision attack
* Preimage attack
* Birthday attack
* Brute-force attack
* Rainbow table
* Side-channel attack
* Length extension attack

Design|

* Avalanche effect
* Hash collision
* Merkle–Damgård construction
* Sponge function
* HAIFA construction

Standardization|

* CAESAR Competition
* CRYPTREC
* NESSIE
* NIST hash function competition
* Password Hashing Competition
* NSA Suite B
* CNSA

Utilization|

* Hash-based cryptography
* Merkle tree
* Message authentication
* Proof of work
* Salt
* Pepper

* v
* t
* e

Cryptography

General|

* History of cryptography
* Outline of cryptography
* Classical cipher
* Cryptographic protocol
* Authentication protocol
* Cryptographic primitive
* Cryptanalysis
* Cryptocurrency
* Cryptosystem
* Cryptographic nonce
* Cryptovirology
* Hash function
* Cryptographic hash function
* Key derivation function
* Secure Hash Algorithms
* Digital signature
* Kleptography
* Key (cryptography)
* Key exchange
* Key generator
* Key schedule
* Key stretching
* Keygen
* Machines
* Cryptojacking malware
* Ransomware
* Random number generation
* Cryptographically secure pseudorandom number generator (CSPRNG)
* Pseudorandom noise (PRN)
* Secure channel
* Insecure channel
* Subliminal channel
* Encryption
* Decryption
* End-to-end encryption
* Harvest now, decrypt later
* Information-theoretic security
* Plaintext
* Codetext
* Ciphertext
* Shared secret
* Trapdoor function
* Trusted timestamping
* Key-based routing
* Onion routing
* Garlic routing
* Kademlia
* Mix network

Mathematics|

* Cryptographic hash function
* Block cipher
* Stream cipher
* Symmetric-key algorithm
* Authenticated encryption
* Public-key cryptography
* Quantum key distribution
* Quantum cryptography
* Post-quantum cryptography
* Message authentication code
* Random numbers
* Steganography

* Category

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template