[cryptography] Duplicate primes in lots of RSA moduli

Marsh Ray marsh at extendedsubset.com
Thu Feb 16 12:52:01 EST 2012

On 02/16/2012 11:05 AM, Jeffrey I. Schiller 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.

Are you thinking this is because it causes the entropy estimate in the 
RNG to be higher than it really is? Last time I checked OpenSSL it 
didn't block requests for numbers in cases of low entropy estimates 
anyway, so line 3 wouldn't reduce security for that reason.

> 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]

How often have we seen Linux distros generate SSH keys 2 seconds after 
the first boot?

> 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, the real bottom line is that if a cryptographic
> operation/protocol calls for strong random input, you better provide
> it or your security is significantly at risk.


Trying to reason about which completely broken thing is less-broken is 
madness, unless you're on the attack side.

> Ted Ts'o and I spoke about this the other day (Ted is one of the
> authors of /dev/random, and he is likely reading this list!). One of
> the things that concerns us is the number of virtual machines using
> /dev/random for a random number source.

Don't most Linux distros save some entropy to a file on clean shutdown 
and reload it at the next boot? I know OpenBSD did.

> When it was first written,
> linux (and other Unix like operating systems) ran on bare metal and we
> had a reasonably good understanding of the hardware random sources we
> were using.
> However virtual machines change things. Timing intervals that on bare
> metal are likely "random" are probably less so in a VM context. I
> don't know if anyone has done a good study of how "random" /dev/random
> is in common VM environments.

I played with timing on my hosted VPS of the RDTSC (CPU cycle counter) 
instruction in a tight loop. A few simple bit operations showed visually 
an upper bound of at most 1/5 BoE per RDTSC instruction (when used in 
this manner).

> This concerns me because of the number of TOR nodes that are now
> hosted on Amazon's EC2 (VM) service, particularly since some of the
> adversaries of the TOR network (if that is the right way to describe
> them) are state actors.

Also, it is sometimes possible for an attacker in could environments to 
arrange for his own VM to run concurrently on the same physical CPU as 
his target.

- Marsh

More information about the cryptography mailing list