Network Working Group S. Turner
Internet Draft IECA
Updates: 1319, 4572 (once approved) L. Chen
Intended Status: Informational NIST
Expires: January 12, 2011 July 12, 2010
MD2 to Historic Status
draft-turner-md2-to-historic-02.txt
Abstract
This document recommends the retirement of MD2 and discusses the
reasons for doing so. This document recommends RFC 1319 be moved to
Historic status. This document also updates the IANA Hash Algorithm
Registry.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may contain material
from IETF Documents or IETF Contributions published or made publicly
available before November 10, 2008.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 12, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
Turner & Chen Expires January 12, 2011 [Page 1]
Internet-Draft MD2 to Historic July 2010
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) 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.
1. Introduction
MD2 [MD2] 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 recommends that MD2 be
retired. Specifically, this document recommends RFC 1319 [MD2] be
moved to Historic status. The reasons for taking this action are
discussed. This document also updates the IANA Hash Registry.
2. 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] and shown to have successful pre-image attacks
[KNMA2005] [MULL2004] [KMM2010]. In fact, RSA, in '96, suggested
that MD2 should not be used [RSA-AdviceOnMD2].
Another consideration is that industry is independently leading the
charge to deprecate MD2:
o Many TLS implementations, OpenSSL, Network Security Services,
and GNUTLS, have disabled support for MD2 by default.
o Microsoft has also banned MD2 [MS-AdviceOnMD2].
3. Documents that Reference RFC 1319
MD2 has been specified in the following RFCs:
Proposed Standard (PS):
o [RFC3279] Algorithms and Identifiers for the Internet X.509
Public Key Infrastructure Certificate and Certificate
Revocation List (CRL) Profile.
o [RFC4572] Connection-Oriented Media Transport over the
Transport Layer Security (TLS) Protocol in the Session
Description Protocol (SDP).
Turner & Chen Expires January 12, 2011 [Page 2]
Internet-Draft MD2 to Historic July 2010
Informational:
o [RFC1983] Internet Users' Glossary.
o [RFC2315] PKCS #7: Cryptographic Message Syntax Version 1.5.
o [RFC2898] PKCS #5: Password-Based Cryptography Specification
Version 2.0.
o [RFC3447] Public-Key Cryptography Standards (PKCS) #1: RSA
Cryptography Specifications Version 2.1.
Experimental:
o [RFC2660] The Secure HyperText Transfer Protocol.
There are other RFCs that refer to MD2, but their status is either
Historic or Obsoleted. References and discussions about these RFCs
are omitted.
4. Impact of Moving MD2 to Historic.
The impact of moving MD2 to Historic on the RFCs specified in Section
3 is minimal, as described below.
Concentrating on the PS RFCs:
o MD2 support in TLS was dropped in TLS 1.1.
o MD2 support is optional in [RFC4572], and SHA-1 is specified
as the preferred algorithm.
o MD2 is included in the original PKIX certificate profile and
the PKIX algorithm document [RFC3279] for compatibility with
older applications, but its use is discouraged. SHA-1 is
identified as the preferred algorithm for the Internet PKI.
Looking at the Informational RFCs:
o The Internet Users' Guide [RFC1983] provided a definition for
Message Digest and listed MD2 as one example.
o PKCS#1 [RFC3447] indicates that support MD2 is only retained
for compatibility with existing applications. One of the
motivations for updating PKCS#1 was to add support for
algorithms such as SHA-224, SHA-256, SHA-384, and SHA-512.
Turner & Chen Expires January 12, 2011 [Page 3]
Internet-Draft MD2 to Historic July 2010
o PKCS#5 [RFC2898] recommends that the Password Based Encryption
Scheme (PBES) that uses MD2 not be used for new applications.
o PKCS#7 [RFC2315] was replaced by a series of standards track
publications, "Cryptographic Message Syntax" [RFC2630]
[RFC3369] [RFC5652] and "Cryptographic Message Syntax (CMS)
Algorithms" [RFC3370]. Support for MD2 was dropped in
[RFC3370].
RFC 2818 "HTTP Over TLS", which does not reference MD2, largely
supplanted implementation of [RFC2660]. [RFC2660] specified MD2 for
use both as a digest algorithm as a MAC algorithm [RFC2104]. Note
that this is the only reference to HMAC-MD2 found in the RFC
repository.
5. Other Considerations
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.
6. Security Considerations
MD2 is differently 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. [ROCH1997], 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
according, while with the checksum, the best collision attack takes
2^63.3 operations with 2^50 memory complexity [MULL2004], which is
not significantly better than the birthday attack.
Even though collision attacks on MD2 are not more powerful than the
birthday attack, MD2 was found not to be one way. In [KMM2010], a
pre-image can be found with 2^104 MD2 operations. In an improved
attack described in [KMM2010], 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
collision attack to digital signatures. Therefore, MD2 must not be
used for digital signatures.
Turner & Chen Expires January 12, 2011 [Page 4]
Internet-Draft MD2 to Historic July 2010
Some may find the guidance for key lengths and algorithm strengths in
[SP800-57] and [SP800-131] useful.
7. Recommendation
Despite MD2 seeing some deployment on the Internet, this
specification recommends obsoleting MD2 because 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).
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.
8. IANA Considerations
IANA is requested to update that hash registration procedures found
in [RFC4572] with a fourth piece of information:
o The intended usage of the algorithm: One of COMMON, LIMITED
USE or OBSOLETE.
IANA is further requested to add a fourth column to the IANA Hash
Function Textual Name Registry: Usage.
Finally, IANA is requested to populate the column as follows: MD2 as
OBSOLETE and MD5, SHA-1, SHA-224, SHA-256, SHA-384, and SHA-512 as
COMMON.
9. Informative References
[KNMA2005] Knudsen, L., and J. Mathiassen, "Preimage and
Collision Attacks on MD2," FSE 2005.
[KMM2010] Knudsen, L., Mathiassen, J., Muller, F., and
Thomsen, S., "Cryptanalysis of MD2", Journal of
Cryptology, 23(1):72-90, 2010.
[MD2] Rivest, R., "The MD5 Message-Digest Algorithm", RFC
1319, April 1992.
[MULL2004] Muller, F., "The MD2 Hash Function Is Not One-Way",
ASIACRYPT, LNCS 3329, pp. 214-229, Springer, 2004.
Turner & Chen Expires January 12, 2011 [Page 5]
Internet-Draft MD2 to Historic July 2010
[MD4] Rivest, R., "The MD4 Message-Digest Algorithm", RFC
1320, April 1992.
[MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC
1321, April 1992.
[MS-AdviceOnMD2] Sullican, B., "Security Briefs: Cryptographic
Agility", August 2009,
,http://msdn.microsoft.com/en-
us/magazine/dvdarchive/ee321570.aspx
[RFC1983] Malkin, G., "Internet Users' Glossary", RFC 1983,
August 1996.
[RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC:
Keyed-Hashing for Message Authentication", RFC 2104,
February 1997.
[RFC2315] Kaliski, B., "PKCS #7: Cryptographic Message Syntax
Version 1.5," RFC 2315, March 1998.
[RFC2630] Housley, R., "Cryptographic Message Syntax", RFC
2630, June 1999.
[RFC2660] Rescorla, E., and A. Schiffman, "The Secure
HyperText Transfer Protocol", RFC 2660, August 1999.
[RFC2898] Kaliski, B., "PKCS #5: Password-Based Cryptography
Specification Version 2.0", RFC 2898, September
2000.
[RFC3279] Polk, W., Housley, R., and L. Bassham, "Algorithms
and Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate
Revocation List (CRL) Profile", RFC 3279, April
2002.
[RFC3369] Housley, R., "Cryptographic Message Syntax (CMS)",
RFC 3369, August 2002.
[RFC3370] Housley, R., "Cryptographic Message Syntax (CMS)
Algorithms", RFC 3370, August 2002.
[RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography
Standards (PKCS) #1: RSA Cryptography Specifications
Version 2.1" RFC 3447, February 2003.
Turner & Chen Expires January 12, 2011 [Page 6]
Internet-Draft MD2 to Historic July 2010
[RFC4572] Lennox, J., "Connection-Oriented Media Transport
over the Transport Layer Security (TLS) Protocol in
the Session Description Protocol (SDP)", RFC 4572,
July 2006.
[RFC5652] Housley, R., "Cryptographic Message Syntax (CMS)",
RFC 5652, August 2002.
[ROCH1995] 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.
[ROCH1997] Rogier, N. and P. Chauvaud, "MD2 is not secure
without the checksum byte", Des. Codes Cryptogr.
12(3), 245-251 (1997).
[RSA-AdviceOnMD2] Robshaw, M.J.B., "On Recent Results for MD2, MD4
and MD5", November 1996,
ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf
[SP800-57] National Institute of Standards and Technology
(NIST), Special Publication 800-57: Recommendation
for Key Management - Part 1 (Revised), March 2007.
[SP800-131] National Institute of Standards and Technology
(NIST), Special Publication 800-131: DRAFT
Recommendation for the Transitioning of
Cryptographic Algorithms and Key Sizes, June 2010.
[SHS] National Institute of Standards and Technology
(NIST), FIPS Publication 180-3: Secure Hash
Standard, October 2008.
Turner & Chen Expires January 12, 2011 [Page 7]
Internet-Draft MD2 to Historic July 2010
Authors' Addresses
Sean Turner
IECA, Inc.
3057 Nutley Street, Suite 106
Fairfax, VA 22031
USA
EMail: turners@ieca.com
Lily Chen
National Institute of Standards and Technology
100 Bureau Drive, Mail Stop 8930
Gaithersburg, MD 20899-8930
USA
EMail: lily.chen@nist.gov
Turner & Chen Expires January 12, 2011 [Page 8]