< draft-hoffman-hash-attacks-03.txt		draft-hoffman-hash-attacks-04.txt >
	Network Working Group P. Hoffman		Network Working Group P. Hoffman
	Internet-Draft VPN Consortium		Internet-Draft VPN Consortium
	Expires: November 10, 2005 B. Schneier		Expires: December 7, 2005 B. Schneier
	Counterpane Internet Security		Counterpane Internet Security
	May 9, 2005		June 5, 2005
	Attacks on Cryptographic Hashes in Internet Protocols		Attacks on Cryptographic Hashes in Internet Protocols
	draft-hoffman-hash-attacks-03.txt		draft-hoffman-hash-attacks-04.txt
	Status of this Memo		Status of this Memo
	By submitting this Internet-Draft, each author represents that any		By submitting this Internet-Draft, each author represents that any
	applicable patent or other IPR claims of which he or she is aware		applicable patent or other IPR claims of which he or she is aware
	have been or will be disclosed, and any of which he or she becomes		have been or will be disclosed, and any of which he or she becomes
	aware will be disclosed, in accordance with Section 6 of BCP 79.		aware will be disclosed, in accordance with Section 6 of BCP 79.
	Internet-Drafts are working documents of the Internet Engineering		Internet-Drafts are working documents of the Internet Engineering
	Task Force (IETF), its areas, and its working groups. Note that		Task Force (IETF), its areas, and its working groups. Note that
	skipping to change at page 1, line 35 ¶		skipping to change at page 1, line 35 ¶
	and may be updated, replaced, or obsoleted by other documents at any		and may be updated, replaced, or obsoleted by other documents at any
	time. It is inappropriate to use Internet-Drafts as reference		time. It is inappropriate to use Internet-Drafts as reference
	material or to cite them other than as "work in progress."		material or to cite them other than as "work in progress."
	The list of current Internet-Drafts can be accessed at		The list of current Internet-Drafts can be accessed at
	http://www.ietf.org/ietf/1id-abstracts.txt.		http://www.ietf.org/ietf/1id-abstracts.txt.
	The list of Internet-Draft Shadow Directories can be accessed at		The list of Internet-Draft Shadow Directories can be accessed at
	http://www.ietf.org/shadow.html.		http://www.ietf.org/shadow.html.
	This Internet-Draft will expire on November 10, 2005.		This Internet-Draft will expire on December 7, 2005.
	Copyright Notice		Copyright Notice
	Copyright (C) The Internet Society (2005).		Copyright (C) The Internet Society (2005).
	Abstract		Abstract
	Recent announcements of better-than-expected collision attacks in		Recent announcements of better-than-expected collision attacks in
	popular hash algorithms have caused some people to question whether		popular hash algorithms have caused some people to question whether
	common Internet protocols need to be changed, and if so, how. This		common Internet protocols need to be changed, and if so, how. This
	document summarizes the use of hashes in many protocols, discusses		document summarizes the use of hashes in many protocols, discusses
	how the collision attacks affect and do not affect the protocols,		how the collision attacks affect and do not affect the protocols,
	shows how to thwart known attacks on digital certificates, and		shows how to thwart known attacks on digital certificates, and
	discusses future directions for protocol designers.		discusses future directions for protocol designers.
	1. Introduction		1. Introduction
	In summer 2004, a team of researchers showed concrete evidence that		In summer 2004, a team of researchers showed concrete evidence that
	the MD5 hash algorithm was susceptible to collision attacks [MD5-		the MD5 hash algorithm was susceptible to collision attacks [MD5-
	attack]. In early 2005, the same team demonstrated a similar attack		attack]. In early 2005, the same team demonstrated a similar attack
	on a variant of the SHA-1 hash algorithm, with a prediction that the		on a variant of the SHA-1 [RFC3174] hash algorithm, with a prediction
	normally used SHA-1 would also be susceptible with a large amount of		that the normally used SHA-1 would also be susceptible with a large
	work (but at a level below what should be required if SHA-1 worked		amount of work (but at a level below what should be required if SHA-1
	properly) [SHA-1-attack]. Also in early 2005, researchers showed a		worked properly) [SHA-1-attack]. Also in early 2005, researchers
	specific construction of PKIX certificates [RFC3280] that use MD5 for		showed a specific construction of PKIX certificates [RFC3280] that
	signing [PKIX-MD5-construction], and another researcher showed a		use MD5 for signing [PKIX-MD5-construction], and another researcher
	faster method for finding MD5 collisions (eight hours on 1.6 GHz		showed a faster method for finding MD5 collisions (eight hours on 1.6
	computer) [MD5-faster].		GHz computer) [MD5-faster].
	Because of these announcements, there has been a great deal of		Because of these announcements, there has been a great deal of
	discussion by cryptography experts, protocol designers, and other		discussion by cryptography experts, protocol designers, and other
	concerned people about what, if anything, should be done based on the		concerned people about what, if anything, should be done based on the
	news. Unfortunately, some of these discussions have been based on		news. Unfortunately, some of these discussions have been based on
	erroneous interpretations of both the news and on how hash algorithms		erroneous interpretations of both the news and on how hash algorithms
	are used in common Internet protocols.		are used in common Internet protocols.
	Hash algorithms are used by cryptographers in a variety of security		Hash algorithms are used by cryptographers in a variety of security
	protocols, for a variety of purposes, at all levels of the Internet.		protocols, for a variety of purposes, at all levels of the Internet
	They are used because they have two security properties: to be one-		protocol stack. They are used because they have two security
	way and collision-free. (There is more about these properties in the		properties: to be one-way and collision-free. (There is more about
	next section; they're easier to explain in terms of breaking them.)		these properties in the next section; they're easier to explain in
	The recent attacks have demonstrated that one of those security		terms of breaking them.) The recent attacks have demonstrated that
	properties is not true. While it is certainly possible, and at a		one of those security properties is not true. While it is certainly
	first glance even probable, that the broken security property will		possible, and at a first glance even probable, that the broken
	not affect the overall security of many specific Internet protocols,		security property will not affect the overall security of many
	the conservative security approach is to change hash algorithms. The		specific Internet protocols, the conservative security approach is to
	Internet protocol community needs to migrate in an orderly manner		change hash algorithms. The Internet protocol community needs to
	away from SHA-1 and MD5 -- especially MD5 -- and toward more secure		migrate in an orderly manner away from SHA-1 and MD5 -- especially
	hash algorithms.		MD5 -- and toward more secure hash algorithms.
	This document summarizes what is currently known about hash		This document summarizes what is currently known about hash
	algorithms and the Internet protocols that use them. It also gives		algorithms and the Internet protocols that use them. It also gives
	advice on how to avoid the currently known problems with MD5 and		advice on how to avoid the currently known problems with MD5 and
	SHA-1, and what to consider if future predicted attacks become real.		SHA-1, and what to consider if predicted attacks become real.
	A high-level summary of the current situation is:		A high-level summary of the current situation is:
	o Both MD5 and SHA-1 have newly found attacks against them, the		o Both MD5 and SHA-1 have newly found attacks against them, the
	attacks against MD5 being much more severe than the attacks		attacks against MD5 being much more severe than the attacks
	against SHA-1.		against SHA-1.
	o The attacks against MD5 are practical on any modern computer.		o The attacks against MD5 are practical on any modern computer.
	o The attacks against SHA-1 are not feasible with today's computers,		o The attacks against SHA-1 are not feasible with today's computers,
	skipping to change at page 4, line 16 ¶		skipping to change at page 4, line 16 ¶
	message M1 to find another message M2 that has the same hash value		message M1 to find another message M2 that has the same hash value
	in fewer than 2^L attempts.		in fewer than 2^L attempts.
	The two preimage attacks are very similar. In a first-preimage		The two preimage attacks are very similar. In a first-preimage
	attack, you know a hash value but not the message that created it,		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		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		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		second message that has the same hash. Attacks that can find one
	type of preimage can often find the other as well.		type of preimage can often find the other as well.
	When analyzing a protocol's use of hash algorithms, it is important		analyzing the use of hash algorithms in protocols, it is important to
	to differentiate which of the two properties of hashes are important,		differentiate which of the two properties of hashes are important,
	particularly now that the collision-free property is becoming weaker		particularly now that the collision-free property is becoming weaker
	for currently popular hash algorithms. It is certainly important to		for currently popular hash algorithms. It is certainly important to
	determine whether one or both parties gets to determine what goes		determine which parties select the material being hashed. Further,
	into the material being hashed. Further, as shown by some of the		as shown by some of the early work, particularly [PKIX-MD5-
	early work, particularly [PKIX-MD5-construction], it is also		construction], it is also important to consider which party can
	important to consider which party can predict the material at the		predict the material at the beginning of the hashed object.
	beginning of the hashed object.
	2.1 Currently known attacks		2.1 Currently known attacks
	All the currently known practical or almost-practical attacks on MD5		All the currently known practical or almost-practical attacks on MD5
	and SHA-1 are collision attacks. This is fortunate: significant		and SHA-1 are collision attacks. This is fortunate: significant
	first- and second-preimage attacks on a hash algorithm would be much		first- and second-preimage attacks on a hash algorithm would be much
	more devastating in the real world than collision attacks, as		more devastating in the real world than collision attacks, as
	described later in this document.		described later in this document.
	It is also important to note that the current collision attacks		It is also important to note that the current collision attacks
	skipping to change at page 5, line 5 ¶		skipping to change at page 5, line 5 ¶
	Hash algorithms are used in many ways on the Internet. Most		Hash algorithms are used in many ways on the Internet. Most
	protocols that use hash algorithms do so in a way that makes them		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		immune to harm from collision attacks. This is not by accident: good
	protocol designers develop their protocols to withstand as many		protocol designers develop their protocols to withstand as many
	future changes in the underlying cryptography as possible, including		future changes in the underlying cryptography as possible, including
	attacks on the cryptographic algorithms themselves.		attacks on the cryptographic algorithms themselves.
	Uses for hash algorithms include:		Uses for hash algorithms include:
	o Non-repudiable digital signatures on messages. S/MIME and OpenPGP		o Non-repudiable digital signatures on messages. Non-repudiation is
	allow mail senders to sign the contents of a message they create,		a security service that provides protection against false denial
	and the recipient of that message can verify whether or not the		of involvement in a communication. S/MIME and OpenPGP allow mail
	signature is actually associated with the message. A message is		senders to sign the contents of a message they create, and the
	used for non-repudiation if the message is signed and the		recipient of that message can verify whether or not the signature
	recipient of the message can later use that in a legal proceeding		is actually associated with the message. A message is used for
	to prove that the signer indeed created the message.		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.		o Digital signatures in certificates from trusted third-parties.
	Although this is similar to "digital signatures on messages",		Although this is similar to "digital signatures on messages",
	certificates themselves are used in many other protocols for		certificates themselves are used in many other protocols for
	authenticating access.		authentication and key management.
	o Challenge-response protocols. These protocols combine a public		o Challenge-response protocols. These protocols combine a public
	large random number with a value to help hide the value when being		large random number with a value to help hide the value when being
	sent over unencrypted channels.		sent over unencrypted channels.
	o Message authentication with shared secrets. These are similar to		o Message authentication with shared secrets. These are similar to
	challenge-response protocols, except that instead of using public		challenge-response protocols, except that instead of using public
	values, the message is combined with a shared secret before		values, the message is combined with a shared secret before
	hashing.		hashing.
	skipping to change at page 6, line 42 ¶		skipping to change at page 6, line 47 ¶
	hash must be created by the same person, and do not happen by		hash must be created by the same person, and do not happen by
	accident under any known probable circumstances. The fact that the		accident under any known probable circumstances. The fact that the
	two messages have the same hash value should cause enough doubt in		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 mind of the person judging the validity of the signature to cause
	the legal attack to fail (and possibly bring intentional fraud		the legal attack to fail (and possibly bring intentional fraud
	charges against the attacker).		charges against the attacker).
	Thwarting hash collision attacks in automated non-repudiation		Thwarting hash collision attacks in automated non-repudiation
	protocols is potentially more difficult, because there may be no		protocols is potentially more difficult, because there may be no
	humans paying enough attention to be able to argue about what should		humans paying enough attention to be able to argue about what should
	have happened. Determining the practical effects of hash collisions		have happened. For example, in electronic data interchange (EDI)
	would require a detailed evaluation of the protocol.		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		5. Hash collision attacks and digital certificates from trusted third
	parties		parties
	Digital certificates are a special case of digital signatures. In		Digital certificates are a special case of digital signatures. In
	general, there is no non-repudiation attack on trusted third parties		general, there is no non-repudiation attack on trusted third parties
	due to the fact that certificates have specific formatting. Digital		due to the fact that certificates have specific formatting. Digital
	certificates are often used in Internet protocols for authenticating		certificates are often used in Internet protocols for key management
	a party with whom you are communicating, possibly before granting		and for authenticating a party with whom you are communicating,
	access to network services or trusting the party with private data		possibly before granting access to network services or trusting the
	such as credit card information.		party with private data such as credit card information.
	It is therefore important that the granting party can trust that the		It is therefore important that the granting party can trust that the
	certificate correctly identifies the person or system identified by		certificate correctly identifies the person or system identified by
	the certificate. If the attacker can get a certificate for two		the certificate. If the attacker can get a certificate for two
	different identities using just one public key, the victim can be		different identities using just one public key, the victim can be
	fooled into believing that one person is someone else.		fooled into believing that one person is someone else.
	The collision attack on PKIX certificates described in early 2005		The collision attack on PKIX certificates described in early 2005
	relied on the ability of the attacker to create two different public		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		keys that would cause the body of the certificate to have the same
	skipping to change at page 8, line 28 ¶		skipping to change at page 8, line 34 ¶
	now.		now.
	One of us (Bruce) believes that everyone should start migrating to		One of us (Bruce) believes that everyone should start migrating to
	SHA-256 [SHA-256] now, due to the weaknesses that have already been		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		demonstrated in both MD5 and SHA-1. There is an old saying inside
	the US National Security Agency (NSA): "Attacks always get better;		the US National Security Agency (NSA): "Attacks always get better;
	they never get worse." The current collision attacks against MD5 are		they never get worse." The current collision attacks against MD5 are
	easily done on a single computer; the collision attacks against SHA-1		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		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		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		there is a panic, instead of after. Just as we all migrated from
	to SHA-1 based on some unknown vulnerability discovered inside the		SHA-0 to SHA-1 based on some unknown vulnerability discovered inside
	NSA, we need to migrate from SHA-1 to SHA-256 based on these most		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		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		give us a much larger security margin in the event of newly
	discovered attacks. Meanwhile, further research inside the		discovered attacks. Meanwhile, further research inside the
	cryptographic community over the next several years should point to		cryptographic community over the next several years should point to
	further improvements in hash algorithm design, and potentially an		further improvements in hash algorithm design, and potentially an
	even more secure hash algorithm.		even more secure hash algorithm.
	The other of us (Paul) believes that this may not be wise for two		The other of us (Paul) believes that this may not be wise for two
	reasons. First, the collision attacks on current protocols have not		reasons. First, the collision attacks on current protocols have not
	been shown to have any discernible real-world effects. Further, it		been shown to have any discernible real-world effects. Further, it
	skipping to change at page 9, line 51 ¶		skipping to change at page 10, line 10 ¶
	Arjen Lenstra and Benne de Weger, "On the possibility of		Arjen Lenstra and Benne de Weger, "On the possibility of
	constructing meaningful hash collisions for public keys",		constructing meaningful hash collisions for public keys",
	February 2005, <http://www.win.tue.nl/~bdeweger/		February 2005, <http://www.win.tue.nl/~bdeweger/
	CollidingCertificates/ddl-final.pdf>.		CollidingCertificates/ddl-final.pdf>.
	[Preimaging-attack]		[Preimaging-attack]
	John Kelsey and Bruce Schneier, "Second Preimages on n-bit		John Kelsey and Bruce Schneier, "Second Preimages on n-bit
	Hash Functions for Much Less than 2^n Work",		Hash Functions for Much Less than 2^n Work",
	November 2004, <http://eprint.iacr.org/2004/304>.		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] R. Housley, R., W. Polk, W., W. Ford, W., and D. D. Solo,		[RFC3280] R. Housley, R., W. Polk, W., W. Ford, W., and D. D. Solo,
	"Internet X.509 Public Key Infrastructure Certificate and		"Internet X.509 Public Key Infrastructure Certificate and
	Certificate Revocation List (CRL) Profile", RFC 3280,		Certificate Revocation List (CRL) Profile", RFC 3280,
	April 2002.		April 2002.
	[SHA-1-attack]		[SHA-1-attack]
	Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, "Collision		Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu, "Collision
	Search Attacks on SHA1", February 2005,		Search Attacks on SHA1", February 2005,
	<http://theory.csail.mit.edu/~yiqun/shanote.pdf>.		<http://theory.csail.mit.edu/~yiqun/shanote.pdf>.
End of changes. 15 change blocks.
	49 lines changed or deleted		56 lines changed or added
This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/