idnits 2.17.00 (12 Aug 2021) /tmp/idnits21407/draft-turner-md5-seccon-update-07.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 RFC2104, updated by this document, for RFC5378 checks: 1996-03-30) -- 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.) -- however, there's a paragraph with a matching beginning. Boilerplate error? -- The document date (November 8, 2010) is 4211 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. -------------------------------------------------------------------------------- 1 Network Working Group S. Turner 2 Internet Draft IECA 3 Updates: 1321, 2104 (once approved) L. Chen 4 Intended Status: Informational NIST 5 Expires: May 8, 2011 November 8, 2010 7 Updated Security Considerations for the 8 MD5 Message-Digest and the HMAC-MD5 Algorithms 9 draft-turner-md5-seccon-update-07.txt 11 Abstract 13 This document updates the security considerations for the MD5 message 14 digest algorithm. It also updates the security considerations for 15 HMAC-MD5. 17 Status of this Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. This document may contain material 21 from IETF Documents or IETF Contributions published or made publicly 22 available before November 10, 2008. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF), its areas, and its working groups. Note that 26 other groups may also distribute working documents as Internet- 27 Drafts. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 The list of current Internet-Drafts can be accessed at 35 http://www.ietf.org/ietf/1id-abstracts.txt. 37 The list of Internet-Draft Shadow Directories can be accessed at 38 http://www.ietf.org/shadow.html. 40 This Internet-Draft will expire on May 8, 2011. 42 Copyright Notice 44 Copyright (c) 2010 IETF Trust and the persons identified as the 45 document authors. All rights reserved. 47 This document is subject to BCP 78 and the IETF Trust's Legal 48 Provisions Relating to IETF Documents 49 (http://trustee.ietf.org/license-info) in effect on the date of 50 publication of this document. Please review these documents 51 carefully, as they describe your rights and restrictions with respect 52 to this document. Code Components extracted from this document must 53 include Simplified BSD License text as described in Section 4.e of 54 the Trust Legal Provisions and are provided without warranty as 55 described in the Simplified BSD License. 57 1. Introduction 59 MD5 [MD5] is a message digest algorithm that takes as input a message 60 of arbitrary length and produces as output a 128-bit "fingerprint" or 61 "message digest" of the input. The published attacks against MD5 62 show that it is not prudent to use MD5 when collision resistance is 63 required. This document replaces the security considerations in RFC 64 1321 [MD5]. 66 [HMAC] defined a mechanism for message authentication using 67 cryptographic hash functions. Any message digest algorithm can be 68 used, but the cryptographic strength of HMAC depends on the 69 properties of the underlying hash function. [HMAC-MD5] defined test 70 cases for HMAC-MD5. This document updates the security 71 considerations in [HMAC-MD5]. 73 [HASH-Attack] summarizes the use of hashes in many protocols and 74 discusses how attacks against a message digest algorithm's one-way 75 and collision-free properties affect and do not affect Internet 76 protocols. Familiarity with [HASH-Attack] is assumed. 78 2. Security Considerations 80 MD5 was published in 1992 as an Informational RFC. Since that time, 81 MD5 has been studied extensively. What follows are recent attacks 82 against MD5's collision, pre-image, and second pre-image resistance. 83 Additionally, attacks against MD5 used in message authentication with 84 a shared secret (i.e., HMAC-MD5) are discussed. 86 Some may find the guidance for key lengths and algorithm strengths in 87 [SP800-57] and [SP800-131] useful. 89 2.1. Collision Resistance 91 Psuedo-collisions for the compress function of MD5 were first 92 described in 1993 [denBBO1993]. In 1996, [DOB1995] demonstrated a 93 collision pair for the MD5 compression function with a chosen initial 94 value. The first paper that demonstrated two collision pairs for MD5 95 was published in 2004 [WFLY2004]. The detailed attack techniques for 96 MD5 were published at EUROCRYPT 2005 [WAYU2005]. Since then, a lot of 97 research results have been published to improve collision attacks on 98 MD5. The attacks presented in [KLIM2006] can find MD5 collision in 99 about one minute on a standard notebook PC (Intel Pentium, 1.6 GHz.). 100 [STEV2007] claims that it takes 10 seconds or less on a 2.6Ghz 101 Pentium4 to find collisions. In 102 [STEV2007][SLdeW2007][SSALMOdeW2009][SLdeW2009], the collision 103 attacks on MD5 were successfully applied to X.509 certificates. 105 Notice that the collision attack on MD5 can also be applied to 106 password based challenge-and-response authentication protocols such 107 as the APOP option in the Post Office Protocol (POP) used in post 108 office authentication as presented in [LEUR2007]. 110 In fact, more delicate attacks on MD5 to improve the speed of finding 111 collisions have been published recently. However, the aforementioned 112 results have provided sufficient reason to eliminate MD5 usage in 113 applications where collision resistance is required such as digital 114 signatures. 116 2.2. Pre-image and Second Pre-image Resistance 118 Even though the best result can find a pre-image attack of MD5 faster 119 than exhaustive search as presented in [SAAO2009], the complexity 120 2^123.4 is still pretty high. 122 2.3. HMAC 124 The cryptanalysis of HMAC-MD5 is usually conducted together with NMAC 125 (Nested MAC) since they are closely related. NMAC uses two 126 independent keys K1 and K2 such that NMAC(K1, K2, M) = H(K1, H(K2, 127 M), where K1 and K2 are used as secret IVs for hash function H(IV,M). 128 If we re-write the HMAC equation using two secret IVs such that IV2 = 129 H(K Xor ipad) and IV1 = H(K Xor opad), then HMAC(K, M) = NMAC(IV1, 130 IV2, M). Here it is very important to notice that IV1 and IV2 are 131 not independently selected. 133 The first analysis was explored on NMAC-MD5 using related keys in 134 [COYI2006]. The partial key recovery attack cannot be extended to 135 HMAC-MD5, since for HMAC, recovering partial secret IVs can hardly 136 lead to recovering (partial) key K. Another paper presented at Crypto 137 2007 [FLN2007] extended results of [COYI2006] to a full key recovery 138 attack on NMAC-MD5. Since it also uses related key attack, it does 139 not seem applicable to HMAC-MD5. 141 A EUROCRYPT 2009 paper presented a distinguishing attack on HMAC-MD5 142 [WYWZZ2009] without using related keys. It can distinguish an 143 instantiation of HMAC with MD5 from an instantiation with a random 144 function with 2^97 queries with probability 0.87. This is called 145 distinguishing-H. Using the distinguishing attack, it can recover 146 some bits of the intermediate status of the second block. However, as 147 it is pointed out in [WYWZZ2009], it cannot be used to recover the 148 (partial) inner key H(K Xor ipad). It is not obvious how the attack 149 can be used to form a forgery attack either. 151 The attacks on HMAC-MD5 do not seem to indicate a practical 152 vulnerability when used as a message authentication code. Considering 153 that the distinguishing-H attack is different from a distinguishing-R 154 attack, which distinguishes an HMAC from a random function, the 155 practical impact on HMAC usage as a PRF such as in a key derivation 156 function is not well understood. 158 Therefore, it may not be urgent to remove HMAC-MD5 from the existing 159 protocols. However, since MD5 must not be used for digital 160 signatures, for a new protocol design, a ciphersuite with HMAC-MD5 161 should not be included. Options include HMAC-SHA256 [HMAC][HMAC- 162 SHA256] and [AES-CMAC] when AES is more readily available than a hash 163 function. 165 3. IANA Considerations 167 IANA is requested to update the md5 usage entry in the Hash Function 168 Textual Names registry by replacing "COMMON" with "DEPRECATED". 170 4. Acknowledgements 172 Obviously, we have to thank all the cryptographers who produced the 173 results we refer to in this document. We'd also like to thank Alfred 174 Hoenes, Martin Rex, and Benne de Weger for their comments. 176 5. Normative References 178 [AES-CMAC] Song, J., Poovendran, R., Lee., J., and T. Iwata, 179 "The AES-CMAC Algorithm", RFC 4493, June 2006. 181 [COYI2006] S. Contini, Y.L. Yin. Forgery and partial key- 182 recovery attacks on HMAC and NMAC using hash 183 collisions. ASIACRYPT 2006. LNCS 4284, Springer, 184 2006. 186 [denBBO1993] den Boer, B. and A. Bosselaers, "Collisions for the 187 compression function of MD5", Eurocrypt 1993. 189 [DOB1995] Dobbertin, H., "Cryptanalysis of MD5 Compress", 190 Eurocrypt 1996. 192 [FLN2007] Fouque, P.-A., Leurent, G., Nguyen, P.Q.: Full key- 193 recovery attacks on HMAC/NMAC-MD4 and NMAC-MD5. 194 CRYPTO 2007. LNCS, 4622, Springer, 2007. 196 [HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on 197 Cryptographic Hashes in Internet Protocols", RFC 198 4270, November 2005. 200 [HMAC] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: 201 Keyed-Hashing for Message Authentication", RFC 202 2104, February 1997. 204 [HMAC-MD5] Cheng, P., and R. Glenn, "Test Cases for HMAC-MD5 205 and HMAC-SHA-1", RC 2201, September 1997. 207 [HMAC-SHA256] Nystrom, M., "Identifiers and Test Vectors for 208 HMAC-SHA-224, HMAC-SHA-256, HMAC-SHA-384, and 209 HMAC-SHA-512", RFC 4231, December 2005. 211 [KLIM2006] V. Klima. Tunnels in Hash Functions: MD5 Collisions 212 within a Minute. Cryptology ePrint Archive, Report 213 2006/105 (2006), http://eprint.iacr.org/2006/105. 215 [LEUR2007] G. Leurent, Message freedom in MD4 and MD5 216 collisions: Application to APOP. Proceedings of 217 FSE 2007. Lecture Notes in Computer Science 4715. 218 Springer 2007. 220 [MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 221 1321, April 1992. 223 [SAAO2009] Y. Sasaki and K. Aoki. Finding preimages in full 224 MD5 faster than exhaustive search. Advances in 225 Cryptology - EUROCRYPT 2009, LNCS 5479 of Lecture 226 Notes in Computer Science, Springer, 2009. 228 [SLdeW2007] Stevens, M., Lenstra, A., de Weger, B., Chosen- 229 prefix Collisions for MD5 and Colliding X.509 230 Certificates for Different Identities. EuroCrypt 231 2007. 233 [SLdeW2009] Stevens, M., Lenstra, A., de Weger, B., "Chosen- 234 prefix Collisions for MD5 and Applications", 235 Journal of Cryptology, 2009. 236 http://deweger.xs4all.nl/papers/%5B42%5DStLedW- 237 MD5-JCryp%5B2009%5D.pdf. 239 [SSALMOdeW2009] Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, 240 A., Molnar, D., Osvik, D., and B. de Weger. Short 241 chosen-prefix collisions for MD5 and the creation 242 of a rogue CA certificate, Crypto 2009. 244 [SP800-57] National Institute of Standards and Technology 245 (NIST), Special Publication 800-57: Recommendation 246 for Key Management - Part 1 (Revised), March 2007. 248 [SP800-131] National Institute of Standards and Technology 249 (NIST), Special Publication 800-131: DRAFT 250 Recommendation for the Transitioning of 251 Cryptographic Algorithms and Key Sizes, June 2010. 253 [STEV2007] Stevens, M., On Collisions for MD5. 254 http://www.win.tue.nl/hashclash/On%20Collisions%20 255 for%20MD5%20-%20M.M.J.%20Stevens.pdf. 257 [WAYU2005] X. Wang and H. Yu. How to Break MD5 and other Hash 258 Functions. LNCS 3494. Advances in Cryptology - 259 EUROCRYPT2005, Springer 2005. 261 [WFLY2004] X. Wang, D. Feng, X. Lai, H. Yu, Collisions for 262 Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, 263 2004, http://eprint.iacr.org/2004/199.pdf 265 [WYWZZ2009] X. Wang, H. Yu, W. Wang, H. Zhang, and T. Zhan. 266 Cryptanalysis of HMAC/NMAC-MD5 and MD5-MAC. LNCS 267 5479. Advances in Cryptology - EUROCRYPT2009, 268 Springer 2009. 270 Authors' Addresses 272 Sean Turner 273 IECA, Inc. 274 3057 Nutley Street, Suite 106 275 Fairfax, VA 22031 276 USA 278 EMail: turners@ieca.com 280 Lily Chen 281 National Institute of Standards and Technology 282 100 Bureau Drive, Mail Stop 8930 283 Gaithersburg, MD 20899-8930 284 USA 286 EMail: lily.chen@nist.gov