Re: [saag] SHA-1 to SHA-n transition

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

OK, traditionally, PKIX is based on a Kohnfelder style certificate architecture. At the time (1977) it was believed that it was impractical to run a directory of keys, or update keys frequently. The Internet such as it was ran at dial up speeds.
 
Since then a number of things have happened
 
1) The original monolithic PEM root was replaced with a heterachy.
2) CRLs became too big to be useful for large CAs.
3) Network connectivity became dependable and ubiquitous.
4) OCSP began to be used as the default revocation checking mechanism (vista).
 
What I think we need to do is to create an insurance policy that uses the OCSP token as a fallback certificate mechanism as follows:
 
1) Client software authors create a Rivest style 'suicide note' for the SHA1 algorithm (OK he did it just for certs, this is for algs, same idea).
1a) They chose a random number x which is appropriately sequestered.
1b) They generate the witness value W = SHA1(x) 
1c) Code in the browser recognizes a suicide note as being authentic if it contains a value x such that SHA1(x) = W
1d) If the suicide note is delivered the browser will henceforth not accept a certificate if the authentication chain is dependent on SHA1.
 
2) A legacy browser may still make use of a SHA1 authenticated certificate, provided that it can obtain an alternative certification route via an acceptable digest in the OCSP token.
2a) Client asks for an OCSP token signed with SHA2
2b) Server returns token signed with SHA2 and contains a digest of the original cert in SHA2
 
[Hold your horses on efficiency grumbles, OCSP stapling, short lived certs can be used]
[Oh and yes, do the same for all algorithms]
 
 
OK so that meets our security requirements, it allows a browser to be delivered today that works with existing SHA1 certificates right up until the moment that it is deemed no longer safe to use SHA1.
 
So for example, let us imagine that we deployed this scheme on the day that the SHA1 problems were first uncovered. At that point the population of Web browsers would be:
 
[The SHA2 browser supporting SHA1 via a suicide note scheme, ditto for SHAn so total is more than 100%]
 
SHA1: 100%
SHA2: 0%
SHAn: 0%
 
So if SHA1 was compromised then, every browser in creation would have to be upgraded which would be a party for the attackers since they are very good at exploiting chaos and in particular transition arrangements. Every time a bank merges they send out phishing attacks.
 
Now lets wind forward to maybe where we will be in a few years:
 
SHA1: 100%
SHA2: 50%
SHAn: 5%
 
At this point SHA1 is still deemed to be acceptably secure, there is a large population of SHA2 browsers. But any site that buys a SHA2 certs would automatically lose half their business and they are not going to do that. This is the problem with algorithm transitions.
 
Now lets wind forward to where I would hope we are when SHA1 starts to look really bad, let us imagine that we have a collision attack but not a first pre-image, lets also imagine that we have an acceptable amount of randomness to foil exploits:
 
SHA1: 30%
SHA2: 80%
SHAn: 20%
 
The suicide note has been delivered. We are worried anough about the security of SHA1 to require CAs to deliver SHA2 validated tokens. But even so there is a significant proportion of browsers using SHA1 and businesses want to continue to use.
 
At this point, there will of course be some people saying cut the old browsers lose, but that will create chaos that the criminals will exploit. Better to withdraw the old algorithm gradually. 
 
 
Now compare this withdrawal scheme with what happens if you try to do a hard cut-over. This time the decision is made by the browser provider and the significant quantity is the number of certificates in the population. In particular, remember that CAs will sell what their customers demand and their customers will demand certificates that work with the greatest number of browsers and no browser provider can cut over if the proportion of SHA1 certs is greater than 50%
 
So on day 1 the population of certs is:
 
SHA1: 100%
 
Therefore every browser must support SHA1 and every business will buy an SHA1 cert, so on day 2 the population of certs will be 
 
SHA1: 100%
 
Therefore every browser must support SHA1 and every business will buy an SHA1 cert, so on day n+1 the population of certs will be 
 
SHA1: 100%
 
The induction goes on forever. The only way to escape it is to create a bifurcated transition path so that new browsers can take advantage of better security without impacting the old.
 
 
On the efficiency issue, there are two possible fixes. The simplest is to deploy OCSP token stapling in SSL so that a browser gets a token and cert chain all in one go. 
 
Another possibility is to create short lived certs and provide a selection mechanism. This is more expensive in bits however as two complete cert chains are required.
 
 
So in conclusion, we can manage this transition, but only if we first abandon the foolish notion that people are going to do the right thing of their own accord. Even though every party in this system is aware of the right thing, none is able to do it because the business imperative is to keep the system running one more day.
 
