Hash function security summary

Last updated

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.

Contents

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 functionSecurity claimBest attackPublish dateComment
MD5 264218 time2013-03-25This attack takes seconds on a regular PC. Two-block collisions in 218, single-block collisions in 241. [1]
SHA-1 280261.22020-01-08Paper by Gaëtan Leurent and Thomas Peyrin [2]
SHA256 212831 of 64 rounds (265.5)2013-05-28Two-block collision. [3]
SHA512 225624 of 80 rounds (232.5)2008-11-25Paper. [4]
SHA-3 Up to 25126 of 24 rounds (250)2017Paper. [5]
BLAKE2s 21282.5 of 10 rounds (2112)2009-05-26Paper. [6]
BLAKE2b 22562.5 of 12 rounds (2224)2009-05-26Paper. [6]

Chosen prefix collision attack

Hash functionSecurity claimBest attackPublish dateComment
MD5 2642392009-06-16This attack takes hours on a regular PC. [7]
SHA-1 280263.42020-01-08Paper by Gaëtan Leurent and Thomas Peyrin [2]
SHA256 2128
SHA512 2256
SHA-3 Up to 2512
BLAKE2s 2128
BLAKE2b 2256

Preimage resistance

Hash functionSecurity claimBest attackPublish dateComment
MD5 21282123.42009-04-27Paper. [8]
SHA-1 216045 of 80 rounds2008-08-17Paper. [9]
SHA256 225643 of 64 rounds (2254.9 time, 26 memory)2009-12-10Paper. [10]
SHA512 251246 of 80 rounds (2511.5 time, 26 memory)2008-11-25Paper, [11] updated version. [10]
SHA-3 Up to 2512
BLAKE2s 22562.5 of 10 rounds (2241)2009-05-26Paper. [6]
BLAKE2b 25122.5 of 12 rounds (2481)2009-05-26Paper. [6]

Length extension

Less-common hash functions

Collision resistance

Hash functionSecurity claimBest attackPublish dateComment
GOST 212821052008-08-18Paper. [12]
HAVAL-128264272004-08-17Collisions originally reported in 2004, [13] followed up by cryptanalysis paper in 2005. [14]
MD2 264 263.3 time, 252 memory 2009Slightly less computationally expensive than a birthday attack, [15] but for practical purposes, memory requirements make it more expensive.
MD4 2643 operations2007-03-22Finding collisions almost as fast as verifying them. [16]
PANAMA 2128262007-04-04Paper, [17] improvement of an earlier theoretical attack from 2001. [18]
RIPEMD (original)264218 time2004-08-17Collisions originally reported in 2004, [13] followed up by cryptanalysis paper in 2005. [19]
RadioGatún Up to 2608 [20] 27042008-12-04For 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-16028048 of 80 rounds (251 time)2006Paper. [22]
SHA-0 280233.6 time2008-02-11Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC. [23]
Streebog 22569.5 rounds of 12 (2176 time, 2128 memory)2013-09-10 Rebound attack. [24]
Whirlpool 22564.5 of 10 rounds (2120 time)2009-02-24Rebound attack. [25]

Preimage resistance

