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.