Subject: [pkix] CA T&A proofs as cert extensions. WAS: fyi: Sovereign Keys

From: "Hill, Brad" <[email-masked]>
Date: Mon, 19 Dec 2011 15:28:57 -0700

Rob and others,

  Catching up on this list, I see you've also thought of an idea I'd sent an email to Ben and Adam about privately on the 12th, and have been refining in consultation with some other folks: including the CA Transparency and Auditability proof as an extension in the issued certificate.

Since it's clear it's not a completely unobvious idea, I'll share what I've got so far here to get it out in public and hopefully further the discussion.  (though it may be premature to get into details at this level) Given the evidence of the uptake rate of renegotiation fixes, TLS 1.1 intolerance and plain ordinary misconfiguration, I think that any scheme that relies on server operators making configuration changes isn't going to be hard-fail before I retire.  I think there are natural incentives for CAs to participate in a scheme like this and if they do it makes full deployment look possible.
-------------------

Before beginning this protocol, the CA generates a key pair and leaf certificate (Basic Constraints CA=false) intended specifically for use in this protocol.  The purpose of this new certificate is to allow the CA to authenticate itself to the log without adding additional attack surface from this protocol to the standard issuing certificate private key. The new certificate ("CAProtoCert Signing Certificate") should have an Enhanced Key Usage (EKU) extension ("CAProtoCert Signing") indicating it is intended for use specifically with this protocol.  The CAProtoCert Signing Certificate must be signed by the same issuing certificate used to sign the certificate intended to be registered in the log. (i.e. the Authority field in the CAProtoCert Signing Cert MUST match that of any CAProtoCert it signs.)

1)	A Relying Party submits CSR to CA, authenticated per standard practice today.
2)	CA formulates the entire X.509v3 TBSCertificate structure that would result from issuance, but does not sign it. 
3)	The CA formulates the "CAProtoCert" by doing the following to the  TBSCertificate:
	a)	Add critical extension to "poison" the TBSCertificate. (described below) 
	b)	The CA signs the CAProtoCert with its CAProtoCert Signing Certificate.
4)	CA sends to the Public Log:
	a)	A certificate chain.  The first certificate in the chain MUST be the CA's CAProtoCert Signing Certificate, the next certificate MUST be the issuing certificate for the CAProtoCert Signing Certificate, which MUST also be the issuing certificate identified by the CAProtoCert's Authority and Authority Key Indicator extensions, and the chain must terminate at a well-known public trust root.
5)	Public Log verifies the CAProtoCert
	a)	The CAProtoCert signing cert, issuing CA certificate and chain is valid according to standard PKIX rules.
	b)	A certificate which would result from the Authority certificate signing the CAProtoCert is valid according to standard PKIX rules.
	c)	The issuing certificate matches exactly the Authority indicated in the CAProtoCert.
	d)	The signature of the CAProtoCert validates with the key of the CAProtoCert Signing Certificate.
6)	If 5 succeeds, the Public Log adds the CAProtoCert to the log/tree.
7)	Public Log calculates Merkle proof for new cert.
8)	Public Log sends Merkle proof back to CA.
9)	CA verifies Merkle proof.
10)	CA replaces the "poison" extension with an extension containing the actual value of the Merkle proof.
11)	The CA adds a new extension containing the signature over the CAProtoCert with the CAProtoCert Signing Certificate.
12)	CA signs the certificate with its standard issuing certificate.  (including over the Merkle proof extension and original CAProtoCert Signature extension) This signature replaces the existing signature block with the CAProtoCert Signing Certificate's signature.
13)	CA gives certificate to RP.
14)	[At browser TLS connection time] Browser gets certificate from RP.
15)	Browser verifies certificate according to standard PKIX rules.
16)	Browser is CT aware and finds Merkle proof in an X.509v3 cert extension.
17)	Browser re-creates the CAProtoCert by:
	a)	Replacing the Merkle proof with the "poison" extension
	b)	Removing the CAProtoCert Signing Cert signature extension and replacing the signature block with the values from this extension.
18)	The browser validates the Merkle proof over the CAProtoCert.

"Poison" Extension:  This is simply an extension marked as "critical" which it is intended that browsers and other TLS client libraries never support.  The presence of the unrecognized critical extension should cause all clients to fail to validate any CAProtoCert should it be presented outside the context of the log.   

