[saag] Deployment Deadlock

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

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