6 ms·

The article says 400K revoked certificates leading to 51MB uncompressed bloom filter. That's like 133 bytes per certificate, which seems wrong. Am I missing som

by gorset 15y ago

The article says 400K revoked certificates leading to 51MB uncompressed bloom filter. That's like 133 bytes per certificate, which seems wrong. Am I missing something? If 1 out of 1024 false positive is the target, then using 8 bytes per entry should be more than enough, which gives ~3MB of data without any magic. The article is a bit untidy, so it would be nice to get a clearer picture of the sizes of the different approaches.

davidst 15y ago
You're not missing anything. I don't want to knock the author because there's a lot of good stuff here that is well-worth reading but in this case I think he got a little carried away and missed the obvious, simple solution.
gjm11 15y ago
That's an uncompressed Bloom filter with a single hash function. To get a false-positive probability of p with a single hash function you need 1/p bits per entry. But that's the uncompressed filter. It compresses way, way down: to about 8 bits per entry. That gives 400KB of data, still with a 1/1024 false-positive rate. Much better than 3MB. If you consider (uncompressed) Bloom filters with arbitrarily many hashes, the best you can do for a false-positive rate of 1/1024 is about 14 bits per entry.
agl 15y ago
I lost several people at that point, so I clearly didn't communicate that point well. Sorry about that, I'll see if I can tweak it tomorrow. But the point was that you can beat a Bloom filter on size, for the same performance, if you use only a single hash function (making the Bloom huge) and then compress the result. Of course, you lose the random access in that case and, if you're looking at processing the whole thing for a lookup, then the volume of the uncompressed data becomes a concern. Thus the GCS...
- gorset 15y ago
  Thanks. Which values are you using for the matching? I was assuming a fingerprint of the cert. Have you considered compressing the domains? Compiling them to a DFA should yield a very small structure, and you then will need far fewer bits for the actual fingerprint.
  - agl 15y ago
    We can only use the information that the CAs give us, which is the serial number of the certificate. So we match the serial number and issuer.
  - MichaelGG 15y ago
    If you use the domains, then any domain that ever had a cert revoked would hit, and need a secondary lookup. That means some of the busiest sites on the Internet would not benefit from this check. Also, I think if you re-issue or otherwise change your cert, the old one goes into the CRL, even if it wasn't for a compromise, right? (Which would explain a high number of revocations?)

by gorset 15y ago

davidst 15y ago

You're not missing anything. I don't want to knock the author because there's a lot of good stuff here that is well-worth reading but in this case I think he got a little carried away and missed the obvious, simple solution.

gjm11 15y ago

That's an uncompressed Bloom filter with a single hash function. To get a false-positive probability of p with a single hash function you need 1/p bits per entry. But that's the uncompressed filter. It compresses way, way down: to about 8 bits per entry. That gives 400KB of data, still with a 1/1024 false-positive rate. Much better than 3MB. If you consider (uncompressed) Bloom filters with arbitrarily many hashes, the best you can do for a false-positive rate of 1/1024 is about 14 bits per entry.

agl 15y ago

I lost several people at that point, so I clearly didn't communicate that point well. Sorry about that, I'll see if I can tweak it tomorrow. But the point was that you can beat a Bloom filter on size, for the same performance, if you use only a single hash function (making the Bloom huge) and then compress the result. Of course, you lose the random access in that case and, if you're looking at processing the whole thing for a lookup, then the volume of the uncompressed data becomes a concern. Thus the GCS...

gorset 15y ago
Thanks. Which values are you using for the matching? I was assuming a fingerprint of the cert. Have you considered compressing the domains? Compiling them to a DFA should yield a very small structure, and you then will need far fewer bits for the actual fingerprint.
- agl 15y ago
  We can only use the information that the CAs give us, which is the serial number of the certificate. So we match the serial number and issuer.
- MichaelGG 15y ago
  If you use the domains, then any domain that ever had a cert revoked would hit, and need a secondary lookup. That means some of the busiest sites on the Internet would not benefit from this check. Also, I think if you re-issue or otherwise change your cert, the old one goes into the CRL, even if it wasn't for a compromise, right? (Which would explain a high number of revocations?)