Editing MD2 (hash function)

{{Short description|Obsolete cryptographic hash function}}
{{use dmy dates|date=April 2021}}
{{Infobox cryptographic hash function
| name           = MD2
| image          = 
| caption        = 
<!-- General -->
| designers      = [[Ronald Rivest]]
| publish date   = August 1989<ref name="RFC 1115">{{cite IETF |ref= {{harvid|RFC 1115}}
|last= Linn |first= John |rfc= 1115 |date= August 1989 |title= Privacy Enhancement for Internet Electronic Mail: Part III — Algorithms, Modes, and Identifiers |section= 4.2 |sectionname= RSA-MD2 Message Digest Algorithm |others= Rivest, Ron |publisher= [[Internet Engineering Task Force|IETF]] |access-date= 26 April 2021 }}</ref>
| series         = MD2, [[MD4]], [[MD5]], [[MD6]]
| derived from   = 
| derived to     = 
| related to     = 
| certification  = 
<!-- Detail -->
| digest size    = 128 bits
| structure      = 
| rounds         = 18
| cryptanalysis  = 
}}

The '''MD2 Message-Digest Algorithm''' is a [[cryptographic hash function]] developed by [[Ronald Rivest]] in 1989.<ref name="RSA PKCS #7" /> The algorithm is optimized for [[8-bit]] computers. MD2 is specified in  [[Request for Comments|IETF RFC]] 1319.<ref name="RFC 1319" /> The "MD" in MD2 stands for "Message Digest".

Even though MD2 is not yet fully compromised, the IETF retired MD2 to "historic" status in 2011, citing "signs of weakness". It is deprecated in favor of [[SHA-2|SHA-256]] and other strong hashing algorithms.<ref>{{IETF RFC|6149}}, MD2 to Historic Status</ref>

Nevertheless, {{As of|2014|lc=on}}, it remained in use in [[public key infrastructure]]s as part of [[certificate (cryptography)|certificate]]s generated with MD2 and [[RSA (algorithm)|RSA]].{{cn|reason=Which PKI(s)? The CA Browser Forum Baseline Requirements (WebPKI) do not allow it.|date=September 2024}}

==Description==

