Login
Login

hash function security summary

{{short description|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

{{See also|Security level}}

{{legend|#f9f9f9|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}}

{{legend|#ffff90|Attack demonstrated in theory — attack breaks all rounds and has lower complexity than security claim}}

{{legend|#ff9090|Attack demonstrated in practice — complexity is low enough to be actually used}}

Common hash functions

=Collision resistance=

{{main|Collision attack}}

class="wikitable" border="1"
Hash function

! Security claim

! Best attack

! Publish date

! Comment

style="background: #ff9090; color: black"

| 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.{{cite journal |author1=Tao Xie |author2=Fanbao Liu |author3=Dengguo Feng |date=25 March 2013 |title=Fast Collision Attack on MD5 |url=https://eprint.iacr.org/2013/170 |journal=IACR Cryptol. ePrint Arch. }}

style="background: #ff9090; color: black"

| SHA-1

| 280

| 261.2

| 2020-01-08

| Paper by Gaëtan Leurent and Thomas Peyrin

SHA256

| 2128

| 31 of 64 rounds (265.5)

| 2013-05-28

| Two-block collision.{{cite conference |author=Florian Mendel |author2=Tomislav Nad |author3=Martin Schläffer |date=2013-05-28 |title=Improving Local Collisions: New Attacks on Reduced SHA-256 |conference=Eurocrypt 2013 |url=https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=69018 }}

SHA512

| 2256

| 24 of 80 rounds (232.5)

| 2008-11-25

| Paper.{{cite conference |author1=Somitra Kumar Sanadhya |author2=Palash Sarkar |date=2008-11-25 |title=New Collision Attacks against Up to 24-Step SHA-2 |conference=Indocrypt 2008 |doi=10.1007/978-3-540-89754-5_8 }}

SHA-3

| Up to 2512

| 6 of 24 rounds (250)

| 2017

| Paper.L. Song, G. Liao and J. Guo, Non-Full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak, CRYPTO, 2017

BLAKE2s

| 2128

| 2.5 of 10 rounds (2112)

| 2009-05-26

| Paper.{{cite journal |author1=LI Ji |author2=XU Liangyu |date=2009-05-26 |title=Attacks on Round-Reduced BLAKE |url=https://eprint.iacr.org/2009/238|journal=IACR Cryptol. ePrint Arch. }}

BLAKE2b

| 2256

| 2.5 of 12 rounds (2224)

| 2009-05-26

| Paper.

=Chosen prefix collision attack=

class="wikitable" border="1"
Hash function

! Security claim

! Best attack

! Publish date

! Comment

style="background: #ff9090; color: black"

| MD5

| 264

| 239

| 2009-06-16

| This attack takes hours on a regular PC.{{cite journal |author1=Marc Stevens |author2=Arjen Lenstra |author3=Benne de Weger |date=2012-07-12 |title=Chosen-prefix Collisions for MD5 and Applications |url=https://documents.epfl.ch/users/l/le/lenstra/public/papers/lat.pdf | journal=International Journal of Applied Cryptography| volume=2| issue=4 | pages=322–359 |doi=10.1504/IJACT.2012.048084}}

style="background: #ff9090; color: black"

| SHA-1

| 280

| 263.4

| 2020-01-08

| Paper by Gaëtan Leurent and Thomas Peyrin{{cite conference |author1=Gaëtan Leurent |author2=Thomas Peyrin |date=2020-01-08 |title=SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust|url=https://eprint.iacr.org/2020/014.pdf|conference=USENIX Security Symposium|volume=29|pages=1839-1856|isbn=978-1-939133-17-5|series=SEC'20|publisher=USENIX Association}}

SHA256

| 2128

|

|

|

SHA512

| 2256

|

|

|

SHA-3

| Up to 2512

|

|

|

BLAKE2s

| 2128

|

|

|

BLAKE2b

| 2256

|

|

|

=Preimage resistance=

{{main|Preimage attack}}

class="wikitable" border="1"
Hash function

! Security claim

! Best attack

! Publish date

! Comment

style="background: #ffff90; color: black"

| MD5

| 2128

| 2123.4

| 2009-04-27

| Paper.{{cite conference |author1=Yu Sasaki |author2=Kazumaro Aoki |date=2009-04-27 |title=Finding Preimages in Full MD5 Faster Than Exhaustive Search |conference=Eurocrypt 2009 |doi=10.1007/978-3-642-01001-9_8 |doi-access=free }}

SHA-1

| 2160

| 45 of 80 rounds

| 2008-08-17

| Paper.{{cite conference |author1=Christophe De Cannière |author2=Christian Rechberger |date=2008-08-17 |title=Preimages for Reduced SHA-0 and SHA-1 |conference=Crypto 2008 |url=https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=36848 }}

SHA256

| 2256

| 43 of 64 rounds (2254.9 time, 26 memory)

| 2009-12-10

| Paper.{{cite conference |author1=Kazumaro Aoki |author2=Jian Guo |author3=Krystian Matusiewicz |author4=Yu Sasaki |author5=Lei Wang |date=2009-12-10 |title=Preimages for Step-Reduced SHA-2 |conference=Asiacrypt 2009 |doi=10.1007/978-3-642-10366-7_34 |doi-access=free }}

SHA512

| 2512

| 46 of 80 rounds (2511.5 time, 26 memory)

| 2008-11-25

| Paper,{{cite journal |author1=Yu Sasaki |author2=Lei Wang |author3=Kazumaro Aoki |date=2008-11-25 |title=Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512 |url=https://eprint.iacr.org/2009/479|journal=IACR Cryptol. ePrint Arch. }} updated version.

SHA-3

| Up to 2512

|

|

|

BLAKE2s

| 2256

| 2.5 of 10 rounds (2241)

| 2009-05-26

| Paper.

BLAKE2b

| 2512

| 2.5 of 12 rounds (2481)

| 2009-05-26

| Paper.

=Length extension=

{{main|Length extension attack}}

  • Vulnerable: MD5, SHA1, SHA256, SHA512
  • Not vulnerable: SHA384, SHA-3, BLAKE2

Less-common hash functions

=Collision resistance=

class="wikitable" border="1"
Hash function

! Security claim

! Best attack

! Publish date

! Comment

style="background: #ffff90; color: black"

| GOST

| 2128

| 2105

| 2008-08-18

| Paper.{{cite conference |author=Florian Mendel |author2=Norbert Pramstaller |author3=Christian Rechberger |author4=Marcin Kontak |author5=Janusz Szmidt |date=2008-08-18 |title=Cryptanalysis of the GOST Hash Function |conference=Crypto 2008 |url=https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=36649 }}

style="background: #ff9090; color: black"

| HAVAL-128

| 264

| 27

| 2004-08-17

| Collisions originally reported in 2004,{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xuejia Lai |author4=Hongbo Yu |date=2004-08-17 |title=Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD |journal=Cryptology ePrint Archive |url=https://eprint.iacr.org/2004/199 }} followed up by cryptanalysis paper in 2005.{{cite journal |author=Xiaoyun Wang |author2=Dengguo Feng |author3=Xiuyuan Yu |date=October 2005 |title=An attack on hash function HAVAL-128 |journal=Science in China Series F |volume=48 |issue=5 |pages=545–556 |url=http://www.infosec.sdu.edu.cn/uploadfile/papers/An%20attack%20on%20hash%20function%20HAVAL-128.pdf |doi=10.1360/122004-107 |citeseerx=10.1.1.506.9546 |access-date=2014-10-23 |archive-url=https://web.archive.org/web/20170809100011/http://infosec.sdu.edu.cn/uploadfile/papers/An%20attack%20on%20hash%20function%20HAVAL-128.pdf |archive-date=2017-08-09 }}

MD2

| 264

| {{nowrap| 263.3 time, 252 memory }}

| 2009

| Slightly less computationally expensive than a birthday attack,{{cite journal |author1=Lars R. Knudsen |author2=John Erik Mathiassen |author3=Frédéric Muller |author4=Søren S. Thomsen |date=January 2010 |title=Cryptanalysis of MD2 |journal=Journal of Cryptology |volume=23 |issue=1 |pages=72–90 |doi=10.1007/s00145-009-9054-1|s2cid=2443076 |doi-access=free }} but for practical purposes, memory requirements make it more expensive.

style="background: #ff9090; color: black"

| MD4

| 264

| 3 operations

| 2007-03-22

| Finding collisions almost as fast as verifying them.{{cite journal |author=Yu Sasaki |author2=Yusuke Naito |author3=Noboru Kunihiro |author4=Kazuo Ohta |date=2007-03-22 |title=Improved Collision Attacks on MD4 and MD5 |journal=IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences |volume=E90-A |issue=1 |pages=36–47 |doi=10.1093/ietfec/e90-a.1.36 |bibcode=2007IEITF..90...36S }}

style="background: #ff9090; color: black"

| PANAMA

| 2128

| 26

| 2007-04-04

| Paper,{{cite conference |author=Joan Daemen |author2=Gilles Van Assche |date=2007-04-04 |title=Producing Collisions for Panama, Instantaneously |conference=FSE 2007 |url=http://radiogatun.noekeon.org/panama/ }} improvement of an earlier theoretical attack from 2001.{{cite conference |author=Vincent Rijmen |author2=Bart Van Rompay |author3=Bart Preneel |author4=Joos Vandewalle |date=2001 |title=Producing Collisions for PANAMA |conference=FSE 2001 |url=https://www.cosic.esat.kuleuven.be/publications/article-81.ps }}

style="background: #ff9090; color: black"

| RIPEMD (original)

| 264

| 218 time

| 2004-08-17

| Collisions originally reported in 2004, followed up by cryptanalysis paper in 2005.{{cite conference |author=Xiaoyun Wang |author2=Xuejia Lai |author3=Dengguo Feng |author4=Hui Chen |author5=Xiuyuan Yu |date=2005-05-23 |title=Cryptanalysis of the Hash Functions MD4 and RIPEMD |conference=Eurocrypt 2005 |doi=10.1007/11426639_1 |doi-access=free }}

RadioGatún

| Up to 2608RadioGatú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.

| 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.{{cite conference |author1=Thomas Fuhr |author2=Thomas Peyrin |date=2008-12-04 |title=Cryptanalysis of RadioGatun |conference=FSE 2009 |url=https://eprint.iacr.org/2008/515 }}

RIPEMD-160

| 280

| 48 of 80 rounds (251 time)

| 2006

| Paper.{{cite conference |author=Florian Mendel |author2=Norbert Pramstaller |author3=Christian Rechberger |author4=Vincent Rijmen |date=2006 |title=On the Collision Resistance of RIPEMD-160 |conference=ISC 2006 |url=https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=17675 }}

style="background: #ff9090; color: black"

| SHA-0

| 280

| 233.6 time

| 2008-02-11

| Two-block collisions using boomerang attack. Attack takes estimated 1 hour on an average PC.{{cite conference |author1=Stéphane Manuel |author2=Thomas Peyrin |date=2008-02-11 |title=Collisions on SHA-0 in One Hour |conference=FSE 2008 |doi=10.1007/978-3-540-71039-4_2 |doi-access=free }}

Streebog

| 2256

| 9.5 rounds of 12 (2176 time, 2128 memory)

| 2013-09-10

| Rebound attack.{{cite journal |author=Zongyue Wang |author2=Hongbo Yu |author3=Xiaoyun Wang |date=2013-09-10 |title=Cryptanalysis of GOST R hash function |journal=Information Processing Letters |volume=114 |issue=12 |pages=655–662 |url=https://eprint.iacr.org/2013/584 |doi=10.1016/j.ipl.2014.07.007|url-access=subscription }}

Whirlpool

| 2256

| 4.5 of 10 rounds (2120 time)

| 2009-02-24

| Rebound attack.{{cite conference |author=Florian Mendel |author2=Christian Rechberger |author3=Martin Schläffer |author4=Søren S. Thomsen |date=2009-02-24 |title=The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl |conference=FSE 2009 |url=https://www.iacr.org/archive/fse2009/56650270/56650270.pdf }}

=Preimage resistance=

class="wikitable" border="1"
Hash function

! Security claim

! Best attack

! Publish date

! Comment

style="background: #ffff90; color: black"

| GOST

| 2256

| 2192

| 2008-08-18

| Paper.

style="background: #ffff90; color: black"

| MD2

| 2128

| 273 time, 273 memory

| 2008

| Paper.{{cite journal |author=Søren S. Thomsen |year=2008 |title=An improved preimage attack on MD2 |journal=Cryptology ePrint Archive |url=https://eprint.iacr.org/2008/089 }}

style="background: #ffff90; color: black"

| MD4

| 2128

| 2102 time, 233 memory

| 2008-02-10

| Paper.{{cite conference |author=Gaëtan Leurent |date=2008-02-10 |title=MD4 is Not One-Way |conference=FSE 2008 |url=https://who.rocq.inria.fr/Gaetan.Leurent/files/MD4_FSE08.pdf }}

RIPEMD (original)

| 2128

| 35 of 48 rounds

| rowspan=3 | 2011

| rowspan=3 | Paper.{{cite conference |author= Chiaki Ohtahara |author2= Yu Sasaki |author3= Takeshi Shimoyama |date=2011 |title=Preimage Attacks on Step-Reduced RIPEMD-128 and RIPEMD-160 |conference=ISC 2011 |doi= 10.1007/978-3-642-21518-6_13 }}

RIPEMD-128

| 2128

| 35 of 64 rounds

RIPEMD-160

| 2160

| 31 of 80 rounds

style="background: #ffff90; color: black"

| Streebog

| 2512

| 2266 time, 2259 data

| 2014-08-29

| The paper presents two second-preimage attacks with variable data requirements.{{cite conference |author=Jian Guo |author2=Jérémy Jean |author3=Gaëtan Leurent |author4=Thomas Peyrin |author5=Lei Wang |date=2014-08-29 |title=The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function |conference=SAC 2014 |url=https://eprint.iacr.org/2014/675 }}

style="background: #ffff90; color: black"

| Tiger

| 2192

| 2188.8 time, 28 memory

| 2010-12-06

| Paper.{{cite conference |author=Jian Guo |author2=San Ling |author3=Christian Rechberger |author4=Huaxiong Wang |date=2010-12-06 |title=Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2 |conference=Asiacrypt 2010 |pages=12–17 |url=https://eprint.iacr.org/2010/016 }}

Attacks on hashed passwords

{{main|Password cracking}}

Hashes described here are designed for fast computation and have roughly similar speeds.{{cite web|url=https://bench.cr.yp.to/results-hash.html |title=ECRYPT Benchmarking of Cryptographic Hashes|access-date=November 23, 2020}} 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.{{cite web|url=https://improsec.com/tech-blog/mind-blowing-gpu-performance|title=Mind-blowing GPU performance|publisher=Improsec|date=January 3, 2020}}{{cite web

| url=https://arstechnica.com/information-technology/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/

| title=25-GPU cluster cracks every standard Windows password in <6 hours

| date=2012-12-10

| first=Dan

| last=Goodin

| publisher=Ars Technica

| access-date=2020-11-23}}

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

{{reflist}}

External links

  • 2010 summary of attacks against Tiger, MD4 and SHA-2: {{cite conference |author=Jian Guo |author2=San Ling |author3=Christian Rechberger |author4=Huaxiong Wang |date=2010-12-06 |title=Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2 |conference=Asiacrypt 2010 |page=3 |url=https://eprint.iacr.org/2010/016 }}

{{cryptography navbox | hash}}

Category:Cryptography lists and comparisons