Re: [saag] Deployment Deadlock

["Hallam-Baker, Phillip" <[e-mail]>]

That is another option. But the cost is that every cert now has to carry 512 bytes of extra baggage per algorithm. And this scheme is not so responsive as any change has a lead time of the lifetime of the longest certs - 2 or 3 years. That scheme works a lot better if you have ECC crypto available.

There are many ways that this can be addressed. But all of the ones I have thought of so far are somewhat yukky. That is why I wanted to focus on the fact that we have a problem before we jumped to solutions.


So far I do not see anyone giving a substantive argument that the deployment deadlock effect will not be a problem. I do see statements to the effect that this is a problem that some people would like not to have to think about or rule out of scope. And we go through these arguments every single time someone suggests even thinking about real world deployment constraints in a specification no matter how they are put.

We have the same problem in the DKIM spec. Take a look at how deployed verifiers will react when a zone contains a key for an algorithm that the verifier is unable to process. It is impossible for a verifier to react correctly in that situation without additional information. Publishing one unsupported key effectively negates the effect of the policy. So nobody can deploy new keys without a new policy language. But nobody in the group wants to think about that issue because it is the product of an interaction between policy and signature and the group wanted to keep them in two separate little boxes and hope they did not affect each other.


-----Original Message-----
From: [e-mail] [mailto:[e-mail]]
Sent: Tue 3/3/2009 7:57 AM
To: Hallam-Baker, Phillip
Cc: [e-mail]
Subject: RE: Deployment Deadlock
 
Phillip,
 
Would allowing a single certificate to be signed with multiple algorithms solve some of the problem?
 
Doing it in backwards-compatible way (=current browsers just use the SHA1 signature, and ignore the others) probably would involve violating some pristine ASN.1 style guidelines, though :-) (The "obvious" place to put the "other signatures" is a certificate extension, added after the "real" extensions.)
 
But would this significantly help solving the transition problem? (Perhaps something like this has been proposed before -- I haven't really thought about the potential pitfalls here.)
 
Best regards,
Pasi




________________________________

	From: [e-mail] [mailto:[e-mail]] On Behalf Of ext Hallam-Baker, Phillip
	Sent: 26 February, 2009 17:33
	To: Theodore Tso
	Cc: der Mouse; [e-mail]
	Subject: [saag] Deployment Deadlock
	
	
	Ted,
	 
	Thanks for the comments.
	 
	I agree that this is really hard, but I do not think that tragedy of the commons is a good analogy. This is not a resource depletion issue. This is more like a prisoner's dilema issue in which following their own best short term interests causes everyone to end up with a worst-case result. Unlike the Axelrod prisoner's dilema, the problem does not go away when the game is played repeatedly. On the contrary the deadlock becomes tighter.
	 
	The reason that this is our problem is that the standards establish the set of options available to the parties and the values of the outcomes.
	 
	The good part is that if we can understand this issue and work out a systematic theory of how to address it we have a key that can unlock the deployment of other protocols - IPv6, ubiquitous IPSec, ubiquitous email encryption and so on.
	 
	 
	We have encountered deployment deadlock in various forms in many different protocols. We have a lot of experience of deployment deadlock but no systematic theory. I think that we can develop an adequate theory for the purposes of protocol design by borrowing some ideas from the economists, in particular rational choice theory.
	 
	In rational choice theory we model the behavior of each party by *assuming* that they will follow their exclusive best interests. 
	 
	I emphasize the word assume here as it is merely a modelling assumption and not a factual claim or a normative ethic. I do not want to get into a distraction about whether the Rat Choice modelling assumption is a normative truth. We are merely using it here as a modelling assumption, we do not need to enter into a politcal digression. While it is very clear that some people act from altruistic motives on some occasions, and we could model this, it is necessary to assume an improbable degree of altruism to affect the outcome.
	 
	 
	What I did was to identify the parties:
	 
	1) Web browser providers
	2) Certificate Authorities
	3) Merchants
	 
	I am using merchants as a subset of certificate holders to simplify matters. While it may be argued that other certificate users will behave differently, the merchants are a large enough subset that their actions are sufficient to determine the behavior of the CAs.
	 
	Note that these parties are listed in a particular order. The IETF has the greatest ability to communicate with the Web browser providers, somewhat less contact with CAs and has negligible contact with the merchants. As a pragmatic matter it is much easier to change IETF specs than to mount an Al Gore publicity campaign telling folk to move to SHA-n. And in any case we have a very limited amount of jawboning bandwidth and we have to use that as a last resort. I would much rather have Vint Cerf jawboning carriers into support for IPv6.
	 
	From a business perspective, the actions are determined in the reverse order. The CAs are driven by the demands of their customers. If any CA attempts to behave altruistically by refusing to supply a product demanded by the merchants they will lose business. In practice the actions of the Web browser providers are driven by the facts on the ground in the same way.
	 
	The facts on the ground in question are
	 
	1) The amount of business that merchants receive from browsers that do not support SHA-n
	2) The number of merchants who deploy SHA-n certificates
	 
	We have some influence on the first factor but almost no influence on the second. At this point it is reasonably clear that the browser providers are either supporting SHA2 today or will do so in the very very near future. If not they risk public shame every time RSA and Crypto come round.
	 
	My problem is that based on my experience of the merchants, I cannot see any merchant voluntarily chosing a SHA-n certificate that provides only (100-x)% coverage while there is a SHA-1 certificate on offer that gives 100% for values of x greater than 2. No business is going to voluntarily sacrifice even 1% of sales for a security issue that only affects the credit card issuers.
	 
	And there is no way for the browser providers to withdraw support for SHA1 if 90% or more of merchants are using SHA1 certs. Not without proof-positive that an actual break has occured which by definition means that we are too late. And even then it will take several years for the SHA1 capable browsers to be withdrawn from service and those will still be vulnerable in the interim.
	 
	 
	That is a deployment deadlock.
	 
	 