The 128-bit hash value of any message is formed by padding it to a multiple of the block length (128 bits or 16 [[byte]]s) and adding a 16-byte [[checksum]] to it. For the actual calculation, a 48-byte auxiliary block and a 256-byte [[S-table]] are used. The constants were generated by shuffling the integers 0 through 255 using a variant of [[Fisher–Yates shuffle#The modern algorithm|Durstenfeld's algorithm]] with a [[pseudorandom number generator]] based on decimal digits of [[pi|{{pi}} (pi)]]<ref name="RFC 1319" /><ref>{{cite web|date=2 August 2014|title=How is the MD2 hash function S-table constructed from Pi?|url=https://crypto.stackexchange.com/a/18444|access-date=23 May 2021|website=Cryptography Stack Exchange|publisher=Stack Exchange}}</ref> (see [[nothing up my sleeve number]]).  The algorithm runs through a loop where it permutes each byte in the auxiliary block 18 times for every 16 input bytes processed.  Once all of the blocks of the (lengthened) message have been processed, the first partial block of the auxiliary block becomes the hash value of the message.

The S-table values in hex are:

 { 0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01, 0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13, 
   0x62, 0xA7, 0x05, 0xF3, 0xC0, 0xC7, 0x73, 0x8C, 0x98, 0x93, 0x2B, 0xD9, 0xBC, 0x4C, 0x82, 0xCA, 
   0x1E, 0x9B, 0x57, 0x3C, 0xFD, 0xD4, 0xE0, 0x16, 0x67, 0x42, 0x6F, 0x18, 0x8A, 0x17, 0xE5, 0x12, 
   0xBE, 0x4E, 0xC4, 0xD6, 0xDA, 0x9E, 0xDE, 0x49, 0xA0, 0xFB, 0xF5, 0x8E, 0xBB, 0x2F, 0xEE, 0x7A, 
   0xA9, 0x68, 0x79, 0x91, 0x15, 0xB2, 0x07, 0x3F, 0x94, 0xC2, 0x10, 0x89, 0x0B, 0x22, 0x5F, 0x21,
   0x80, 0x7F, 0x5D, 0x9A, 0x5A, 0x90, 0x32, 0x27, 0x35, 0x3E, 0xCC, 0xE7, 0xBF, 0xF7, 0x97, 0x03, 
   0xFF, 0x19, 0x30, 0xB3, 0x48, 0xA5, 0xB5, 0xD1, 0xD7, 0x5E, 0x92, 0x2A, 0xAC, 0x56, 0xAA, 0xC6, 
   0x4F, 0xB8, 0x38, 0xD2, 0x96, 0xA4, 0x7D, 0xB6, 0x76, 0xFC, 0x6B, 0xE2, 0x9C, 0x74, 0x04, 0xF1, 
   0x45, 0x9D, 0x70, 0x59, 0x64, 0x71, 0x87, 0x20, 0x86, 0x5B, 0xCF, 0x65, 0xE6, 0x2D, 0xA8, 0x02, 
   0x1B, 0x60, 0x25, 0xAD, 0xAE, 0xB0, 0xB9, 0xF6, 0x1C, 0x46, 0x61, 0x69, 0x34, 0x40, 0x7E, 0x0F, 
   0x55, 0x47, 0xA3, 0x23, 0xDD, 0x51, 0xAF, 0x3A, 0xC3, 0x5C, 0xF9, 0xCE, 0xBA, 0xC5, 0xEA, 0x26, 
   0x2C, 0x53, 0x0D, 0x6E, 0x85, 0x28, 0x84, 0x09, 0xD3, 0xDF, 0xCD, 0xF4, 0x41, 0x81, 0x4D, 0x52, 
   0x6A, 0xDC, 0x37, 0xC8, 0x6C, 0xC1, 0xAB, 0xFA, 0x24, 0xE1, 0x7B, 0x08, 0x0C, 0xBD, 0xB1, 0x4A, 
   0x78, 0x88, 0x95, 0x8B, 0xE3, 0x63, 0xE8, 0x6D, 0xE9, 0xCB, 0xD5, 0xFE, 0x3B, 0x00, 0x1D, 0x39, 
   0xF2, 0xEF, 0xB7, 0x0E, 0x66, 0x58, 0xD0, 0xE4, 0xA6, 0x77, 0x72, 0xF8, 0xEB, 0x75, 0x4B, 0x0A, 
   0x31, 0x44, 0x50, 0xB4, 0x8F, 0xED, 0x1F, 0x1A, 0xDB, 0x99, 0x8D, 0x33, 0x9F, 0x11, 0x83, 0x14 }

==MD2 hashes==
The 128-bit (16-byte) MD2 hashes (also termed ''message digests'') are typically represented as 32-digit [[hexadecimal]] numbers. The following demonstrates a 43-byte [[ASCII]] input and the corresponding MD2 hash:

  MD2("The quick brown fox jumps over the lazy {{Background color|#87CEEB|d}}og") = 
  03d85a0d629d2c442e987525319fc471

As the result of the [[avalanche effect]] in MD2, even a small change in the input message will (with overwhelming probability) result in a completely different hash. For example, changing the letter {{mono|d}} to {{mono|c}} in the message results in:

  MD2("The quick brown fox jumps over the lazy {{Background color|#87CEEB|c}}og") = 
  6b890c9292668cdbbfda00a4ebf31f05

The hash of the zero-length string is:

  MD2("") = 
  8350e5a3e24c153df2275c9f80692773

==Security==
Rogier and Chauvaud presented in 1995<ref name="Rogier Chauvaud 1995" /> collisions of MD2's [[One-way compression function|compression function]], although they were unable to extend the attack to the full MD2. The described collisions was published in 1997.<ref name="Rogier Chauvaud 1997" />

In 2004, MD2 was shown to be vulnerable to a [[preimage attack]] with [[time complexity]] equivalent to 2<sup>104</sup> applications of the compression function.<ref name="Muller 2004" /> The author concludes, "MD2 can no longer be considered a secure one-way hash function".

In 2008, MD2 has further improvements on a [[preimage attack]] with [[time complexity]] of 2<sup>73</sup> compression function evaluations and memory requirements of 2<sup>73</sup> message blocks.<ref name="Thomsen 2008" />

In 2009, MD2 was shown to be vulnerable to a [[collision attack]] with [[time complexity]] of 2<sup>63.3</sup> compression function evaluations and memory requirements of 2<sup>52</sup> hash values.  This is slightly better than the [[birthday attack]] which is expected to take 2<sup>65.5</sup> compression function evaluations.<ref name="Knudsen et al 2009" />

In 2009, security updates were issued disabling MD2 in [[OpenSSL]], [[GnuTLS]], and [[Network Security Services]].<ref>{{CVE|2009-2409}}</ref>

==See also==
* [[Hash function security summary]]
* [[Comparison of cryptographic hash functions]]
* [[MD4]]
* [[MD5]]
* [[MD6]]
* [[SHA-1]]

==References==
{{reflist|refs=
<ref name="RFC 1319">{{cite IETF |last= Kaliski |first= Burt |author-link1= Burt Kaliski |rfc= 1319 |date= April 1992 |title= The MD2 Message-Digest Algorithm |page= 3 |publisher= [[Internet Engineering Task Force|IETF]] |access-date= 22 November 2014 }}</ref>
<ref name="Knudsen et al 2009">{{Cite journal |last1= Knudsen |first1= Lars R. |last2= Mathiassen |first2= John Erik |last3= Muller |first3= Frédéric |last4= Thomsen |first4= Søren S. |date= 2009  |title=Cryptanalysis of MD2 |journal= Journal of Cryptology |volume= 23 |pages= 72–90 |s2cid= 2443076 |doi= 10.1007/s00145-009-9054-1 |doi-access= free }}</ref>
<ref name="Muller 2004">{{cite conference |last= Muller |first= Frédéric |date= 2004 |title= The MD2 Hash Function is Not One-Way |conference= ASIACRYPT 2004 |pages= 214–229 |doi= 10.1007/978-3-540-30539-2_16 |url= https://www.iacr.org/conferences/asiacrypt2004/data/Asiacrypt2004/05%20Hash%20Functions/03_Frederic%20Muller.pdf |access-date= 26 April 2021 |via= [[International Association for Cryptologic Research]] |doi-access= free }}</ref>
<ref name="RSA PKCS #7">{{cite web |author= RSA Laboratories |title= What are MD2, MD4, and MD5? |publisher= RSA Laboratories |work= Public-Key Cryptography Standards (PKCS): PKCS #7: Cryptographic Message Syntax Standard |url=http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/md2-md4-and-md5.htm |archive-url= https://web.archive.org/web/20170116172936/http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/md2-md4-and-md5.htm |archive-date= 16 January 2017 }}</ref>
<ref name="Thomsen 2008">{{cite journal |last= Thomsen |first= Søren S. |date= 2008 |title= An Improved Preimage Attack on MD2 |url= http://eprint.iacr.org/2008/089.pdf }}</ref>
<ref name="Rogier Chauvaud 1997">{{cite journal | last=Rogier | first=N. | last2=Chauvaud | first2=Pascal | title=MD2 is not Secure without the Checksum Byte | journal=Designs, Codes and Cryptography | volume=12 | issue=3 | date=1997 | doi=10.1023/A:1008220711840 | s2cid=21613457 | pages=245–251}}</ref>
<ref name="Rogier Chauvaud 1995">{{cite conference |last1= Rogier |first1= N. |last2= Chauvaud |first2= Pascal |date= 18–19 May 1995 |title= The Compression Function of MD2 is not Collision Free |conference= Selected Areas in Cryptography (SAC) 1995, Ottawa, Canada |type= workshop record }}</ref>
}}

==Further reading==
{{refbegin}}
* {{cite conference |last1= Knudsen |first= Lars R. |author-link1= Lars R. Knudsen |last2= Mathiassen |first2= John Erik |date= 21–23 February 2005 |title= Preimage and Collision Attacks on MD2 |conference= Fast Software Encryption (FSE) 2005 |url= https://www.iacr.org/cryptodb/archive/2005/FSE/3106/3106.pdf |access-date= 26 April 2021 }}
{{refend}}

==External links==
{{Cryptography navbox | hash}}


[[Category:Broken hash functions]]