Re: openssl-blacklist & two keys per one pid

[Bodo Moeller <bmoeller@acm.org>]

On Mon, May 19, 2008 at 02:17:42PM +0200, Florian Weimer wrote:
> * Kees Cook:

>>> The rule is simple. When the ~/.rnd file doesn't exist I get one key and  
>>> in other situation I get another (that listed in Ubuntu  
>>> openssl-blacklist) key. Because of this problem openssl-blacklist has to  
>>> be twice big than openssh-blacklist. I developed simple shell scripts to  
>>> generate list of all key lengths we are interested in. They are attached.

>> Yes, this was realized during the generation of the openssl-blacklist in
>> Ubuntu.  We're expecting to have the more complete lists published soon,
>> for all 3 architectures.

> BTW, it appears that the same blacklist can be used for -3 and -F4 keys.
> (Just in case you haven't checked that already.)

A more elaborate explanation seems in place to make sure that
we avoid uninentionally incomplete blacklists.


I'd expect there to be some significant overlapping between the
blacklists, but these should still be different lists: Many RSA moduli
will appear on both lists, but some will only appear on the  e = 3  list
(option -3) and others only on the  e = 65537  list (option -F4).

This follows from how the RSA keys are generated in the library.
Exponent e is fixed, and pseudorandom primes p and q must be found
such that e is a factor of neither  p - 1  nor  q - 1.  So for
e = 65537,  you'll usually have an acceptable p and q in a single
try.  However, for  e = 3,  you'll relatively often need multiple
attempts to arrive at good primes.

If the first choice of p is such that  p - 1  is a multiple neither
of 3 nor of 65537, then this will generate the same prime no matter
which of these exponents you've chosen.  Similary, if the first p
is such that  p - 1  is a multiple both of 3 and of 65537, you
may arrive at the same value p.  But with some probability p will
differ; and if it doesn't, then with some probability q will differ.


Thus, to get complete blacklist coverage for these two standard
exponents, you'll have to explicitly consider both exponents.

Bodo