Acknowledgments:

Thanks to Jeff Hodges, Ben Laurie, Nico Williams and Marsh Ray for their feedback and contributions to this proposal. 

----------
Though obviously under NOTE WELL on this list, additionally:

This is licensed under a Creative Commons Attribution 3.0 United States License.
http://creativecommons.org/licenses/by/3.0/us/ 

THIS SPECIFICATION IS PROVIDED "AS IS." PayPal, Inc., Brad Hill, et al MAKE NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, TITLE OR NON-INFRINGEMENT.

Brad Hill
Sr. MTS, Internet Standards and Governance PayPal Information Risk Management
cell: 206.245.7844 / skype: hillbrad
email: [email-masked]

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Rob Stradling
> Sent: Wednesday, December 14, 2011 4:21 AM
> To: Adam Langley
> Cc: [email-masked]
> Subject: Re: [pkix] fyi: Sovereign Keys: an EFF proposal for more secure TLS
> authentication
> 
> On Tuesday 13 Dec 2011 16:05:52 Adam Langley wrote:
> > On Tue, Dec 13, 2011 at 4:56 AM, Rob Stradling
> > <[email-masked]>
> wrote:
> > > If "requiring OCSP stapling from all sites" cannot reasonably be
> > > deployed, then surely we cannot expect ubiquitous support for _any_
> > > new TLS extension?
> >
> > I agree. In additional to the requirement to support a TLS extension,
> > OCSP stapling requires constant, fresh data making it even harder.
> 
> Fair point.  CT Audit Proofs don't have this "even harder" requirement, of
> course, since they will be static data.
> 
> <snip>
> > > So when you say that "most existing verification code will ignore
> > > it", you are correct.  However, I concluded that "most" was not good
> enough.
> >
> > Yep, if we can't wedge the extra data in anywhere then we're in
> > trouble. But the sooner that we start working on making it possible,
> > the better things will be.
> 
> I've thought of a couple of other ways of wedging the data into the TLS
> handshake, although these methods would require more collaboration from
> the CAs than you've thus far intended to require (or perhaps expected).
> 
> IDEA 1 - PUT THE AUDIT PROOF INSIDE THE END-ENTITY CERTIFICATE:
> When a CA is about to issue a certificate, it publishes the "ToBeSigned"
> certificate data to the Public Log.  The Public Log generates an Audit Proof of
> the "ToBeSigned" data and returns this to the CA.  The CA encapsulates the
> Audit Proof in a certificate extension, appends this extension to the
> "ToBeSigned" certificate data, and recalculates ASN.1 tag lengths as
> necessary.
> Then the CA signs the certificate and provides it to the certificate applicant.
> Browsers would recognize the Audit Proof certificate extension and would
> have code to strip this extension and reconstruct the original "ToBeSigned"
> certificate data, so that the Audit Proof can be verified.
> Since the Public Log is involved prior to certificate issuance, the Public Log
> could conceivably check CAA records, the Google Safebrowsing blacklist, etc,
> etc, and refuse to generate an Audit Proof if any problems are encountered.
> 
> IDEA 2 - CERTIFICATE INSIDE A CERTIFICATE:
> A certificate is issued and added to the Public Log in the manner your doc
> describes.  Then, the CA issues a second certificate, which contains (in a
> certificate extension) the Audit Proof and the first certificate's signature and
> serial number.  The second certificate's Subject, Issuer, Validity Dates,
> Extensions, etc, must exactly match those of the first certificate.
> The site owner configures their TLS Server to send the second certificate.
> Browsers would recognize the new certificate extension and would have
> code to pull apart the second certificate, reconstruct the first certificate, and
> verify the Audit Proof.
> Since the first certificate would never be seen by legacy Browsers, its
> signature could use SHA-2.  The second certificate's signature would probably
> use SHA-1 whilst there remain a significant number of legacy Browsers that
> don't support SHA-2.
> Certificate serial numbers are meant to be unique amongst the set of
> certificates issued by any particular CA, but maybe it would be OK to break
> this rule for each pair of certificates envisaged by this idea, since they are
> essentially the same.  If revocation is required, both certificates should be
> revoked together, so sharing a serial number would make sure this happens.
> 
> Comments welcome.
> 
> > This is not something that we expect to be done next year, it's going
> > to take many years to deploy.
> 
> If at least one my ideas would work, I think it could be deployed more quickly
> than that.  You'd only need buy-in from the CAs and Browsers.  No need to
> update any webserver software, and no need for site admins to do anything
> any differently.
> 
> > Cheers
> >
> > AGL
> 
> Rob Stradling
> Senior Research & Development Scientist
> COMODO - Creating Trust Online
> _______________________________________________
> pkix mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/pkix

