Thursday, February 16, 2012

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.

No comments:

Post a Comment