6149
INFORMATIONAL
MD2 to Historic Status
Authors: S. Turner, L. Chen
Date: March 2011
Working Group: NON WORKING GROUP
Stream: IETF
Obsoletes:
RFC 1319
Abstract
This document retires MD2 and discusses the reasons for doing so. This document moves RFC 1319 to Historic status. This document is not an Internet Standards Track specification; it is published for informational purposes.
RFC 6149
INFORMATIONAL
Errata Exist
Internet Engineering Task Force (IETF) S. Turner
Request for Comments: 6149 IECA
Obsoletes: <a href="./rfc1319">1319</a> L. Chen
Category: Informational NIST
ISSN: 2070-1721 March 2011
<span class="h1">MD2 to Historic Status</span>
Abstract
This document retires MD2 and discusses the reasons for doing so.
This document moves <a href="./rfc1319">RFC 1319</a> to Historic status.
Status of This Memo
This document is not an Internet Standards Track specification; it is
published for informational purposes.
This document is a product of the Internet Engineering Task Force
(IETF). It represents the consensus of the IETF community. It has
received public review and has been approved for publication by the
Internet Engineering Steering Group (IESG). Not all documents
approved by the IESG are a candidate for any level of Internet
Standard; see <a href="./rfc5741#section-2">Section 2 of RFC 5741</a>.
Information about the current status of this document, any errata,
and how to provide feedback on it may be obtained at
<a href="https://www.rfc-editor.org/info/rfc6149">http://www.rfc-editor.org/info/rfc6149</a>.
Copyright Notice
Copyright (c) 2011 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal
Provisions Relating to IETF Documents
(<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
<span class="grey">Turner & Chen Informational [Page 1]</span><span id="page-2" ></span>
<span class="grey"><a href="./rfc6149">RFC 6149</a> MD2 to Historic Status March 2011</span>
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span>
MD2 [<a href="#ref-MD2" title=""The MD2 Message-Digest Algorithm"">MD2</a>] is a message digest algorithm that takes as input a message
of arbitrary length and produces as output a 128-bit "fingerprint" or
"message digest" of the input. This document retires MD2.
Specifically, this document moves <a href="./rfc1319">RFC 1319</a> [<a href="#ref-MD2" title=""The MD2 Message-Digest Algorithm"">MD2</a>] to Historic status.
The reasons for taking this action are discussed.
[<a id="ref-HASH-Attack">HASH-Attack</a>] summarizes the use of hashes in many protocols and
discusses how attacks against a message digest algorithm's one-way
and collision-free properties affect and do not affect Internet
protocols. Familiarity with [<a href="#ref-HASH-Attack" title=""Attacks on Cryptographic Hashes in Internet Protocols"">HASH-Attack</a>] is assumed.
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Rationale</span>
MD2 was published in 1992 as an Informational RFC. Since its
publication, MD2 has been shown to not be collision-free [<a href="#ref-ROCH1995" title=""The compression function of MD2 is not collision free"">ROCH1995</a>]
[<a href="#ref-KNMA2005" title=""Preimage and Collision Attacks on MD2"">KNMA2005</a>] [<a href="#ref-ROCH1997" title=""MD2 is not secure without the checksum byte"">ROCH1997</a>], 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 [<a href="#ref-KNMA2005" title=""Preimage and Collision Attacks on MD2"">KNMA2005</a>]
[<a href="#ref-MULL2004" title=""The MD2 Hash Function Is Not One-Way"">MULL2004</a>] [<a href="#ref-KMM2010" title=""Cryptanalysis of MD2"">KMM2010</a>].
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Documents that Reference <a href="./rfc1319">RFC 1319</a></span>
Use of MD2 has been specified in the following RFCs:
Proposed Standard (PS):
o [<a href="./rfc3279" title=""Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile"">RFC3279</a>] Algorithms and Identifiers for the Internet X.509 Public
Key Infrastructure Certificate and Certificate Revocation
List (CRL) Profile.
o [<a href="./rfc4572" title=""Connection-Oriented Media Transport over the Transport Layer Security (TLS) Protocol in the Session Description Protocol (SDP)"">RFC4572</a>] Connection-Oriented Media Transport over the Transport
Layer Security (TLS) Protocol in the Session Description
Protocol (SDP).
Informational:
o [<a href="./rfc1983" title=""Internet Users' Glossary"">RFC1983</a>] Internet Users' Glossary.
o [<a href="./rfc2315" title=""PKCS #7: Cryptographic Message Syntax Version 1.5"">RFC2315</a>] PKCS #7: Cryptographic Message Syntax Version 1.5.
o [<a href="./rfc2898" title=""PKCS #5: Password-Based Cryptography Specification Version 2.0"">RFC2898</a>] PKCS #5: Password-Based Cryptography Specification
Version 2.0.
o [<a href="./rfc3447" title=""Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1"">RFC3447</a>] Public-Key Cryptography Standards (PKCS) #1: RSA
Cryptography Specifications Version 2.1.
<span class="grey">Turner & Chen Informational [Page 2]</span><span id="page-3" ></span>
<span class="grey"><a href="./rfc6149">RFC 6149</a> MD2 to Historic Status March 2011</span>
Experimental:
o [<a href="./rfc2660" title=""The Secure HyperText Transfer Protocol"">RFC2660</a>] The Secure HyperText Transfer Protocol.
There are other RFCs that refer to MD2, but they have been either
moved to Historic status or obsoleted by a later RFC. References and
discussions about these RFCs are omitted. The exceptions are:
o [<a href="./rfc2313" title=""PKCS #1: RSA Encryption Version 1.5"">RFC2313</a>] PKCS #1: RSA Encryption Version 1.5.
o [<a href="./rfc2437" title=""PKCS #1: RSA Cryptography Specifications Version 2.0"">RFC2437</a>] PKCS #1: RSA Cryptography Specifications Version 2.0.
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Impact on Moving MD2 to Historic</span>
The impact of moving MD2 to Historic on the RFCs specified in <a href="#section-3">Section</a>
<a href="#section-3">3</a> is minimal, as described below.
Regarding PS RFCs:
o MD2 support in TLS was dropped in TLS 1.1.
o MD2 support is optional in [<a href="./rfc4572" title=""Connection-Oriented Media Transport over the Transport Layer Security (TLS) Protocol in the Session Description Protocol (SDP)"">RFC4572</a>], and SHA-1 is specified as the
preferred algorithm.
o MD2 is included in the original PKIX certificate profile and the
PKIX algorithm document [<a href="./rfc3279" title=""Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile"">RFC3279</a>] for compatibility with older
applications, but its use is discouraged. SHA-1 is identified as
the preferred algorithm for the Internet PKI.
Regarding Informational RFCs:
o The Internet Users' Guide [<a href="./rfc1983" title=""Internet Users' Glossary"">RFC1983</a>] provided a definition for
Message Digest and listed MD2 as one example.
o PKCS#1 v1.5 [<a href="./rfc2313" title=""PKCS #1: RSA Encryption Version 1.5"">RFC2313</a>] stated that there are no known attacks
against MD2. PKCS#1 v2.0 [<a href="./rfc2437" title=""PKCS #1: RSA Cryptography Specifications Version 2.0"">RFC2437</a>] updated this stance to indicate
that MD2 should only be supported for backward compatibility and to
mention the attacks in [<a href="#ref-ROCH1995" title=""The compression function of MD2 is not collision free"">ROCH1995</a>]. PKCS#1 [<a href="./rfc3447" title=""Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1"">RFC3447</a>] indicates that
support of MD2 is only retained for compatibility with existing
applications.
o PKCS#5 [<a href="./rfc2898" title=""PKCS #5: Password-Based Cryptography Specification Version 2.0"">RFC2898</a>] recommends that the Password-Based Encryption
Scheme (PBES) that uses MD2 not be used for new applications.
o PKCS#7 [<a href="./rfc2315" title=""PKCS #7: Cryptographic Message Syntax Version 1.5"">RFC2315</a>] was replaced by a series of Standards Track
publications, "Cryptographic Message Syntax" [<a href="./rfc2630" title=""Cryptographic Message Syntax"">RFC2630</a>] [<a href="./rfc3369" title=""Cryptographic Message Syntax (CMS)"">RFC3369</a>]
[<a href="./rfc5652" title=""Cryptographic Message Syntax (CMS)"">RFC5652</a>] and "Cryptographic Message Syntax (CMS) Algorithms"
[<a href="./rfc3370" title=""Cryptographic Message Syntax (CMS) Algorithms"">RFC3370</a>]. Support for MD2 was dropped in [<a href="./rfc3370" title=""Cryptographic Message Syntax (CMS) Algorithms"">RFC3370</a>].
<span class="grey">Turner & Chen Informational [Page 3]</span><span id="page-4" ></span>
<span class="grey"><a href="./rfc6149">RFC 6149</a> MD2 to Historic Status March 2011</span>
<a href="./rfc2818">RFC 2818</a>, "HTTP Over TLS", which does not reference MD2, largely
supplanted implementation of [<a href="./rfc2660" title=""The Secure HyperText Transfer Protocol"">RFC2660</a>]. [<a href="./rfc2660" title=""The Secure HyperText Transfer Protocol"">RFC2660</a>] specified MD2 for
use both as a digest algorithm and as a MAC (Message Authentication
Code) algorithm [<a href="./rfc2104" title=""HMAC: Keyed-Hashing for Message Authentication"">RFC2104</a>]. Note that this is the only reference to
HMAC-MD2 found in the RFC repository.
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Other Considerations</span>
MD2 has also fallen out of favor because it is slower than both MD4
[<a href="#ref-MD4" title=""The MD4 Message-Digest Algorithm"">MD4</a>] and MD5 [<a href="#ref-MD5" title=""The MD5 Message-Digest Algorithm"">MD5</a>]. 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) [<a href="#ref-SHS" title=" FIPS Publication 180-3: Secure Hash Standard">SHS</a>] algorithms:
SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512.
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Security Considerations</span>
MD2 is different from MD4 and MD5 in that is not a straight Merkle-
Damgaard design. For a padded message with t blocks, it generates a
nonlinear checksum as its t+1 block. The checksum is considered as
the final block input of MD2.
As confirmed in 1997 by Rogier et al. [<a href="#ref-ROCH1997" title=""MD2 is not secure without the checksum byte"">ROCH1997</a>], the collision
resistance property of MD2 highly depends on the nonlinear checksum.
Without the checksum, a collision can be found in 2^12 MD2
operations, while with the checksum, the best collision attack takes
2^63.3 operations with 2^50 memory complexity [<a href="#ref-MULL2004" title=""The MD2 Hash Function Is Not One-Way"">MULL2004</a>], which is
not significantly better than the birthday attack.
Even though collision attacks on MD2 are not significantly more
powerful than the birthday attack, MD2 was found not to be one-way.
In [<a href="#ref-KMM2010" title=""Cryptanalysis of MD2"">KMM2010</a>], a pre-image can be found with 2^104 MD2 operations. In
an improved attack described in [<a href="#ref-KMM2010" title=""Cryptanalysis of MD2"">KMM2010</a>], a pre-image can be found
in 2^73 MD2 operations. Because of this "invertible" property of
MD2, when using MD2 in HMAC, it may leak information of the keys.
Obviously, the pre-image attack can be used to find a second pre-
image. The second pre-image attack is even more severe than a
collision attack to digital signatures. Therefore, MD2 must not be
used for digital signatures.
Some may find the guidance for key lengths and algorithm strengths in
[<a href="#ref-SP800-57" title=" Special Publication 800-57: Recommendation for Key Management - Part 1 (Revised)">SP800-57</a>] and [<a href="#ref-SP800-131" title=" Special Publication 800-131: DRAFT Recommendation for the Transitioning of Cryptographic Algorithms and Key Sizes">SP800-131</a>] useful.
<span class="grey">Turner & Chen Informational [Page 4]</span><span id="page-5" ></span>
<span class="grey"><a href="./rfc6149">RFC 6149</a> MD2 to Historic Status March 2011</span>
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. Recommendation</span>
Despite MD2 seeing some deployment on the Internet, this
specification recommends obsoleting MD2. MD2 is not a reasonable
candidate for further standardization and should be deprecated in
favor of one or more existing hash algorithms (e.g., SHA-256 [<a href="#ref-SHS" title=" FIPS Publication 180-3: Secure Hash Standard">SHS</a>]).
RSA Security considers it appropriate to move the MD2 algorithm to
Historic status.
It takes a number of years to deploy crypto and it also takes a
number of years to withdraw it. Algorithms need to be withdrawn
before a catastrophic break is discovered. MD2 is clearly showing
signs of weakness, and implementations should strongly consider
removing support and migrating to another hash algorithm.
<span class="h2"><a class="selflink" id="section-8" href="#section-8">8</a>. Acknowledgements</span>
We'd like to thank RSA for publishing MD2. We'd also like to thank
all the cryptographers who studied the algorithm. For their
contributions to this document, we'd like to thank Ran Atkinson,
Alfred Hoenes, John Linn, and Martin Rex.
<span class="h2"><a class="selflink" id="section-9" href="#section-9">9</a>. Informative References</span>
[<a id="ref-HASH-Attack">HASH-Attack</a>] Hoffman, P. and B. Schneier, "Attacks on Cryptographic
Hashes in Internet Protocols", <a href="./rfc4270">RFC 4270</a>, November 2005.
[<a id="ref-KMM2010">KMM2010</a>] Knudsen, L., Mathiassen, J., Muller, F., and Thomsen,
S., "Cryptanalysis of MD2", Journal of Cryptology,
23(1):72-90, 2010.
[<a id="ref-KNMA2005">KNMA2005</a>] Knudsen, L., and J. Mathiassen, "Preimage and Collision
Attacks on MD2", FSE 2005.
[<a id="ref-MD2">MD2</a>] Kaliski, B., "The MD2 Message-Digest Algorithm", <a href="./rfc1319">RFC</a>
<a href="./rfc1319">1319</a>, April 1992.
[<a id="ref-MD4">MD4</a>] Rivest, R., "The MD4 Message-Digest Algorithm", <a href="./rfc1320">RFC</a>
<a href="./rfc1320">1320</a>, April 1992.
[<a id="ref-MD5">MD5</a>] Rivest, R., "The MD5 Message-Digest Algorithm", <a href="./rfc1321">RFC</a>
<a href="./rfc1321">1321</a>, April 1992.
[<a id="ref-MULL2004">MULL2004</a>] Muller, F., "The MD2 Hash Function Is Not One-Way",
ASIACRYPT, LNCS 3329, pp. 214-229, Springer, 2004.
<span class="grey">Turner & Chen Informational [Page 5]</span><span id="page-6" ></span>
<span class="grey"><a href="./rfc6149">RFC 6149</a> MD2 to Historic Status March 2011</span>
[<a id="ref-RFC1983">RFC1983</a>] Malkin, G., Ed., "Internet Users' Glossary", FYI 18,
<a href="./rfc1983">RFC 1983</a>, August 1996.
[<a id="ref-RFC2104">RFC2104</a>] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC:
Keyed-Hashing for Message Authentication", <a href="./rfc2104">RFC 2104</a>,
February 1997.
[<a id="ref-RFC2313">RFC2313</a>] Kaliski, B., "PKCS #1: RSA Encryption Version 1.5", <a href="./rfc2313">RFC</a>
<a href="./rfc2313">2313</a>, March 1998.
[<a id="ref-RFC2315">RFC2315</a>] Kaliski, B., "PKCS #7: Cryptographic Message Syntax
Version 1.5", <a href="./rfc2315">RFC 2315</a>, March 1998.
[<a id="ref-RFC2437">RFC2437</a>] Kaliski, B. and J. Staddon, "PKCS #1: RSA Cryptography
Specifications Version 2.0", <a href="./rfc2437">RFC 2437</a>, October 1998.
[<a id="ref-RFC2630">RFC2630</a>] Housley, R., "Cryptographic Message Syntax", <a href="./rfc2630">RFC 2630</a>,
June 1999.
[<a id="ref-RFC2660">RFC2660</a>] Rescorla, E. and A. Schiffman, "The Secure HyperText
Transfer Protocol", <a href="./rfc2660">RFC 2660</a>, August 1999.
[<a id="ref-RFC2898">RFC2898</a>] Kaliski, B., "PKCS #5: Password-Based Cryptography
Specification Version 2.0", <a href="./rfc2898">RFC 2898</a>, September 2000.
[<a id="ref-RFC3279">RFC3279</a>] Bassham, L., Polk, W., and R. Housley, "Algorithms and
Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate Revocation
List (CRL) Profile", <a href="./rfc3279">RFC 3279</a>, April 2002.
[<a id="ref-RFC3369">RFC3369</a>] Housley, R., "Cryptographic Message Syntax (CMS)", <a href="./rfc3369">RFC</a>
<a href="./rfc3369">3369</a>, August 2002.
[<a id="ref-RFC3370">RFC3370</a>] Housley, R., "Cryptographic Message Syntax (CMS)
Algorithms", <a href="./rfc3370">RFC 3370</a>, August 2002.
[<a id="ref-RFC3447">RFC3447</a>] Jonsson, J. and B. Kaliski, "Public-Key Cryptography
Standards (PKCS) #1: RSA Cryptography Specifications
Version 2.1", <a href="./rfc3447">RFC 3447</a>, February 2003.
[<a id="ref-RFC4572">RFC4572</a>] Lennox, J., "Connection-Oriented Media Transport over
the Transport Layer Security (TLS) Protocol in the
Session Description Protocol (SDP)", <a href="./rfc4572">RFC 4572</a>, July
2006.
[<a id="ref-RFC5652">RFC5652</a>] Housley, R., "Cryptographic Message Syntax (CMS)", STD
70, <a href="./rfc5652">RFC 5652</a>, September 2009.
<span class="grey">Turner & Chen Informational [Page 6]</span><span id="page-7" ></span>
<span class="grey"><a href="./rfc6149">RFC 6149</a> MD2 to Historic Status March 2011</span>
[<a id="ref-ROCH1995">ROCH1995</a>] Rogier, N., and P. Chauvaud, "The compression function
of MD2 is not collision free", Presented at Selected
Areas in Cryptography '95, Carleton University, Ottawa,
Canada. May 18-19, 1995.
[<a id="ref-ROCH1997">ROCH1997</a>] Rogier, N. and P. Chauvaud, "MD2 is not secure without
the checksum byte", Des. Codes Cryptogr. 12(3), 245-251
(1997).
[<a id="ref-SHS">SHS</a>] National Institute of Standards and Technology (NIST),
FIPS Publication 180-3: Secure Hash Standard, October
2008.
[<a id="ref-SP800-57">SP800-57</a>] National Institute of Standards and Technology (NIST),
Special Publication 800-57: Recommendation for Key
Management - Part 1 (Revised), March 2007.
[<a id="ref-SP800-131">SP800-131</a>] National Institute of Standards and Technology (NIST),
Special Publication 800-131: DRAFT Recommendation for
the Transitioning of Cryptographic Algorithms and Key
Sizes, June 2010.
Authors' Addresses
Sean Turner
IECA, Inc.
3057 Nutley Street, Suite 106
Fairfax, VA 22031
USA
EMail: [email protected]
Lily Chen
National Institute of Standards and Technology
100 Bureau Drive, Mail Stop 8930
Gaithersburg, MD 20899-8930
USA
EMail: [email protected]
Turner & Chen Informational [Page 7]
Annotations
Select text to annotate