MD2 (hash function)

<h2 id="description">Description</h2>
<p>The 128-bit hash value of any message is formed by padding it to a multiple of the block length (128 bits or 16 <a href="/facts/Byte/BNHUp9Qq">bytes</a>) and adding a 16-byte <a href="/facts/Checksum/AqxQ0I8g">checksum</a> to it. For the actual calculation, a 48-byte auxiliary block and a 256-byte <a href="/facts/S-table/9xKgnLCF">S-table</a> are used. The constants were generated by shuffling the integers 0 through 255 using a variant of <a href="/facts/Fisher%E2%80%93Yates_shuffle/fIkuVG2X">Durstenfeld's algorithm</a> with a <a href="/facts/Pseudorandom_number_generator/sIrCxIBq">pseudorandom number generator</a> based on decimal digits of <a href="/facts/Pi/vC0UBj1q">π (pi)</a><a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a><a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> (see <a href="/facts/Nothing_up_my_sleeve_number/AwqF2wkR">nothing up my sleeve number</a>).  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.
</p><p>The S-table values in hex are:
</p>
{ 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 }

<h2 id="md2-hashes">MD2 hashes</h2>
<p>The 128-bit (16-byte) MD2 hashes (also termed <i>message digests</i>) are typically represented as 32-digit <a href="/facts/Hexadecimal/02ohQW22">hexadecimal</a> numbers. The following demonstrates a 43-byte <a href="/facts/ASCII/vGUI33Qu">ASCII</a> input and the corresponding MD2 hash:
</p>
 MD2("The quick brown fox jumps over the lazy dog") = 
 03d85a0d629d2c442e987525319fc471

<p>As the result of the <a href="/facts/Avalanche_effect/hpYX5zu5">avalanche effect</a> 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 d to c in the message results in:
</p>
 MD2("The quick brown fox jumps over the lazy cog") = 
 6b890c9292668cdbbfda00a4ebf31f05

<p>The hash of the zero-length string is:
</p>
 MD2("") = 
 8350e5a3e24c153df2275c9f80692773

<h2 id="security">Security</h2>
<p>Rogier and Chauvaud presented in 1995<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> collisions of MD2's <a href="/facts/One-way_compression_function/Rog6N1KR">compression function</a>, although they were unable to extend the attack to the full MD2. The described collisions was published in 1997.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a>
</p><p>In 2004, MD2 was shown to be vulnerable to a <a href="/facts/Preimage_attack/dDktzjys">preimage attack</a> with <a href="/facts/Time_complexity/77T62gmf">time complexity</a> equivalent to 2104 applications of the compression function.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> The author concludes, "MD2 can no longer be considered a secure one-way hash function".
</p><p>In 2008, MD2 has further improvements on a <a href="/facts/Preimage_attack/dDktzjys">preimage attack</a> with <a href="/facts/Time_complexity/77T62gmf">time complexity</a> of 273 compression function evaluations and memory requirements of 273 message blocks.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a>
</p><p>In 2009, MD2 was shown to be vulnerable to a <a href="/facts/Collision_attack/6aXFAMbW">collision attack</a> with <a href="/facts/Time_complexity/77T62gmf">time complexity</a> of 263.3 compression function evaluations and memory requirements of 252 hash values.  This is slightly better than the <a href="/facts/Birthday_attack/he1GAUSM">birthday attack</a> which is expected to take 265.5 compression function evaluations.<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a>
</p><p>In 2009, security updates were issued disabling MD2 in <a href="/facts/OpenSSL/aXvs5fo2">OpenSSL</a>, <a href="/facts/GnuTLS/y3fYe3RI">GnuTLS</a>, and <a href="/facts/Network_Security_Services/y7bq3SV2">Network Security Services</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Hash_function_security_summary/lksNR2aq">Hash function security summary</a></li>
<li><a href="/facts/Comparison_of_cryptographic_hash_functions/QmSFYAa5">Comparison of cryptographic hash functions</a></li>
<li><a href="/facts/MD4/V3dLUpRk">MD4</a></li>
<li><a href="/facts/MD5/8WIXb9Dq">MD5</a></li>
<li><a href="/facts/MD6/m2R6ysYL">MD6</a></li>
<li><a href="/facts/SHA-1/LDYCV1je">SHA-1</a></li></ul>

