Hi @all,
if I see it correctly, the main problem with including the debian
blacklists in firefox was size. The inclusion would be important
because otherwise any server that used a weak cert is vulnerable until
the cert is revoked in a manner firefox recognizes or until the cert
expires. There is at least one critical example where this would allow
attacks on a content distribution provider used by many large
companies.
I managed to get the complete openssl blacklist from 32 MB in
compressed form to well below 10 MB in ready-to-use format by using a
binary format that contains only the first few bytes of the hashes. The
probablility of false positives should be very small, as there are
1,84E+19 possibilities for the shortened hash and only 1.2E+06 bad
keys, more on this below. Short: A blacklist of 6 MB would cause some
but very few false positives, 7.2 MB blacklist size should be enough.
Has this any chance of getting included into the main firefox code? I
would probably be able to donate a small C++ module that checks a given
hash against the blacklist very quickly (probably in less than 25
iterations of a loop with just a few comparisons, a single addition, a
single blacklist access and a single division inside the loop)
False positive estimation:
According to my estimates, the shortened hashes should lead to the
following expected numbers of false positives per BILLION random
"innocent" hashes checked against the list:
less than 0.0001 for a blacklist 9.6 MB in size
0.017 for a blacklist 8.4 MB in size
4.3 for a blacklist 7.2 MB in size
1091 (0.0001% of the checked certs) for a blacklist 6.0 MB in size
over 275000 (0.03%) for a blacklist 4.8 MB in size
and an unacceptable false positive rate of over 7% for a blacklist size
of 3.6 MB.
My calculations might be wrong, of course. I assumed 1200000 bad certs
existing, 256^n possible hashes for a length of n bytes per hash (1.2*n
would be the DB size in MB). Then I just calcluated the approx.
probability for a false positive p = 1200000 / 256^n and multiplied it
with one billion.
Binary blacklist generation:
cat openssl-blacklist_0.4.2.tar.gz | gzip -d | tar -xO trunk/blacklists
| perl -e "while (<>) { if ( m/([a-f0-9]{16})[a-f0-9]{16}$/) {print
$1.chr(0x0a);}}" | sort | perl -e "use warnings; use strict;
open(BINBL, '>:bytes', 'binblacklist'); while (<>) { if
(m/([a-f0-9]{16})$/) { syswrite BINBL, pack('H*',$1);}} close(BINBL);"
(beware of weird hacks to get it working with the windows versions of
the tools)
Sincerely,
Jan Schejbal
--
Please avoid sending mails, use the group instead.
If you really need to send me an e-mail, mention "FROM NG"
in the subject line, otherwise my spam filter will delete your mail.
Sorry for the inconvenience, thank the spammers...
_______________________________________________
dev-security mailing list
dev-security@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-security