Looking at the deployed infrastructure, the simplest fix to me is to use the OCSP path. Note that this does effectively turn PKIX into a key centric model PKI. The cert chains are then isomorphic to XKMS.
 
 
________________________________

From: [e-mail] [mailto:[e-mail]]
Sent: Tue 2/24/2009 6:48 AM
To: Hallam-Baker, Phillip; [e-mail]
Subject: RE: [saag] SHA-1 to SHA-n transition


Phillip,
 
Since you did suggest that adhering to "pristine principles of the
PKIX infrastructure" would get us in deep trouble, does that mean you
think relaxing/dropping some of those principles would allow us to
avoid some of the trouble?

Or in other words, what are you proposing? I'd certainly be interested
in hearing it, even if it's not totally in line with how we've done
things earlier...
 
Best regards,
Pasi


________________________________

	From: [e-mail] [mailto:[e-mail]] On Behalf Of ext Hallam-Baker, Phillip
	Sent: 23 February, 2009 21:14
	To: Stephen Kent; [e-mail]
	Subject: Re: [saag] SHA-1 to SHA-n transition
	
	
	Let us see, I suggest that we might need to slay a sacred PKIX cow or two in order to make the SHA-n transition work. Stephen: 
	 
	* Describes the suggestion as 'offensive'
	* Raises a non sequitor about certificate issue policy
	 
	I canot imagine why Stephen would imagine that a sensible response to a technical issue would be found in relaxing certificate issue policy criteria, or for that matter why I would be likely to be suggesting that. 
	 
	I did however anticipate that Stephen would find my proposal objectionable. But was somewhat surprised that he didn't wait to find out what it was before objecting.
	 
	 
	We have a problem here that requires us to work out a coherent transition plan for enabling browsers to make use of the stronger security of SHA2 and SHAn at the earliest possible date taking into account that we have a very small installed base of SHA2 capable clients and no spec for SHAn.
	 
	The problem is that you do not gain security from introducing stronger algorithms, you only gain security from withdrawing insecure algorithms from use. And for better or worse, there are real limits to what the Internet user base will tollerate for security.
	 
	So simply adding SHA2 support to existing browsers does not help us much unless we have a way to retrospectively shut off SHA1 support when it is no longer trustworthy. 
	 
	And even that does not help very much as there will be a large number of certificate customers who want to sell to people who can only use SHA1 capable browsers.
	 
	And then we have the problem that PKIX does not really have a strategy for algorithm transition. It has the ability to use multiple algorithms but not very much thought of how the transition from one to another takes place.
	 

________________________________

	From: [e-mail] on behalf of Stephen Kent
	Sent: Sat 2/21/2009 11:10 AM
	To: [e-mail]
	Subject: [saag] SHA-1 to SHA-n transition
	
	
	I agree wit Phil's suggestion that we begin work on this topic sooner rather than later.  Solutions probably will require coordination between folks in both PKIX and TLS, plus some browser experts from the APP area.

	However, Phil's comment (underling added by me)

	If we start addressing the problem now we can lay ourselves an insurance policy. If we try to insist on the pristine principles of the PKIX infrastructure we are going to be in deep trouble in about five years time.

	is offensive, at best. Moreover, unless Phil and his favorite browser vendors already have a solution in mind, and he anticipates that it will be objectionable to PKIX, this comment is gratuitous.

	Since we're talking about how well browsers implement PKI mechanisms in the context of SSL/TLS, it is worth noting a presentation at last week's Black Hat conference in D.C. The presentation provided details on how several browsers remain vulnerable to attacks because they fails to check the Basic Constraints extension. This oversight of one of those pristine principles of PKIX ( we can use the acronym P3 going forward) and allows a web sites to act as a CA, based o the EE cert issued to it by any of the trust anchors embedded in the browser.

	Another vulnerability, and matching MITM attack, is enabled by the issuance of certs that contain wildcard DNS names. This is not, a violation of P3, because PKIX caved to pressure from the TLS WG, to accommodate web site operators who wanted to purchase one cert from a TTP that could be used to verify the EE certs for multiple web sites. I argued against this, but lost. The phrase "I told you so" comes to mind :-).

	So, contrary to Phil's assertion that adherence to P3 will get us into deep trouble in five years (with regard to this transition issue), I believe that PKI shortcuts (hacks) in browsers have gotten us into deep trouble for many years, and are likely to persist.

	Steve