---

From: Rob Stradling <[email-masked]>
Date: Tue, 20 Dec 2011 10:49:40 +0000

On Monday 19 Dec 2011 22:28:57 Hill, Brad wrote:
> Rob and others,
> 
>   Catching up on this list, I see you've also thought of an idea I'd sent
> an email to Ben and Adam about privately on the 12th, and have been
> refining in consultation with some other folks: including the CA
> Transparency and Auditability proof as an extension in the issued
> certificate.
> 
> Since it's clear it's not a completely unobvious idea, I'll share what I've
> got so far here to get it out in public and hopefully further the
> discussion.  (though it may be premature to get into details at this
> level) Given the evidence of the uptake rate of renegotiation fixes, TLS
> 1.1 intolerance and plain ordinary misconfiguration, I think that any
> scheme that relies on server operators making configuration changes isn't
> going to be hard-fail before I retire.  I think there are natural
> incentives for CAs to participate in a scheme like this and if they do it
> makes full deployment look possible. -------------------
> 
> Before beginning this protocol, the CA generates a key pair and leaf
> certificate (Basic Constraints CA=false) intended specifically for use in
> this protocol.  The purpose of this new certificate is to allow the CA to
> authenticate itself to the log without adding additional attack surface
> from this protocol to the standard issuing certificate private key.

Hi Brad.  Have you thought of any particular attacks that this would defend 
against?

Since this would give the CAs (especially those who operate lots of 
intermediate CA certs) extra work to do, I'd like to know why it would be 
necessary.

In my similar proposal, I envisaged the two certificates being signed by the 
same Issuer: the "outer" certificate would typically have an RSA/SHA-1 
signature (for maximum compatibility), but the "inner" certificate's signature 
could use a stronger hash algorithm.  CT-aware clients would verify the 
"inner" signature with the stronger hash; legacy clients would verify the 
"outer" signature with the SHA-1 hash.
To achieve this same thing with your proposal, the client would need to obtain 
the CAProtoCert Signing Certificate from somewhere.  To avoid side-channels, it 
would need to be embedded in the "outer" certificate, but this would 
approximately double the size of the cert.

<snip>
> 6)      If 5 succeeds, the Public Log adds the CAProtoCert to the log/tree.

Adam,

A few months ago you proposed solving the problems with revocation checking by 
having CAs issue certificates that are valid for only a few days (and so don't 
really need to be subjected to revocation checking).  This would probably 
result in lots and lots of certificates with the same 
Issuer/Subject/Key/Extensions, differing only in their Serial Numbers, Validity 
Dates and Signatures.

If short-duration certs and CT both happen, the CT Public Log would end up 
containing lots and lots of duplicated certificate fields.

So I'm wondering...
Instead of tying each CT log entry / Merkle proof to an individual certificate, 
would it be possible to instead tie each CT log entry / Merkle proof to some 
sort of data structure that contains just the Issuer/Subject/Key/Extensions?

This would mean that the purpose of a CA contacting a Public Log would be to 
announce that CA's intention to issue 1 or more certificates containing the 
specified Issuer/Subject/Key/Extensions.

The same Merkle proof could then be embedded into each certificate that 
contains that exact combination of Issuer/Subject/Key/Extensions.

Rob Stradling

---

From: Tom Gindin <[email-masked]>
Date: Tue, 20 Dec 2011 08:28:51 -0500

