Cert-within-cert / Digest algorithm transition strategy

[Rob Stradling]

One option for distributing CT proofs to relying parties is for the CA to embed the proof into the end-entity certificate.  This would require the CA to issue a "pre-cert", then send it to the CT log and wait for the proof to become available, then issue a certificate containing both the "pre-cert" and the proof.  There has been discussion on other lists about whether it is better for the "pre-cert" to be a full X.509 certificate or a custom data structure containing just a subset of fields.

Now, there is another problem for which I've previously proposed [1] a similar cert-within-cert solution...

The vast majority of CAs still generate certificate signatures with SHA-1 because various legacy clients (notably Windows XP SP 2 and earlier), which still have a significant userbase, do not support any stronger digest algorithms (e.g. SHA-2).  Since X.509 only provides 1 slot for a signature, the only way to effect a global transition to a stronger digest algorithm would be to replace nearly every certificate on the planet.  Therefore, it would be good to have a way to roll-out SHA-2 signatures now, but without breaking SHA-1-only clients.  Then, if/when SHA-1 is no longer considered secure enough for certificate signatures, we wouldn't need to panic nearly as much because most users would already be relying on the "additional" SHA-2 signatures.

My proposal is that CAs would sign a cert with SHA-2, then append that SHA-2 signature to the tbsCertificate structure (and recalculate various ASN.1 lengths), then sign it with SHA-1.

Legacy clients would see the "outer" certificate and verify the SHA-1 signature as normal.  They would simply ignore the extension containing the SHA-2 signature.

Newer clients would ignore the SHA-1 signature.  They would understand the extension, reconstruct the "inner" cert, and verify the SHA-2 signature.

So can we kill 2 birds with 1 stone here?  Could the CT cert-within-cert proposal for embedding CT proofs also accommodate an additional signature from the CA?

To keep the certificate size down, I think it should be possible to embed the CT proof inside the additional signature.  Much of the plaintext data in a PKCS#1 signature is "wasted" on padding, but since there wouldn't be any legacy code for parsing the additional signature extension, I don't think we'd have to stick to the PKCS#1 format.

[1] http://www.ietf.org/mail-archive/web/pkix/current/msg03765.html (and follow-ups)

[Ben Laurie]

I don't see why not - I'd assume in that case that like RFC 5878 we'd
have an extension capable of holding various types of authorisation
data.

>
> To keep the certificate size down, I think it should be possible to embed
> the CT proof inside the additional signature.  Much of the plaintext data in
> a PKCS#1 signature is "wasted" on padding, but since there wouldn't be any
> legacy code for parsing the additional signature extension, I don't think
> we'd have to stick to the PKCS#1 format.

Perhaps I'm misunderstanding, but ... assuming you are talking about
OAEP and the like, the "wasted" padding in the plaintext is essential
for security.

[Rob Stradling]

On Friday, May 4, 2012 10:38:57 AM UTC+1, Ben Laurie wrote:

On 3 May 2012 16:30, Rob Stradling <r...@comodo.com> wrote:

<snip> 

> So can we kill 2 birds with 1 stone here?  Could the CT cert-within-cert
> proposal for embedding CT proofs also accommodate an additional signature
> from the CA?

I don't see why not - I'd assume in that case that like RFC 5878 we'd
have an extension capable of holding various types of authorisation
data.

RFC 5878 documents a TLS extension, but since my proposal in this thread only relates to the contents of certificates, I presume that what you're suggesting here is that we'd need a _certificate_ extension capable of holding various types of "authorisation data".  That makes sense.  This certificate extension, present only in the "outer" certificate, would contain at least one of: i) a CT proof, ii) an additional signature (using a stronger digest algorithm) from the CA, iii) anything else we define in the future.

> To keep the certificate size down, I think it should be possible to embed
> the CT proof inside the additional signature.  Much of the plaintext data in
> a PKCS#1 signature is "wasted" on padding, but since there wouldn't be any
> legacy code for parsing the additional signature extension, I don't think
> we'd have to stick to the PKCS#1 format.