________________________________

	From: Theodore Tso [mailto:[e-mail]]
	Sent: Thu 2/26/2009 9:38 AM
	To: Hallam-Baker, Phillip
	Cc: David Harrington; der Mouse; [e-mail]
	Subject: Re: [saag] SHA-1 to SHA-n transition
	
	

	On Wed, Feb 25, 2009 at 05:35:04PM -0800, Hallam-Baker, Phillip wrote:
	> 
	> If people really think that Amazon.com is going to say 'I know that
	> only 95% of browsers support SHA1, but I am going to get an SHA2
	> cert and lose that 5% of sales so that our transactions are as
	> secure as possible' because someone finds a practical attack on
	> SHA1, then let them say that. So far nobody has challenged the
	> analysis directly, they have merely described themselves as
	> unconvinced that there is a problem.
	> 
	
	OK, so let's get real here.  The reality is that transitioning between
	crypto algorithms is *hard*, and that the tragedy of the commons is
	hitting us hard.  We can try to create technical solutions (such as
	the Svengali-style suicide note which causes browsers to break
	intranets), but their have shortcomings because this is fundamentally
	a social problem.
	
	There are couple of things we need to do in order to successfully
	carry off a migration:
	
	(1) We need to get browsers to add support for the new crypto algorithm
	(2) We need to get users to upgrade to the new browsers with support
	        for the new crypto algorithm
	(3) Once (1) and (2) are done, we need to get secure commerce sites to
	        upgrade to use certificates that utilize the new crypto algorithm.
	        (In practice this will be the crypto checksum; but the same thing
	        applies if we ever need to get nervous about replacing the PK
	        algorithm.)
	
	This normally takes time --- years, but it is possible to speed things
	up.  For example, an interested body, perhaps funded by far-sighted
	merchants and other concerned citizens, could track which browsers
	have added the new algorithms, and jawbone (and perhaps in the later
	part of the effort, publically shame) entities distributing browsers
	to implement the new algorithm.
	
	For (2), sites who were interested in being "good citizens" could test
	to see if the browser supports the new crypto algorithm, and display a
	"nag screen" if the browser apparently doesn't support the new crypto
	algorithm.  Said nag message could be gentle at first, but could get
	increasingly strident; a lot of this would be up to the web site(s)
	involved, of course.
	
	So it's possible to encourage the ecosystem to move in a particular
	way, but it all requires effort and coordination, and the tragedy of
	the commons is that until the emergency comes up, it's unlikely that
	such an effort will get funding and support. 
	
	But again, this is all nothing new, and I suspect one of the reasons
	why we're thrashing a little in this discussion is because it really
	is much more of a social problem than a technical problem, which means
	it's a bit outside of the IETF's core competency.
	
	                                        - Ted