More on the danger revealed by duplicated keys

In my last post, I suggested that the existence duplicate keys generated by a particular device could lead an attacker to reverse engineer that device to learn the details of its entropy generation weakness. He could then replicate that weak process to generate large numbers of RSA keys and see if they match RSA public keys that haven been published or obtained some other way.  One can do even better, however. Instead of generating RSA keys to test, just generate primes, following the method the device uses to generate the first prime of an RSA pair. There is no need to spend time generating the second prime and forming the product. Each prime generated would then be tested to see if it divides any of the real RSA keys.  As Heninger points out, this test can be performed fairly quickly on all the keys at once by computing the product of all the real RSA keys.  

There is a further speed up possible. In generating primes to create an RSA key, one selects an odd number from some starting point (ideally random) and tests that number for primality, repeating the process until a prime is found. Getting certainty or a very high probability that a trial number is indeed prime takes considerable computation, involving a series of ever more stringent and expensive tests, see for example http://www.openssl.org/docs/apps/genrsa.html. For our purposes, however, a lower probability of primality suffices. The risk is that by limiting the testing, we might select a prime that the real software would have rejected and thus possibly miss a factorable key.That risk should be balanced by the possibility of testing many more keys. 

Another possible speed up might be to multiply a large number of test keys together and test their product against the product of the real keys in one big operation using a GCD algorithm. If a divisor is found, it can then be tested again the real keys to find the one (or more) that is broken. 

Testing candidate RSA primes is likely the most expensive computation in this process. However that operation is easily distributed to many processors working in parallel and might even be suitable for implementation on General Purpose Graphics processors (GPGPUs). Several groups have worked on using GPGPUs for modular arithmetic on large numbers of the type involved in primality tests. For a nice review, see:

http://brage.bibsys.no/hig/bitstream/URN:NBN:no-bibsys_brage_15987/1/Implementing%20modular%20arithmetic%20using%20OpenCL.pdf

However, the work I've seen attempts to use all the GPU processors for a single large number modular multiplication. It might be faster to test many candidate primes at once, perhaps from different entropy starting points, each on its own graphics processor, or SIMD unit.

Absent the hard work of implementing these suggestions, their potential to break real RSA keys is speculative. However, the possibility of such an attack is real enough to convince me that all keys generated by devices that have exhibited inadvertent key duplication are suspect and should be replaced as soon as possible. In my next post, I plan to offer some suggestions for generating enough strong entropy prior to key generation on systems that allow manual entropy input.

Duplicate keys could be a sign of exploitable weakness

In my previous post, I may have understated the danger of duplicate RSA keys. Here's what I said:

 "Say the entropy pool is nearly empty at the start. Then there is a good chance two different users, Adam and Alfred, using method A could generate the same two primes, and would have the same public key. That means Adam could read Alfred's mail, forge his signature and vice versa. Poor security to be sure, and anyone could find out this had happened by inspecting a public key database. But only Adam and Alfred can take advantage of the security hole, and if both Adam and Alfred are good guys, it's not that likely to be a problem.  It's like discovering two people in your town have the same front door key."

That's true as far as it goes, but discovering the existence of shared RSA keys is a clue that a weak source of entropy may had been used in generating them. If they were both created by the the same security appliance, say a particular brand of firewall, an attacker could purchase the same device and attempt to recreate the shared key by restarting the device multiple times. Collecting all available duplicate keys from the same appliance would allow them to be attacked together. But why stop there? By collecting every public key available that was generated from the same appliance, an attacker would likely discover many more keys that were created from the weak entropy pool, but had not been duplicated. With some more effort, the attacker could reverse engineer the key creation mechanism and its entropy pool weakness, allowing much faster attempts to find the vulnerable keys. They could generate hundreds of millions of keys and see which matched published or intercepted public keys. 

So the existence duplicate keys are a tell-tale that more weak keys are out there that are ripe for attack. Once the details of the poor entropy collection are known, even single-secret public keys, such as Diffie-Hellman or DSA, might be subject to such attacks. This weakness is not the instant fail of a single shared prime, but it may have broader impact. Discovering two people in your town have the same front door key could tell a thief that their locks are easy to pick.

More on the RSA shared prime story

A new blog post by Nadia Heninger https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs provides an expiation for most of the strange results reported by Lenstra et al. that my previous blog post discusses. It seems almost all of the duplicated and factorable RSA keys were generated by security appliances like firewalls and routers. These typically have poor access to entropy, particularly when they first start up, and often that is when they generate their public key pairs. 

In particular, she offers a simple explanation of the shared prime problem, based on two snippets of pseudo-code for generating an RSA key:

// method A:

seed_random_number_generator (entropy-pool)

P=generate_random_prime ()

Q=generate_random_prime ()

public_key=P*Q  

// method B:

seed_random_number_generator (entropy-pool)

P=generate_random_prime ()

add_entropy_to_pool (whatever)

Q=generate_random_prime ()

public_key=P*Q  

At first glance method B seems more secure. We want our primes to be random and adding more entropy to a random number generator can only make things better, right? Had you asked me yesterday I might have agreed. Wrong!

Say the entropy pool is nearly empty at the start. Then there is a good chance two different users, Adam and Alfred, using method A could generate the same two primes, and would have the same public key. That means Adam could read Alfred's mail, forge his signature and vice versa. Poor security to be sure, and anyone could find out this had happened by inspecting a public key database. But only Adam and Alfred can take advantage of the security hole, and if both Adam and Alfred are good guys, it's not that likely to be a problem.  It's like discovering two people in your town have the same front door key. 

Now suppose Ben and Bill use method B. There's a good chance they will share the same first prime, P, but their second prime, Q, is likely to be different. Again anyone could find out this had happened by inspecting a public key database, but in this case, once they do that, they can easily break both public keys using Euclid's two thousand year old GCD algorithm. So anyone, not just Ben and Bill, can take advantage of this security hole. It's like publishing a hi-def photo of your front door key on Flickr, allowing anyone to make a copy.  

Security software isn't easy.

So the problem does not seem to be the Random Number Generator Attack I speculated on yesterday, but that attack mode is still a real threat. Heninger has notified the manufacturers of the security devices she found to have this problem.  Whether they will be more responsive to this threat than they have been so far to the WPS problem that I blogged about in January remains to be seen.

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.