full-disclosure-uk August 2008 archive
Main Archive Page > Month Archives  > full-disclosure-uk archives
full-disclosure-uk: [Full-disclosure] key blacklisting & fil

[Full-disclosure] key blacklisting & file size (was: OpenID/Debian PRNG/DNS Cache poisoning advisory)

From: Solar Designer <solar_at_nospam>
Date: Fri Aug 08 2008 - 20:04:34 GMT
To: Eric Rescorla <ekr@networkresonance.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:


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/