[cryptography] Duplicate primes in lots of RSA moduli

Jeffrey I. Schiller jis at qyv.net
Thu Feb 16 12:05:47 EST 2012

Hash: SHA1

(Sorry for the length of this post. If you don't want to muck through
it, at least read the last three paragraphs!).

> It would be silly to speculate on the cause of this, but for mild
> amusement consider the following made-up situation.
> Hypothetically, within an API genRSA(), calls to genPrime() in
> library UNSAFE might use a stale context/seed for generating the
> first prime, and then use a fresh context for the second prime. Two
> successive calls to the API would give the problem, and it would go
> unnoticed as the output moduli would be different.

Everyone on this thread should go read Nadia Heninger's blog entry at:


(short link: http://qyv.me/xlJoa)

She and her colleagues did their own survey of keys and found plenty
of duplicates as well as RSA keys that share a prime. She discusses
how they efficiently tested the RSA keys for shared primes (already
discussed here).

Peter says:

> My thoughts exactly, I've always stayed away from DLP-based PKCs
> (except DH) because they're extraordinarily brittle, with RSA you
> have to get entropy use right just once, with DLP PKCs you have to
> get it right every single time you use them. For embedded systems
> in particular that's just too risky.

Just to make it clear, if you re-use the random input value to a DSA
signature, you not only compromise the signature, you compromise the
private key. In my opinion this makes DSA much more brittle then RSA
(I wrote a paper about this for one of the early NDSS papers).

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, 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.

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

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.


- -- 
Jeffrey I. Schiller
MIT Technologist, Consultant, and Cavy Breeder
Cambridge, MA 02139-4307
617.910.0259 - Voice
jis at qyv.net

Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/


More information about the cryptography mailing list