Perhaps I'm misunderstanding, but ... assuming you are talking about
OAEP and the like, the "wasted" padding in the plaintext is essential
for security.

RSAES-OAEP is the PKCS#1 v2 encryption scheme, so it's not relevant to digital signatures.  I presume you meant to say RSASSA-PSS, which is the PKCS#1 v2 signature scheme.

Even though PKCS#1 v2.1 was published nearly 10 years ago, support for the RSASSA-PSS signature scheme is still not widespread.  So CAs are still having to use the PKCS#1 v1.5 signature scheme.

I agree that some of the padding in the signature is essential for security.  Skimming through the PKCS#1 spec, I see the requirement that the padding string (PS) must be "at least 8 octets".  Add a SHA-256 digest (32 octets), ASN.1 fluff (19 bytes) and the rest of the PKCS#1 v1.5 signature header (3 octets), and we're up to 62 octets.  If we're using RSA-2048, the signature size is going to be 256 octets.  256 minus 62 equals 194 octets of "wasted" space that we could use for something useful...such as...

https://sites.google.com/site/certificatetransparency/sizes

"Proof length                     134 bytes"

Or maybe we could rip apart the signature format even more than that...discard the DigestInfo structure from PKCS#1 but retain the >8 bytes of padding, and let the CA form the "additional signature" by simply encrypting the CT proof with the CA private key (assuming the CT proof already contains a SHA-256 digest calculated over the "inner" certificate).  This should leave enough room inside the additional signature for...

https://sites.google.com/site/certificatetransparency/sizes

"Proof length                     230 bytes"

(Obviously embedding the CT proof inside the additional signature is an optional optimization, but I wanted to mention it now before someone says that they don't like the "additional signature" idea purely because it would increase the size of each certificate. ;-) )

[Emilia Kasper]

On Tue, May 8, 2012 at 10:26 AM, Rob Stradling <r...@comodo.com> wrote:

On Friday, May 4, 2012 10:38:57 AM UTC+1, Ben Laurie wrote:

On 3 May 2012 16:30, Rob Stradling <r...@comodo.com> wrote:

<snip> 

> So can we kill 2 birds with 1 stone here?  Could the CT cert-within-cert
> proposal for embedding CT proofs also accommodate an additional signature
> from the CA?

I don't see why not - I'd assume in that case that like RFC 5878 we'd
have an extension capable of holding various types of authorisation
data.

RFC 5878 documents a TLS extension, but since my proposal in this thread only relates to the contents of certificates, I presume that what you're suggesting here is that we'd need a _certificate_ extension capable of holding various types of "authorisation data".  That makes sense.  This certificate extension, present only in the "outer" certificate, would contain at least one of: i) a CT proof, ii) an additional signature (using a stronger digest algorithm) from the CA, iii) anything else we define in the future.

Yep, that's what Ben is suggesting. We've been looking into using rfc 5878 for conveying audit proofs in a TLS extension; we could have a complementing flexible certificate extension for authorization data.

> To keep the certificate size down, I think it should be possible to embed
> the CT proof inside the additional signature.  Much of the plaintext data in
> a PKCS#1 signature is "wasted" on padding, but since there wouldn't be any
> legacy code for parsing the additional signature extension, I don't think
> we'd have to stick to the PKCS#1 format.

Perhaps I'm misunderstanding, but ... assuming you are talking about
OAEP and the like, the "wasted" padding in the plaintext is essential
for security.

RSAES-OAEP is the PKCS#1 v2 encryption scheme, so it's not relevant to digital signatures.  I presume you meant to say RSASSA-PSS, which is the PKCS#1 v2 signature scheme.

Even though PKCS#1 v2.1 was published nearly 10 years ago, support for the RSASSA-PSS signature scheme is still not widespread.  So CAs are still having to use the PKCS#1 v1.5 signature scheme.

I agree that some of the padding in the signature is essential for security.  Skimming through the PKCS#1 spec, I see the requirement that the padding string (PS) must be "at least 8 octets".  Add a SHA-256 digest (32 octets), ASN.1 fluff (19 bytes) and the rest of the PKCS#1 v1.5 signature header (3 octets), and we're up to 62 octets.  If we're using RSA-2048, the signature size is going to be 256 octets.  256 minus 62 equals 194 octets of "wasted" space that we could use for something useful...such as...