<h2 id="further-reading">Further reading</h2>

<ul><li><a href="/facts/Lars_R._Knudsen/ludw9nqB">Knudsen, Lars R.</a>; Mathiassen, John Erik (21–23 February 2005). <a href="https://www.iacr.org/cryptodb/archive/2005/FSE/3106/3106.pdf"><i>Preimage and Collision Attacks on MD2</i></a> (PDF). Fast Software Encryption (FSE) 2005. Retrieved 26 April 2021.</li></ul>

<h2 id="external-links">External links</h2>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Kaliski, Burt (April 1992). The MD2 Message-Digest Algorithm. IETF. p. 3. doi:10.17487/RFC1319. RFC 1319. Retrieved 22 November 2014. <a href="/wiki/Burt_Kaliski" target="_blank">/wiki/Burt_Kaliski</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>RFC 6149, MD2 to Historic Status <a href="/wiki/RFC_(identifier)" target="_blank">/wiki/RFC_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Kaliski, Burt (April 1992). The MD2 Message-Digest Algorithm. IETF. p. 3. doi:10.17487/RFC1319. RFC 1319. Retrieved 22 November 2014. <a href="/wiki/Burt_Kaliski" target="_blank">/wiki/Burt_Kaliski</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>"How is the MD2 hash function S-table constructed from Pi?". Cryptography Stack Exchange. Stack Exchange. 2 August 2014. Retrieved 23 May 2021. <a href="https://crypto.stackexchange.com/a/18444" target="_blank">https://crypto.stackexchange.com/a/18444</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Rogier, N.; Chauvaud, Pascal (18–19 May 1995). The Compression Function of MD2 is not Collision Free. Selected Areas in Cryptography (SAC) 1995, Ottawa, Canada (workshop record). <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Rogier, N.; Chauvaud, Pascal (1997). "MD2 is not Secure without the Checksum Byte". Designs, Codes and Cryptography. 12 (3): 245–251. doi:10.1023/A:1008220711840. S2CID 21613457. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Muller, Frédéric (2004). The MD2 Hash Function is Not One-Way (PDF). ASIACRYPT 2004. pp. 214–229. doi:10.1007/978-3-540-30539-2_16. Retrieved 26 April 2021 – via International Association for Cryptologic Research. <a href="https://www.iacr.org/conferences/asiacrypt2004/data/Asiacrypt2004/05%20Hash%20Functions/03_Frederic%20Muller.pdf" target="_blank">https://www.iacr.org/conferences/asiacrypt2004/data/Asiacrypt2004/05%20Hash%20Functions/03_Frederic%20Muller.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Thomsen, Søren S. (2008). "An Improved Preimage Attack on MD2" (PDF). {{cite journal}}: Cite journal requires |journal= (help) <a href="http://eprint.iacr.org/2008/089.pdf" target="_blank">http://eprint.iacr.org/2008/089.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Knudsen, Lars R.; Mathiassen, John Erik; Muller, Frédéric; Thomsen, Søren S. (2009). "Cryptanalysis of MD2". Journal of Cryptology. 23: 72–90. doi:10.1007/s00145-009-9054-1. S2CID 2443076. <a href="https://doi.org/10.1007%2Fs00145-009-9054-1" target="_blank">https://doi.org/10.1007%2Fs00145-009-9054-1</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>CVE-2009-2409 <a href="/wiki/CVE_(identifier)" target="_blank">/wiki/CVE_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
</ol>

MD2 (hash function) open-in-new

MD2 (hash function)