One document matched: draft-turner-md5-seccon-update-00.txt

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]