I would like to present a counterproposal, which is much closer to 
our current model.  I call it "renewal endorsement", and would implement 
it through two non-critical X.509 extensions.  The first and simpler 
extension would be called "Renewal endorsement expected", and would go 
into the older certificate.  It would contain an optional public key, or 
perhaps a SEQUENCE of them.  It would be conveyed as part of a PKCS#10 in 
the usual way and copied into the certificate by the CA.   The second 
extension would be a CMS SignedData called "Renewal endorsement" going 
into the new certificate, containing the issuer name and the new public 
key signed by the public key from the "Renewal endorsement expected" 
extension or the public key in the older certificate if the extension was 
absent or didn't contain a public key.  It would be created using the old 
key, and included in the PKCS#10 in the usual way, then copied into the 
certificate by the CA. 
        If the original certificate contains the "Renewal endorsement 
expected" extension, and the received one does not contain the "Renewal 
endorsement", the UI should put up a screen with a statement such as "This 
certificate was issued to a site which is unusually likely to have been 
compromised.  The site you reached last time stated that its policy was to 
use key rollover, and this new certificate did not do so."  The screen 
should then include "The site claims to be www.x at IP1, and its issuer is 
Y.  On your last visit to it that same name was issued by Z at IP2". 
Similarly, if the signature does not verify against an expected key (NOT 
against the certificate), the UI should put up a similar error, with the 
second sentence "The endorsement on this site was signed by a key which 
wasn't in the last certificate".  A wild card name match without 
endorsement should put up a similar message.
        This would not make the users' keys sovereign, but at least they 
would have some influence on their successors independent of the global 
set of CA's.  The advantages of the centralized PKI for introduction would 
remain, but a user who has previously visited a site would detect the use 
of a compromised CA or RA to issue a certificate to an attacker.

Tom Gindin

P.S.    The suggestion above is mine, and not necessarily that of my 
employer.

From:   "Hill, Brad" <[email-masked]>
To:     Rob Stradling <[email-masked]>, Adam Langley 
<[email-masked]>, "[email-masked]" <[email-masked]>, 
Date:   12/19/2011 05:29 PM
Subject:        [pkix] CA T&A proofs as cert extensions. WAS: fyi: 
Sovereign Keys
Sent by:        [email-masked]

Rob and others,

Since it's clear it's not a completely unobvious idea, I'll share what 
I've got so far here to get it out in public and hopefully further the 
discussion.  (though it may be premature to get into details at this 
level) Given the evidence of the uptake rate of renegotiation fixes, TLS 
1.1 intolerance and plain ordinary misconfiguration, I think that any 
scheme that relies on server operators making configuration changes isn't 
going to be hard-fail before I retire.  I think there are natural 
incentives for CAs to participate in a scheme like this and if they do it 
makes full deployment look possible.
-------------------

Before beginning this protocol, the CA generates a key pair and leaf 
certificate (Basic Constraints CA=false) intended specifically for use in 
this protocol.  The purpose of this new certificate is to allow the CA to 
authenticate itself to the log without adding additional attack surface 
from this protocol to the standard issuing certificate private key. The 
new certificate ("CAProtoCert Signing Certificate") should have an 
Enhanced Key Usage (EKU) extension ("CAProtoCert Signing") indicating it 
is intended for use specifically with this protocol.  The CAProtoCert 
Signing Certificate must be signed by the same issuing certificate used to 
sign the certificate intended to be registered in the log. (i.e. the 
Authority field in the CAProtoCert Signing Cert MUST match that of any 
CAProtoCert it signs.)

1)               A Relying Party submits CSR to CA, authenticated per 
standard practice today.
2)               CA formulates the entire X.509v3 TBSCertificate structure 
that would result from issuance, but does not sign it. 
3)               The CA formulates the "CAProtoCert" by doing the 
following to the  TBSCertificate:
                 a)              Add critical extension to "poison" the 
TBSCertificate. (described below) 
                 b)              The CA signs the CAProtoCert with its 
CAProtoCert Signing Certificate.
4)               CA sends to the Public Log:
                 a)              A certificate chain.  The first 
certificate in the chain MUST be the CA's CAProtoCert Signing Certificate, 
the next certificate MUST be the issuing certificate for the CAProtoCert 
Signing Certificate, which MUST also be the issuing certificate identified 
by the CAProtoCert's Authority and Authority Key Indicator extensions, and 
the chain must terminate at a well-known public trust root.
5)               Public Log verifies the CAProtoCert
                 a)              The CAProtoCert signing cert, issuing CA 
