Network Working Group S. Turner
Internet Draft IECA
Updates: 1321 (once approved) L. Chen
Intended Status: Informational NIST
Expires: January 5, 2011 July 5, 2010
Updated Security Considerations for the MD5 Message-Digest Algorithm
draft-turner-md5-seccon-update-00.txt
Abstract
This document updates the security considerations for the MD5 message
digest algorithm.
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 5, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
Turner & Chen Expires January 5, 2011 [Page 1]
Internet-Draft Updated MD5 Security Considerations June 2010
(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
MD5 [MD5] 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. The published attacks against MD5
show and that it is not prudent to use MD5 when collision resistance
is required. This document replaces the security considerations in
RFC 1321 [MD5].
[HASH-Attack] 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.
2. Security Considerations
MD5 was published in 1992 as an Informational RFC. Since that time,
MD5 has been studied extensively. What follows are recent attacks
against MD5's collisions, pre-image, and second pre-image resistance.
Additionally, attacks against MD5 used in message authentication with
a shared secret (i.e., HMAC-MD5) are discussed.
Some may find the guidance for key lengths and algorithm strengths in
[SP800-57] and [SP800-131] useful.
2.1. Collision Resistance
The first paper that demonstrates actual collisions of MD5 was
published in 2004 [MD5-Analysis1]. The detailed attack techniques for
MD5 were published at EUROCRYPT 2005 [MD5-Analysis2]. Since then, a
lot of research results have been published to improve collision
attacks on MD5. The attacks presented in [MD5-Analysis3] can find MD5
collision in about one minute on a standard notebook PC (Intel
Pentium, 1.6 GHz.). In [MD5-Analysis4], the collision attack on MD5
was successfully applied to X.509 certificates.
Notice that the collision attack on MD5 can also be applied to
password based challenge-and-response authentication protocols such
as APOP protocol used in post office authentication as presented in
[MD5-Analysis5].
Turner & Chen Expires January 5, 2011 [Page 2]
Internet-Draft Updated MD5 Security Considerations June 2010
In fact, more delicate attacks on MD5 to improve the speed of finding
collisions have published recently. However, the aforementioned
results have provided sufficient reason to eliminate MD5 usage in
applications where collision resistance is required such as digital
signatures.
2.2. Pre-image and Second Pre-image Resistance
Even though the best result can find a pre-image attack of MD5 faster
than exhaustive search as presented in [MD5-Analysis6], the
complexity 2^123.4 is still pretty high.
2.3. HMAC
The cryptanalysis of HMAC-MD5 usually conducted together with NMAC
(Nested MAC) since they are closely related. NMAC uses two
independent keys K1 and K2 such that NMAC(K1, K2, M) = H(K1, H(K2,
M), where K1 and K2 are used as secret IVs for hash functions
H(IV,M). If we re-write HMAC equation using two secret IVs such that
IV2 = H(K Xor ipad) and IV1 = H(K Xor opad), then HMAC(K, M) =
NMAC(IV1, IV2, M). Here it is very important to notice that IV1 and
IV2 are not independently selected.
The first analysis was explored on NMAC-MD5 using related keys in
[HMAC-Analysis1]. The partial key recovery attack cannot be extended
to HMAC-MD5, since for HMAC, recovering partial secret IVs can hardly
lead to recovering (partial) key K. Another paper presented at Crypto
2007 [HMAC-Analysis2] extended results of [HMAC-Analysis1] to a full
key recovery attack on NMAC-MD5. Since it also uses related key
attack, it does not seem applicable to HMAC-MD5.
A EUROCRYPT 2009 paper presented a distinguishing attack on HMAC-MD5
[HMAC-Analysis3] without using related keys. It can distinguish an
instantiation of HMAC with MD5 from an instantiation with a random
function with 2^97 queries with probability 0.87. This is called
distinguishing-H. Using the distinguishing attack, it can recover
some bits of the intermediate status of the second block. However, as
it is pointed in [HMAC-Analysis3], it cannot be used to recover the
(partial) inner key H(K Xor ipad). It is not obvious how the attack
can be used to form a forgery attack either.
The attacks on HMAC-MD5 do not seem to indicate a practical
vulnerability when used as a message authentication code. Considering
that the distinguishing-H attack is different from distinguishing-R
attack, which distinguishes an HMAC from a random function, the
practical impact on HMAC usage as a PRF such as in a key derivation
function is not well understood.
Turner & Chen Expires January 5, 2011 [Page 3]
Internet-Draft Updated MD5 Security Considerations June 2010
Therefore, it may not be urgent to remove HMAC-MD5 from the existing
protocols. However, since MD5 must not be used for digital
signatures, for a new protocol design, a ciphersuite with HMAC-MD5
should not be included.
3. IANA Considerations
None.
4. Normative References
[HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on
Cryptographic Hashes in Internet Protocols", RFC
4270, November 2005.
[HMAC-Analysis1] S. Contini, Y.L. Yin. Forgery and partial key-
recovery attacks on HMAC and NMAC using hash
collisions. ASIACRYPT 2006. LNCS 4284, Springer,
2006.
[HMAC-Analysis2] Fouque, P.-A., Leurent, G., Nguyen, P.Q.: Full key-
recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5.
CRYPTO 2007. LNCS, 4622, Springer, 2007.
[HMAC-Analysis3] X. Wang, H. Yu, W. Wang, H. Zhang, and T. Zhan.
Cryptanalysis of HMAC/NMAC-MD5 and MD5-MAC. LNCS
5479. Advances in Cryptology - EUROCRYPT2009,
Springer 2009.
[MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC
1321, April 1992.
[MD5-Analysis1] X. Wang, D. Feng, X. Lai, H. Yu, Collisions for
Hash Functions MD4, MD5, HAVAL-128 and RIPEMD,
2004, http://eprint.iacr.org/2004/199.pdf
[MD5-Analysis2] X. Wang and H. Yu. How to Break MD5 and other Hash
Functions. LNCS 3494. Advances in Cryptology -
EUROCRYPT2005, Springer 2005.
[MD5-Analysis3] V. Klima. Tunnels in Hash Functions: MD5 Collisions
within a Minute. Cryptology ePrint Archive, Report
2006/105 (2006), http://eprint.iacr.org/2006/105.
[MD5-Analysis4] Stevens, M., Lenstra, A., de Weger, B., Target
Collisions for MD5 and Colliding X.509
Certificates for Different Identities. Cryptology
Turner & Chen Expires January 5, 2011 [Page 4]
Internet-Draft Updated MD5 Security Considerations June 2010
ePrint Archive, Report 2006/360 (2006),
http://eprint.iacr.org/2006/360.
[MD5-Analysis5] G. Leurent, Message freedom in MD4 and MD5
collisions: Application to APOP. Proceedings of
FSE 2007. Lecture Notes in Computer Science 4715.
Springer 2007.
[MD5-Analysis6] Y. Sasaki and K. Aoki. Finding preimages in full
MD5 faster than exhaustive search. Advances in
Cryptology - EUROCRYPT 2009, LNCS 5479 of Lecture
Notes in Computer Science, Springer, 2009.
[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.
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 5, 2011 [Page 5]