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 [email protected] https://lists.mozilla.org/listinfo/dev-security-policy
