idnits 2.17.1 draft-hoffman-schneier-4270bis-02.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 document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (April 29, 2013) is 4009 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Obsolete informational reference (is this intentional?): RFC 3280 (Obsoleted by RFC 5280) Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group P. Hoffman 3 Internet-Draft VPN Consortium 4 Obsoletes: 4270 (if approved) B. Schneier 5 Intended status: Informational Counterpane Internet Security 6 Expires: October 31, 2013 April 29, 2013 8 Attacks on Cryptographic Hashes in Internet Protocols 9 draft-hoffman-schneier-4270bis-02 11 Abstract 13 Announcements in the past decade of better-than-expected collision 14 attacks in popular hash algorithms have caused some people to 15 question whether common Internet protocols need to be changed, and if 16 so, how. This document summarizes the use of hashes in many 17 protocols, discusses how the collision attacks affect and do not 18 affect the protocols, shows how to thwart known attacks on digital 19 certificates, and discusses future directions for protocol designers. 20 It also gives rationales for moving away from some hash algorithms 21 altogether and for choosing when to start using newer, presumably 22 better, hash algorithms in Internet protocols. 24 This document obsoletes RFC 4270 and introduces significant new 25 material that has been learned since the publication of that 26 document. 28 Status of This Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 This Internet-Draft will expire on October 31, 2013. 45 Copyright Notice 47 Copyright (c) 2013 IETF Trust and the persons identified as the 48 document authors. All rights reserved. 50 This document is subject to BCP 78 and the IETF Trust's Legal 51 Provisions Relating to IETF Documents 52 (http://trustee.ietf.org/license-info) in effect on the date of 53 publication of this document. Please review these documents 54 carefully, as they describe your rights and restrictions with respect 55 to this document. Code Components extracted from this document must 56 include Simplified BSD License text as described in Section 4.e of 57 the Trust Legal Provisions and are provided without warranty as 58 described in the Simplified BSD License. 60 Table of Contents 62 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 63 2. Hash Algorithms and Attacks on Them . . . . . . . . . . . . . 3 64 2.1. Currently Known Attacks . . . . . . . . . . . . . . . . . 5 65 3. How Internet Protocols Use Hash Algorithms . . . . . . . . . 5 66 4. Hash Collision Attacks and Non-repudiation of Digital 67 Signatures . . . . . . . . . . . . . . . . . . . . . . . . . 6 68 5. Hash Collision Attacks and Digital Certificates from Trusted 69 Third Parties . . . . . . . . . . . . . . . . . . . . . . . . 7 70 5.1. Reducing the Likelihood of Hash-based Attacks on PKIX 71 Certificates . . . . . . . . . . . . . . . . . . . . . . 9 72 6. Cost of Creating Collisions in SHA-1 . . . . . . . . . . . . 9 73 7. The SHA-3 Competition and the Future . . . . . . . . . . . . 11 74 8. Future Attacks and Their Effects . . . . . . . . . . . . . . 11 75 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 76 10. Informative References . . . . . . . . . . . . . . . . . . . 13 77 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 14 78 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 14 80 1. Introduction 82 In summer 2004, a team of researchers showed concrete evidence that 83 the MD5 hash algorithm was susceptible to collision attacks 84 [MD5-attack]. In early 2005, the same team demonstrated a similar 85 attack on a variant of the SHA-1 [RFC3174] hash algorithm, with a 86 prediction that the normally used SHA-1 would also be susceptible 87 with a large amount of work (but at a level below what should be 88 required if SHA-1 worked properly) [SHA-1-attack]; that work has been 89 improved on more recently [Stevens]. Also in early 2005, researchers 90 showed a specific construction of PKIX certificates [RFC3280] that 91 use MD5 for signing [PKIX-MD5-construction], and another researcher 92 showed a faster method for finding MD5 collisions (eight hours on 93 1.6-GHz computer) [MD5-faster]. 95 Because of these announcements, there was a great deal of discussion 96 by cryptography experts, protocol designers, and other concerned 97 people about what, if anything, should be done based on the news. 99 Unfortunately, some of these discussions have been based on erroneous 100 interpretations of both the news and on how hash algorithms are used 101 in common Internet protocols. 103 Hash algorithms are used by cryptographers in a variety of security 104 protocols, for a variety of purposes, at all levels of the Internet 105 protocol stack. They are used because they have two security 106 properties: to be "one way" and "collision free". (There is more 107 about these properties in the next section; they're easier to explain 108 in terms of breaking them.) The attacks have demonstrated that one 109 of those security properties is not true. While it is certainly 110 possible, and at a first glance even probable, that the broken 111 security property will not affect the overall security of many 112 specific Internet protocols, the conservative security approach is to 113 change hash algorithms. The Internet protocol community needs to 114 migrate in an orderly manner away from SHA-1 and MD5 -- especially 115 MD5 -- and toward more secure hash algorithms, namely the SHA-2 116 family[RFC6234]. 118 This document summarizes what is currently known about hash 119 algorithms and the Internet protocols that use them. It also gives 120 advice on how to avoid the currently known problems with MD5 and 121 SHA-1. 123 A high-level summary of the current situation is: 125 o Both MD5 and SHA-1 have attacks against them, the attacks against 126 MD5 being much more severe than the attacks against SHA-1. 128 o The attacks against MD5 are practical on any modern computer. 130 o The attacks against SHA-1 are practical for some attackers now, 131 and will be more practical for more attackers in the near future. 133 o Attackers are able to use collisions in PKIX certificates to 134 generate certificates that can act as trusted entities to create 135 other certificates. 137 o Many common Internet protocols use hashes in ways that are 138 unaffected by these attacks. 140 o Most of the affected protocols use digital signatures. 142 o Better hash algorithms will reduce the susceptibility of these 143 attacks to an acceptable level for all users. 145 2. Hash Algorithms and Attacks on Them 146 A "perfect" hash algorithm has a few basic properties. The algorithm 147 converts a chunk of data (normally, a message) of any size into a 148 fixed-size result. The length of the result is called the "hash 149 length" and is often denoted as "L"; the result of applying the hash 150 algorithm on a particular chunk of data is called the "hash value" 151 for that data. Any two different messages of any size should have an 152 exceedingly small probability of having the same hash value, 153 regardless of how similar or different the messages are. 155 This description leads to two mathematical results. Finding a pair 156 of messages M1 and M2 that have the same hash value takes 2^(L/2) 157 attempts. For any reasonable hash length, this is an impossible 158 problem to solve (collision free). Also, given a message M1, finding 159 any other message M2 that has the same hash value as M1 takes 2^L 160 attempts. This is an even harder problem to solve (one way). 162 Note that this is the description of a perfect hash algorithm; if the 163 algorithm is less than perfect, an attacker can expend less than the 164 full amount of effort to find two messages with the same hash value. 166 There are two categories of attacks. 168 Attacks against the "collision free" property: 170 o A "collision attack" allows an attacker to find two messages M1 171 and M2 that have the same hash value in fewer than 2^(L/2) 172 attempts. 174 Attacks against the "one way" property: 176 o A "first-preimage attack" allows an attacker who knows a desired 177 hash value to find a message that results in that value in fewer 178 than 2^L attempts. 180 o A "second-preimage attack" allows an attacker who has a desired 181 message M1 to find another message M2 that has the same hash value 182 in fewer than 2^L attempts. 184 The two preimage attacks are very similar. In a first-preimage 185 attack, you know a hash value but not the message that created it, 186 and you want to discover any message with the known hash value; in 187 the second-preimage attack, you have a message and you want to find a 188 second message that has the same hash. Attacks that can find one 189 type of preimage can often find the other as well. 191 When analyzing the use of hash algorithms in protocols, it is 192 important to differentiate which of the two properties of hashes are 193 important, particularly now that the collision-free property is 194 becoming weaker for currently popular hash algorithms. It is 195 certainly important to determine which parties select the material 196 being hashed. Further, as shown by some of the early work, 197 particularly [PKIX-MD5-construction], it is also important to 198 consider which party can predict the material at the beginning of the 199 hashed object. 201 2.1. Currently Known Attacks 203 All the currently known practical or almost-practical attacks on MD5 204 and SHA-1 are collision attacks. This is fortunate: significant 205 first- and second-preimage attacks on a hash algorithm would be much 206 more devastating in the real world than collision attacks, as 207 described later in this document. 209 It is also important to note that the current collision attacks 210 require at least one of the two messages to have a fair amount of 211 structure in the bits of the message. This means that finding two 212 messages that both have the same hash value *and* are useful in a 213 real-world attack is more difficult than just finding two messages 214 with the same hash value. 216 Since the time that the collision attacks were first discovered, some 217 attackers have used them to bootstrap other more devastating types of 218 attacks. Probably the most significant is [Chosen-Prefix], which 219 shows how to use collisions to forge new CA certificates that would 220 be accepted by web browsers at the time. The "Flame" worm attack 221 discovered in 2012 relied on spoofed Microsoft code-signing 222 certificates that were acquired using the collision reduction attack 223 on MD5 [Flame-Microsoft]. 225 3. How Internet Protocols Use Hash Algorithms 227 Hash algorithms are used in many ways on the Internet. Most 228 protocols that use hash algorithms do so in a way that makes them 229 immune to harm from collision attacks. This is not by accident: good 230 protocol designers develop their protocols to withstand as many 231 future changes in the underlying cryptography as possible, including 232 attacks on the cryptographic algorithms themselves. 234 Uses for hash algorithms include: 236 o Non-repudiable digital signatures on messages. Non-repudiation is 237 a security service that provides protection against false denial 238 of involvement in a communication. S/MIME and OpenPGP allow mail 239 senders to sign the contents of a message they create, and the 240 recipient of that message can verify whether or not the signature 241 is actually associated with the message. A message is used for 242 non-repudiation if the message is signed and the recipient of the 243 message can later use the signature to prove that the signer 244 indeed created the message. 246 o Digital signatures in certificates from trusted third parties. 247 Although this is similar to "digital signatures on messages", 248 certificates themselves are used in many other protocols for 249 authentication and key management. 251 o Challenge-response protocols. These protocols combine a public 252 large random number with a value to help hide the value when being 253 sent over unencrypted channels. 255 o Message authentication with shared secrets. These are similar to 256 challenge-response protocols, except that instead of using public 257 values, the message is combined with a shared secret before 258 hashing. 260 o Key derivation functions. These functions make repeated use of 261 hash algorithms to mix data into a random string for use in one or 262 more keys for a cryptographic protocol. 264 o Mixing functions. These functions also make repeated use of hash 265 algorithms to mix data into random strings, for uses other than 266 cryptographic keys. 268 o Integrity protection. It is common to compare a hash value that 269 is received out-of-band for a file with the hash value of the file 270 after it is received over an unsecured protocol such as FTP. 272 Of the above methods, only the first two are affected by collision 273 attacks, and even then, only in limited circumstances. So far, it is 274 believed that, in general, challenge-response protocols are not 275 susceptible, because the sender is authenticating a secret already 276 stored by the recipient. In message authentication with shared 277 secrets, the fact that the secret is known to both parties is also 278 believed to prevent any sensible attack. All key derivation 279 functions in IETF protocols take random input from both parties, so 280 the attacker has no way of structuring the hashed message. 282 4. Hash Collision Attacks and Non-repudiation of Digital Signatures 283 The basic idea behind the collision attack on a hash algorithm used 284 in a digital-signature protocol is that the attacker creates two 285 messages that have the same hash value, causes one of them to be 286 signed, and then uses that signature over the other message for some 287 nefarious purpose. The specifics of the attack depend on the 288 protocol being used and what the victim does when presented with the 289 signed message. 291 The canonical example is where you create two messages, one of which 292 says "I will pay $10 for doing this job" and the other of which says 293 "I will pay $10,000 for doing this job". You present the first 294 message to the victim, get them to sign it, do the job, substitute 295 the second message in the signed authorization, present the altered 296 signed message (whose signature still verifies), and demand the 297 higher amount of money. If the victim refuses, you take them to 298 court and show the second signed message. 300 Most non-repudiation attacks rely on a human assessing the validity 301 of the purportedly signed message. In the case of the hash-collision 302 attack, the purportedly signed message's signature is valid, but so 303 is the signature on the original message. The victim can produce the 304 original message, show that they signed it, and show that the two 305 hash values are identical. The chance of this happening by accident 306 is one in 2^L, which is infinitesimally small for either MD5 or 307 SHA-1. 309 In other words, to thwart a hash collision attack in a non- 310 repudiation protocol where a human is using a signed message as 311 authorization, the signer needs to keep a copy of the original 312 message they signed. Messages that have other messages with the same 313 hash must be created by the same person, and do not happen by 314 accident under any known probable circumstances. The fact that the 315 two messages have the same hash value should cause enough doubt in 316 the mind of the person judging the validity of the signature to cause 317 the legal attack to fail (and possibly bring intentional fraud 318 charges against the attacker). 320 Thwarting hash collision attacks in automated non-repudiation 321 protocols is potentially more difficult, because there may be no 322 humans paying enough attention to be able to argue about what should 323 have happened. For example, in electronic data interchange (EDI) 324 applications, actions are usually taken automatically after 325 authentication of a signed message. Determining the practical 326 effects of hash collisions would require a detailed evaluation of the 327 protocol. 329 5. Hash Collision Attacks and Digital Certificates from Trusted Third 330 Parties 332 Digital certificates are a special case of digital signatures. In 333 general, there is no non-repudiation attack on trusted third parties 334 due to the fact that certificates have specific formatting. Digital 335 certificates are often used in Internet protocols for key management 336 and for authenticating a party with whom you are communicating, 337 possibly before granting access to network services or trusting the 338 party with private data such as credit card information. 340 It is therefore important that the granting party can trust that the 341 certificate correctly identifies the person or system identified by 342 the certificate. If the attacker can get a certificate for two 343 different identities using just one public key, the victim can be 344 fooled into believing that one person is someone else. 346 The collision attack on PKIX certificates described in early 2005 347 relied on the ability of the attacker to create two different public 348 keys that would cause the body of the certificate to have the same 349 hash value. For this attack to work, the attacker needs to be able 350 to predict the contents and structure of the certificate before it is 351 issued, including the identity that will be used, the serial number 352 that will be included in the certificate, and the start and stop 353 dates of the validity period for the certificate. 355 One effective result of this attack is that one person using a single 356 identity can get a digital certificate over one public key, but be 357 able to pretend that it is over a different public key (but with the 358 same identity, valid dates, and so on). Because the identity in the 359 two certificates is the same, there are probably no real-world 360 examples where such an attack would get the attacker any advantage. 361 At best, someone could claim that the trusted third party made a 362 mistake by issuing a certificate with the same identity and serial 363 number based on two different public keys. This is indeed far- 364 fetched. 366 After the above attack was described, many CAs continued to use the 367 MD5 hash function. Because of this, a group of researchers went 368 further and showed how to create a rogue CA that would be accepted by 369 all the common web browsers at the time [Chosen-Prefix]. After that, 370 the CAs mostly (but not completely) stopped using the MD5 hash 371 function, and most browsers stopped accepting signatures that used 372 MD5. It should be noted that the same attack would work with SHA-1, 373 but it would take much more effort to mount such an attack. An 374 estimate for the actual amount of effort is described later in this 375 document. 377 It is very important to note that collision attacks only affect the 378 parts of certificates that have no human-readable information in 379 them, such as the public keys. An attack that involves getting a 380 certificate with one human-readable identity and making that 381 certificate useful for a second human-readable identity would require 382 more effort than a simple collision attack. 384 5.1. Reducing the Likelihood of Hash-based Attacks on PKIX Certificates 386 If a trusted third party who issues PKIX certificates wants to avoid 387 the attack described above, they should sign using a hash algorithm 388 for which collisions are believed to be essentially impossible, such 389 as those from the SHA-2 family. If they want to use weaker hashes 390 such as SHA-1, they can also prevent the attack by making other 391 signed parts of the certificate random enough to eliminate any 392 advantage gained by the attack. Ideas that have been suggested 393 include: 395 o making part of the certificate serial number unpredictable to the 396 attacker 398 o adding a randomly chosen component to the identity 400 o making the validity dates unpredictable to the attacker by skewing 401 each one forwards or backwards 403 Any of these mechanisms would increase the amount of work the 404 attacker needs to do to trick the issuer of the certificate into 405 generating a certificate that is susceptible to the attack. 407 6. Cost of Creating Collisions in SHA-1 409 At the time that this document has been prepared, a scheme for 410 creating collisions in SHA-1 has been widely discussed, but no 411 collision has been published. However, it is widely assumed that 412 such a collision is currently possible in non-public settings, and 413 that a public demonstration of a SHA-1 collision should be expected 414 within a few years. The current estimate is that creating a 415 collision will take approximately 2^60 operations [Stevens]. 417 The following is an estimate, originated by Jesse Walker, of how much 418 money and time it would take to create a SHA-1 hash collision in the 419 future. [Walker] It uses numbers based on hardware from the time 420 this document is published, and has a lot of room for error. 422 Using the eBACS benchmarks [eBACS], SHA-1 takes about 16 cycles per 423 byte for 64-byte blocks on modern processors. SHA-1 processes input 424 data by blocks of 64 bytes, so the cost of one block of a SHA-1 425 operation is 16 * 64, or 2^10 cycles. If an attack of 2^60 SHA-1 426 operations serves as the baseline, then finding a collision costs 427 about 2^10 * 2^60, or 2^70, cycles. 429 A CPU core today provides about 2^31 cycles per second. The state of 430 the art is 2^3 cores per processor, for a total of 2^3 * 2^31, or 431 2^34, cycles per second. A server typically has 4 processors, 432 increasing the total to 2^2 * 2^34, or 2^36, cycles per second. 433 Because there are about 2^25 seconds per year, a server can deliver 434 about 2^25 * 2^36, or 2^61, cycles per year, with the beginning of 435 2013 as a base. This is called a "server year" in this discussion. 437 For this discussion, we assume that Moore's law as currently applied 438 to server-level CPUs says that the speed will increase approximately 439 40% per year, or double ever two years, and this will continue for 440 the next decade. (Note that the authors do not have a good reference 441 for a respected estimate of applying Moore's law to current server- 442 level CPUs, and would appreciate one!). 444 This means that the processor power should double by 2015, double 445 again by 2017, and then double again by 2019. Thus, a commodity 446 "server year" should be about 448 2^1 * 2^61, or 2^62 cycles per year by 2015 449 2^2 * 2^61, or 2^63 cycles per year by 2017 450 2^4 * 2^61, or 2^65 cycles per year by 2019 451 2^8 * 2^61, or 2^69 cycles per year by 2021 453 With an attack that takes 2^69 iterations, the attack should cost 454 approximately 456 2^70 / 2^62, or 2^8 server years by 2015 457 2^70 / 2^63, or 2^7 server years by 2017 458 2^70 / 2^65, or 2^5 server years by 2019 459 2^70 / 2^69, or 2^1 server year by 2021 461 Today, Amazon rents compute time on commodity servers for about 462 US$0.04 per hour, or about US$350 per year. Assume that compute 463 rental fees remain fixed while server capacity keeps pace with 464 Moore's law. Then, because log2(350) is approximately 8.4, the cost 465 of the attack will be approximately 467 2^8 * 2^8.4, or about US$86K in 2015 468 2^7 * 2^8.4, or about US$43K in 2017 469 2^5 * 2^8.4, or about US$10K in 2019 470 2^1 * 2^8.4, or about US$700 in 2021 471 A collision attack is therefore well within the range of what an 472 organized crime syndicate can practically budget by 2015, and 473 essentially any criminal by 2021. 475 Since this argument only takes into account commodity server hardware 476 and not instruction set improvements (for example, ARM 8 specifies a 477 SHA-1 instruction), other commodity computing devices with even 478 greater processing power (particularly GPUs) and custom hardware, the 479 need to transition away from SHA-1 because of collision resistance 480 functions could be more urgent than this back-of-the-envelope 481 analysis suggests. 483 7. The SHA-3 Competition and the Future 485 After the events in 2005, NIST decided that it needed to have a 486 backup hash function in case the SHA-2 family had problems similar to 487 those found in MD5 and SHA-1. NIST held a competition 488 [SHA3-competition] to design a new family of hashes that was as 489 strong as the SHA-2 family but was based on different underlying 490 technologies. 492 The competition was both a success and a disappointment. It was a 493 success in that there were many different strong candidates for the 494 new family, and the competition caused a leap in understanding of the 495 weaknesses in many proposals for hash functions. It was a 496 disappointment in that none of the finalists were actually faster or 497 provably better than the SHA-2 family. 499 In late 2012, NIST announced that the winner of the competition was 500 the Keccak hash function [KECCAK-winner]. NIST was pleased about the 501 properties of KECCAK, noting that it was sufficiently different from 502 SHA-2 to have made the competition worthwhile. At the same time, 503 NIST emphasized that "SHA-2 has held up well and NIST considers SHA-2 504 to be secure and suitable for general use" and that KECCAK is "an 505 essential insurance policy in case SHA-2 is ever broken". 507 8. Future Attacks and Their Effects 508 The authors believe that everyone should start migrating to SHA-2 509 now, due to the weaknesses that have already been demonstrated in 510 both MD5 and SHA-1. There is an old saying inside the US National 511 Security Agency (NSA): "Attacks always get better; they never get 512 worse." The current collision attacks against MD5 are easily done on 513 a single computer; the collision attacks against SHA-1 are at the far 514 edge of feasibility today, but will only improve with time. It is 515 noted that at the time of this writing, there has still not been 516 shown a successful collision in SHA-1 in public; there has also not 517 been shown any problem with the descriptions of how such a collision 518 could probably be found. 520 It is preferable to migrate to the SHA-2 family of hashes before 521 there is a panic, instead of after. Just as we all migrated from 522 SHA-0 to SHA-1 based on some unknown vulnerability discovered inside 523 the NSA, we need to migrate from SHA-1 to SHA-256 based on these 524 attacks. SHA-256 has a 256-bit hash length. This length will give 525 us a much larger security margin in the event of newly discovered 526 attacks. 528 The authors acknowledge that deprecating a hash algorithm is 529 difficult from an operational standpoint, but it needs to be done 530 eventually, and this is a good time to again make a significant push 531 to SHA-2. When NIST finalizes the parameters and test vectors for 532 SHA-3, implementors might want to start adding SHA-3 to their 533 products. However, the authors do not believe that any push to start 534 using SHA-3 is warranted at any time soon. 536 The authors also feel that work should continue to make all Internet 537 protocols able to use different hash algorithms. Fortunately, most 538 protocols today already are capable of this; those that are not 539 really should be fixed soon. 541 9. Security Considerations 543 The entire document discusses security on the Internet. 545 The discussion in this document assumes that the only attacks on hash 546 algorithms used in Internet protocols are collision attacks. Some 547 significant preimaging attacks have already been discovered 548 [Preimaging-attack], but they are not yet practical. If a practical 549 preimaging attack is discovered, it would drastically affect many 550 Internet protocols. In this case, "practical" means that it could be 551 executed by an attacker in a meaningful amount of time for a 552 meaningful amount of money. 554 A preimaging attack that costs trillions of dollars and takes decades 555 to preimage one desired hash value or one message is not practical; 556 one that costs a few thousand dollars and takes a few weeks might be 557 very practical. Even a preimaging attack that costs millions of 558 dollars and takes over a year would be practical in high-value 559 environments such as issuance of certificates. 561 10. Informative References 563 [Chosen-Prefix] 564 , "Short Chosen-Prefix Collisions for MD5 and the Creation 565 of a Rogue CA Certificate", 2009, 566 . 568 [Flame-Microsoft] 569 , "TechNet Blogs: Flame malware collision attack 570 explained", June 2012, . 574 [KECCAK-winner] 575 , "NIST Selects Winner of Secure Hash Algorithm (SHA-3) 576 Competition", October 2012, 577 . 579 [MD5-attack] 580 X. Wang, , D. Feng, , X. Lai, , and H. Yu, "Collisions for 581 Hash Functions MD4, MD5, HAVAL-128 and RIPEMD", August 582 2004, . 584 [MD5-faster] 585 Vlastimil Klima, , "Finding MD5 Collisions - a Toy For a 586 Notebook", March 2005, 587 . 589 [PKIX-MD5-construction] 590 Arjen Lenstra, and Benne de Weger, "On the possibility of 591 constructing meaningful hash collisions for public keys", 592 February 2005, . 595 [Preimaging-attack] 596 John Kelsey, and Bruce Schneier, "Second Preimages on 597 n-bit Hash Functions for Much Less than 2^n Work", 598 November 2004, . 600 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 601 (SHA1)", RFC 3174, September 2001. 603 [RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo, "Internet 604 X.509 Public Key Infrastructure Certificate and 605 Certificate Revocation List (CRL) Profile", RFC 3280, 606 April 2002. 608 [RFC6234] Eastlake, D. and T. Hansen, "US Secure Hash Algorithms 609 (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 2011. 611 [SHA-1-attack] 612 Xiaoyun Wang, , Yiqun Lisa Yin, , and Hongbo Yu, 613 "Collision Search Attacks on SHA1", February 2005, 614 . 616 [SHA3-competition] 617 , "Cryptographic Hash Algorithm Competition", October 618 2012, 619 . 621 [Stevens] , "Cryptanalysis of MD5 and SHA-1", 2010, 622 . 624 [Walker] , "When Will We See Collisions for SHA-1?", 2012, . 628 [eBACS] Dan Bernstein, , "eBACS: ECRYPT Benchmarking of 629 Cryptographic Systems", 2012, 630 . 632 Appendix A. Acknowledgements 634 Acknowledgements from RFC 4270: The authors would like to thank the 635 IETF community, particularly those active on the SAAG mailing list, 636 for their input. We would also like to thank Eric Rescorla, Arjen 637 Lenstra, and Benne de Weger for material and significant comments on 638 the first draft of this document. 640 Jesse Walker contributed the analysis of the cost of creating SHA-1 641 collisions. [[ There will probably be more here. ]] 643 Authors' Addresses 645 Paul Hoffman 646 VPN Consortium 648 Email: paul.hoffman@vpnc.org 649 Bruce Schneier 650 Counterpane Internet Security 652 Email: schneier@counterpane.com