certificate and chain is valid according to standard PKIX rules.
                 b)              A certificate which would result from the 
Authority certificate signing the CAProtoCert is valid according to 
standard PKIX rules.
                 c)              The issuing certificate matches exactly 
the Authority indicated in the CAProtoCert.
                 d)              The signature of the CAProtoCert 
validates with the key of the CAProtoCert Signing Certificate.
6)               If 5 succeeds, the Public Log adds the CAProtoCert to the 
log/tree.
7)               Public Log calculates Merkle proof for new cert.
8)               Public Log sends Merkle proof back to CA.
9)               CA verifies Merkle proof.
10)              CA replaces the "poison" extension with an extension 
containing the actual value of the Merkle proof.
11)              The CA adds a new extension containing the signature over 
the CAProtoCert with the CAProtoCert Signing Certificate.
12)              CA signs the certificate with its standard issuing 
certificate.  (including over the Merkle proof extension and original 
CAProtoCert Signature extension) This signature replaces the existing 
signature block with the CAProtoCert Signing Certificate's signature.
13)              CA gives certificate to RP.
14)              [At browser TLS connection time] Browser gets certificate 
from RP.
15)              Browser verifies certificate according to standard PKIX 
rules.
16)              Browser is CT aware and finds Merkle proof in an X.509v3 
cert extension.
17)              Browser re-creates the CAProtoCert by:
                 a)              Replacing the Merkle proof with the 
"poison" extension
                 b)              Removing the CAProtoCert Signing Cert 
signature extension and replacing the signature block with the values from 
this extension.
18)              The browser validates the Merkle proof over the 
CAProtoCert.

"Poison" Extension:  This is simply an extension marked as "critical" 
which it is intended that browsers and other TLS client libraries never 
support.  The presence of the unrecognized critical extension should cause 
all clients to fail to validate any CAProtoCert should it be presented 
outside the context of the log. 

Acknowledgments:

Thanks to Jeff Hodges, Ben Laurie, Nico Williams and Marsh Ray for their 
feedback and contributions to this proposal. 

----------

This is licensed under a Creative Commons Attribution 3.0 United States 
License.
http://creativecommons.org/licenses/by/3.0/us/ 

THIS SPECIFICATION IS PROVIDED "AS IS." PayPal, Inc., Brad Hill, et al 
MAKE NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, INCLUDING, BUT 
NOT LIMITED TO, WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR 
PURPOSE, TITLE OR NON-INFRINGEMENT.

Brad Hill
Sr. MTS, Internet Standards and Governance PayPal Information Risk 
Management
cell: 206.245.7844 / skype: hillbrad
email: [email-masked]

---

From: Yoav Nir <[email-masked]>
Date: Tue, 20 Dec 2011 15:45:30 +0200

Hi Tom

When you say that the UI should put us a screen with some statement, what UI is this?  If it's in the relying party, then this works only for such relying parties that cache the previously-seen certificates, such as a browser implementing the cached info TLS extension. Usually RPs don't have that information.

Yoav

---

From: Tom Gindin <[email-masked]>
Date: Tue, 20 Dec 2011 09:58:23 -0500

I am largely thinking of browsers, although POP clients could do 
the same thing.  After all, browsers are the single most common RP type. 
I'd be happier with a DNS+Cert hijack resulting in even 10% of the 
affected users seeing the problem (and a warning that this is more likely 
malicious than careless) than with the current state of affairs.
        A mail server seeing this condition (although most mail servers 
don't use TLS) should just drop the connection and print a warning.  I 
don't know what the server administrator would do with it.

Tom Gindin

From:   Yoav Nir <[email-masked]>
To:     Tom Gindin/Watson/IBM@IBMUS, 
Cc:     "Hill, Brad" <[email-masked]>, "[email-masked]" 
<[email-masked]>
Date:   12/20/2011 08:45 AM
Subject:        Re: [pkix] CA T&A proofs as cert extensions. WAS: fyi: 
Sovereign       Keys

Hi Tom

When you say that the UI should put us a screen with some statement, what 
UI is this?  If it's in the relying party, then this works only for such 
relying parties that cache the previously-seen certificates, such as a 
browser implementing the cached info TLS extension. Usually RPs don't have 
that information.

Yoav