idnits 2.17.1 draft-turner-md5-seccon-update-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- -- The draft header indicates that this document updates RFC1321, but the abstract doesn't seem to mention this, which it should. -- The draft header indicates that this document updates RFC2104, but the abstract doesn't seem to mention this, which it should. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year (Using the creation date from RFC1321, updated by this document, for RFC5378 checks: 1992-04-01) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (December 29, 2010) is 4861 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 4 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group S. Turner 3 Internet-Draft IECA 4 Updates: 1321, 2104 (once approved) L. Chen 5 Intended Status: Informational NIST 6 Expires: June 28, 2011 December 29, 2010 8 Updated Security Considerations for 9 the MD5 Message-Digest and the HMAC-MD5 Algorithms 10 draft-turner-md5-seccon-update-08.txt 12 Abstract 14 This document updates the security considerations for the MD5 message 15 digest algorithm. It also updates the security considerations for 16 HMAC-MD5. 18 Status of this Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on June 28, 2011. 35 Copyright Notice 37 Copyright (c) 2010 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29 52 1. Introduction 54 MD5 [MD5] is a message digest algorithm that takes as input a message 55 of arbitrary length and produces as output a 128-bit "fingerprint" or 56 "message digest" of the input. The published attacks against MD5 57 show that it is not prudent to use MD5 when collision resistance is 58 required. This document replaces the security considerations in RFC 59 1321 [MD5]. 61 [HMAC] defined a mechanism for message authentication using 62 cryptographic hash functions. Any message digest algorithm can be 63 used, but the cryptographic strength of HMAC depends on the 64 properties of the underlying hash function. [HMAC-MD5] defined test 65 cases for HMAC-MD5. This document updates the security 66 considerations in [HMAC], which [HMAC-MD5] points to for its security 67 considerations. 69 [HASH-Attack] summarizes the use of hashes in many protocols and 70 discusses how attacks against a message digest algorithm's one-way 71 and collision-free properties affect and do not affect Internet 72 protocols. Familiarity with [HASH-Attack] is assumed. One of the 73 uses of message digest algorithms in [HASH-Attack] was integrity 74 protection. Where the MD5 checksum is used inline with the protocol 75 solely to protect against errors an MD5 checksum is still an 76 acceptable use. Applications and protocols need to clearly state in 77 their security considerations what security services, if any, are 78 expected from the MD5 checksum. In fact, any application and 79 protocol that employs MD5 needs to clearly state the expected 80 security services from their use of MD5. 82 2. Security Considerations 84 MD5 was published in 1992 as an Informational RFC. Since that time, 85 MD5 has been studied extensively. What follows are recent attacks 86 against MD5's collision, pre-image, and second pre-image resistance. 87 Additionally, attacks against MD5 used in message authentication with 88 a shared secret (i.e., HMAC-MD5) are discussed. 90 Some may find the guidance for key lengths and algorithm strengths in 91 [SP800-57] and [SP800-131] useful. 93 2.1. Collision Resistance 95 Pseudo-collisions for the compress function of MD5 were first 96 described in 1993 [denBBO1993]. In 1996, [DOB1995] demonstrated a 97 collision pair for the MD5 compression function with a chosen initial 98 value. The first paper that demonstrated two collision pairs for MD5 99 was published in 2004 [WFLY2004]. The detailed attack techniques for 101 Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29 103 MD5 were published at EUROCRYPT 2005 [WAYU2005]. Since then, a lot of 104 research results have been published to improve collision attacks on 105 MD5. The attacks presented in [KLIM2006] can find MD5 collision in 106 about one minute on a standard notebook PC (Intel Pentium, 1.6GHz). 107 [STEV2007] claims that it takes 10 seconds or less on a 2.6Ghz 108 Pentium4 to find collisions. In 109 [STEV2007][SLdeW2007][SSALMOdeW2009][SLdeW2009], the collision 110 attacks on MD5 were successfully applied to X.509 certificates. 112 Notice that the collision attack on MD5 can also be applied to 113 password based challenge-and-response authentication protocols such 114 as the APOP option in the Post Office Protocol (POP) [POP] used in 115 post office authentication as presented in [LEUR2007]. 117 In fact, more delicate attacks on MD5 to improve the speed of finding 118 collisions have been published recently. However, the aforementioned 119 results have provided sufficient reason to eliminate MD5 usage in 120 applications where collision resistance is required such as digital 121 signatures. 123 2.2. Pre-image and Second Pre-image Resistance 125 Even though the best result can find a pre-image attack of MD5 faster 126 than exhaustive search as presented in [SAAO2009], the complexity 127 2^123.4 is still pretty high. 129 2.3. HMAC 131 The cryptanalysis of HMAC-MD5 is usually conducted together with NMAC 132 (Nested MAC) since they are closely related. NMAC uses two 133 independent keys K1 and K2 such that 134 NMAC(K1, K2, M) = H(K1, H(K2, M), where K1 and K2 are used as secret 135 IVs for hash function H(IV, M). If we re-write the HMAC equation 136 using two secret IVs such that IV2 = H(K Xor ipad) and 137 IV1 = H(K Xor opad), then HMAC(K, M) = NMAC(IV1, IV2, M). Here it is 138 very important to notice that IV1 and IV2 are not independently 139 selected. 141 The first analysis was explored on NMAC-MD5 using related keys in 142 [COYI2006]. The partial key recovery attack cannot be extended to 143 HMAC-MD5, since for HMAC, recovering partial secret IVs can hardly 144 lead to recovering (partial) key K. Another paper presented at Crypto 145 2007 [FLN2007] extended results of [COYI2006] to a full key recovery 146 attack on NMAC-MD5. Since it also uses related key attack, it does 147 not seem applicable to HMAC-MD5. 149 A EUROCRYPT 2009 paper presented a distinguishing attack on HMAC-MD5 150 [WYWZZ2009] without using related keys. It can distinguish an 152 Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29 154 instantiation of HMAC with MD5 from an instantiation with a random 155 function with 2^97 queries with probability 0.87. This is called 156 distinguishing-H. Using the distinguishing attack, it can recover 157 some bits of the intermediate status of the second block. However, as 158 it is pointed out in [WYWZZ2009], it cannot be used to recover the 159 (partial) inner key H(K Xor ipad). It is not obvious how the attack 160 can be used to form a forgery attack either. 162 The attacks on HMAC-MD5 do not seem to indicate a practical 163 vulnerability when used as a message authentication code. Considering 164 that the distinguishing-H attack is different from a distinguishing-R 165 attack, which distinguishes an HMAC from a random function, the 166 practical impact on HMAC usage as a PRF such as in a key derivation 167 function is not well understood. 169 Therefore, it may not be urgent to remove HMAC-MD5 from the existing 170 protocols. However, since MD5 must not be used for digital 171 signatures, for a new protocol design, a ciphersuite with HMAC-MD5 172 should not be included. Options include HMAC-SHA256 [HMAC][HMAC- 173 SHA256] and [AES-CMAC] when AES is more readily available than a hash 174 function. 176 4. IANA Considerations 178 None. 180 5. Acknowledgements 182 Obviously, we have to thank all the cryptographers who produced the 183 results we refer to in this document. We'd also like to thank Wesley 184 Eddy, Sam Hartman, Alfred Hoenes, Martin Rex, Benne de Weger, and 185 Lloyd Wood for their comments. 187 6. Normative References 189 [AES-CMAC] Song, J., Poovendran, R., Lee., J., and T. Iwata, "The 190 AES-CMAC Algorithm", RFC 4493, June 2006. 192 [COYI2006] S. Contini, Y.L. Yin. Forgery and partial key-recovery 193 attacks on HMAC and NMAC using hash collisions. ASIACRYPT 194 2006. LNCS 4284, Springer, 2006. 196 [denBBO1993] den Boer, B. and A. Bosselaers, "Collisions for the 197 compression function of MD5", Eurocrypt 1993. 199 [DOB1995] Dobbertin, H., "Cryptanalysis of MD5 Compress", Eurocrypt 200 1996. 202 Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29 204 [FLN2007] Fouque, P.-A., Leurent, G., Nguyen, P.Q.: Full key-recovery 205 attacks on HMAC/NMAC-MD4 and NMAC-MD5. CRYPTO 2007. LNCS, 206 4622, Springer, 2007. 208 [HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on Cryptographic 209 Hashes in Internet Protocols", RFC 4270, November 2005. 211 [HMAC] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 212 Hashing for Message Authentication", RFC 2104, February 213 1997. 215 [HMAC-MD5] Cheng, P., and R. Glenn, "Test Cases for HMAC-MD5 and 216 HMAC-SHA-1", RFC 2202, September 1997. 218 [HMAC-SHA256] Nystrom, M., "Identifiers and Test Vectors for HMAC- 219 SHA-224, HMAC-SHA-256, HMAC-SHA-384, and HMAC-SHA-512", 220 RFC 4231, December 2005. 222 [KLIM2006] V. Klima. Tunnels in Hash Functions: MD5 Collisions within 223 a Minute. Cryptology ePrint Archive, Report 2006/105 224 (2006), http://eprint.iacr.org/2006/105. 226 [LEUR2007] G. Leurent, Message freedom in MD4 and MD5 collisions: 227 Application to APOP. Proceedings of FSE 2007. Lecture 228 Notes in Computer Science 4715. Springer 2007. 230 [MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 231 1992. 233 [POP] Myers, J., and M. Rose, "Post Office Protocol - Version 3", RFC 234 1939, May 1996. 236 [SAAO2009] Y. Sasaki and K. Aoki. Finding preimages in full MD5 237 faster than exhaustive search. Advances in Cryptology - 238 EUROCRYPT 2009, LNCS 5479 of Lecture Notes in Computer 239 Science, Springer, 2009. 241 [SLdeW2007] Stevens, M., Lenstra, A., de Weger, B., Chosen-prefix 242 Collisions for MD5 and Colliding X.509 Certificates for 243 Different Identities. EuroCrypt 2007. 245 [SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen-prefix 246 Collisions for MD5 and Applications", Journal of 247 Cryptology, 2009. http://deweger.xs4all.nl/papers/ 248 %5B42%5DStLedW-MD5-JCryp%5B2009%5D.pdf. 250 [SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A., 251 Molnar, D., Osvik, D., and B. de Weger. Short chosen- 253 Internet-Draft MD5 and HMAC-MD5 Security Considerations 2010-12-29 255 prefix collisions for MD5 and the creation of a rogue CA 256 certificate, Crypto 2009. 258 [SP800-57] National Institute of Standards and Technology (NIST), 259 Special Publication 800-57: Recommendation for Key 260 Management - Part 1 (Revised), March 2007. 262 [SP800-131] National Institute of Standards and Technology (NIST), 263 Special Publication 800-131: DRAFT Recommendation for the 264 Transitioning of Cryptographic Algorithms and Key Sizes, 265 June 2010. 267 [STEV2007] Stevens, M., On Collisions for MD5. 268 http://www.win.tue.nl/hashclash/ 269 On%20Collisions%20for%20MD5%20-%20M.M.J.%20Stevens.pdf. 271 [WAYU2005] X. Wang and H. Yu. How to Break MD5 and other Hash 272 Functions. LNCS 3494. Advances in Cryptology - 273 EUROCRYPT2005, Springer 2005. 275 [WFLY2004] X. Wang, D. Feng, X. Lai, H. Yu, Collisions for Hash 276 Functions MD4, MD5, HAVAL-128 and RIPEMD, 2004, 277 http://eprint.iacr.org/2004/199.pdf 279 [WYWZZ2009] X. Wang, H. Yu, W. Wang, H. Zhang, and T. Zhan. 280 Cryptanalysis of HMAC/NMAC-MD5 and MD5-MAC. LNCS 5479. 281 Advances in Cryptology - EUROCRYPT2009, Springer 2009. 283 Authors' Addresses 285 Sean Turner 286 IECA, Inc. 287 3057 Nutley Street, Suite 106 288 Fairfax, VA 22031 289 USA 291 EMail: turners@ieca.com 293 Lily Chen 294 National Institute of Standards and Technology 295 100 Bureau Drive, Mail Stop 8930 296 Gaithersburg, MD 20899-8930 297 USA 299 EMail: lily.chen@nist.gov