MD2 (hash function): Difference between revisions

Revision as of 18:32, 29 April 2020

Latest revision as of 04:19, 31 December 2024

(43 intermediate revisions by 28 users not shown)

Line 1:

{{Short description|Obsolete cryptographic hash function}}

{{use dmy dates|date=April 2021}}

{{Infobox cryptographic hash function

| name.mimeyThammakot = MD2

| image =

|image//https://share.icloud.com/photos/0YfG2XySegpx_ZFM4WVW7dPfQ =

| caption =

<!-- General -->

| designers = [[Ronald Rivest]]

| publish date = August 1989<ref name="RFC 1115">{{cite IETF |ref= {{harvid|RFC 1115}}

| publish date = August 1989<ref>John Linn, RFC 1115 - Privacy Enhancement for Internet Electronic Mail: Part III—Algorithms, Modes, and Identifiers, Section 4.2, August 1989, Source by Ron L. Rivest October, 1988.</ref>

|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 =

Line 18 ⟶ 21:

}}

The '''MD2 Message-Digest Algorithm''' is a [[cryptographic hash function]] developed by [[Ronald Rivest]] in 1989.<ref>{{cite web |url=http://www.emc.com/emc-plus/rsa-labs/standards-initiatives/md2-md4-and-md5.htm |title=What are MD2, MD4, and MD5? |accessdate=2011-04-29 |publishername="RSA Laboratories |work=Public-Key Cryptography Standards (PKCS): PKCS #7:" Cryptographic Message Syntax Standard: 3.6 Other Cryptographic Techniques: 3.6.6 What are MD2, MD4, and MD5?}}</ref> The algorithm is optimized for [[8-bit]] computers. MD2 is specified in RFC 1319. Although MD2 is no longer considered secure, even {{As of|2014|lc=on}}, it remains in use in [[publicRequest keyfor infrastructure]]sComments|IETF as part of [[certificate (cryptography)|certificateRFC]]s generated1319.<ref withname="RFC MD21319" and [[RSA (algorithm)|RSA]]./> The "MD" in MD2 stands for "Message Digest". result

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 indirectlyby fromshuffling the digitsintegers 0 through 255 using a variant of the[[Fisher–Yates fractionalshuffle#The partmodern algorithm|Durstenfeld's algorithm]] with a [[pseudorandom number generator]] based on decimal digits of [[pi|{{pi}} (pi)]]<ref arename="RFC used1319" /><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:

The S-table's values are derived from Pi,<ref>{{cite web|last1=Kaliski|first1=Burt|authorlink1=Burt Kaliski|title=RFC 1319 - The MD2 Message-Digest Algorithm|url=http://tools.ietf.org/html/rfc1319|publisher=RSA Laboratories|accessdate=22 November 2014|page=3|date=April 1992}}</ref><ref>{{cite web|title=How is the MD2 hash function S-table constructed from Pi?|url=https://crypto.stackexchange.com/questions/11935/how-is-the-md2-hash-function-s-table-constructed-from-pi|website=Cryptography Stack Exchange|publisher=Stack Exchange|accessdate=22 November 2014|date=2 August 2014}}</ref> and in hex are:

{ 0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01, 0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13,

Line 49 ⟶ 56:

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 <tt>{{mono|d</tt>}} to <tt>{{mono|c</tt>}} in the message results in:

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

Line 60 ⟶ 67:

==Security==

Rogier and Chauvaud (1997)presented describedin 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¹⁰⁴ 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⁷³ compression function evaluations and memory requirements of 2⁷³ message blocks.<ref>{{cite paper |authorname=Søren S. "Thomsen |year=2008" |title=An improved preimage attack on MD2 |url=http://eprint.iacr.org/2008/089.pdf }}</ref>

In 2009, MD2 was shown to be vulnerable to a [[collision attack]] with [[time complexity]] of 2^63.3 compression function evaluations and memory requirements of 2⁵² hash values. This is slightly better than the [[birthday attack]] which is expected to take 2^65.5 compression function evaluations.<ref>{{Cite journal | doiname=10.1007/s00145-009-9054-1|"Knudsen title=Cryptanalysiset ofal MD2| journal=Journal of Cryptology| volume=23| pages=72–90| year=2009| last1=Knudsen| first1=Lars R.| last2=Mathiassen| first2=John Erik| last3=Muller| first3=Frédéric| last4=Thomsen| first4=Søren" S.}}</ref>

In 2009, security updates were issued disabling MD2 in [[OpenSSL]], [[GnuTLS]], and [[Network Security Services]].<ref>[http://cve.mitre.org/cgi-bin/cvename.cgi?name={{CVE-2009-2409 CVE-|2009-2409]}}</ref>

==See also==

Line 79 ⟶ 86:

==References==

{{reflist|refs=

* [[Burt Kaliski]], RFC 1319 - MD2 Message Digest Algorithm, April 1992.

<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>

* N. Rogier, Pascal Chauvaud, The compression function of MD2 is not collision free, ''Selected Areas in Cryptography - SAC'95 Ottawa'', Canada, May 18–19, 1995 (workshop record).

<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>

* N. Rogier, Pascal Chauvaud, MD2 is not Secure without the Checksum Byte, ''Designs, Codes and Cryptography'', 12(3), pp245&ndash;251, 1997.

<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>

* Frédéric Muller, The MD2 Hash Function is Not One-Way, ASIACRYPT 2004, pp214&ndash;229.

<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>

* [[Lars R. Knudsen]] and John Erik Mathiassen, Preimage and Collision Attacks on MD2. FSE 2005.

<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==

<references/>

{{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==

*RFC 1319, The MD2 Message-Digest Algorithm

*RFC 6149, MD2 to Historic Status

* [http://quickhash.com/md2 Online MD2 Calculator over HTTPS]

{{Cryptography navbox | hash}}

[[Category:Broken hash functions]]