-----BEGIN PGP SIGNED MESSAGE----- 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: https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs (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. -Jeff - -- _______________________________________________________________________ Jeffrey I. Schiller MIT Technologist, Consultant, and Cavy Breeder Cambridge, MA 02139-4307 617.910.0259 - Voice [email protected] http://jis.qyv.name _______________________________________________________________________ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iD8DBQFPPTdm8CBzV/QUlSsRAkbsAJsEzUtfSlMwk1coiAqELv8AJaseLwCdGApp eSLeCxne6d36Edh0pTWZ0yM= =vmpC -----END PGP SIGNATURE----- _______________________________________________ cryptography mailing list [email protected] http://lists.randombit.net/mailman/listinfo/cryptography
