key blacklisting & file size (was: OpenID/Debian PRNG/DNS Cache poisoning advisory)

[Solar Designer <solar () openwall com>]

On Fri, Aug 08, 2008 at 11:20:15AM -0700, Eric Rescorla wrote:
> Why do you say a couple of megabytes? 99% of the value would be
> 1024-bit RSA keys. There are ~32,000 such keys. If you devote an
> 80-bit hash to each one (which is easily large enough to give you a
> vanishingly small false positive probability; you could probably get
> away with 64 bits), that's 320KB.

Regarding blacklist file size, we (Openwall and ALT Linux, with support
from CivicActions) have done some work on SSH key blacklisting, and our
encoding scheme should be reusable for SSL as well.  Our default
blacklist file contains 48-bit partial fingerprints for 1024-bit and
2048-bit RSA and 1024-bit DSA keys for PID range 1 to 32767 (a total of
almost 300k keys).  The installed file size is just 1.3 MB, which
corresponds to less than 4.5 bytes per fingerprint, and the .bz2 (and
.rpm) is just 1.2 MB.  (Naturally, with non-compressing binary encoding
the 48-bit fingerprints would be 6 bytes each.)

Lookups are very quick, and only three small portions of the file are
read per lookup, for a total of under 100 bytes of data to read (as far
as sshd is concerned).

Neither the code nor the file format is specific to 48-bit partial
fingerprints; it is possible to use larger ones by supplying something
other than "6" (the size in bytes) on blacklist-encode's command-line.

This code is currently in use in Openwall GNU/*/Linux (Owl) and ALT Linux
distributions, and it has successfully caught some weak SSH keys in the
wild.  Other systems/projects/whatever are more than welcome to reuse
the code or the encoding scheme.

My original announcement on oss-security:

        http://www.openwall.com/lists/oss-security/2008/05/27/3

Dmitry V. Levin's follow-up with URL for forward-port of the patch to
newer OpenSSH:

        http://www.openwall.com/lists/oss-security/2008/05/27/4

-- 
Alexander Peslyak <solar at openwall.com>
GPG key ID: 5B341F15  fp: B3FB 63F4 D7A3 BCCC 6F6E  FC55 A2FC 027C 5B34 1F15
http://www.openwall.com - bringing security into open computing environments

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/