99.8% Security For Real-World Public Keys

An anonymous reader writes "If you grab all the public keys you can find on the net, then you might expect to uncover a few duds — but would you believe that 2 out of every 1000 RSA keys is bad? This is one of the interesting findings in the paper 'Ron was wrong, Whit is right' by Lenstra, Hughes, Augier, Bos, Kleinjung and Wachter. Quoting from the paper's abstract: 'We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for "multiple-secrets" cryptosystems such as RSA is significantly riskier than for "single-secret" ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.'" For a layman's interpretation of the research, the NY Times has an article about the paper. Update: 02/15 01:34 GMT by S : Security researcher Dan Kaminsky has commented on the paper, saying that while the survey work itself is good, it doesn't necessarily support the paper's thesis. He writes, "On the most basic level, risk in cryptography is utterly dominated, not by cipher selection, but by key management. The study found 12,720 public keys. It also found approximately 2.94 million expired certificates. And while the study didn’t discuss the number of certificates that had no reason to be trusted in the first place (being self signed), it did find 5.4M PGP keys. It does not matter the strength of your public key if nobody knows to demand it."

Comments

Re:No security at all...?

[Omnifarious]

Steps:
1. You scoop up all the public keys you can find. People generally publish them. They're public keys.
2. You run GCD on each pair.
3. You find they share a common factor and you win! Both keys are now completely and totally compromised. You know the secret key for both of them.
4. Or... you find they share a common factor of 1. Oh, well, on to the next pair.

Re:This is pretty bad

[Omnifarious]

As an addendum, this means that anything that was encrypted with this public key may now be decrypted. It also means that any signature it's ever made is now suspect as anybody who knew about this problem could've made that signature.

Of course, if someone is a protocol that implements forward secrecy and just using the RSA key to sign a diffie-helman exchange and then using the resulting key from that to encrypt their communications with a block cipher, they might be safe. Of course, the same bug might result in predictable diffie-helman keys too.

But any of those conversations may still have had a man-in-the middle.

Re:This needs a car analogy!

[martin-boundary]

But the situation looks different from an attacker's point of view. The attacker sees 2/1000 guaranteed easy targets, ie it's a fishing expedition which costs about 1000 tries for about 2 successes, so he can budget for the processing power etc.

Moreover, the attacker doesn't care if the ultimate cause of the security failure is the manufacturer or the user or some freak lightning storm. All he cares is that statistically 2/1000 are guaranteed.

Re:This is pretty bad

[Omnifarious]

Does this mean that every key generated has a chance of rendering a previously existing key totally compromised? If that's the case, RSA is actually broken. There are only so many prime numbers, so as more keys are created, more keys will potentially be compromised. Please, tell me I'm wrong (using a car analogy if possible).

It does indeed mean this. But if the keys chosen are really and truly random, the chances of this ever happening are astronomically tiny.

But there are an infinite number of prime numbers. There's even a mathematical proof of this fact. :-)

More practically speaking, the actual distribution of primes is one prime every x/ln(x) numbers. This means that for numbers that are 1024 bits long, one in every 1024 of them is prime. This effectively means that the space of possible 1024-bit primes is 2^1023 (the top bit must always be one) / 2^10 = 2^1013. The chances that any two randomly generated 1013 bit numbers are exactly the same is extremely small. So small that you'd have to generate one such number for every proton or neutron in the solar system before you even got close to entering the realm of writing it down the percentage chance reasonably in non-exponent notation.

So, no, this doesn't break RSA, even though what you say is true.

Re:/dev/urandom vs /dev/random?

[Junta]

The problem with /dev/random is that it frequently is not feasible. The amount of usable entropy in /dev/random is rather low considering some needs. OpenSSL project itself defaults to urandom in fact. Frequently seeding /dev/urandom with /dev/random is a compromise.