Editing MD5 (section)

==History and cryptanalysis==
MD5 is one in a series of [[message digest]] algorithms designed by Professor [[Ronald Rivest]] of [[Massachusetts Institute of Technology|MIT]] (Rivest, 1992).  When analytic work indicated that MD5's predecessor [[MD4]] was likely to be insecure, Rivest designed MD5 in 1991 as a secure replacement. ([[Hans Dobbertin]] did indeed later find weaknesses in MD4.)

In 1993, Den Boer and Bosselaers gave an early, although limited, result of finding a "[[hash collision|pseudo-collision]]" of the MD5 [[One-way compression function|compression function]]; that is, two different [[initialization vector]]s that produce an identical digest.

In 1996, Dobbertin announced a collision of the compression function of MD5 (Dobbertin, 1996). While this was not an attack on the full MD5 hash function, it was close enough for cryptographers to recommend switching to a replacement, such as [[SHA-1]] (also compromised since) or [[RIPEMD-160]].

The size of the hash value (128 bits) is small enough to contemplate a [[birthday attack]]. [[MD5CRK]] was a [[distributed computing|distributed project]] started in March 2004 to demonstrate that MD5 is practically insecure by finding a collision using a birthday attack.

MD5CRK ended shortly after 17 August 2004, when [[hash collision|collisions]] for the full MD5 were announced by [[Xiaoyun Wang]], Dengguo Feng, [[Xuejia Lai]], and Hongbo Yu.<ref name="autogenerated2" /><ref>{{cite journal |last1=Hawkes |first1=Philip |last2=Paddon |first2=Michael |last3=Rose |first3=Gregory G. |author-link3=Gregory G. Rose |title=Musings on the Wang et al. MD5 Collision |journal=[[Cryptology ePrint Archive]] |date=13 Oct 2004 |url=https://eprint.iacr.org/2004/264 |access-date=10 October 2018 |archive-url=https://web.archive.org/web/20181105220829/https://eprint.iacr.org/2004/264 |archive-date=5 November 2018 }}</ref> Their analytical attack was reported to take only one hour on an [[IBM p690]] cluster.<ref>{{cite web|url=http://www.bishopfox.com/resources/tools/other-free-tools/md4md5-collision-code/|title=Fast MD5 and MD4 Collision Generators |website=BishopFox |date=26 September 2013|author=Bishop Fox|access-date=10 February 2014|archive-date=26 April 2017|archive-url=https://web.archive.org/web/20170426171733/http://www.bishopfox.com/resources/tools/other-free-tools/md4md5-collision-code/}}</ref>

On 1 March 2005, [[Arjen Lenstra]], [[Wang Xiaoyun|Xiaoyun Wang]], and Benne de Weger demonstrated construction of two [[X.509]] certificates with different public keys and the same MD5 hash value, a demonstrably practical collision.<ref>{{cite journal |last1=Lenstra |first1=Arjen |last2=Wang |first2=Xiaoyun |last3=Weger |first3=Benne de |author-link1=Arjen Lenstra |author-link2=Xiaoyun Wang |title=Colliding X.509 Certificates |journal=[[Cryptology ePrint Archive]] |date=1 Mar 2005 |url=http://eprint.iacr.org/2005/067 |access-date=10 October 2018 |archive-date=23 May 2017 |archive-url=https://web.archive.org/web/20170523000238/http://eprint.iacr.org/2005/067 |url-status=live }}</ref> The construction included private keys for both public keys. A few days later, [[Vlastimil Klima]] described an improved algorithm, able to construct MD5 collisions in a few hours on a single notebook computer.<ref>{{cite journal |last1=Klíma |first1=Vlastimil |author-link1=Vlastimil Klíma |title=Finding MD5 Collisions&nbsp;– a Toy For a Notebook |journal=[[Cryptology ePrint Archive]] |date=5 Mar 2005 |url=http://eprint.iacr.org/2005/075 |access-date=10 October 2018 |archive-date=17 May 2017 |archive-url=https://web.archive.org/web/20170517175404/http://eprint.iacr.org/2005/075 |url-status=live }}</ref> On 18 March 2006, Klima published an algorithm that could find a collision within one minute on a single notebook computer, using a method he calls tunneling.<ref>Vlastimil Klima: [http://eprint.iacr.org/2006/105 Tunnels in Hash Functions: MD5 Collisions Within a Minute] {{Webarchive|url=https://web.archive.org/web/20110806052832/http://eprint.iacr.org/2006/105 |date=6 August 2011 }}, Cryptology ePrint Archive Report 2006/105, 18 March 2006, revised 17 April 2006. Retrieved 27 July 2008.</ref>

Various MD5-related [[Request for Comments#Obtaining RFCs|RFC errata]] have been published. 
In 2009, the [[United States Cyber Command]] used an MD5 hash value of their mission statement as a part of their official emblem.<ref>{{cite magazine
|url= https://www.wired.com/dangerroom/2010/07/code-cracked-cyber-command-logos-mystery-solved/
|title= Code Cracked! Cyber Command Logo Mystery Solved
|magazine= [[United States Cyber Command|USCYBERCOM]]
|publisher= [[Wired News]]
|date= 8 July 2010
|access-date= 29 July 2011
|archive-date= 17 February 2014
|archive-url= https://web.archive.org/web/20140217212938/http://www.wired.com/dangerroom/2010/07/code-cracked-cyber-command-logos-mystery-solved/
|url-status= live
}}</ref>

On 24 December 2010, Tao Xie and Dengguo Feng announced the first published single-block (512-bit) MD5 collision.<ref>{{cite web
|url=http://eprint.iacr.org/2010/643
|title=Construct MD5 Collisions Using Just A Single Block Of Message
|year=2010
|format=PDF
|author1=Tao Xie
|author2=Dengguo Feng
|access-date=28 July 2011
|archive-date=14 May 2017
|archive-url=https://web.archive.org/web/20170514185806/http://eprint.iacr.org/2010/643
|url-status=live
}}</ref> (Previous collision discoveries had relied on multi-block attacks.) For "security reasons", Xie and Feng did not disclose the new attack method. They issued a challenge to the cryptographic community, offering a US$10,000 reward to the first finder of a different 64-byte collision before 1 January 2013. [[Marc Stevens (cryptology)|Marc Stevens]] responded to the challenge and published colliding single-block messages as well as the construction algorithm and sources.<ref>{{cite web |url= http://marc-stevens.nl/research/md5-1block-collision/ |title= Marc Stevens – Research – Single-block collision attack on MD5 |publisher= Marc-stevens.nl |date= 2012 |access-date= 10 April 2014 |archive-date= 15 May 2017 |archive-url= https://web.archive.org/web/20170515070731/http://marc-stevens.nl/research/md5-1block-collision/ |url-status= live }}</ref>

In 2011 an informational RFC 6151<ref>{{cite journal|url=https://tools.ietf.org/html/rfc6151|title=RFC 6151 – Updated Security Considerations for the MD5 Message-Digest and the HMAC-MD5 Algorithms|website=Internet Engineering Task Force|date=March 2011|access-date=11 November 2013|last1=Turner|first1=Sean|doi=10.17487/RFC6151|archive-date=15 June 2017|archive-url=https://web.archive.org/web/20170615213134/https://tools.ietf.org/html///rfc6151|url-status=live}}</ref> was approved to update the security considerations in MD5<ref>{{cite journal |url=https://tools.ietf.org/html/rfc1321 |title=RFC 1321 – The MD5 Message-Digest Algorithm |website=Internet Engineering Task Force |date=April 1992 |access-date=5 October 2013 |last1=Rivest |first1=Ronald L. |doi=10.17487/RFC1321 |doi-access=free |archive-date=9 April 2021 |archive-url=https://web.archive.org/web/20210409200613/https://tools.ietf.org/html/rfc1321 |url-status=live |hdl=1721.1/149165 |hdl-access=free }}</ref> and HMAC-MD5.<ref>{{cite journal |url= https://tools.ietf.org/html/rfc2104 |title= RFC 2104 – HMAC: Keyed-Hashing for Message Authentication |website= Internet Engineering Task Force |date= February 1997 |access-date= 5 October 2013 |last1= Krawczyk |first1= Hugo |last2= Bellare |first2= Mihir |last3= Canetti |first3= Ran |doi= 10.17487/RFC2104 |archive-date= 15 April 2021 |archive-url= https://web.archive.org/web/20210415003434/https://tools.ietf.org/html/rfc2104 |url-status= live }}</ref>