Re: Proposal: prohibit issuance of new certificates with known-compromised keys, and for related purposes
On Thu, Apr 09, 2020 at 04:55:51PM +0100, Nick Lamb via dev-security-policy wrote: > Right-sizing of Bloom filters is an issue, but you only need to get > ballpark accuracy. If we genuinely aren't sure if there will be a > thousand or a billion RSA private keys compromised next year then yup > that's a problem to address early. "Like bloom filters? Then you'll *love* new Scalable Bloom Filters!" http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf They are a rather neat trick. Bucketing keys isn't a bad idea, either. > A Bloom filter doesn't solve the whole problem unless you're > comfortable being a bit savage. You *can* say "If it matches the bloom > filter, reject as possibly compromised" and set your false positive > ratio in the sizing decision as a business policy. e.g. "We accept > that we'll reject 1-in-a-million issuances for false positive". But I'd > suggest CAs just slow-path these cases, if it's a match to the Bloom > filter you do the real check, and maybe that's not fast enough for goal > response times in your customer service, but in most cases issuance > fails anyway because somebody was trying to re-use a bad key. Customers > who just got tremendously unlucky get a slightly slower issuance. "Huh, > these are normally instant. What's up with... oh, there is goes". If you're storing all the keys on local disk anyway, providing an index of all the keys that's going to be Fast Enough(TM) isn't hard. The database isn't *that* big, and the lookup rate isn't *that* huge, that you need to have a bloom filter in the middle to cut down on the lookup rate. I'm interested in bloom filters for pwnedkeys because of the additional latency that a lookup over HTTP introduces. > Is it necessary to spell out that even though _Private_ key compromise > is what we care about the things you need to be keeping in filters and > databases to weed out compromised keys are the corresponding _Public_ > keys? You don't even need to keep the actual public keys; the (SHA256) SPKI fingerprint is entirely sufficient. - Matt ___ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
Re: Proposal: prohibit issuance of new certificates with known-compromised keys, and for related purposes
On Mon, 6 Apr 2020 12:56:02 -0400 Ryan Sleevi via dev-security-policy wrote: > It's not as easy as saying "use a bloom filter" if a bloom filter > takes X amount of time to generate. I've spent a bunch of time up to my neck in bloom filters (they're one of the key components of 4store, a GPL'd RDF storage engine / SPARQL implementation for which I wrote a lot of the code and its proprietary successors). Adding things to a bloom filter is cheap enough that we'd definitely not shy away from putting it in the human perceptible updates rather than batching it up to do asynchronously. The part that's non-viable in Bloom filters is removing things, but that's cool because we're all agreed that "This key is no longer compromised" is not a thing. The most we should do there is recommend people have one filter for each type of key they support, for example if we imagine this rule had been in place from the outset, you no longer need your "compromised" bloom filter for 1024-bit RSA because all 1024-bit RSA issuance is prohibited now, so you can throw that away. Right-sizing of Bloom filters is an issue, but you only need to get ballpark accuracy. If we genuinely aren't sure if there will be a thousand or a billion RSA private keys compromised next year then yup that's a problem to address early. I recommended ISRG look at Bloom Filters for their response to Matt's enquiries about refusing to re-issue, I have been busy but I don't think they responded, which is fine it was unsolicited advice. A Bloom filter doesn't solve the whole problem unless you're comfortable being a bit savage. You *can* say "If it matches the bloom filter, reject as possibly compromised" and set your false positive ratio in the sizing decision as a business policy. e.g. "We accept that we'll reject 1-in-a-million issuances for false positive". But I'd suggest CAs just slow-path these cases, if it's a match to the Bloom filter you do the real check, and maybe that's not fast enough for goal response times in your customer service, but in most cases issuance fails anyway because somebody was trying to re-use a bad key. Customers who just got tremendously unlucky get a slightly slower issuance. "Huh, these are normally instant. What's up with... oh, there is goes". Is it necessary to spell out that even though _Private_ key compromise is what we care about the things you need to be keeping in filters and databases to weed out compromised keys are the corresponding _Public_ keys? Nick. ___ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
Re: Proposal: prohibit issuance of new certificates with known-compromised keys, and for related purposes
On Mon, Apr 06, 2020 at 12:56:02PM -0400, Ryan Sleevi wrote: > On Mon, Mar 30, 2020 at 5:32 PM Matt Palmer via dev-security-policy > wrote: > > Righto, the goals are: > > > > * Make it a policy violation for CAs to issue a certificate using a public > > key they've revoked before. > > > > * Clarify the language around key compromise revocation to make it obvious > > that CAs have to revoke everything with a given private key. > > > > * Clarify the language around revocation time limits to make it obvious that > > the time period starts when the communication leaves the reporter. > > I've attempted the first two points with > https://github.com/sleevi/cabforum-docs/pull/12 . You can seem some of > the discussion at > https://github.com/sleevi/cabforum-docs/pull/12/files#r401919547 and > https://github.com/sleevi/cabforum-docs/pull/12/files#diff-7f6d14a20e7f3beb696b45e1bf8196f2R1425 Thanks, I've made a comment on part of that change. > > I, personally, do not have a problem with mandating that CAs keep records of > > compromised keys in perpetuity. > > I've not yet addressed this part in the above PR, because I think > there's still work to sort out the objectives and goals. We've seen > some CAs express concerns (not unreasonably) at the potential of an > unbounded growth of key sizes creating a disproportionate load on CAs. > I think more napkin math is needed here in terms of load and lookups. Well, I can say that indexing 1.3M private keys, at least, isn't a particular challenge, even comparing that against the entire corpus of known certificates. I don't know how many private keys CAs' customers are planning on dumping onto the public Internet, though... > It's not as easy as saying "use a bloom filter" if a bloom filter > takes X amount of time to generate. A bloom filter could potentially be a *part* of an approach, but it certainly can't be the entire solution (for a great many reasons). As an aside, if anyone wants to try out a bloom filter, I've generated one containing all the Debian weak keys I've generated so far: https://assets.pwnedkeys.com/public/debian-weak-keys.pkf (file format documented at https://pwnedkeys.com/filter.html). > > > While I appreciate the suggestion, I'm worried this does more to sow > > > confusion rather than bring clarity. As you note, 4.9.1.1 is liked to > > > evidence about the Private Key, not the Certificate, so this is > > > already a "clear" requirement. > > > > What about it sows (additional) confusion? > > Every time we've seen an existing requirement stated in two places, > CAs have tried to argue they're disjoint requirements OR they become > disjoint requirements through a lack of consistent updating. If a CA > can't read 4.9.1.1 and reach the conclusion, I've got worries, but if > a CA has reached that, they should be offering suggestions here as to > why. Yes, well, I suppose we should ask the CAs that have come to that conclusion as to how they managed that. I'm not hopeful, however; whenever I've asked questions about how a CA came to a particular conclusion, the best I've gotten back is "lol we dunno". The most common response is radio silence. > Unfortunately, I think that's where we might disagree. More words > often creates more opportunity here for getting creative, so I want to > figure out how to tighten up or entirely reframe requirements, rather > than merely state them multiple times in slightly-different ways that > might be seen as offering slightly different requirements. In short, > I'd like to avoid the CA-equivalent of the Genesis creation narrative > debate :) I see your point. > > > > Step 3: Insert a new paragraph at the end of section 4.9.1.1, with the > > > > following contents (or a reasonable facsimile thereof): > > > > > > This isn't where the suggested requirements go. That's covered in 4.9.5 > > > > I'm not sure what you mean by this. Could you expand a little? > > Yeah, 4.9.5 is the "Time within which CA must process the revocation > request" - that's where requirements for timeliness go. Hmm, I think the cat's nose is poking out of the bag on that one, because of all the mentions of timeframes for different sorts of revocation already in 4.9.1.1. I don't have a problem with a clarification of exactly what "receipt" means into 4.9.5, though, if it works better there. The important thing is that there *is* a clear definition of such things, because there are CAs who aren't clear on what that means. - Matt ___ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
Re: Proposal: prohibit issuance of new certificates with known-compromised keys, and for related purposes
On Mon, Mar 30, 2020 at 5:32 PM Matt Palmer via dev-security-policy wrote: > Righto, the goals are: > > * Make it a policy violation for CAs to issue a certificate using a public > key they've revoked before. > > * Clarify the language around key compromise revocation to make it obvious > that CAs have to revoke everything with a given private key. > > * Clarify the language around revocation time limits to make it obvious that > the time period starts when the communication leaves the reporter. I've attempted the first two points with https://github.com/sleevi/cabforum-docs/pull/12 . You can seem some of the discussion at https://github.com/sleevi/cabforum-docs/pull/12/files#r401919547 and https://github.com/sleevi/cabforum-docs/pull/12/files#diff-7f6d14a20e7f3beb696b45e1bf8196f2R1425 > I, personally, do not have a problem with mandating that CAs keep records of > compromised keys in perpetuity. I've not yet addressed this part in the above PR, because I think there's still work to sort out the objectives and goals. We've seen some CAs express concerns (not unreasonably) at the potential of an unbounded growth of key sizes creating a disproportionate load on CAs. I think more napkin math is needed here in terms of load and lookups. It's not as easy as saying "use a bloom filter" if a bloom filter takes X amount of time to generate. I'd love to see more thoughts in this space before trying to nail down the precise language here, although I do agree with the spirit here of being something that 'seems' like it should be indefinitely maintainable. That said, there are obvious edge cases to think through, such as: - If CA Foo purchases CA Bar, what happens with Foo's database of compromised keys? - Scenarios: Foo ends up using Bar's database (Foo is transitioned to Bar's infrastructure), Bar ends up using Foo's database (Bar is 'reverse-transitioned' onto Foo's infrastructure), the database becomes Foo+Bar, etc - What happens if Foo's the crappy CA and their database doesn't record enough info for Bar to be able to reliably/safely implement? > > While I appreciate the suggestion, I'm worried this does more to sow > > confusion rather than bring clarity. As you note, 4.9.1.1 is liked to > > evidence about the Private Key, not the Certificate, so this is > > already a "clear" requirement. > > What about it sows (additional) confusion? Every time we've seen an existing requirement stated in two places, CAs have tried to argue they're disjoint requirements OR they become disjoint requirements through a lack of consistent updating. If a CA can't read 4.9.1.1 and reach the conclusion, I've got worries, but if a CA has reached that, they should be offering suggestions here as to why. > > I think we'd want to understand why/how CAs are misinterpreting this. > > I think we've seen a common thread, which is CAs thinking about > > systems in terms of Certificates, rather than thinking about Keys and > > Issuers. We've seen that problem systemically come up in other areas, > > such as OCSP, Precertificates, and SHA-1. > > > > Does that seem to track with the root cause of the problem? That is, > > that this is an existing requirement, but CAs aren't recognizing it as > > such? > > Yes, I certainly believe that you and I are in agreement that this is an > existing requirement. However, CA interpretations appear to diverge from > ours, and the easiest way to re-align CA interpretations would seem to be to > add more words to the BRs. Unfortunately, I think that's where we might disagree. More words often creates more opportunity here for getting creative, so I want to figure out how to tighten up or entirely reframe requirements, rather than merely state them multiple times in slightly-different ways that might be seen as offering slightly different requirements. In short, I'd like to avoid the CA-equivalent of the Genesis creation narrative debate :) > > > > Step 3: Insert a new paragraph at the end of section 4.9.1.1, with the > > > following contents (or a reasonable facsimile thereof): > > > > This isn't where the suggested requirements go. That's covered in 4.9.5 > > I'm not sure what you mean by this. Could you expand a little? Yeah, 4.9.5 is the "Time within which CA must process the revocation request" - that's where requirements for timeliness go. ___ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy
Re: Proposal: prohibit issuance of new certificates with known-compromised keys, and for related purposes
On Mon, Mar 30, 2020 at 10:59:02AM -0400, Ryan Sleevi wrote: > On Mon, Mar 30, 2020 at 6:28 AM Matt Palmer via dev-security-policy > wrote: > It's useful to focus on the goal, rather than the precise language, or > where you see folks getting confused or misunderstanding things. That > is, making sure we have a common understanding of the problems here. Righto, the goals are: * Make it a policy violation for CAs to issue a certificate using a public key they've revoked before. * Clarify the language around key compromise revocation to make it obvious that CAs have to revoke everything with a given private key. * Clarify the language around revocation time limits to make it obvious that the time period starts when the communication leaves the reporter. > > Step 1: add a new section 4.2.3 (pushing down the existing 4.2.3 to be > > 4.2.4, because RFC3647 says that "Finally, this subcomponent sets a time > > limit", which I assume means that the time limit section needs to be last), > > worded something like this: > > Well, no, that doesn't work with https://tools.ietf.org/html/rfc3647#section-6 Drat. Makes it hard to fit key checks into there anywhere, then. Shoehorn it into 4.2.2, perhaps? > > I know that Section 5.5.2 only requires storage of records for seven years; > > I figure if someone's going to hold onto a compromised private key for seven > > years just so they can bring it out for another cert, then they've earned > > the right to get their cert revoked again. Requiring CAs to maintain a list > > of keys in perpetuity may be considered an overly onerous burden. > > I don't think we want the explicit dependency on 5.5.2, because it > would be good to reduce that time in line with reducing certificate > lifetimes. > > The 7 years is derived from the validity period of the certificates > being issued (at the time, up to 10 year certs; 7 years was a > compromise between the 5 years the BRs were phasing in and the 10y+ > existing practice) Huh, that's interesting; I figured the 7 year requirement was in line with other standard business record-keeping requirements, like tax records. > By this logic, Debian weak keys would not need to be blocked, because > that even occurred in 2006. Hmm, no, unless the CA had previously issued a certificate for every Debian weak key and subsequently revoked them for key compromise. The existing provisions regarding Debian weak keys (as potentially to-be-amended in the near future) would still be in force, with no expiry time limit. I, personally, do not have a problem with mandating that CAs keep records of compromised keys in perpetuity. > Broadly, it seems your problem that this first proposal is trying to > solve is that CAs don't see it as logical that they must maintain a > database of revoked keys. Is that a fair statement? Close, but I'll quibble with "logical", and I dislike talking about "revoked keys" because it gives people the wrong mental shorthand -- you can't "revoke" a key, as such. Although I suppose published attestations of compromise are pretty close to a kind of OKSP, if you wanted to think that way. I'd rather word it as: "CAs don't see it as necessary that they must maintain a database of keys from *all* certificates they revoked for key compromise, and that they must check that database before issuance." > > Step 2: Replace the existing text of section 4.9.12 with something like the > > following: > > > > > In the event that the CA obtains evidence of Key Compromise, all > > > Certificates issued by the CA which contain the compromised key MUST be > > > revoked as per the requirements of Section 4.9.1.1, including the time > > > period requirements therein, even if no Certificate Problem Report for a > > > given Certificate has been received by the CA. > > > > In a perfect world, this sentence wouldn't be necessary, because 4.9.1.1 > > doesn't say that the certificate has to be revoked if a problem report comes > > in alleging key compromise, but since CAs don't appear to have interpreted > > 4.9.1.1 in that way, we may as well use 4.9.12 for a good purpose and > > clarify the situation. > > While I appreciate the suggestion, I'm worried this does more to sow > confusion rather than bring clarity. As you note, 4.9.1.1 is liked to > evidence about the Private Key, not the Certificate, so this is > already a "clear" requirement. What about it sows (additional) confusion? > I think we'd want to understand why/how CAs are misinterpreting this. > I think we've seen a common thread, which is CAs thinking about > systems in terms of Certificates, rather than thinking about Keys and > Issuers. We've seen that problem systemically come up in other areas, > such as OCSP, Precertificates, and SHA-1. > > Does that seem to track with the root cause of the problem? That is, > that this is an existing requirement, but CAs aren't recognizing it as > such? Yes, I certainly believe that you and I are in agreement that this is
Re: Proposal: prohibit issuance of new certificates with known-compromised keys, and for related purposes
Thanks for starting this! On Mon, Mar 30, 2020 at 6:28 AM Matt Palmer via dev-security-policy wrote: > If such a modification were deemed appropriate for the BRs, I would suggest > that the following changes would fit the bill. All sections, etc taken from > version 1.6.7 of the BRs. Discussing changes to the BRs here are a bit complicated, for IP reasons (And no, disclaiming IP doesn't make this go away) It's useful to focus on the goal, rather than the precise language, or where you see folks getting confused or misunderstanding things. That is, making sure we have a common understanding of the problems here. > > Step 1: add a new section 4.2.3 (pushing down the existing 4.2.3 to be > 4.2.4, because RFC3647 says that "Finally, this subcomponent sets a time > limit", which I assume means that the time limit section needs to be last), > worded something like this: Well, no, that doesn't work with https://tools.ietf.org/html/rfc3647#section-6 > I know that Section 5.5.2 only requires storage of records for seven years; > I figure if someone's going to hold onto a compromised private key for seven > years just so they can bring it out for another cert, then they've earned > the right to get their cert revoked again. Requiring CAs to maintain a list > of keys in perpetuity may be considered an overly onerous burden. I don't think we want the explicit dependency on 5.5.2, because it would be good to reduce that time in line with reducing certificate lifetimes. The 7 years is derived from the validity period of the certificates being issued (at the time, up to 10 year certs; 7 years was a compromise between the 5 years the BRs were phasing in and the 10y+ existing practice) By this logic, Debian weak keys would not need to be blocked, because that even occurred in 2006. Broadly, it seems your problem that this first proposal is trying to solve is that CAs don't see it as logical that they must maintain a database of revoked keys. Is that a fair statement? > Step 2: Replace the existing text of section 4.9.12 with something like the > following: > > > In the event that the CA obtains evidence of Key Compromise, all > > Certificates issued by the CA which contain the compromised key MUST be > > revoked as per the requirements of Section 4.9.1.1, including the time > > period requirements therein, even if no Certificate Problem Report for a > > given Certificate has been received by the CA. > > In a perfect world, this sentence wouldn't be necessary, because 4.9.1.1 > doesn't say that the certificate has to be revoked if a problem report comes > in alleging key compromise, but since CAs don't appear to have interpreted > 4.9.1.1 in that way, we may as well use 4.9.12 for a good purpose and > clarify the situation. While I appreciate the suggestion, I'm worried this does more to sow confusion rather than bring clarity. As you note, 4.9.1.1 is liked to evidence about the Private Key, not the Certificate, so this is already a "clear" requirement. I think we'd want to understand why/how CAs are misinterpreting this. I think we've seen a common thread, which is CAs thinking about systems in terms of Certificates, rather than thinking about Keys and Issuers. We've seen that problem systemically come up in other areas, such as OCSP, Precertificates, and SHA-1. Does that seem to track with the root cause of the problem? That is, that this is an existing requirement, but CAs aren't recognizing it as such? > Step 3: Insert a new paragraph at the end of section 4.9.1.1, with the > following contents (or a reasonable facsimile thereof): This isn't where the suggested requirements go. That's covered in 4.9.5 Did I miss reports where this seemed to be an issue? I didn't really see this one coming up, since 4.9.5 tried to make it pretty clear. Please feel free to highlight the incidents though, I'm happy to take a second look. ___ dev-security-policy mailing list dev-security-policy@lists.mozilla.org https://lists.mozilla.org/listinfo/dev-security-policy