MD2 was a hash function based on swapping bytes in a state array permutation, much like the RC4 stream cipher, whereas MD4 was a novel construction. MD4 replaced MD2 despite the fact that MD4 is more badly broken. Even MD5, an improvement upon MD4, is more badly broken than MD2 is! The best collision attack against MD2 has a time complexity of 263.3 compression function evaluations and a memory requirement of 252 hash values, which is only slightly better than the birthday attack and not significantly different from the collision attack against SHA-1 (263.1 time). It seems to me like people could have saved a lot of trouble by using MD2 until the collision attack became feasible, skipping MD4, MD5, and even SHA-1, but clearly this did not happen. So why was MD2 dropped for MD4 and friends?
-
2$\begingroup$ Note: These attacks are all far more expensive than generic search (and some of them are obviously slower too at the same circuit area cost). It's not clear that the preimage resistance of MD2 or MD4 is broken. $\endgroup$– Squeamish OssifrageCommented Feb 18, 2019 at 23:29
-
$\begingroup$ @SqueamishOssifrage Indeed. I suppose mentioning preimage resistance was a bit of a red herring, but my point was that it isn't broken for any of these functions, yet MD2 still fares better wrt collision attacks. $\endgroup$– forestCommented Feb 18, 2019 at 23:30
-
1$\begingroup$ I'm not familiar with the history or rather the volume of cryptanalysis of these, but it may be not that they are less broken, but that they have received more analysis that uncovered their flaws. AES could be said to be more broken than insert-other-cipher-here, while insert-other-cipher-here is in fact more broken but only has 1 public cryptanalysis paper. In such a situation, AES would look worse, despite being actually stronger. No idea if this is applicable here, but it could be. $\endgroup$– Ella RoseCommented Feb 18, 2019 at 23:52
-
$\begingroup$ @EllaRose That's very possible, but I have a feeling it's more likely related to performance or something along that line (MD2 uses 8-bit operations whereas MD4 uses 32-bit operations). $\endgroup$– forestCommented Feb 18, 2019 at 23:58
1 Answer
We can get some clues from the various Internet RFCs defining or mentioning the three algorithms. There appear to have been two advantages of MD4, and subsequently MD5:
- Performance
- Licensing
It also appears that an attack on MD2 was expected long before one was found for MD5, even if none was actually found.
August 1989: RFC 1115 defines MD2. It is presented as part of a series of RFCs for Privacy Enhanced Mail. It states simply:
It has been provided by Ron Rivest of RSA Data Security, Incorporated for use in support of privacy-enhanced electronic mail, free of licensing restrictions.
The "specification" is simply the source code of a reference implementation in C, dated "10/1/88" (presumably 1st October 1988)
October 1990: RFC 1186 defines MD4. Oddly, there is no mention of MD2 in the entire document.
Unlike RFC 1115, MD4 is presented as a general purpose algorithm, rather than as part of a particular framework:
The MD4 algorithm is thus ideal for digital signature applications, where a large file must be "compressed" in a secure manner before being signed with the RSA public-key cryptosystem.
Intellectual property rights are also more clearly waived for any and all purposes:
The MD4 algorithm is being placed in the public domain for review and possible adoption as a standard.
There is a clear emphasis on the algorithm's performance:
The MD4 algorithm is designed to be quite fast on 32-bit machines. On a SUN Sparc station, MD4 runs at 1,450,000 bytes/second. On a DEC MicroVax II, MD4 runs at approximately 70,000 bytes/second. On a 20MHz 80286, MD4 runs at approximately 32,000 bytes/second. In addition, the MD4 algorithm does not require any large substitution tables; the algorithm can be coded quite compactly.
Buried in the summary is a disclaimer that this is a novel algorithm, and may need further scrutiny:
The MD4 algorithm has been carefully scrutinized for weaknesses. It is, however, a relatively new algorithm and further security analysis is of course justified, as is the case with any new proposal of this sort.
April 1992: RFCs 1319, 1320, and 1321 respectively re-define MD2 and MD4, and define MD5
Although clearly published as a series, there doesn't appear to be any comparison of MD2 against MD4 or MD5 in any of these three. All three RFCs include a reference implementation that actually implements all three algorithms.
RFC 1319's main purpose is to provide a textual description of the algorithm, and a more portable reference implementation. It also incorporates the purpose statement applied to MD4:
The MD2 algorithm is intended for digital signature applications, where a large file must be "compressed" in a secure manner before being signed with a private (secret) key under a public-key cryptosystem such as RSA.
Although it goes on to say:
License to use MD2 is granted for non-commerical Internet Privacy-Enhanced Mail
Which appears to be more restrictive than "placed in the public domain", and makes it ambiguous whether the algorithm could be used outside that realm, if it was protected by any intellectual property laws.
Under "Security Considerations", confidence in MD2's security is stated bluntly:
The level of security discussed in this memo is considered to be sufficient for implementing very high security hybrid digital signature schemes based on MD2 and a public-key cryptosystem.
RFC 1320 is a minor revision of the previous MD4 description, with the new reference implementation.
The concerns previously mentioned in the Summary are now prominent in the Security Considerations section, with a mild recommendation to try MD5 instead:
We do not know of any reason that MD4 would not be sufficient for implementing very high security digital-signature schemes, but because MD4 was designed to be exceptionally fast, it is "at the edge" in terms of risking successful cryptanalytic attack. After further critical review, it may be appropriate to consider MD4 for very high security applications. For very high security applications before the completion of that review, the MD5 algorithm [4] is recommended.
RFC 1321 is the first to define MD5. Its introduction includes most of the same claims of speed, compactness, and general applicability as MD4, along with an explanation for why a new algorithm was designed:
The MD5 algorithm is an extension of the MD4 message-digest algorithm. MD5 is slightly slower than MD4, but is more "conservative" in design. MD5 was designed because it was felt that MD4 was perhaps being adopted for use more quickly than justified by the existing critical review; because MD4 was designed to be exceptionally fast, it is "at the edge" in terms of risking successful cryptanalytic attack. MD5 backs off a bit, giving up a little in speed for a much greater likelihood of ultimate security. It incorporates some suggestions made by various reviewers, and contains additional optimizations.
It also includes the same unambiguous licensing statement:
The MD5 algorithm is being placed in the public domain for review and possible adoption as a standard.
March 1998: RFC 2313 references all three algorithms. After repeating that MD4 is "on the edge" because of its emphasis on speed, it compares MD2 and MD5:
MD5, which has four rounds and is proportionally slower than MD4, is recommended until the completion of MD4's review. The reported "pseudocollisions" in MD5's internal compression function [dBB93] do not appear to have any practical impact on MD5's security.
MD2, the slowest of the three, has the most conservative design. No attacks on MD2 have been published.
April 2002: RFC 3279 references MD2. It includes this interesting note, which confirms my suspicion about licensing issues with MD2:
MD2 was developed by Ron Rivest for RSA Security. RSA Security has recently placed the MD2 algorithm in the public domain. Previously, RSA Data Security had granted license for use of MD2 for non- commercial Internet Privacy-Enhanced Mail (PEM).
It doesn't give any reference for this release, so it's not clear how "recent" it was.
It also somewhat contradicts the assertion quoted above from RFC 2313, citing a partial attack on MD2 published in 1995:
At the Selected Areas in Cryptography '95 conference in May 1995, Rogier and Chauvaud presented an attack on MD2 that can nearly find collisions. Collisions occur when one can find two different messages that generate the same message digest. A checksum operation in MD2 is the only remaining obstacle to the success of the attack. For this reason, the use of MD2 for new applications is discouraged.
March 2011: RFCs 6149, 6150, and 6151 retire or update the status of all three algorithms. 19 years after the previous series, we get some retrospective analysis.
RFC 6149 retires MD2, citing as rationale:
MD2 was published in 1992 as an Informational RFC. Since its publication, MD2 has been shown to not be collision-free [ROCH1995] [KNMA2005] [ROCH1997], albeit successful collision attacks for properly implemented MD2 are not that damaging. Successful pre-image and second pre-image attacks against MD2 have been shown [KNMA2005] [MULL2004] [KMM2010].
It gives a list of RFCs which reference MD2; most appear to have offered it as an option alongside MD5.
More interestingly for our purposes, it notes that:
MD2 has also fallen out of favor because it is slower than both MD4 [MD4] and MD5 [MD5]. This is because MD2 was optimized for 8-bit machines, while MD4 and MD5 were optimized for 32-bit machines. MD2 is also slower than the Secure Hash Standard (SHS) [SHS] algorithms: SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512.
RFC 6150 retires MD4, with a similar, but stronger rationale. Amusingly, there are a number of accidental mentions of "MD2" instead of "MD4" in the RFC text, but there doesn't appear to be any explicit comparison.
Unlike MD2, the RFC includes extensive documentation on breaks in MD4; it seems Rivest was right to warn of its untested nature in 1992.
RFC 6151 doesn't go as far as retiring MD5, instead advising against some uses.
Where the MD5 checksum is used inline with the protocol solely to protect against errors, an MD5 checksum is still an acceptable use.
but
MD5 is no longer acceptable where collision resistance is required such as digital signatures.
It makes no mention of MD2 or MD4, other than referencing papers that covered both MD4 and MD5 in their cryptanalysis.
