Was Whit really right?

A recent paper titled "Ron was wrong, Whit is right" by Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter (http://eprint.iacr.org/2012/064.pdf) presents some disturbing results from their analysis of several million RSA public keys, which they obtained from published databases of key certificates. The authors did what amounts to a sanity check, testing the keys for simple vulnerabilities. Basically an RSA public key is a number that is the product of two large prime numbers. The corresponding secret key is, essentially, either of the two prime numbers. Once one is known, finding the other can be obtained by a simple (for a computer) division operation. The security RSA  depends on the widely-believed difficulty of factoring numbers, that is finding either prime given that you know the product. 

Each prime is supposed to be chosen in a random manner, making duplications unlikely. What Lenstra and his team found was that a surprising number of RSA keys were duplicated in more than one certificate (i.e. both primes were the same). Even more surprising, they found a small but significant fraction (about 0.2%) of RSA keys in their database shared one prime factor with a different RSA key in the database. That's a serious problem because there is a simple and efficient algorithm, known to Euclid, that lets you find a factor that two numbers share.  Looking for dups is easy, just sort the public keys by size. Finding shared factors is a little trickier for such a large collection, but the authors found an efficient way to test all pairs of keys in the database to see if they have a common prime factor.

Some duplicate keys appear to have the same owner, which is harmless enough. But the large number of duplicates, and particularly the keys with one shared prime, are much harder to understand. 

I would like to float one possible explanation that involves a simple, but subtle way to attack computer security: using malware injection to subvert a computer system's random number generation process. All that is necessary is to insert code that intercepts calls to the system's random number generator and replaces the proper returned value with a number generated by an algorithm crafted by the attacker.  This algorithm would be designed to have a relatively small state space, producing say only a few million or even billion possible results. These would appear random enough to simple inspection, but the attacker could test the limited number of possible keys generated using the cooked algorithm to find the correct key, thus defeating all security. Note that this attack does not require the infected computer transmit stolen keys, or logged passwords. Indeed the malware need not communicate with the outside world in any way, making detection very difficult. 

I propose that the Lenstra research may have found a signature of this attack in operation.  That is, the weakness in the substituted random number generator on infected machines may have caused the duplications. Perhaps a statistical model of the types of duplication a random number generator attack might produce could test this hypothesis. 

Lenstra et. al.'s title suggest that, due to their their findings, RSA is less secure than other public key systems, such as Diffie-Hellman. The latter only needs a single secret prime number, hence there can be no shared factors. But If I am correct, those too would have been compromised by random number generator attacks, though in ways that are less evident, since the attacker still has a limited number of possible primes to test.