[cryptography] Duplicate primes in lots of RSA moduli

Ben Laurie ben at links.org
Thu Feb 16 13:00:45 EST 2012


On Thu, Feb 16, 2012 at 5:05 PM, Jeffrey I. Schiller <jis at qyv.net> wrote:
> What I found most interesting in Nadia's blog entry is this snippet of
> (pseudo) code from OpenSSL:
>
> 1       prng.seed(seed)
> 2       p = prng.generate_random_prime()
> 3       prng.add_randomness(bits)
> 4       q = prng.generate_random_prime()
> 5       N = p*q
>
> In theory line 3 helps improve security by adding more entropy prior to
> generating the second prime Q. However, and this is
> counter-intuitive (like many things in security), it in fact reduces
> security in low-entropy situations. As she explains, a lot of the poor
> RSA keys found *may* be the results of key generations performed by
> embedded devices and things like home routers NOT LONG AFTER THEIR
> FIRST POWER ON. This would be a very low entropy time.[1]
>
> If line 3 was omitted, many devices would have the same key. This
> isn't great, but it is a far better situation then we have now with a
> lot of devices having the same first prime!

However, if line 3 was omitted, then something much worse would
happen: if a process forked, then the new process would produce the
same PRNG stream as the old one.

The problem with the pseudo-code is it doesn't reflect what's really
going on (the text explains it, but not why it does it). The purpose
of the "extra entropy" is to make the two PRNG streams different, not
to increase entropy. You're supposed to have sufficient entropy in the
first place.

So, the underlying issue is not a poor design choice in OpenSSL, but
poor seeding in some applications.



More information about the cryptography mailing list