< draft-turner-md5-seccon-update-07.txt   draft-turner-md5-seccon-update-08.txt >
Network Working Group S. Turner
Internet Draft IECA
Updates: 1321, 2104 (once approved) L. Chen
Intended Status: Informational NIST
Expires: May 8, 2011 November 8, 2010
Updated Security Considerations for the Network Working Group S. Turner
MD5 Message-Digest and the HMAC-MD5 Algorithms Internet-Draft IECA
draft-turner-md5-seccon-update-07.txt Updates: 1321, 2104 (once approved) L. Chen
Intended Status: Informational NIST
Expires: June 28, 2011 December 29, 2010
Updated Security Considerations for
the MD5 Message-Digest and the HMAC-MD5 Algorithms
draft-turner-md5-seccon-update-08.txt
Abstract Abstract
This document updates the security considerations for the MD5 message This document updates the security considerations for the MD5 message
digest algorithm. It also updates the security considerations for digest algorithm. It also updates the security considerations for
HMAC-MD5. HMAC-MD5.
Status of this Memo Status of this Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. This document may contain material provisions of BCP 78 and BCP 79.
from IETF Documents or IETF Contributions published or made publicly
available before November 10, 2008.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF). Note that other groups may also distribute
other groups may also distribute working documents as Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at This Internet-Draft will expire on June 28, 2011.
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 May 8, 2011.
Copyright Notice Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
1. Introduction Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29
1. Introduction
MD5 [MD5] is a message digest algorithm that takes as input a message 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 of arbitrary length and produces as output a 128-bit "fingerprint" or
"message digest" of the input. The published attacks against MD5 "message digest" of the input. The published attacks against MD5
show that it is not prudent to use MD5 when collision resistance is show that it is not prudent to use MD5 when collision resistance is
required. This document replaces the security considerations in RFC required. This document replaces the security considerations in RFC
1321 [MD5]. 1321 [MD5].
[HMAC] defined a mechanism for message authentication using [HMAC] defined a mechanism for message authentication using
cryptographic hash functions. Any message digest algorithm can be cryptographic hash functions. Any message digest algorithm can be
used, but the cryptographic strength of HMAC depends on the used, but the cryptographic strength of HMAC depends on the
properties of the underlying hash function. [HMAC-MD5] defined test properties of the underlying hash function. [HMAC-MD5] defined test
cases for HMAC-MD5. This document updates the security cases for HMAC-MD5. This document updates the security
considerations in [HMAC-MD5]. considerations in [HMAC], which [HMAC-MD5] points to for its security
considerations.
[HASH-Attack] summarizes the use of hashes in many protocols and [HASH-Attack] summarizes the use of hashes in many protocols and
discusses how attacks against a message digest algorithm's one-way discusses how attacks against a message digest algorithm's one-way
and collision-free properties affect and do not affect Internet and collision-free properties affect and do not affect Internet
protocols. Familiarity with [HASH-Attack] is assumed. protocols. Familiarity with [HASH-Attack] is assumed. One of the
uses of message digest algorithms in [HASH-Attack] was integrity
protection. Where the MD5 checksum is used inline with the protocol
solely to protect against errors an MD5 checksum is still an
acceptable use. Applications and protocols need to clearly state in
their security considerations what security services, if any, are
expected from the MD5 checksum. In fact, any application and
protocol that employs MD5 needs to clearly state the expected
security services from their use of MD5.
2. Security Considerations 2. Security Considerations
MD5 was published in 1992 as an Informational RFC. Since that time, MD5 was published in 1992 as an Informational RFC. Since that time,
MD5 has been studied extensively. What follows are recent attacks MD5 has been studied extensively. What follows are recent attacks
against MD5's collision, pre-image, and second pre-image resistance. against MD5's collision, pre-image, and second pre-image resistance.
Additionally, attacks against MD5 used in message authentication with Additionally, attacks against MD5 used in message authentication with
a shared secret (i.e., HMAC-MD5) are discussed. a shared secret (i.e., HMAC-MD5) are discussed.
Some may find the guidance for key lengths and algorithm strengths in Some may find the guidance for key lengths and algorithm strengths in
[SP800-57] and [SP800-131] useful. [SP800-57] and [SP800-131] useful.
2.1. Collision Resistance 2.1. Collision Resistance
Psuedo-collisions for the compress function of MD5 were first Pseudo-collisions for the compress function of MD5 were first
described in 1993 [denBBO1993]. In 1996, [DOB1995] demonstrated a described in 1993 [denBBO1993]. In 1996, [DOB1995] demonstrated a
collision pair for the MD5 compression function with a chosen initial collision pair for the MD5 compression function with a chosen initial
value. The first paper that demonstrated two collision pairs for MD5 value. The first paper that demonstrated two collision pairs for MD5
was published in 2004 [WFLY2004]. The detailed attack techniques for was published in 2004 [WFLY2004]. The detailed attack techniques for
Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29
MD5 were published at EUROCRYPT 2005 [WAYU2005]. Since then, a lot of MD5 were published at EUROCRYPT 2005 [WAYU2005]. Since then, a lot of
research results have been published to improve collision attacks on research results have been published to improve collision attacks on
MD5. The attacks presented in [KLIM2006] can find MD5 collision in MD5. The attacks presented in [KLIM2006] can find MD5 collision in
about one minute on a standard notebook PC (Intel Pentium, 1.6 GHz.). about one minute on a standard notebook PC (Intel Pentium, 1.6GHz).
[STEV2007] claims that it takes 10 seconds or less on a 2.6Ghz [STEV2007] claims that it takes 10 seconds or less on a 2.6Ghz
Pentium4 to find collisions. In Pentium4 to find collisions. In
[STEV2007][SLdeW2007][SSALMOdeW2009][SLdeW2009], the collision [STEV2007][SLdeW2007][SSALMOdeW2009][SLdeW2009], the collision
attacks on MD5 were successfully applied to X.509 certificates. attacks on MD5 were successfully applied to X.509 certificates.
Notice that the collision attack on MD5 can also be applied to Notice that the collision attack on MD5 can also be applied to
password based challenge-and-response authentication protocols such password based challenge-and-response authentication protocols such
as the APOP option in the Post Office Protocol (POP) used in post as the APOP option in the Post Office Protocol (POP) [POP] used in
office authentication as presented in [LEUR2007]. post office authentication as presented in [LEUR2007].
In fact, more delicate attacks on MD5 to improve the speed of finding In fact, more delicate attacks on MD5 to improve the speed of finding
collisions have been published recently. However, the aforementioned collisions have been published recently. However, the aforementioned
results have provided sufficient reason to eliminate MD5 usage in results have provided sufficient reason to eliminate MD5 usage in
applications where collision resistance is required such as digital applications where collision resistance is required such as digital
signatures. signatures.
2.2. Pre-image and Second Pre-image Resistance 2.2. Pre-image and Second Pre-image Resistance
Even though the best result can find a pre-image attack of MD5 faster Even though the best result can find a pre-image attack of MD5 faster
than exhaustive search as presented in [SAAO2009], the complexity than exhaustive search as presented in [SAAO2009], the complexity
2^123.4 is still pretty high. 2^123.4 is still pretty high.
2.3. HMAC 2.3. HMAC
The cryptanalysis of HMAC-MD5 is usually conducted together with NMAC The cryptanalysis of HMAC-MD5 is usually conducted together with NMAC
(Nested MAC) since they are closely related. NMAC uses two (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, independent keys K1 and K2 such that
M), where K1 and K2 are used as secret IVs for hash function H(IV,M). NMAC(K1, K2, M) = H(K1, H(K2, M), where K1 and K2 are used as secret
If we re-write the HMAC equation using two secret IVs such that IV2 = IVs for hash function H(IV, M). If we re-write the HMAC equation
H(K Xor ipad) and IV1 = H(K Xor opad), then HMAC(K, M) = NMAC(IV1, using two secret IVs such that IV2 = H(K Xor ipad) and
IV2, M). Here it is very important to notice that IV1 and IV2 are IV1 = H(K Xor opad), then HMAC(K, M) = NMAC(IV1, IV2, M). Here it is
not independently selected. very important to notice that IV1 and IV2 are not independently
selected.
The first analysis was explored on NMAC-MD5 using related keys in The first analysis was explored on NMAC-MD5 using related keys in
[COYI2006]. The partial key recovery attack cannot be extended to [COYI2006]. The partial key recovery attack cannot be extended to
HMAC-MD5, since for HMAC, recovering partial secret IVs can hardly HMAC-MD5, since for HMAC, recovering partial secret IVs can hardly
lead to recovering (partial) key K. Another paper presented at Crypto lead to recovering (partial) key K. Another paper presented at Crypto
2007 [FLN2007] extended results of [COYI2006] to a full key recovery 2007 [FLN2007] extended results of [COYI2006] to a full key recovery
attack on NMAC-MD5. Since it also uses related key attack, it does attack on NMAC-MD5. Since it also uses related key attack, it does
not seem applicable to HMAC-MD5. not seem applicable to HMAC-MD5.
A EUROCRYPT 2009 paper presented a distinguishing attack on HMAC-MD5 A EUROCRYPT 2009 paper presented a distinguishing attack on HMAC-MD5
[WYWZZ2009] without using related keys. It can distinguish an [WYWZZ2009] without using related keys. It can distinguish an
Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29
instantiation of HMAC with MD5 from an instantiation with a random instantiation of HMAC with MD5 from an instantiation with a random
function with 2^97 queries with probability 0.87. This is called function with 2^97 queries with probability 0.87. This is called
distinguishing-H. Using the distinguishing attack, it can recover distinguishing-H. Using the distinguishing attack, it can recover
some bits of the intermediate status of the second block. However, as some bits of the intermediate status of the second block. However, as
it is pointed out in [WYWZZ2009], it cannot be used to recover the it is pointed out in [WYWZZ2009], it cannot be used to recover the
(partial) inner key H(K Xor ipad). It is not obvious how the attack (partial) inner key H(K Xor ipad). It is not obvious how the attack
can be used to form a forgery attack either. can be used to form a forgery attack either.
The attacks on HMAC-MD5 do not seem to indicate a practical The attacks on HMAC-MD5 do not seem to indicate a practical
vulnerability when used as a message authentication code. Considering vulnerability when used as a message authentication code. Considering
skipping to change at page 4, line 26 skipping to change at page 4, line 29
practical impact on HMAC usage as a PRF such as in a key derivation practical impact on HMAC usage as a PRF such as in a key derivation
function is not well understood. function is not well understood.
Therefore, it may not be urgent to remove HMAC-MD5 from the existing Therefore, it may not be urgent to remove HMAC-MD5 from the existing
protocols. However, since MD5 must not be used for digital protocols. However, since MD5 must not be used for digital
signatures, for a new protocol design, a ciphersuite with HMAC-MD5 signatures, for a new protocol design, a ciphersuite with HMAC-MD5
should not be included. Options include HMAC-SHA256 [HMAC][HMAC- should not be included. Options include HMAC-SHA256 [HMAC][HMAC-
SHA256] and [AES-CMAC] when AES is more readily available than a hash SHA256] and [AES-CMAC] when AES is more readily available than a hash
function. function.
3. IANA Considerations 4. IANA Considerations
IANA is requested to update the md5 usage entry in the Hash Function None.
Textual Names registry by replacing "COMMON" with "DEPRECATED".
4. Acknowledgements 5. Acknowledgements
Obviously, we have to thank all the cryptographers who produced the Obviously, we have to thank all the cryptographers who produced the
results we refer to in this document. We'd also like to thank Alfred results we refer to in this document. We'd also like to thank Wesley
Hoenes, Martin Rex, and Benne de Weger for their comments. Eddy, Sam Hartman, Alfred Hoenes, Martin Rex, Benne de Weger, and
Lloyd Wood for their comments.
5. Normative References 6. Normative References
[AES-CMAC] Song, J., Poovendran, R., Lee., J., and T. Iwata, [AES-CMAC] Song, J., Poovendran, R., Lee., J., and T. Iwata, "The
"The AES-CMAC Algorithm", RFC 4493, June 2006. AES-CMAC Algorithm", RFC 4493, June 2006.
[COYI2006] S. Contini, Y.L. Yin. Forgery and partial key- [COYI2006] S. Contini, Y.L. Yin. Forgery and partial key-recovery
recovery attacks on HMAC and NMAC using hash attacks on HMAC and NMAC using hash collisions. ASIACRYPT
collisions. ASIACRYPT 2006. LNCS 4284, Springer, 2006. LNCS 4284, Springer, 2006.
2006.
[denBBO1993] den Boer, B. and A. Bosselaers, "Collisions for the [denBBO1993] den Boer, B. and A. Bosselaers, "Collisions for the
compression function of MD5", Eurocrypt 1993. compression function of MD5", Eurocrypt 1993.
[DOB1995] Dobbertin, H., "Cryptanalysis of MD5 Compress", [DOB1995] Dobbertin, H., "Cryptanalysis of MD5 Compress", Eurocrypt
Eurocrypt 1996. 1996.
[FLN2007] Fouque, P.-A., Leurent, G., Nguyen, P.Q.: Full key- Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29
recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5.
CRYPTO 2007. LNCS, 4622, Springer, 2007.
[HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on [FLN2007] Fouque, P.-A., Leurent, G., Nguyen, P.Q.: Full key-recovery
Cryptographic Hashes in Internet Protocols", RFC attacks on HMAC/NMAC-MD4 and NMAC-MD5. CRYPTO 2007. LNCS,
4270, November 2005. 4622, Springer, 2007.
[HMAC] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: [HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on Cryptographic
Keyed-Hashing for Message Authentication", RFC Hashes in Internet Protocols", RFC 4270, November 2005.
2104, February 1997.
[HMAC-MD5] Cheng, P., and R. Glenn, "Test Cases for HMAC-MD5 [HMAC] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed-
and HMAC-SHA-1", RC 2201, September 1997. Hashing for Message Authentication", RFC 2104, February
1997.
[HMAC-SHA256] Nystrom, M., "Identifiers and Test Vectors for [HMAC-MD5] Cheng, P., and R. Glenn, "Test Cases for HMAC-MD5 and
HMAC-SHA-224, HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-1", RFC 2202, September 1997.
HMAC-SHA-512", RFC 4231, December 2005.
[KLIM2006] V. Klima. Tunnels in Hash Functions: MD5 Collisions [HMAC-SHA256] Nystrom, M., "Identifiers and Test Vectors for HMAC-
within a Minute. Cryptology ePrint Archive, Report SHA-224, HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-512",
2006/105 (2006), http://eprint.iacr.org/2006/105. RFC 4231, December 2005.
[LEUR2007] G. Leurent, Message freedom in MD4 and MD5 [KLIM2006] V. Klima. Tunnels in Hash Functions: MD5 Collisions within
collisions: Application to APOP. Proceedings of a Minute. Cryptology ePrint Archive, Report 2006/105
FSE 2007. Lecture Notes in Computer Science 4715. (2006), http://eprint.iacr.org/2006/105.
Springer 2007.
[MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC [LEUR2007] G. Leurent, Message freedom in MD4 and MD5 collisions:
1321, April 1992. Application to APOP. Proceedings of FSE 2007. Lecture
Notes in Computer Science 4715. Springer 2007.
[SAAO2009] Y. Sasaki and K. Aoki. Finding preimages in full [MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April
MD5 faster than exhaustive search. Advances in 1992.
Cryptology - EUROCRYPT 2009, LNCS 5479 of Lecture
Notes in Computer Science, Springer, 2009.
[SLdeW2007] Stevens, M., Lenstra, A., de Weger, B., Chosen- [POP] Myers, J., and M. Rose, "Post Office Protocol - Version 3", RFC
prefix Collisions for MD5 and Colliding X.509 1939, May 1996.
Certificates for Different Identities. EuroCrypt
2007.
[SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen- [SAAO2009] Y. Sasaki and K. Aoki. Finding preimages in full MD5
prefix Collisions for MD5 and Applications", faster than exhaustive search. Advances in Cryptology -
Journal of Cryptology, 2009. EUROCRYPT 2009, LNCS 5479 of Lecture Notes in Computer
http://deweger.xs4all.nl/papers/%5B42%5DStLedW- Science, Springer, 2009.
MD5-JCryp%5B2009%5D.pdf.
[SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, [SLdeW2007] Stevens, M., Lenstra, A., de Weger, B., Chosen-prefix
A., Molnar, D., Osvik, D., and B. de Weger. Short Collisions for MD5 and Colliding X.509 Certificates for
chosen-prefix collisions for MD5 and the creation Different Identities. EuroCrypt 2007.
of a rogue CA certificate, Crypto 2009.
[SP800-57] National Institute of Standards and Technology [SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen-prefix
(NIST), Special Publication 800-57: Recommendation Collisions for MD5 and Applications", Journal of
for Key Management - Part 1 (Revised), March 2007. Cryptology, 2009. http://deweger.xs4all.nl/papers/
%5B42%5DStLedW-MD5-JCryp%5B2009%5D.pdf.
[SP800-131] National Institute of Standards and Technology [SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A.,
(NIST), Special Publication 800-131: DRAFT Molnar, D., Osvik, D., and B. de Weger. Short chosen-
Recommendation for the Transitioning of
Cryptographic Algorithms and Key Sizes, June 2010.
[STEV2007] Stevens, M., On Collisions for MD5. Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29
http://www.win.tue.nl/hashclash/On%20Collisions%20
for%20MD5%20-%20M.M.J.%20Stevens.pdf.
[WAYU2005] X. Wang and H. Yu. How to Break MD5 and other Hash prefix collisions for MD5 and the creation of a rogue CA
Functions. LNCS 3494. Advances in Cryptology - certificate, Crypto 2009.
EUROCRYPT2005, Springer 2005.
[WFLY2004] X. Wang, D. Feng, X. Lai, H. Yu, Collisions for [SP800-57] National Institute of Standards and Technology (NIST),
Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, Special Publication 800-57: Recommendation for Key
2004, http://eprint.iacr.org/2004/199.pdf Management - Part 1 (Revised), March 2007.
[WYWZZ2009] X. Wang, H. Yu, W. Wang, H. Zhang, and T. Zhan. [SP800-131] National Institute of Standards and Technology (NIST),
Cryptanalysis of HMAC/NMAC-MD5 and MD5-MAC. LNCS Special Publication 800-131: DRAFT Recommendation for the
5479. Advances in Cryptology - EUROCRYPT2009, Transitioning of Cryptographic Algorithms and Key Sizes,
Springer 2009. June 2010.
[STEV2007] Stevens, M., On Collisions for MD5.
http://www.win.tue.nl/hashclash/
On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf.
[WAYU2005] X. Wang and H. Yu. How to Break MD5 and other Hash
Functions. LNCS 3494. Advances in Cryptology -
EUROCRYPT2005, Springer 2005.
[WFLY2004] 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
[WYWZZ2009] 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.
Authors' Addresses Authors' Addresses
Sean Turner Sean Turner
IECA, Inc. IECA, Inc.
3057 Nutley Street, Suite 106 3057 Nutley Street, Suite 106
Fairfax, VA 22031 Fairfax, VA 22031
USA USA
EMail: turners@ieca.com EMail: turners@ieca.com
 End of changes. 48 change blocks. 
118 lines changed or deleted 131 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/