99.8% Security For Real-World Public Keys 108
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."
No security at all...? (Score:5, Interesting)
Quoting from the NYT article:
They were able to produce evidence that a small percentage of those numbers were not truly random, making it possible to determine the underlying numbers, or secret keys, used to generate the public key.
This is a far cry from "no security at all" if I understand it correctly. Any email encrypted with those keys would still be encrypted. And Joe Random Lurkerr would not be able to decrypt it even if he did intercept it.
However Random Monitoring Agency might amass enough such emails to make a guess at the random number used key generation. You have to have a fairly good sized pool of keys to work from in order to figure out the keys of any single encryption.
The paper goes on to state:
Cryptosystems such as RSA that require, during key-setup, multiple secrets are more aaffected by the apparent difficulty to generate proper random values than systems such as Diffe-Hellman (cf. [8]), ElGamal, and (EC)DSA that require a single secret. For either type of system identical keys can be exploited only by parties that can be identified by searching for the owner of the duplicate. But for the former (RSA) partially identical choices allow any malcreant to commit fraud.
For some values of "Any". You still need a significant number of such RSA keys in which to search for the use of duplicate random numbers.
So DSA keys are safer it would seem.
Slow down (Score:5, Interesting)
It's damn fine survey work, but the conclusions are just strange. More detail here:
<a href="http://dankaminsky.com/ronwhit">Survey is good. Thesis is strange.</a>
Re:No security at all...? (Score:4, Interesting)
Well, left unsaid is just how many trials it takes to determine if the key in question is one of those 2 in 100 that is vulnerable.
And the exact process is still not documented.
Re:No security at all...? (Score:4, Interesting)
So DSA keys are safer it would seem.
DSA has it's own problems. Most notably merely USING your key to generate a signature with a broken random number generator can be enough to reveal it to an attacker. Thankfully PGP doesn't use openssl and while it's POSSIBLE to use the same keys for ssh and pgp the impression I got is that not many people do.
http://rdist.root.org/2009/05/17/the-debian-pgp-disaster-that-almost-was/ [root.org]