Network Working Group T. Polk Internet Draft L. Chen Intended Status: Informational NIST Expires: March 30, 2011 S. Turner IECA September 30, 2010 Security Considerations for the SHA-0 and SHA-1 Message-Digest Algorithms draft-turner-sha0-sha1-seccon-00.txt Abstract This document updates the security considerations for the SHA-1 message digest algorithm. Additionally, it discusses security considerations for the SHA-0 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 March 30, 2011. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. Turner & Chen Expires March 30, 2011 [Page 1] Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010 This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (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 The Secure Hash Algorithms, SHA-1 and SHA-2 family (SHA) are specified in [SHS]. This document also makes assertions about SHA-0, which was documented in an earlier version of [SHS]. NIST withdrew SHA-0 in 1996. SHA-0 and SHA-1 are message digest algorithms that take as input a message of arbitrary length and produces as output a 160-bit "fingerprint" or "message digest" of the input. The published attacks against both algorithms show that it is not prudent to use them when collision resistance is required. [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. Some may find the guidance for key lengths and algorithm strengths in [SP800-57] and [SP800-131] useful. 1.1. Requirements Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [WORDS]. 2. SHA-0 Security Considerations What follows are recent attacks against SHA-0's collision, pre-image, and second pre-image resistance. Additionally, attacks against SHA-0 used in message authentication with a shared secret (i.e., HMAC-SHA- 0) are discussed. It must be noted that the discussions about SHA-0 is for completeness only. NIST withdrew SHA-0 in 1996. Any use of SHA-0 is strongly discouraged. Polk, et al. Expires January 30, 2011 [Page 2] Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010 2.1. Collision Resistance SHA-0 was published in 1993 by NIST. The first attacks were published in 1998 [CHJO1998] and showed collisions can be found in 2^61 operations. In 2006, [NSSYK2006] showed an improved attack that can find collisions in 2^36 operations. 2.2. Pre-image and Second Pre-image Resistance Even though SHA-0 has been withdrawn, it has been studied as a weaker version of SHA-1 in many research literatures. The main results obtained on pre-image and second pre-image attack are on reduced versions of SHA-0. [deCARE2008] showed a pre-image attack on 49 out of 80 rounds of SHA-0 with a complexity of 2^159 and [AOSA2009] showed a pre-image attack on 52 out of 80 rounds of SHA-0 with a complexity of 2^156. These results are considered as assertions on security margins of SHA-0 on pre-image resistance. 2.3. HMAC-SHA-0 The attacks on HMAC presented so far can be classified in three types: distinguishing attacks, existential forgery attacks, and key recovery attacks. Of course, among all these attacks, key recovery attacks are the most severe attacks. As opposed to attacking a hash function, which can be conducted through purely offline computations, an attack on HMAC would need to query a large amount of HMAC values, since the keys are unknown. The best results on partial key recovery attacks on HMAC-SHA0 were published at ASIACRYPT 2006 with 2^84 queries and 2^60 SHA-0 computations [COYI2006]. 3. SHA-1 Security Considerations What follows are recent attacks against SHA-1's collision, pre-image, and second pre-image resistance. Additionally, attacks against SHA-1 used in message authentication with a shared secret (i.e., HMAC-SHA- 1) are discussed. It must be noted that NIST has recommended that SHA-1 not be used for generating digital signatures after Dec 31st 2010 and has mandated that it not be used for generating digital signatures after December 31st 2013 [SP800-131]. 3.1. Collision Resistance SHA-1 was published by NIST in 1995. The first attack was published in early 2005 [RIOS2005]. It described a theoretical shortcut attack Polk, et al. Expires January 30, 2011 [Page 3] Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010 on a version of SHA-1 reduced to 53 rounds. The very next month [WLY2005] showed collisions in the full 80 round SHA-1 in 2^69 operations. Since then, many new analysis methods have been developed to improve the attack presented in [WLY2005]. However, there is no formal claimed complexity in finding collision for full version SHA-1 in less complexity than the result presented in [WLY2005]. The IACR ePrint version [Man2008/469] of [Man2009] claimed that using the method presented in the paper, a collision of full SHA-1 can be found in 2^51 hash function calls. However, the claimed bound is removed when it was published at a conference [Man2009]. In any case, the known research results indicated that SHA-1 is not as collision resistant as expected. The collision security strength is significantly less than an ideal hash function, and its use in digital signature generation after 2010 has been deprecated by NIST. 3.2. Pre-image and Second Pre-image Resistance The preimage and second preimage attacks published so far on reduced versions of SHA-1 just indicate the security margin of SHA-1 in resistance to these attacks. [AOSA2009] showed a preimage attack on 48 out of 80 steps with complexity of 2^159. [KeSch] discovered for a narrow pipe Merkle-Damgaard hash functions, finding a second preimage takes less than 2^n computations. This result applies to all the narrow pipe Merkle-Damgaard hash functions and not specific for SHA-1. When n = 160 in case of SHA-1, for 60 byte message, it will take 2^106 computations to find a second preimage. 3.3. HMAC-SHA-1 So far, there is no indication that attacks and analysis results on SHA-1 can be extended to HMAC-SHA-1. 4. Guidance SHA-1 no longer provides an acceptable security level when used in digital signature applications. IETF protocol designers SHOULD NOT specify digital signature algorithms using SHA-1 as mandatory to implement. IETF protocols that rely on SHA-1 based digital signatures MUST include countermeasures that mitigate SHA-1's reduced collision resistance by randomized hashing (e.g., as specified in [SP800-107]). HMAC-SHA-1 remains secure and is the preferred keyed hash algorithm for IETF protocol design. Polk, et al. Expires January 30, 2011 [Page 4] Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010 As noted above, any use of SHA-0 is strongly discouraged. Discussions regarding the strength of SHA-0 were included for completeness only. SHA-0 has no functional or performance advantage, and SHA-1 is considered significantly more secure. 5. Security Considerations This entire document addresses security considerations. 6. IANA Considerations None. 7. Normative References [AOSA2009] Aoki, K., and K. Saski, "Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1", Crypto 2009. [deCARE2008] De Canniere, C. and C. Rechberger, "Preimages for Reduced SHA-0 and SHA-1", Crypto 2008. [CHJO1998] Chaubad, F., and A. Joux, "Differential Collisions in SHA-0", Crypto 1998. [COYI2006] Contini, S., and Y. Lin, "Forgery and Partial Key- Recovery Attacks on HMAC and NMAC Using Hash Collisions", Asiacrypt 2006. [HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on Cryptographic Hashes in Internet Protocols", RFC 4270, November 2005. [KeSch] Kelsey, J., and B. Schneier, "Second Preimages on n-Bit Hash Functions for Much Less than 2n Work", In Cramer, R., ed.: EUROCRYPT'05. Volume 3494 of Lecture Notes in Computer Science, Springer (2005) 474-490. [Man2008/469] Manuell, S., "Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1", http://eprint.iacr.org/2008/469.pdf. [Man2009] Manuell, S., "Classification and Generation of Disturbance Vectors for Collision Attacks against SHA-1", International Workshop on Coding and Cryptography, 2009, Norway. Polk, et al. Expires January 30, 2011 [Page 5] Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010 [NSSYK2006] Naito, Y., Sasaki, Y., Shimoyama, T., Yajima, J., Kunihiro, N. and K. Ohta, "Improved Collision Search for SHA-0", ASIACRYPT 2006. [RIOS2005] Rijmen, V., and E. Oswald, "Update on SHA-1", CT- RSA 2005, LNCS 3376, pp. 58-71. [SHS] National Institute of Standards and Technology (NIST), FIPS Publication 180-3: Secure Hash Standard, October 2008. [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. [SP800-107] National Institute of Standards and Technology (NIST), Special Publication 800-107: Recommendation for Applications using Approved Hash Algorithms of Algorithms, February 2009. [WLY2005] Wang, X., Yin, Y. and H. Yu. "Finding Collisions in the Full SHA-1", Crypto 2005. [WORDS] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. Authors' Addresses Tim Polk National Institute of Standards and Technology 100 Bureau Drive, Mail Stop 8930 Gaithersburg, MD 20899-8930 USA EMail: tim.polk@nist.gov Lily Chen National Institute of Standards and Technology 100 Bureau Drive, Mail Stop 8930 Gaithersburg, MD 20899-8930 USA EMail: lily.chen@nist.gov Polk, et al. Expires January 30, 2011 [Page 6] Internet-Draft SHA-0 and SHA-1 Security Considerations Sept 2010 Sean Turner IECA, Inc. 3057 Nutley Street, Suite 106 Fairfax, VA 22031 USA EMail: turners@ieca.com Polk, et al. Expires January 30, 2011 [Page 7]