idnits 2.17.1 draft-turner-sha0-sha1-seccon-05.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 3, 2011) is 4828 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group T. Polk 3 Internet-Draft L. Chen 4 Intended Status: Informational NIST 5 Expires: August 3, 2011 S. Turner 6 IECA 7 P. Hoffman 8 VPN Consortium 9 February 3, 2011 11 Security Considerations for the 12 SHA-0 and SHA-1 Message-Digest Algorithms 13 draft-turner-sha0-sha1-seccon-05 15 Abstract 17 This document includes security considerations for the SHA-0 and SHA- 18 1 message digest algorithm. 20 Status of this Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on August 3, 2011. 37 Copyright Notice 39 Copyright (c) 2011 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 51 Internet-Draft SHA-0 and SHA-1 Security Considerations 2011-02-03 53 described in the Simplified BSD License. 55 1. Introduction 57 The Secure Hash Algorithms are specified in [SHS]. A previous version 58 of [SHS] also specified SHA-0. SHA-0, first published in 1993, and 59 SHA-1, first published in 1996, are message digest algorithms, 60 sometimes referred to as hash functions or hash algorithms, that take 61 as input a message of arbitrary length and produce as output a 160- 62 bit "fingerprint" or "message digest" of the input. The published 63 attacks against both algorithms show that it is not prudent to use 64 either algorithm when collision resistance is required. 66 [HASH-Attack] summarizes the use of hashes in Internet protocols and 67 discusses how attacks against a message digest algorithm's one-way 68 and collision-free properties affect and do not affect Internet 69 protocols. Familiarity with [HASH-Attack] is assumed. 71 Some may find the guidance for key lengths and algorithm strengths in 72 [SP800-57] and [SP800-131] useful. 74 2. SHA-0 Security Considerations 76 What follows are summaries of recent attacks against SHA-0's 77 collision, pre-image, and second pre-image resistance. Additionally, 78 attacks against SHA-0 when used as a keyed-hash (e.g., HMAC-SHA-0) 79 are discussed. 81 The U.S. National Institute of Standards and Technology (NIST) 82 withdrew SHA-0 in 1996. That is, NIST no longer considers it 83 appropriate to use SHA-0 for any transactions associated with the use 84 of cryptography by U.S. Federal government agencies for the 85 protection of sensitive, but unclassified information. SHA-0 is 86 discussed here only for the sake of completeness. 88 Any use of SHA-0 is strongly discouraged. Analysis of SHA-0 continues 89 today because many see it as a weaker version of SHA-1. 91 2.1. Collision Resistance 93 The first attack on SHA-0 was published in 1998 [CHJO1998] and showed 94 that collisions can be found in 2^61 operations. In 2006, 95 [NSSYK2006] showed an improved attack that can find collisions in 96 2^36 operations. 98 In any case, the known research results indicate that SHA-0 is not as 99 collision resistant as expected. The collision security strength is 100 significantly less than an ideal hash function (i.e., 2^36 compared 102 Internet-Draft SHA-0 and SHA-1 Security Considerations 2011-02-03 104 to 2^80). 106 2.2. Pre-image and Second Pre-image Resistance 108 The pre-image and second pre-image attacks published on reduced 109 versions of SHA-0 (i.e., less than 80 rounds) indicate that the 110 security margin of SHA-0 is resistant to these attacks. [deCARE2008] 111 showed a pre-image attack on 49 out of 80 rounds with complexity of 112 2^159 and [AOSA2009] showed a pre-image attack on 52 out of 80 rounds 113 with a complexity of 2^156. 115 2.3. HMAC-SHA-0 117 The current attack vectors on HMAC can be classified as follows: 118 distinguishing attacks, existential forgery attacks, and key recovery 119 attacks. Key recovery attacks are by far the most severe. 121 Attacks on hash functions can be conducted entirely offline, since 122 the attacker can generate unlimited plaintext-ciphertext pairs. 123 Attacks on HMACs must be online because attackers need a large amount 124 of HMAC values to deduce the key. The best results for a partial key 125 recovery attack on HMAC-SHA0 were published at ASIACRYPT 2006 with 126 2^84 queries and 2^60 SHA-0 computations [COYI2006]. 128 3. SHA-1 Security Considerations 130 What follows are recent attacks against SHA-1's collision, pre-image, 131 and second pre-image resistance. Additionally, attacks against SHA-1 132 when used as a keyed-hash (i.e., HMAC-SHA-1) are discussed. 134 It must be noted that NIST has recommended that SHA-1 not be used for 135 generating digital signatures after Dec 31st 2010 and has specified 136 that it not be used for generating digital signatures by U.S. Federal 137 government agencies "for the protection of sensitive, but 138 unclassified information" after December 31st 2013 [SP800-131]. 140 3.1. Collision Resistance 142 The first attack on SHA-1 was published in early 2005 [RIOS2005]. 143 This attack described a theoretical attack on a version of SHA-1 144 reduced to 53 rounds. The very next month [WLY2005] showed 145 collisions in the full 80 rounds in 2^69 operations. Since then, 146 many new analysis methods have been developed to improve the attack 147 presented in [WLY2005]. However, there are no published results that 148 improve upon the results found in [WLY2005]. The IACR ePrint version 149 [Man2008/469] of [Man2009] claimed that using the method presented in 150 the paper, a collision of full SHA-1 can be found in 2^51 hash 151 function calls. However, this claim is absent from the published 153 Internet-Draft SHA-0 and SHA-1 Security Considerations 2011-02-03 155 conference paper [Man2009]. 157 In any case, the known research results indicate that SHA-1 is not as 158 collision resistant as expected. The collision security strength is 159 significantly less than an ideal hash function (i.e., 2^69 compared 160 to 2^80). 162 3.2. Pre-image and Second Pre-image Resistance 164 There are no known pre-image or second pre-image attacks that are 165 specific to the full round SHA-1 algorithm. [KeSch] discovered a 166 general result for all narrow pipe Merkle-Damgaard hash functions 167 (which includes SHA-1), finding a second pre-image takes less than 168 2^n computations. When n = 160 as is the case for SHA-1, it will take 169 2^106 computations to find a second pre-image in a 60-byte message. 171 In the absence of full round attacks, cryptographers consider 172 reduced-round attacks for clues regarding an algorithm's strength. 173 Reduced-round attacks, where the number of reduced rounds is not more 174 than a few less than the full rounds, have not been shown to relate 175 to full-round attacks. However, the best reduced round attack 176 indicates a certain security margin. For example, if the best known 177 attack is on 60 out of 80 rounds, then the algorithm has about 20 178 rounds to resist improved attacks. However, the relationship between 179 the number of rounds an attack can reach and the number of rounds 180 defined in the algorithm is not linear; it does not provide a 181 mathematical proof. In other words, reduced round attacks indicate 182 how strong the algorithm is with regard to a certain attack, not how 183 close it is to being broken. Therefore, the following information 184 about reduced-round attacks is included only for completeness. 186 The pre-image and second pre-image attacks published on reduced 187 versions of SHA-1 (i.e., less than 80 rounds) indicate that SHA-1 188 retains a significant security margin against these attacks. 189 [AOSA2009] showed a pre-image attack on 48 out of 80 rounds with 190 complexity of 2^159. 192 3.3. HMAC-SHA-1 194 As of today, there is no indication that attacks on SHA-1 can be 195 extended to HMAC-SHA-1. 197 4. Conclusions 199 SHA-1 provides less collision resistance than was originally 200 expected, and collision resistance has been shown to affect some (but 201 not all) applications that use digital signatures. Designers of IETF 202 protocols that use digital signature algorithms should strongly 204 Internet-Draft SHA-0 and SHA-1 Security Considerations 2011-02-03 206 consider support for a hash algorithm with greater collision 207 resistance than that provided by SHA-1. Of course, SHA-0 should 208 continue to not be used in any IETF protocol. 210 [Note: Protocol designers should review the current state of the art 211 to ensure that selected hash algorithms provide sufficient security. 212 At the time of publication, SHA-256 [SHS] is the most commonly 213 specified alternative. The known (reduced round) attacks on the 214 collision resistance of SHA-256 indicate a significant security 215 margin, and the longer message digest provides increased strength.] 217 Nearly all IETF protocols that use signatures assume existing public 218 key infrastructures, and SHA-1 is still used in signatures nearly 219 everywhere. Therefore, it is unwise to strictly prohibit the use of 220 SHA-1 in signature algorithms. Protocols that permit the use of SHA-1 221 based digital signatures as an option should strongly consider 222 referencing this document in the security considerations. 224 A protocol designer might want to consider the use of SHA-1 with 225 randomized hashing such as is specified in [SP800-107]. Note that 226 randomized hashing expands the size of signatures and requires 227 protocols to carry material that is not needed today. HMAC-SHA-1 228 remains secure and is the preferred keyed-hash algorithm for IETF 229 protocol design. 231 5. Security Considerations 233 This entire document is about security considerations. 235 6. IANA Considerations 237 None. 239 7. Acknowledgements 241 We'd like to thank Ran Atkinson and Sheila Frankel for their comments 242 and suggestions. 244 8. Normative References 246 [AOSA2009] Aoki, K., and K. Saski, "Meet-in-the-Middle Preimage 247 Attacks Against Reduced SHA-0 and SHA-1", Crypto 2009. 249 [deCARE2008] De Canniere, C. and C. Rechberger, "Preimages for 250 Reduced SHA-0 and SHA-1", Crypto 2008. 252 Internet-Draft SHA-0 and SHA-1 Security Considerations 2011-02-03 254 [CHJO1998] Chaubad, F., and A. Joux, "Differential Collisions in 255 SHA-0", Crypto 1998. 257 [COYI2006] Contini, S., and Y. Lin, "Forgery and Partial Key- 258 Recovery Attacks on HMAC and NMAC Using Hash Collisions", 259 Asiacrypt 2006. 261 [HASH-Attack] Hoffman, P., and B. Schneier, "Attacks on 262 Cryptographic Hashes in Internet Protocols", RFC 4270, 263 November 2005. 265 [KeSch] Kelsey, J., and B. Schneier, "Second Preimages on n-Bit Hash 266 Functions for Much Less than 2n Work", In Cramer, R., ed.: 267 EUROCRYPT'05. Volume 3494 of Lecture Notes in Computer 268 Science, Springer (2005) 474-490. 270 [Man2008/469] Manuell, S., "Classification and Generation of 271 Disturbance Vectors for Collision Attacks against SHA-1", 272 http://eprint.iacr.org/2008/469.pdf. 274 [Man2009] Manuell, S., "Classification and Generation of Disturbance 275 Vectors for Collision Attacks against SHA-1", International 276 Workshop on Coding and Cryptography, 2009, Norway. 278 [NSSYK2006] Naito, Y., Sasaki, Y., Shimoyama, T., Yajima, J., 279 Kunihiro, N. and K. Ohta, "Improved Collision Search for 280 SHA-0", ASIACRYPT 2006. 282 [RIOS2005] Rijmen, V., and E. Oswald, "Update on SHA-1", CT-RSA 283 2005, LNCS 3376, pp. 58-71. 285 [SHS] National Institute of Standards and Technology (NIST), FIPS 286 Publication 180-3: Secure Hash Standard, October 2008. 288 [SP800-57] National Institute of Standards and Technology (NIST), 289 Special Publication 800-57: Recommendation for Key 290 Management - Part 1 (Revised), March 2007. 292 [SP800-107] National Institute of Standards and Technology (NIST), 293 Special Publication 800-107: Recommendation for 294 Applications using Approved Hash Algorithms, February 2009. 296 [SP800-131] National Institute of Standards and Technology (NIST), 297 Special Publication 800-131A: Recommendation for the 298 Transitioning of Cryptographic Algorithms and Key Sizes, 299 January 2011. 301 [WLY2005] Wang, X., Yin, Y. and H. Yu., "Finding Collisions in the 303 Internet-Draft SHA-0 and SHA-1 Security Considerations 2011-02-03 305 Full SHA-1", Crypto 2005. 307 Authors' Addresses 309 Tim Polk 310 National Institute of Standards and Technology 311 100 Bureau Drive, Mail Stop 8930 312 Gaithersburg, MD 20899-8930 313 USA 315 EMail: tim.polk@nist.gov 317 Lily Chen 318 National Institute of Standards and Technology 319 100 Bureau Drive, Mail Stop 8930 320 Gaithersburg, MD 20899-8930 321 USA 323 EMail: lily.chen@nist.gov 325 Sean Turner 326 IECA, Inc. 327 3057 Nutley Street, Suite 106 328 Fairfax, VA 22031 329 USA 331 EMail: turners@ieca.com 333 Paul Hoffman 334 VPN Consortium 336 EMail: paul.hoffman@vpnc.org