https://sites.google.com/site/certificatetransparency/sizes

"Proof length                     134 bytes"

Interesting idea, but I doubt we'll actually want to go with proofs (=trees) this small. It makes auditing more complicated.

  

Or maybe we could rip apart the signature format even more than that...discard the DigestInfo structure from PKCS#1 but retain the >8 bytes of padding, and let the CA form the "additional signature" by simply encrypting the CT proof with the CA private key (assuming the CT proof already contains a SHA-256 digest calculated over the "inner" certificate).  

It doesn't...

[Phillip Hallam-Baker]

What is essential from the security point of view is that the signed object be entirely deterministic and contain the OID of the signature digest function.

Due to the way that the RSA algorithm works, the strongest bits are at the low end of the signature. But the high order bits can be any fluff you like provided that they are entirely deterministic and prevent some sort of Chaumian type game.

Choosing straight 0s is OK but not optimal since it means that every signature is going to have the same sequence and arguably makes things easier for the attacker.

Padding that space out with 'stuff' that is signature specific is just as good as digests or what have you.

Rob and I have been talking about other games we could play if we needed to. For example it is not widely known that it is actually possible to 'compress' an RSA modulus. Although actually what is done is that you choose part of the modulus deterministically so you don't need to send it.

[Rob Stradling]

On Tuesday, May 8, 2012 1:20:23 PM UTC+1, Emilia Kasper wrote:

On Tue, May 8, 2012 at 10:26 AM, Rob Stradling <r...@comodo.com> wrote:

Or maybe we could rip apart the signature format even more than that...discard the DigestInfo structure from PKCS#1 but retain the >8 bytes of padding, and let the CA form the "additional signature" by simply encrypting the CT proof with the CA private key (assuming the CT proof already contains a SHA-256 digest calculated over the "inner" certificate).  

It doesn't...

Sorry, "contains" was the wrong word to use there.  I'll try to clarify...

A certificate's signature consists of an encrypted digest.  What I was trying to suggest here is that the digest algorithm for the "additional signature" would be "CT" rather than SHA-256.

IINM, the CT proof of the "inner" tbsCertificate and the SHA-256 digest of the same "inner" tbsCertificate will be equally good at protecting message integrity, so there would be no security requirement for having both the SHA-256 digest and the CT proof inside the "additional signature".

So...

This should leave enough room inside the additional signature for...

https://sites.google.com/site/certificatetransparency/sizes

"Proof length                     230 bytes"

Are you still considering "proofs (=trees) this small" ?

[Ben Laurie]

The smaller the tree gets, the more has to be revealed to auditors
about what websites you have visited. So, we should not design a
system that stands no chance of being privacy respecting.

Emilia also tells me I got the numbers slightly wrong in that table
(they're slightly bigger than stated). I will correct this soon.

[Emilia Kasper]

On Fri, May 11, 2012 at 2:37 PM, Rob Stradling <r...@comodo.com> wrote:

On Tuesday, May 8, 2012 1:20:23 PM UTC+1, Emilia Kasper wrote:

On Tue, May 8, 2012 at 10:26 AM, Rob Stradling <r...@comodo.com> wrote:

Or maybe we could rip apart the signature format even more than that...discard the DigestInfo structure from PKCS#1 but retain the >8 bytes of padding, and let the CA form the "additional signature" by simply encrypting the CT proof with the CA private key (assuming the CT proof already contains a SHA-256 digest calculated over the "inner" certificate).  

It doesn't...

Sorry, "contains" was the wrong word to use there.  I'll try to clarify...

A certificate's signature consists of an encrypted digest.  What I was trying to suggest here is that the digest algorithm for the "additional signature" would be "CT" rather than SHA-256.

Yes but... We include everything needed to compute the CT hash from the certificate, but not the certificate hash or the CT hash itself. You rely on the validity of the CT signature to know the cert hasn't been swapped.