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
