idnits 2.17.1 draft-turner-md4-to-historic-11.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 obsoletes RFC1320, but the abstract doesn't seem to directly say this. It does mention RFC1320 though, so this could be OK. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 6, 2011) is 4851 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Unused Reference: 'I-D.des-die-die-die' is defined on line 425, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 1320 (ref. 'MD4') (Obsoleted by RFC 6150) -- Obsolete informational reference (is this intentional?): RFC 2313 (Obsoleted by RFC 2437) -- Obsolete informational reference (is this intentional?): RFC 2437 (Obsoleted by RFC 3447) -- Obsolete informational reference (is this intentional?): RFC 3447 (Obsoleted by RFC 8017) Summary: 0 errors (**), 0 flaws (~~), 2 warnings (==), 6 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 Obsoletes: 1320 (once approved) L. Chen 5 Intended Status: Informational NIST 6 Expires: July 6, 2011 January 6, 2011 8 MD4 to Historic Status 9 draft-turner-md4-to-historic-11.txt 11 Abstract 13 This document retires RFC 1320, which documents the MD4 algorithm, 14 and discusses the reasons for doing so. This document moves RFC 1320 15 to Historic status. 17 Status of this Memo 19 This Internet-Draft is submitted in full conformance with the 20 provisions of BCP 78 and BCP 79. 22 Internet-Drafts are working documents of the Internet Engineering 23 Task Force (IETF). Note that other groups may also distribute 24 working documents as Internet-Drafts. The list of current Internet- 25 Drafts is at http://datatracker.ietf.org/drafts/current/. 27 Internet-Drafts are draft documents valid for a maximum of six months 28 and may be updated, replaced, or obsoleted by other documents at any 29 time. It is inappropriate to use Internet-Drafts as reference 30 material or to cite them other than as "work in progress." 32 This Internet-Draft will expire on June 29, 2011. 34 Copyright Notice 36 Copyright (c) 2010 IETF Trust and the persons identified as the 37 document authors. All rights reserved. 39 This document is subject to BCP 78 and the IETF Trust's Legal 40 Provisions Relating to IETF Documents 41 (http://trustee.ietf.org/license-info) in effect on the date of 42 publication of this document. Please review these documents 43 carefully, as they describe your rights and restrictions with respect 44 to this document. Code Components extracted from this document must 45 include Simplified BSD License text as described in Section 4.e of 46 the Trust Legal Provisions and are provided without warranty as 47 described in the Simplified BSD License. 49 1. Introduction 50 Internet-Draft MD4 to Historic 2011-01-06 52 MD4 [MD4] is a message digest algorithm that takes as input a message 53 of arbitrary length and produces as output a 128-bit "fingerprint" or 54 "message digest" of the input. This document retires [MD4]. 55 Specifically, this document moves RFC 1320 [MD4] to Historic status. 56 The reasons for taking this action are discussed. 58 [HASH-Attack] summarizes the use of hashes in many protocols and 59 discusses how attacks against a message digest algorithm's one-way 60 and collision-free properties affect and do not affect Internet 61 protocols. Familiarity with [HASH-Attack] is assumed. 63 2. Rationale 65 MD4 was published in 1992 as an Informational RFC. Since its 66 publication, MD4 has been under attack [denBORBOS1992] [DOBB1995] 67 [DOBB1996] [GLRW2010] [WLDCY2005] [LUER2008]. In fact, RSA, in 1996, 68 suggested that MD4 should not be used [RSA-AdviceOnMD4]. Microsoft 69 also made similar statements [MS-AdviceOnMD4]. 71 In Section 6, this document discusses attacks against MD4 that 72 indicate use of MD4 is no longer appropriate when collision 73 resistance is required. Section 6 also discusses attack against 74 MD4's pre-image and second pre-image resistance. Additionally, 75 attacks against MD4 used in message authentication with a shared 76 secret (i.e., HMAC-MD4) are discussed. 78 3. Documents that reference RFC 1320 80 Use of MD4 has been specified in the following RFCs: 82 Internet Standard (IS): 84 o [RFC2289] A One-Time Password System. 86 Draft Standard (DS): 88 o [RFC1629] Guidelines for OSI NSAP Allocation in the Internet. 90 Proposed Standard (PS): 92 o [RFC3961] Encryption and Checksum Specifications for Kerberos 5. 94 Best Current Practice (BCP): 96 o [RFC4086] Randomness Requirements for Security. 98 Informational: 100 Internet-Draft MD4 to Historic 2011-01-06 102 o [RFC1760] The S/KEY One-Time Password System. 104 o [RFC1983] Internet Users' Glossary. 106 o [RFC2433] Microsoft PPP CHAP Extensions. 108 o [RFC2759] Microsoft PPP CHAP Extensions, Version 2. 110 o [RFC3174] US Secure Hash Algorithm 1 (SHA1). 112 o [RFC4757] The RC4-HMAC Kerberos Encryption Types Used by 113 Microsoft Windows. 115 o [RFC5126] CMS Advanced Electronic Signatures (CAdES). 117 There are other RFCs that refer to MD4, but their status is either 118 Historic or Obsoleted. References and discussions about these RFCs 119 are omitted. The notable exceptions are: 121 o [RFC2313] PKCS #1: RSA Encryption Version 1.5. 123 o [RFC2437] PKCS #1: RSA Cryptography Specifications Version 2.0. 125 o [RFC3447] Public-Key Cryptography Standards (PKCS) #1: RSA 126 Cryptography Specifications Version 2.1. 128 4. Impact of Moving MD4 to Historic 130 The impact of moving MD4 to Historic is minimal with the one 131 exception of Microsoft's use of MD4 as part of RC4-HMAC in Windows, 132 as described below. 134 Regarding DS, PS, and BCP RFCs: 136 o The initial One-Time Password systems, based on [RFC2289], have 137 ostensibly been replaced by HMAC based mechanism, as specified in 138 HOTP: An HMAC-Based One-Time Password Algorithm [RFC4226]. 139 [RFC4226] suggests following recommendations in [RFC4086] for 140 random input, and in [RFC4086] weaknesses of MD4 are discussed. 142 o MD4 was used in the Inter-Domain Routing Protocol (IDRP); each IDRP 143 message carries a 16-octet hash that is computed by applying the 144 MD-4 algorithm (RFC 1320) to the context of the message itself. 145 Over time IDRP was replaced by BGP-4 [RFC4271], which required at 146 least [MD5]. 148 o Kerberos Version 5 [RFC3961] specifies the use of MD4 for DES 149 encryption types and checksum types. They were specified, never 151 Internet-Draft MD4 to Historic 2011-01-06 153 really used, and are in the process of being deprecated by [I- 154 D.des-die-die-die]. Further, the mandatory-to-implement encrypted 155 types and checksum types specified by Kerberos are based on AES-256 156 and HMAC-SHA1 [RFC3962]. 158 Regarding Informational RFCs: 160 o PKCS#1 v1.5 [RFC2313] indicated that there was no reason to not use 161 MD4. PKCS#1 v2.0 [RFC2437] and v2.1 [RFC3447] recommend against MD4 162 due to cryptoanalytic progess having uncovered weaknesses in the 163 collision resistance of MD4. 165 o Randomness Requirements [RFC4086] does mention MD4, but not in a 166 good way; it explains how the algorithm works and that there have 167 been a number of attacks found against it. 169 o The Internet Users' Glossary [RFC1983] provided a definition for 170 Message Digest and listed MD4 as one example. 172 o The IETF OTP specification [RFC2289] was based on S/Key technology. 173 So S/Key was replaced by OTP, at least in theory. Additonally, the 174 S/Key implementations in the wild have started to use MD5 in lieu 175 of MD4. 177 o The CAdES document [RFC5126] lists MD4 as hash algorithm, 178 disparages it, and then does not mention it again. 180 o The SHA-1 document [RFC3174] mentions MD4 in the acknowledgements 181 section. 183 o The three RFCs describing Microsoft protocols, [RFC2433], 184 [RFC2759], and [RFC4757], are very widely deployed, MS-CHAP v1, MS- 185 CHAP v2, and RC4-HMAC, respectively. 187 o MS-CHAP Version 1 is supported in Microsoft's Windows XP, 2000, 188 98, 95, NT 4.0, NT 3.51, NT 3.5, but support has been dropped in 189 Vista. MS-CHAP Version 2 is supported in Microsoft's Windows 7, 190 Vista, XP, 2000, 98, 95, and NT 4.0. Both versions of MS-CHAP 191 are also supported by RADIUS [RFC2548], and EAP [RFC5281]. In 192 2007, [RFC4962] listed MS-CHAP v1 and v2 as flawed and 193 recommended against their use; these incidents were presented as 194 a strong indication for the necessity of built-in crypto- 195 algorithm agility in AAA protocols. 197 o The RC4-HMAC is supported in Microsoft's Windows 2000 and later 198 versions of Windows for backwards compatibility with Windows 199 2000. As [RFC4757] stated, RC4-HMAC doesn't rely on the 200 collision resistance property of MD4, but uses it to generate a 202 Internet-Draft MD4 to Historic 2011-01-06 204 key from a password, which is then used as input to HMAC-MD5. 205 For an attacker to recover the password from RC4-HMAC, the 206 attacker first needs to recover the key that is used with HMAC- 207 MD5. As noted in [ID.turner-md5-seccon-update], key recovery 208 attacks on HMAC-MD5 are not yet practical. 210 5. Other Considerations 212 rsync [RSYNC], a non-IETF protocol, once specified the use of MD4, 213 but as of version 3.0.0 published in 2008 it has adopted MD5 [MD5]. 215 6. Security Considerations 217 This section addresses attacks against MD4's collisions, pre-image, 218 and second pre-image resistance. Additionally, attacks against HMAC- 219 MD4 are discussed. 221 Some may find the guidance for key lengths and algorithm strengths in 222 [SP800-57] and [SP800-131] useful. 224 6.1. Collision Resistance 226 A practical attack on MD4 was shown by Dobbertin in 1996 with 227 complexity 2^20 of MD4 hash computations [DOBB1996]. In 2004, a more 228 devastating result presented by Xiaoyun Wang showed that the 229 complexity can be reduced to 2^8 of MD4 hash operations. At the Rump 230 Session of Crypto 2004, Wang said that as a matter of fact, finding a 231 collision of MD4 can be accomplished with a pen on a piece of paper. 232 The formal result was presented at EUROCRYPT 2005 in [WLDCY2005]. 234 6.2. Pre-image and Second Pre-image Resistance 236 The first pre-image attack on full MD4 was accomplished in [LUER2008] 237 with complexity 2^100. Some improvements are shown on pre-image 238 attacks and second pre-image attacks of MD4 with certain pre- 239 computations [GLRW2010], where complexity is reduced to 2^78.4 and 240 2^69.4 for pre-image and second pre-image, respectively. The pre- 241 image attacks on MD4 are practical. It cannot be used as a one-way 242 function. For example, it must not be used to hash a cryptographic 243 key of 80 bits or longer. 245 6.3. HMAC 247 The attacks on Hash-based Message Authentication Code (HMAC) 248 algorithms [RFC2104] presented so far can be classified in three 249 types: distinguishing attacks, existential forgery attacks, and key 250 recovery attacks. Of course, among all these attacks, key recovery 251 attacks are the most severe attacks. 253 Internet-Draft MD4 to Historic 2011-01-06 255 The best results on key recovery attacks on HMAC-MD4 were published 256 at EUROCRYPT 2008 with 2^72 queries and 2^77 MD4 computations 257 [WOK2008]. 259 7. Recommendation 261 Despite MD4 seeing some deployment on the Internet, this 262 specification obsoletes [MD4] because MD4 is not a reasonable 263 candidate for further standardization and should be deprecated in 264 favor of one or more existing hash algorithms (e.g., SHA-256 [SHS]). 266 RSA Security considers it appropriate to move the MD4 algorithm to 267 Historic status. 269 It takes a number of years to deploy crypto and it also takes a 270 number of years to withdraw it. Algorithms need to be withdrawn 271 before a catastrophic break is discovered. MD4 is clearly showing 272 signs of weakness and implementations should strongly consider 273 removing support and migrating to another hash algorithm. 275 8. IANA Considerations 277 None. 279 9. Acknowledgements 281 We'd like to thank RSA for publishing MD4. Obviously, we have to 282 thank all the cryptographers who produced the results we refer to in 283 this document. We'd also like to thank Ran Atkinson, Sue Hares, Sam 284 Hartman, Alfred Hoenes, John Linn, Catherine Meadows, Magnus Nystrom, 285 and Martin Rex for their input. 287 10. Informative References 289 [denBORBOS1992] B. den Boer and A. Bosselaers. An attack on the last 290 two rounds of MD4. In Advances in Cryptology -Crypto '91, 291 pages 194-203, Springer-Verlag, 1992. 293 [DOBB1995] H. Dobbertin. Alf swindles Ann. CryptoBytes, 1(3): 5, 294 1995. 296 [DOBB1996] H. Dobbertin. Cryptanalysis of MD4. In Proceedings of the 297 3rd Workshop on Fast Software Encryption, Cambridge, U.K., 298 pages 53-70, Lecture Notes in Computer Science 1039, 299 Springer-Verlag, 1996. 301 [GLRW2010] Guo, J., Ling, S., Rechberger, C., and H. Wang, "Advanced 302 Meet-in-the-Middle Preimage Attacks: First Results on Full 304 Internet-Draft MD4 to Historic 2011-01-06 306 Tiger, and Improved Results on MD4 and SHA-2", 307 http://eprint.iacr.org/2010/016.pdf. 309 [HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on Cryptographic 310 Hashes in Internet Protocols", RFC 4270, November 2005. 312 [LUER2008] G. Leurent. MD4 is Not One-Way. Fast Software Encryption 313 2008, Lausanne, Switzerland, February 10-13, 2008, LNCS 314 5086. Springer, 2008. 316 [MD4] Rivest, R., "The MD4 Message-Digest Algorithm", RFC 1320, April 317 1992. 319 [MD5] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 320 1992. 322 [MS-AdviceOnMD4] Howard, M., "Secure Habits: 8 Simple Rules For 323 Developing More Secure Code", http://msdn.microsoft.com/en- 324 us/magazine/dvdarchive/cc163518.aspx#S6 326 [RFC1629] Colella, R., Callon, R., Gardner, E., and Y. Rekhter, 327 "Guidelines for OSI NSAP Allocation in the Internet", RFC 328 1629, May 1994. 330 [RFC1760] Haller, N., "The S/Key One-Time Password System", RFC 1760, 331 February 1995. 333 [RFC1983] Malkin, G., "Internet Users' Glossary", FYI 18, RFC 1983, 334 August 1996. 336 [RFC2289] Haller, N., Metz, C., Nesser, P. and M. Straw, "A One-Time 337 Password System", RFC 2289, February 1998. 339 [RFC2313] Kaliski, B., "PKCS #1: RSA Encryption Version 1.5", RFC 340 2313, March 1998. 342 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 343 Hashing for Message Authentication", RFC 2104, February 344 1997. 346 [RFC2433] Zorn, G. and S. Cobb, "Microsoft PPP CHAP Extensions", RFC 347 2433, October 1998. 349 [RFC2437] Kaliski, B., and J. Staddon, "PKCS #1: RSA Cryptography 350 Specifications Version 2.0", RFC 2437, October 1998. 352 [RFC2548] Zorn, G., "Microsoft Vendor-specific RADIUS Attributes", 353 RFC 2548, March 1998. 355 Internet-Draft MD4 to Historic 2011-01-06 357 [RFC2759] Zorn, G., "Microsoft PPP CHAP Extensions, Version 2", RFC 358 2759, January 2000. 360 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 361 (SHA1)", RFC 3174, September 2001. 363 [RFC3447] Jonsson, J. and B. Kaliski, "Public-Key Cryptography 364 Standards (PKCS) #1: RSA Cryptography Specifications 365 Version 2.1" RFC 3447, February 2003. 367 [RFC3961] Raeburn, K., "Encryption and Checksum Specifications for 368 Kerberos 5", RFC 3961, February 2005. 370 [RFC3962] Raeburn, K., "Advanced Encryption Standard (AES) Encryption 371 for Kerberos 5", RFC 3962, February 2005. 373 [RFC4086] R Eastlake, D., 3rd, Schiller, J., and S. Crocker, 374 "Randomness Requirements for Security", BCP 106, RFC 4086, 375 June 2005. 377 [RFC4226] Nikander, P., Arkko, J., Aura, T., Montenegro, G., and E. 378 Nordmark, "Mobile IP Version 6 Route Optimization Security 379 Design Background", RFC 4226, December 2005. 381 [RFC4271] Rekhter, Y., Li, T., and S. Hares, "A Border Gateway 382 Protocol 4 (BGP-4)", RFC 4271, January 2006. 384 [RFC4757] Jaganathan, K., Zhu, L., and J. Brezak, "The RC4-HMAC 385 Kerberos Encryption Types Used by Microsoft Windows," RFC 386 4757, December 2006. 388 [RFC4962] Housley, R., and Aboba, B., "Guidance for Authentication, 389 Authorization, and Accounting (AAA) Key Management", RFC 390 4962, July 2007. 392 [RFC5126] Pinkas, D., Pope, N., and J. Ross, "CMS Advanced Electronic 393 Signatures (CAdES)", RFC 5126, February 2008. 395 [RFC5281] Funk, P., and S. Blake-Wilson, "Extensible Authentication 396 Protocol Tunneled Transport Layer Security Authenticated 397 Protocol Version 0 (EAP-TTLSv0)", RFC 5281, August 2008. 399 [ID.turner-md5-seccon-update] Turner, S., and L. Chen, "Updated 400 Security Considerations for the MD5 Message-Digest and the 401 HMAC-MD5 Algorithms," draft-turner-md5-seccon-update, work- 402 in-progress. 404 [RSA-AdviceOnMD4] Robshaw, M.J.B., "On Recent Results for MD2, MD4 406 Internet-Draft MD4 to Historic 2011-01-06 408 and MD5", November 1996, 409 ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf 411 [RSYNC] http://www.samba.org/rsync/ 413 [SHS] National Institute of Standards and Technology (NIST), FIPS 414 Publication 180-3: Secure Hash Standard, October 2008. 416 [SP800-57] National Institute of Standards and Technology (NIST), 417 Special Publication 800-57: Recommendation for Key 418 Management - Part 1 (Revised), March 2007. 420 [SP800-131] National Institute of Standards and Technology (NIST), 421 Special Publication 800-131: DRAFT Recommendation for the 422 Transitioning of Cryptographic Algorithms and Key Sizes, 423 June 2010. 425 [I-D.des-die-die-die] Astrand, L.H., "Deprecate DES support for 426 Kerberos", draft-lha-des-die-die-die-05, work-in-progress. 428 [WLDCY2005] X. Wang, X. Lai, D. Feng, H. Chen, and X. Yu. 429 Cryptanalysis of Hash Functions MD4 and RIPEMD. LNCS 3494. 430 Advances in Cryptology - EUROCRYPT2005, Springer 2005. 432 [WOK2008] L. Wang, K. Ohta, and N. Kunihiro. New Key-recovery Attacks 433 on HMAC/NMAC-MD4 and NMAC-MD5. EUROCRYPT 2008.LNCS 4965, 434 Springer, 2008. 436 Authors' Addresses 438 Sean Turner 439 IECA, Inc. 440 3057 Nutley Street, Suite 106 441 Fairfax, VA 22031 442 USA 444 EMail: turners@ieca.com 446 Lily Chen 447 National Institute of Standards and Technology 448 100 Bureau Drive, Mail Stop 8930 449 Gaithersburg, MD 20899-8930 450 USA 452 EMail: lily.chen@nist.gov