Cryptographic hash function: Difference between revisions

Revision as of 18:34, 21 August 2024

Revision as of 01:20, 22 August 2024

Line 178:

Even if a hash function has never been broken, a [[Cryptographic attack#Amount of information available to the attacker|successful attack]] against a weakened variant may undermine the experts' confidence. For instance, in August 2004 collisions were found in several then-popular hash functions, including MD5.<ref name="Mpt5q">XiaoyunWang, Dengguo Feng, Xuejia Lai, Hongbo Yu, [https://eprint.iacr.org/2004/199.pdf Collisions for Hash Functions MD4, MD5, HAVAL-128, and RIPEMD] {{Webarchive|url=https://web.archive.org/web/20041220195626/https://eprint.iacr.org/2004/199.pdf |date=2004-12-20 }}</ref> These weaknesses called into question the security of stronger algorithms derived from the weak hash functions – in particular, SHA-1 (a strengthened version of SHA-0), RIPEMD-128, and RIPEMD-160 (both strengthened versions of RIPEMD).<ref name="R7ASX">{{Citation|last1=Alshaikhli|first1=Imad Fakhri|title=Cryptographic Hash Function|date=2015|work=Handbook of Research on Threat Detection and Countermeasures in Network Security|pages=80–94|publisher=IGI Global |isbn=978-1-4666-6583-5|last2=AlAhmad|first2=Mohammad Abdulateef|doi=10.4018/978-1-4666-6583-5.ch006}}</ref>

On August 12, 2004, Joux, Carribault, Lemuel, and Jalby announced a collision for the full SHA-0 algorithm.{{sfn|Joux|2004}} Joux et al. accomplished this using a generalization of the Chabaud and Joux attack. They found that the collision had complexity {{math|2⁵¹}} and took about 80,000 CPU hours on a [[supercomputer]] with 256 [[Itanium 2]] processors – equivalent to 13 days of full-time use of the supercomputer.{{Citation needed|date=May 2016}}

In February 2005, an attack on SHA-1 was reported that would find collision in about 2⁶⁹ hashing operations, rather than the 2⁸⁰ expected for a 160-bit hash function. In August 2005, another attack on SHA-1 was reported that would find collisions in 2⁶³ operations. Other theoretical weaknesses of SHA-1 have been known:,<ref name="NhaRr">Xiaoyun Wang, [[Yiqun Lisa Yin]], and Hongbo Yu, "[http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf Finding Collisions in the Full SHA-1] {{Webarchive|url=https://web.archive.org/web/20170715064257/http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf |date=2017-07-15 }}".</ref><ref name="CmkOx">{{cite web |first1=Bruce |last1=Schneier |url=http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html |title=Cryptanalysis of SHA-1 |website=Schneier on Security |date=February 18, 2005 |access-date=March 30, 2009 |archive-date=January 16, 2013 |archive-url=https://web.archive.org/web/20130116090105/http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html |url-status=live }} Summarizes Wang et al. results and their implications.</ref> and in February 2017 Google announced a collision in SHA-1.<ref name="xW1m9">{{Cite news |url=https://www.forbes.com/sites/thomasbrewster/2017/02/23/google-sha-1-hack-why-it-matters/#3f73df04c8cd |title=Google Just 'Shattered' An Old Crypto Algorithm – Here's Why That's Big For Web Security |last=Brewster |first=Thomas |date=Feb 23, 2017 |newspaper=Forbes |access-date=2017-02-24 |archive-date=2017-02-24 |archive-url=https://web.archive.org/web/20170224140451/https://www.forbes.com/sites/thomasbrewster/2017/02/23/google-sha-1-hack-why-it-matters/#3f73df04c8cd |url-status=live }}</ref> Security researchers recommend that new applications can avoid these problems by using later members of the SHA family, such as [[SHA-2]], or using techniques such as [[Universal hashing|randomized hashing]]<ref name="MrThfd">{{Cite web |last=Halevi |first=Shai |last2=Krawczyk |first2=Hugo |title=Randomized Hashing and Digital Signatures |url=http://webee.technion.ac.il/~hugo/rhash/ |url-status=dead |archive-url=https://web.archive.org/web/20220522134202/http://webee.technion.ac.il/~hugo/rhash/ |archive-date=May 22, 2022}}</ref> that do not require collision resistance.

A successful, practical attack broke MD5 (used within certificates for [[Transport Layer Security]]) in 2008.<ref name="bVltK">{{Cite web |last=Sotirov |first=A |last2=Stevens |first2=M |last3=Appelbaum |first3=J |last4=Lenstra |first4=A |last5=Molnar |first5=D |last6=Osvik |first6=D A |last7=de Weger |first7=B |date=December 30, 2008 |title=MD5 considered harmful today: Creating a rogue CA certificate |url=http://www.win.tue.nl/hashclash/rogue-ca/ |access-date=March 29, 2009 |website=HashClash |publisher=Department of Mathematics and Computer Science of Eindhoven University of Technology |archive-date=March 25, 2017 |archive-url=https://web.archive.org/web/20170325033522/http://www.win.tue.nl/hashclash/rogue-ca/ |url-status=live }}</ref>

Many cryptographic hashes are based on the [[Merkle–Damgård construction]]. All cryptographic hashes that directly use the full output of a Merkle–Damgård construction are vulnerable to [[length extension attack]]s. This makes the MD5, SHA-1, RIPEMD-160, Whirlpool, and the SHA-256 / SHA-512 hash algorithms all vulnerable to this specific attack. SHA-3, BLAKE2, BLAKE3, and the truncated SHA-2 variants are not vulnerable to this type of attack.{{cit|date=April 2020}}