diff options
Diffstat (limited to 'doc/rfc/rfc4270.txt')
| -rw-r--r-- | doc/rfc/rfc4270.txt | 675 |
1 files changed, 675 insertions, 0 deletions
diff --git a/doc/rfc/rfc4270.txt b/doc/rfc/rfc4270.txt new file mode 100644 index 0000000..a3a381c --- /dev/null +++ b/doc/rfc/rfc4270.txt @@ -0,0 +1,675 @@ + + + + + + +Network Working Group P. Hoffman +Request for Comments: 4270 VPN Consortium +Category: Informational B. Schneier + Counterpane Internet Security + November 2005 + + + Attacks on Cryptographic Hashes in Internet Protocols + +Status of This Memo + + This memo provides information for the Internet community. It does + not specify an Internet standard of any kind. Distribution of this + memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (2005). + +Abstract + + Recent announcements of better-than-expected collision attacks in + popular hash algorithms have caused some people to question whether + common Internet protocols need to be changed, and if so, how. This + document summarizes the use of hashes in many protocols, discusses + how the collision attacks affect and do not affect the protocols, + shows how to thwart known attacks on digital certificates, and + discusses future directions for protocol designers. + +1. Introduction + + In summer 2004, a team of researchers showed concrete evidence that + the MD5 hash algorithm was susceptible to collision attacks + [MD5-attack]. In early 2005, the same team demonstrated a similar + attack on a variant of the SHA-1 [RFC3174] hash algorithm, with a + prediction that the normally used SHA-1 would also be susceptible + with a large amount of work (but at a level below what should be + required if SHA-1 worked properly) [SHA-1-attack]. Also in early + 2005, researchers showed a specific construction of PKIX certificates + [RFC3280] that use MD5 for signing [PKIX-MD5-construction], and + another researcher showed a faster method for finding MD5 collisions + (eight hours on a 1.6-GHz computer) [MD5-faster]. + + Because of these announcements, there has been a great deal of + discussion by cryptography experts, protocol designers, and other + concerned people about what, if anything, should be done based on the + + + + + +Hoffman & Schneier Informational [Page 1] + +RFC 4270 Attacks on Hashes November 2005 + + + news. Unfortunately, some of these discussions have been based on + erroneous interpretations of both the news and on how hash algorithms + are used in common Internet protocols. + + Hash algorithms are used by cryptographers in a variety of security + protocols, for a variety of purposes, at all levels of the Internet + protocol stack. They are used because they have two security + properties: to be one way and collision free. (There is more about + these properties in the next section; they're easier to explain in + terms of breaking them.) The recent attacks have demonstrated that + one of those security properties is not true. While it is certainly + possible, and at a first glance even probable, that the broken + security property will not affect the overall security of many + specific Internet protocols, the conservative security approach is to + change hash algorithms. The Internet protocol community needs to + migrate in an orderly manner away from SHA-1 and MD5 -- especially + MD5 -- and toward more secure hash algorithms. + + This document summarizes what is currently known about hash + algorithms and the Internet protocols that use them. It also gives + advice on how to avoid the currently known problems with MD5 and + SHA-1, and what to consider if predicted attacks become real. + + A high-level summary of the current situation is: + + o Both MD5 and SHA-1 have newly found attacks against them, the + attacks against MD5 being much more severe than the attacks + against SHA-1. + + o The attacks against MD5 are practical on any modern computer. + + o The attacks against SHA-1 are not feasible with today's computers, + but will be if the attacks are improved or Moore's Law continues + to make computing power cheaper. + + o Many common Internet protocols use hashes in ways that are + unaffected by these attacks. + + o Most of the affected protocols use digital signatures. + + o Better hash algorithms will reduce the susceptibility of these + attacks to an acceptable level for all users. + +2. Hash Algorithms and Attacks on Them + + A "perfect" hash algorithm has a few basic properties. The algorithm + converts a chunk of data (normally, a message) of any size into a + fixed-size result. The length of the result is called the "hash + + + +Hoffman & Schneier Informational [Page 2] + +RFC 4270 Attacks on Hashes November 2005 + + + length" and is often denoted as "L"; the result of applying the hash + algorithm on a particular chunk of data is called the "hash value" + for that data. Any two different messages of any size should have an + exceedingly small probability of having the same hash value, + regardless of how similar or different the messages are. + + This description leads to two mathematical results. Finding a pair + of messages M1 and M2 that have the same hash value takes 2^(L/2) + attempts. For any reasonable hash length, this is an impossible + problem to solve (collision free). Also, given a message M1, finding + any other message M2 that has the same hash value as M1 takes 2^L + attempts. This is an even harder problem to solve (one way). + + Note that this is the description of a perfect hash algorithm; if the + algorithm is less than perfect, an attacker can expend less than the + full amount of effort to find two messages with the same hash value. + + There are two categories of attacks. + + Attacks against the "collision-free" property: + + o A "collision attack" allows an attacker to find two messages M1 + and M2 that have the same hash value in fewer than 2^(L/2) + attempts. + + Attacks against the "one-way" property: + + o A "first-preimage attack" allows an attacker who knows a desired + hash value to find a message that results in that value in fewer + than 2^L attempts. + + o A "second-preimage attack" allows an attacker who has a desired + message M1 to find another message M2 that has the same hash value + in fewer than 2^L attempts. + + The two preimage attacks are very similar. In a first-preimage + attack, you know a hash value but not the message that created it, + and you want to discover any message with the known hash value; in + the second-preimage attack, you have a message and you want to find a + second message that has the same hash. Attacks that can find one + type of preimage can often find the other as well. + + When analyzing the use of hash algorithms in protocols, it is + important to differentiate which of the two properties of hashes are + important, particularly now that the collision-free property is + becoming weaker for currently popular hash algorithms. It is + certainly important to determine which parties select the material + being hashed. Further, as shown by some of the early work, + + + +Hoffman & Schneier Informational [Page 3] + +RFC 4270 Attacks on Hashes November 2005 + + + particularly [PKIX-MD5-construction], it is also important to + consider which party can predict the material at the beginning of the + hashed object. + +2.1. Currently Known Attacks + + All the currently known practical or almost-practical attacks on MD5 + and SHA-1 are collision attacks. This is fortunate: significant + first- and second-preimage attacks on a hash algorithm would be much + more devastating in the real world than collision attacks, as + described later in this document. + + It is also important to note that the current collision attacks + require at least one of the two messages to have a fair amount of + structure in the bits of the message. This means that finding two + messages that both have the same hash value *and* are useful in a + real-world attack is more difficult than just finding two messages + with the same hash value. + +3. How Internet Protocols Use Hash Algorithms + + Hash algorithms are used in many ways on the Internet. Most + protocols that use hash algorithms do so in a way that makes them + immune to harm from collision attacks. This is not by accident: good + protocol designers develop their protocols to withstand as many + future changes in the underlying cryptography as possible, including + attacks on the cryptographic algorithms themselves. + + Uses for hash algorithms include: + + o Non-repudiable digital signatures on messages. Non-repudiation is + a security service that provides protection against false denial + of involvement in a communication. S/MIME and OpenPGP allow mail + senders to sign the contents of a message they create, and the + recipient of that message can verify whether or not the signature + is actually associated with the message. A message is used for + non-repudiation if the message is signed and the recipient of the + message can later use the signature to prove that the signer + indeed created the message. + + o Digital signatures in certificates from trusted third parties. + Although this is similar to "digital signatures on messages", + certificates themselves are used in many other protocols for + authentication and key management. + + o Challenge-response protocols. These protocols combine a public + large random number with a value to help hide the value when being + sent over unencrypted channels. + + + +Hoffman & Schneier Informational [Page 4] + +RFC 4270 Attacks on Hashes November 2005 + + + o Message authentication with shared secrets. These are similar to + challenge-response protocols, except that instead of using public + values, the message is combined with a shared secret before + hashing. + + o Key derivation functions. These functions make repeated use of + hash algorithms to mix data into a random string for use in one or + more keys for a cryptographic protocol. + + o Mixing functions. These functions also make repeated use of hash + algorithms to mix data into random strings, for uses other than + cryptographic keys. + + o Integrity protection. It is common to compare a hash value that + is received out-of-band for a file with the hash value of the file + after it is received over an unsecured protocol such as FTP. + + Of the above methods, only the first two are affected by collision + attacks, and even then, only in limited circumstances. So far, it is + believed that, in general, challenge-response protocols are not + susceptible, because the sender is authenticating a secret already + stored by the recipient. In message authentication with shared + secrets, the fact that the secret is known to both parties is also + believed to prevent any sensible attack. All key derivation + functions in IETF protocols take random input from both parties, so + the attacker has no way of structuring the hashed message. + +4. Hash Collision Attacks and Non-Repudiation of Digital Signatures + + The basic idea behind the collision attack on a hash algorithm used + in a digital-signature protocol is that the attacker creates two + messages that have the same hash value, causes one of them to be + signed, and then uses that signature over the other message for some + nefarious purpose. The specifics of the attack depend on the + protocol being used and what the victim does when presented with the + signed message. + + The canonical example is where you create two messages, one of which + says "I will pay $10 for doing this job" and the other of which says + "I will pay $10,000 for doing this job". You present the first + message to the victim, get them to sign it, do the job, substitute + the second message in the signed authorization, present the altered + signed message (whose signature still verifies), and demand the + higher amount of money. If the victim refuses, you take them to + court and show the second signed message. + + + + + + +Hoffman & Schneier Informational [Page 5] + +RFC 4270 Attacks on Hashes November 2005 + + + Most non-repudiation attacks rely on a human assessing the validity + of the purportedly signed message. In the case of the hash-collision + attack, the purportedly signed message's signature is valid, but so + is the signature on the original message. The victim can produce the + original message, show that he/she signed it, and show that the two + hash values are identical. The chance of this happening by accident + is one in 2^L, which is infinitesimally small for either MD5 or + SHA-1. + + In other words, to thwart a hash collision attack in a non- + repudiation protocol where a human is using a signed message as + authorization, the signer needs to keep a copy of the original + message he/she signed. Messages that have other messages with the + same hash must be created by the same person, and do not happen by + accident under any known probable circumstances. The fact that the + two messages have the same hash value should cause enough doubt in + the mind of the person judging the validity of the signature to cause + the legal attack to fail (and possibly bring intentional fraud + charges against the attacker). + + Thwarting hash collision attacks in automated non-repudiation + protocols is potentially more difficult, because there may be no + humans paying enough attention to be able to argue about what should + have happened. For example, in electronic data interchange (EDI) + applications, actions are usually taken automatically after + authentication of a signed message. Determining the practical + effects of hash collisions would require a detailed evaluation of the + protocol. + +5. Hash Collision Attacks and Digital Certificates from Trusted Third + Parties + + Digital certificates are a special case of digital signatures. In + general, there is no non-repudiation attack on trusted third parties + due to the fact that certificates have specific formatting. Digital + certificates are often used in Internet protocols for key management + and for authenticating a party with whom you are communicating, + possibly before granting access to network services or trusting the + party with private data such as credit card information. + + It is therefore important that the granting party can trust that the + certificate correctly identifies the person or system identified by + the certificate. If the attacker can get a certificate for two + different identities using just one public key, the victim can be + fooled into believing that one person is someone else. + + + + + + +Hoffman & Schneier Informational [Page 6] + +RFC 4270 Attacks on Hashes November 2005 + + + The collision attack on PKIX certificates described in early 2005 + relied on the ability of the attacker to create two different public + keys that would cause the body of the certificate to have the same + hash value. For this attack to work, the attacker needs to be able + to predict the contents and structure of the certificate before it is + issued, including the identity that will be used, the serial number + that will be included in the certificate, and the start and stop + dates of the validity period for the certificate. + + The effective result of this attack is that one person using a single + identity can get a digital certificate over one public key, but be + able to pretend that it is over a different public key (but with the + same identity, valid dates, and so on). Because the identity in the + two certificates is the same, there are probably no real-world + examples where such an attack would get the attacker any advantage. + At best, someone could claim that the trusted third party made a + mistake by issuing a certificate with the same identity and serial + number based on two different public keys. This is indeed + far-fetched. + + It is very important to note that collision attacks only affect the + parts of certificates that have no human-readable information in + them, such as the public keys. An attack that involves getting a + certificate with one human-readable identity and making that + certificate useful for a second human-readable identity would require + more effort than a simple collision attack. + +5.1. Reducing the Likelihood of Hash-Based Attacks on PKIX Certificates + + If a trusted third party who issues PKIX certificates wants to avoid + the attack described above, they can prevent the attack by making + other signed parts of the certificate random enough to eliminate any + advantage gained by the attack. Ideas that have been suggested + include: + + o making part of the certificate serial number unpredictable to the + attacker + + o adding a randomly chosen component to the identity + + o making the validity dates unpredictable to the attacker by skewing + each one forwards or backwards + + Any of these mechanisms would increase the amount of work the + attacker needs to do to trick the issuer of the certificate into + generating a certificate that is susceptible to the attack. + + + + + +Hoffman & Schneier Informational [Page 7] + +RFC 4270 Attacks on Hashes November 2005 + + +6. Future Attacks and Their Effects + + There is a disagreement in the security community about what to do + now. Even the two authors of this document disagree on what to do + now. + + One of us (Bruce) believes that everyone should start migrating to + SHA-256 [SHA-256] now, due to the weaknesses that have already been + demonstrated in both MD5 and SHA-1. There is an old saying inside + the US National Security Agency (NSA): "Attacks always get better; + they never get worse." The current collision attacks against MD5 are + easily done on a single computer; the collision attacks against SHA-1 + are at the far edge of feasibility today, but will only improve with + time. It is preferable to migrate to the new hash standard before + there is a panic, instead of after. Just as we all migrated from + SHA-0 to SHA-1 based on some unknown vulnerability discovered inside + the NSA, we need to migrate from SHA-1 to SHA-256 based on these most + recent attacks. SHA-256 has a 256-bit hash length. This length will + give us a much larger security margin in the event of newly + discovered attacks. Meanwhile, further research inside the + cryptographic community over the next several years should point to + further improvements in hash algorithm design, and potentially an + even more secure hash algorithm. + + The other of us (Paul) believes that this may not be wise for two + reasons. First, the collision attacks on current protocols have not + been shown to have any discernible real-world effects. Further, it + is not yet clear which stronger hash algorithm will be a good choice + for the long term. Moving from one algorithm to another leads to + inevitable lack of interoperability and confusion for typical crypto + users. (Of course, if any practical attacks are formulated before + there is community consensus of the properties of the cipher-based + hash algorithms, Paul would change his opinion to "move to SHA-256 + now".) + + Both authors agree that work should be done to make all Internet + protocols able to use different hash algorithms with longer hash + values. Fortunately, most protocols today already are capable of + this; those that are not should be fixed soon. + + The authors of this document feel similarly for new protocols being + developed: Bruce thinks they should start using SHA-256 from the + start, and Paul thinks that they should use SHA-1 as long as the new + protocols are not susceptible to collision attacks. Any new protocol + must have the ability to change all of its cryptographic algorithms, + not just its hash algorithm. + + + + + +Hoffman & Schneier Informational [Page 8] + +RFC 4270 Attacks on Hashes November 2005 + + +7. Security Considerations + + The entire document discusses security on the Internet. + + The discussion in this document assumes that the only attacks on hash + algorithms used in Internet protocols are collision attacks. Some + significant preimaging attacks have already been discovered + [Preimaging-attack], but they are not yet practical. If a practical + preimaging attack is discovered, it would drastically affect many + Internet protocols. In this case, "practical" means that it could be + executed by an attacker in a meaningful amount of time for a + meaningful amount of money. A preimaging attack that costs trillions + of dollars and takes decades to preimage one desired hash value or + one message is not practical; one that costs a few thousand dollars + and takes a few weeks might be very practical. + +8. Informative References + + [MD5-attack] X. Wang, D. Feng, X. Lai, and H. Yu, + "Collisions for Hash Functions MD4, MD5, + HAVAL-128 and RIPEMD", August 2004, + <http://eprint.iacr.org/2004/199>. + + [MD5-faster] Vlastimil Klima, "Finding MD5 Collisions - a + Toy For a Notebook", March 2005, + <http://cryptography.hyperlink.cz/ + md5/MD5_collisions.pdf>. + + [PKIX-MD5-construction] Arjen Lenstra and Benne de Weger, "On the + possibility of constructing meaningful hash + collisions for public keys", February 2005, + <http://www.win.tue.nl/~bdeweger/ + CollidingCertificates/ddl-final.pdf>. + + [Preimaging-attack] John Kelsey and Bruce Schneier, "Second + Preimages on n-bit Hash Functions for Much + Less than 2^n Work", November 2004, + <http://eprint.iacr.org/2004/304>. + + [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash + Algorithm 1 (SHA1)", RFC 3174, + September 2001. + + [RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo, + "Internet X.509 Public Key Infrastructure + Certificate and Certificate Revocation List + (CRL) Profile", RFC 3280, April 2002. + + + + +Hoffman & Schneier Informational [Page 9] + +RFC 4270 Attacks on Hashes November 2005 + + + [SHA-1-attack] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, + "Collision Search Attacks on SHA1", + February 2005, + <http://theory.csail.mit.edu/~yiqun/shanote.pdf>. + + [SHA-256] NIST, "Federal Information Processing + Standards Publication (FIPS PUB) 180-2, + Secure Hash Standard", August 2002. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Hoffman & Schneier Informational [Page 10] + +RFC 4270 Attacks on Hashes November 2005 + + +Appendix A. Acknowledgements + + The authors would like to thank the IETF community, particularly + those active on the SAAG mailing list, for their input. We would + also like to thank Eric Rescorla for early material that went into + the first version, and Arjen Lenstra and Benne de Weger for + significant comments on the first version of this document. + +Authors' Addresses + + Paul Hoffman + VPN Consortium + + EMail: paul.hoffman@vpnc.org + + + Bruce Schneier + Counterpane Internet Security + + EMail: schneier@counterpane.com + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Hoffman & Schneier Informational [Page 11] + +RFC 4270 Attacks on Hashes November 2005 + + +Full Copyright Statement + + Copyright (C) The Internet Society (2005). + + This document is subject to the rights, licenses and restrictions + contained in BCP 78, and except as set forth therein, the authors + retain all their rights. + + This document and the information contained herein are provided on an + "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS + OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET + ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, + INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE + INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED + WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Intellectual Property + + The IETF takes no position regarding the validity or scope of any + Intellectual Property Rights or other rights that might be claimed to + pertain to the implementation or use of the technology described in + this document or the extent to which any license under such rights + might or might not be available; nor does it represent that it has + made any independent effort to identify any such rights. Information + on the procedures with respect to rights in RFC documents can be + found in BCP 78 and BCP 79. + + Copies of IPR disclosures made to the IETF Secretariat and any + assurances of licenses to be made available, or the result of an + attempt made to obtain a general license or permission for the use of + such proprietary rights by implementers or users of this + specification can be obtained from the IETF on-line IPR repository at + http://www.ietf.org/ipr. + + The IETF invites any interested party to bring to its attention any + copyrights, patents or patent applications, or other proprietary + rights that may cover technology that may be required to implement + this standard. Please address the information to the IETF at ietf- + ipr@ietf.org. + +Acknowledgement + + Funding for the RFC Editor function is currently provided by the + Internet Society. + + + + + + + +Hoffman & Schneier Informational [Page 12] + |