Assuming keyCompromise for unspecified-reason revocations

[Aaron Gable]

On a recent bugzilla ticket, a commenter (BCC'd) asks: 

> Isn't there a chance that some subscribers are omitting the revocation reason even for key compromise revocations?

> ...

> Isn't it better to err on the side of caution for this type of issues and additionally prevent the reuse of keys whose certificate has been revoked with reason “unspecified” considering that some of them might be compromised?

I'd like to take a moment to reply because I believe this discussion is interesting, but I'm doing so here because I believe it is off-topic for that incident ticket. The issue contained in that preliminary report has to do with handling of revocation requests that specified the keyCompromise reason, not handling of revocation requests that did not specify a reason.

Jaime,

I think it would be a bad idea to assume that all certificates revoked with reason "unspecified" have actually had their keys compromised. I have four arguments:

First, I see no argument that it is more likely that any given unspecified revocation actually be a keyCompromise than that it actually be a cessationOfOperation or some other reason. In fact, I think it is quite likely that the vast majority of unspecified revocations most closely match the superseded revocation reason: this would be the case any time a Subscriber automatically revokes their old certificate after renewing or replacing it.

I can see an obvious counter-argument here: sure, maybe they're almost all actually "superseded", but we should assume the worst, just in case! But that gets right at my second reason this would be a bad idea: the root programs use revocation reasons to inform their own trust behavior. For example, it is my understanding that the CRLite updates its list of keyCompromise-revoked certs (and pushes the resulting bloom filters to Firefox installs) much more frequently than for other revocation reasons. This compromise ensures that keyCompromise revocations are handled as quickly as possible, while saving bandwidth by not updating the whole list every time.

Which brings me to my third reason: treating all unspecified revocations as keyCompromises would increase the number of compromised keys by several orders of magnitude. The minutes of the latest CA/Browser Forum Face-to-Face include a presentation from Ben Wilson at Mozilla which shows that, globally, keyCompromise revocations comprise about 0.2% of revocations while unspecified comprises about 21%. Increasing the number of keyCompromise revocations by 100x would not only drastically increase the bandwidth usage of systems like CRLite, but it would drastically increase the storage costs of CAs. A compromised key is compromised forever, and therefore must be retained forever.

And so finally, the strongest reason of all: per the Baseline Requirements, if a CA treats a key as compromised, then they are required to revoke all other certificates which share that key within 24 hours. Therefore a CA has a prerogative to treat a key as compromised only when that compromise has been demonstrated (e.g. by seeing the private key themselves, receiving an ACME revocation request signed by that key, or receiving a CSR with a "this key is compromised" subject signed by that key). Otherwise they open themselves up to denial-of-service attacks: a malicious actor could identify a victim site, apply for a certificate containing the same public key, revoke that certificate with reason unspecified, and let the CA do the rest of the work to treat that as a keyCompromise and revoke the target site's cert as well.

So while I think this is an interesting line of thinking, treating unspecified revocation requests as keyCompromise revocations and blocking those keys would be very bad for browsers, CAs, and the WebPKI as a whole.

Aaron

[Watson Ladd]

On Tue, Oct 29, 2024 at 6:03 PM 'Aaron Gable' via
dev-secur...@mozilla.org <dev-secur...@mozilla.org>
wrote:
><snip>

> And so finally, the strongest reason of all: per the Baseline Requirements, if a CA treats a key as compromised, then they are required to revoke all other certificates which share that key within 24 hours. Therefore a CA has a prerogative to treat a key as compromised only when that compromise has been demonstrated (e.g. by seeing the private key themselves, receiving an ACME revocation request signed by that key, or receiving a CSR with a "this key is compromised" subject signed by that key). Otherwise they open themselves up to denial-of-service attacks: a malicious actor could identify a victim site, apply for a certificate containing the same public key, revoke that certificate with reason unspecified, and let the CA do the rest of the work to treat that as a keyCompromise and revoke the target site's cert as well.

Minor technical note: a CSR proves possession of the key, so this
isn't possible AFAIK.

> Aaron
>
> --
> You received this message because you are subscribed to the Google Groups "dev-secur...@mozilla.org" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to dev-security-po...@mozilla.org.
> To view this discussion visit https://groups.google.com/a/mozilla.org/d/msgid/dev-security-policy/CAEmnEreLnZH2eqLc2QmBoDTmkRNcrRkYt9h%3DMNAv5gPDZynKqw%40mail.gmail.com.



--
Astra mortemque praestare gradatim

[Aaron Gable]

A CSR does not prove possession of a key. CSRs are generally not treated as confidential data, and are frequently posted in public places. A CSR proves that someone possessed the corresponding private key at some time in the past, but not that the current Applicant controls the private key at the time they are requesting issuance.

Also, the BRs do not specifically require that a CA accept issuance requests in the form of a CSR; it is easy to imagine a CA having a web portal to which you upload the desired public key PEM without signing anything with the corresponding private key.

Aaron

[Jaime Hablutzel]

Hi Aaron. Thanks for replying.

On Tuesday, October 29, 2024 at 8:03:59 PM UTC-5 Aaron Gable wrote:

On a recent bugzilla ticket, a commenter (BCC'd) asks: 

> Isn't there a chance that some subscribers are omitting the revocation reason even for key compromise revocations?

> ...

> Isn't it better to err on the side of caution for this type of issues and additionally prevent the reuse of keys whose certificate has been revoked with reason “unspecified” considering that some of them might be compromised?

I'd like to take a moment to reply because I believe this discussion is interesting, but I'm doing so here because I believe it is off-topic for that incident ticket. The issue contained in that preliminary report has to do with handling of revocation requests that specified the keyCompromise reason, not handling of revocation requests that did not specify a reason.

Jaime,

I think it would be a bad idea to assume that all certificates revoked with reason "unspecified" have actually had their keys compromised. I have four arguments:

First, I see no argument that it is more likely that any given unspecified revocation actually be a keyCompromise than that it actually be a cessationOfOperation or some other reason. In fact, I think it is quite likely that the vast majority of unspecified revocations most closely match the superseded revocation reason: this would be the case any time a Subscriber automatically revokes their old certificate after renewing or replacing it.

I can see an obvious counter-argument here: sure, maybe they're almost all actually "superseded", but we should assume the worst, just in case! But that gets right at my second reason this would be a bad idea: the root programs use revocation reasons to inform their own trust behavior. For example, it is my understanding that the CRLite updates its list of keyCompromise-revoked certs (and pushes the resulting bloom filters to Firefox installs) much more frequently than for other revocation reasons. This compromise ensures that keyCompromise revocations are handled as quickly as possible, while saving bandwidth by not updating the whole list every time.

Which brings me to my third reason: treating all unspecified revocations as keyCompromises would increase the number of compromised keys by several orders of magnitude. The minutes of the latest CA/Browser Forum Face-to-Face include a presentation from Ben Wilson at Mozilla which shows that, globally, keyCompromise revocations comprise about 0.2% of revocations while unspecified comprises about 21%.

The 0.2% reported in the F2F is for revocations where an explicit `keyCompromise` reason code was used. For sure that number is higher for revocations using the `unspecified` reason code where the intention was to revoke because of a key compromise, but how much I can't tell.

Now, in case of vulnerabilities like Heartbleed, surely a lot more `unspecified` revocations would actually be because of key compromise.

 

Increasing the number of keyCompromise revocations by 100x would not only drastically increase the bandwidth usage of systems like CRLite, but it would drastically increase the storage costs of CAs. A compromised key is compromised forever, and therefore must be retained forever.

A technique like the one used by CRLite (i.e. Bloom filters) possibly could help on reducing these storage costs. Additionally, another option to consider might be the proposed called Private Key Compromise Transparency / PKCT (https://mailarchive.ietf.org/arch/msg/trans/tB8YhAapz_6RN9MJVMKlRCR9HK0/).

 

And so finally, the strongest reason of all: per the Baseline Requirements, if a CA treats a key as compromised, then they are required to revoke all other certificates which share that key within 24 hours.

One option here would be not to directly assume `unspecified`s as `keyCompromise`s, but still require CAs to prevent reuse of these keys, as some of them will be effectively compromised!

 

Therefore a CA has a prerogative to treat a key as compromised only when that compromise has been demonstrated (e.g. by seeing the private key themselves, receiving an ACME revocation request signed by that key, or receiving a CSR with a "this key is compromised" subject signed by that key). Otherwise they open themselves up to denial-of-service attacks: a malicious actor could identify a victim site, apply for a certificate containing the same public key, revoke that certificate with reason unspecified, and let the CA do the rest of the work to treat that as a keyCompromise and revoke the target site's cert as well.

Why the TLS BRs don't require certificate requests to include all the requested domains signed by the private key (e.g. with a CSR)? This is required by ACME already.

If that is a requirement, an attacker could not successfully request a certificate using only a victim's public key or even a genuine CSR, as he could not complete DCV to get a certificate to revoke later. Doesn't it eliminate the potential DoS mentioned before?

[Roman Fischer]

Dear Jamie,

 

I don't see what's the final goal here. Is it to prohibit anybody from re-using any key that was ever involved in a certificate that was revoked (any reason could be "false" or "mistaken")? Or also keys of certificates that expired (not everybody who has a key compromise reports it or revokes the certificate, they might just create a new key and let the cert expire)?

 

Kind regards
Roman

--

You received this message because you are subscribed to the Google Groups "dev-secur...@mozilla.org" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dev-security-po...@mozilla.org.

To view this discussion visit https://groups.google.com/a/mozilla.org/d/msgid/dev-security-policy/00f38a3e-f2b7-4000-bb3a-ac8d756c95cfn%40mozilla.org.

[Mike Shaver]

I guess I’m curious about the opposite question: why is it important that a key be permitted to be reused ever? I understand that there are some operational shortcuts that can be taken to avoid deploying a new key along with a new certificate, but I’m not sure if there are other reasons to not just require a new private key for every certificate. They are cheap to generate!

I feel a nagging at the back of my brain as I ask this question, so I anticipate that someone will provide a tremendously obvious answer.

Mike

To view this discussion visit https://groups.google.com/a/mozilla.org/d/msgid/dev-security-policy/ZR0P278MB01706BA4FE843FF7A2E982D3FA562%40ZR0P278MB0170.CHEP278.PROD.OUTLOOK.COM.

[Roman Fischer]

Key-generation isn't that cheap and the larger the keys get, the more expensive it gets.

Also, the CA's would probably need to feed and query one central database of "used" keys to prevent the re-use.

 

-Roman

[Mike Shaver]

Key generation is done by the subscriber, generally, which means it seems like it would scale pretty well given that it happens at the rate of certificate replacement. Even at an imagined 3-day validity window, that’s a pretty small amount of cryptography to amortize. My phone could have done it while I typed the last sentence without me noticing, I think.

That said, you probably generate more keys than I do: what does it cost to generate your preferred (classical, not PQ let’s say) key pair for a modern certificate on your choice of modern data centre CPU? 

The perfect doesn’t need to be the enemy of the good here; we can start by just having CAs track one they’ve seen before. If subscribers think it’s easier to change CAs than to generate another key, then we’re in a pretty good place as an ecosystem I think!

Mike

To view this discussion visit https://groups.google.com/a/mozilla.org/d/msgid/dev-security-policy/ZR0P278MB0170549AE9570AF075D265A0FA562%40ZR0P278MB0170.CHEP278.PROD.OUTLOOK.COM.

[Roman Fischer]

I'm not generating a lot of keys… 😉 The last time I used openssl to generate a keypair it took a few seconds. But of course, you're right, it scales as it's done on the subscriber side.

[Matt Palmer]

On Fri, Nov 01, 2024 at 12:45:31PM +0000, Roman Fischer wrote:

> I'm not generating a lot of keys… 😉 The last time I used openssl to
> generate a keypair it took a few seconds. But of course, you're right,
> it scales as it's done on the subscriber side.

It must have been a while since you generated a private key. Here's my
(not particularly impressive) home box CPU, which is also doing a bunch
of other stuff:

$ time openssl genrsa 2048
-----BEGIN PRIVATE KEY-----
[...]
-----END PRIVATE KEY-----

real 0m0.131s
user 0m0.130s
sys 0m0.001s

$ time openssl genrsa 4096
-----BEGIN PRIVATE KEY-----
[...]
-----END PRIVATE KEY-----

real 0m1.040s
user 0m1.032s
sys 0m0.008s

$ time openssl genpkey -algorithm ec -pkeyopt ec_paramgen_curve:P-256
-----BEGIN PRIVATE KEY-----
[...]
-----END PRIVATE KEY-----

real 0m0.019s
user 0m0.019s
sys 0m0.000s

$ time openssl genpkey -algorithm ec -pkeyopt ec_paramgen_curve:P-384
-----BEGIN PRIVATE KEY-----
[...]
-----END PRIVATE KEY-----

real 0m0.023s
user 0m0.015s
sys 0m0.008s

$ time openssl genpkey -algorithm ec -pkeyopt ec_paramgen_curve:P-521
-----BEGIN PRIVATE KEY-----
[...]
-----END PRIVATE KEY-----

real 0m0.005s
user 0m0.005s
sys 0m0.000s

EC keys are quick to generate because you don't have to keep rolling the
dice until you get two of the "right" numbers.

Ironically, a move to shorter certificate lifetimes and preventing the
reuse of keys would mean that using smaller-sized (ie quicker to
generate) RSA keys would be much safer than they are today. If an
attacker can't crack the key within a month (or three), there's no point
even trying, because that key will be useless forever more in the
WebPKI. We could bring back RSA-1024! :trollface:

- Matt

[Jaime Hablutzel]

On 1 Nov 2024, at 7:28 AM, Roman Fischer <roman....@swisssign.com> wrote:

Key-generation isn't that cheap and the larger the keys get, the more expensive it gets.

Also, the CA's would probably need to feed and query one central database of "used" keys to prevent the re-use.

Private Key Compromise Transparency (PKCT), as mentioned in https://mailarchive.ietf.org/arch/msg/trans/tB8YhAapz_6RN9MJVMKlRCR9HK0/, might help to make this information available to all CAs.

 

-Roman

 

From: Mike Shaver <mike....@gmail.com>
Sent: Freitag, 1. November 2024 13:16
To: Roman Fischer <roman....@swisssign.com>
Cc: dev-secur...@mozilla.org
Subject: Re: Assuming keyCompromise for unspecified-reason revocations

 

I guess I’m curious about the opposite question: why is it important that a key be permitted to be reused ever? I understand that there are some operational shortcuts that can be taken to avoid deploying a new key along with a new certificate, but I’m not sure if there are other reasons to not just require a new private key for every certificate. They are cheap to generate!

 

I feel a nagging at the back of my brain as I ask this question, so I anticipate that someone will provide a tremendously obvious answer.

 

Mike

 

On Fri, Nov 1, 2024 at 6:00 AM Roman Fischer <roman....@swisssign.com> wrote:

Dear Jamie,

 

I don't see what's the final goal here. Is it to prohibit anybody from re-using any key that was ever involved in a certificate that was revoked (any reason could be "false" or "mistaken")? Or also keys of certificates that expired (not everybody who has a key compromise reports it or revokes the certificate, they might just create a new key and let the cert expire)?

I was only suggesting to prohibit reuse of keys for certificates revoked without reason (“unspecified” reasonCode) as there is a chance they are compromised. 

Though, preventing overall reuse of any key seems like the safer approach but I don’t really know what type of negative implications it might bring.

[Matt Palmer]

On Fri, Nov 01, 2024 at 06:47:54PM -0500, Jaime Hablutzel wrote:
> > On 1 Nov 2024, at 7:28 AM, Roman Fischer <roman....@swisssign.com> wrote:
> >
> > Key-generation isn't that cheap and the larger the keys get, the
> > more expensive it gets. Also, the CA's would probably need to feed
> > and query one central database of "used" keys to prevent the re-use.
>
> Private Key Compromise Transparency (PKCT), as mentioned in
> https://mailarchive.ietf.org/arch/msg/trans/tB8YhAapz_6RN9MJVMKlRCR9HK0/,
> might help to make this information available to all CAs.

What benefit does a transparency log bring to this use case, over, say,
a git repo full of keys in files?

- Matt