Hash functionSecurity claimBest attackPublish dateComment
GOST 225621922008-08-18Paper. [12]
MD2 2128273 time, 273 memory2008Paper. [26]
MD4 21282102 time, 233 memory2008-02-10Paper. [27]
RIPEMD (original)212835 of 48 rounds2011Paper. [28]
RIPEMD-128212835 of 64 rounds
RIPEMD-160216031 of 80 rounds
Streebog 25122266 time, 2259 data2014-08-29The paper presents two second-preimage attacks with variable data requirements. [29]
Tiger 21922188.8 time, 28 memory2010-12-06Paper. [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

Related Research Articles

<span class="mw-page-title-main">HMAC</span> Computer communications authentication algorithm

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and authenticity of a message. An HMAC is a type of keyed hash function that can also be used in a key derivation scheme or a key stretching scheme.

The MD5 message-digest algorithm is a widely used hash function producing a 128-bit hash value. MD5 was designed by Ronald Rivest in 1991 to replace an earlier hash function MD4, and was specified in 1992 as RFC 1321.

<span class="mw-page-title-main">RIPEMD</span> Cryptographic hash function

RIPEMD is a family of cryptographic hash functions developed in 1992 and 1996. There are five functions in the family: RIPEMD, RIPEMD-128, RIPEMD-160, RIPEMD-256, and RIPEMD-320, of which RIPEMD-160 is the most common.

In cryptography, SHA-1 is a hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as 40 hexadecimal digits. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard. The algorithm has been cryptographically broken but is still widely used.

<span class="mw-page-title-main">Cryptographic hash function</span> Hash function that is suitable for use in cryptography

A cryptographic hash function (CHF) is a hash algorithm that has special properties desirable for a cryptographic application:

<span class="mw-page-title-main">MD5CRK</span>

In cryptography, MD5CRK was a volunteer computing effort launched by Jean-Luc Cooke and his company, CertainKey Cryptosystems, to demonstrate that the MD5 message digest algorithm is insecure by finding a collision – two messages that produce the same MD5 hash. The project went live on March 1, 2004. The project ended on August 24, 2004 after researchers independently demonstrated a technique for generating collisions in MD5 using analytical methods by Xiaoyun Wang, Feng, Xuejia Lai, and Yu. CertainKey awarded a 10,000 Canadian Dollar prize to Wang, Feng, Lai and Yu for their discovery.

In cryptography, Tiger is a cryptographic hash function designed by Ross Anderson and Eli Biham in 1995 for efficiency on 64-bit platforms. The size of a Tiger hash value is 192 bits. Truncated versions can be used for compatibility with protocols assuming a particular hash size. Unlike the SHA-2 family, no distinguishing initialization values are defined; they are simply prefixes of the full Tiger/192 hash value.

<span class="mw-page-title-main">MD4</span> Cryptographic hash function

The MD4 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1990. The digest length is 128 bits. The algorithm has influenced later designs, such as the MD5, SHA-1 and RIPEMD algorithms. The initialism "MD" stands for "Message Digest".

In cryptography, a collision attack on a cryptographic hash tries to find two inputs producing the same hash value, i.e. a hash collision. This is in contrast to a preimage attack where a specific target hash value is specified.

HAVAL is a cryptographic hash function. Unlike MD5, but like most modern cryptographic hash functions, HAVAL can produce hashes of different lengths – 128 bits, 160 bits, 192 bits, 224 bits, and 256 bits. HAVAL also allows users to specify the number of rounds to be used to generate the hash. HAVAL was broken in 2004.

The MD2 Message-Digest Algorithm is a cryptographic hash function developed by Ronald Rivest in 1989. The algorithm is optimized for 8-bit computers. MD2 is specified in IETF RFC 1319. The "MD" in MD2 stands for "Message Digest".

Wang Xiaoyun is a Chinese cryptographer, mathematician, and computer scientist. She is a professor in the Department of Mathematics and System Science of Shandong University and an academician of the Chinese Academy of Sciences.

SHA-2 is a set of cryptographic hash functions designed by the United States National Security Agency (NSA) and first published in 2001. They are built using the Merkle–Damgård construction, from a one-way compression function itself built using the Davies–Meyer structure from a specialized block cipher.

In cryptography, collision resistance is a property of cryptographic hash functions: a hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b). The pigeonhole principle means that any hash function with more inputs than outputs will necessarily have such collisions; the harder they are to find, the more cryptographically secure the hash function is.

FORK-256 is a hash algorithm designed in response to security issues discovered in the earlier SHA-1 and MD5 algorithms. After substantial cryptanalysis, the algorithm is considered broken.

In cryptography, rotational cryptanalysis is a generic cryptanalytic attack against algorithms that rely on three operations: modular addition, rotation and XOR — ARX for short. Algorithms relying on these operations are popular because they are relatively cheap in both hardware and software and run in constant time, making them safe from timing attacks in common implementations.

This article summarizes publicly known attacks against block ciphers and stream ciphers. Note that there are perhaps attacks that are not publicly known, and not all entries may be up to date.

Streebog is a cryptographic hash function defined in the Russian national standard GOST R 34.11-2012 Information Technology – Cryptographic Information Security – Hash Function. It was created to replace an obsolete GOST hash function defined in the old standard GOST R 34.11-94, and as an asymmetric reply to SHA-3 competition by the US National Institute of Standards and Technology. The function is also described in RFC 6986 and one out of hash functions in ISO/IEC 10118-3:2018.

In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed as a number of "bits of security", where n-bit security means that the attacker would have to perform 2n operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 is designed to offer a 128-bit security level, which is considered roughly equivalent to a RSA using 3072-bit key.

Dmitry Khovratovich is a Russian cryptographer, currently a Lead Cryptographer for the Dusk Network, researcher for the Ethereum Foundation, and member of the International Association for Cryptologic Research.

References

  1. ↑ Tao Xie; Fanbao Liu; Dengguo Feng (25 March 2013). "Fast Collision Attack on MD5". IACR Cryptol. ePrint Arch.
  2. 1 2 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. 1 2 3 4 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. 1 2 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. 1 2 Florian Mendel; Norbert Pramstaller; Christian Rechberger; Marcin Kontak; Janusz Szmidt (2008-08-18). Cryptanalysis of the GOST Hash Function. Crypto 2008.
  13. 1 2 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: 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.
  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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.