Slashdot Mirror
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."
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.
Sig Battery depleted. Reverting to safe mode.
I'm not seeing any data on what portion of those keys with bad moduli were actually attached to valid certificates.
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>
There's not published any mathematical proof of that RSA 4096-bit is broken, so that, it's suppossed to be secure for a short time, one week, or one month, or one year, or one century.
JCPM: crackers aren't fool, they pick 100 best richest people for lottery of breaking 2 of their 100 credit cards (VISAs).
I didn't find any discussion of what may have caused the lack of randomness. Presumably it was a particular implementation on a particular platform of RSA key generation and presumably they know what it is. I would be interested to know too.
Suppose someone checks thousands of cars and finds that 998 out of every thousand cars checked had good, working brakes.
But 2 out of every thousand cars checked had bad brakes.
Is the braking system on cars broken?
Or do we need to find out how and why those particular cars have problems? I vote for this one.
I've seen a *lot* of people take shortcuts like feeding in a well-known arbitrary piece of data as an entropy source in a script invoking SSL utilities. They will complain that '/dev/random is too slow (implicitly not realizing the urandom option)' or 'I wanted a script that would work exactly the same in all platforms and this happened to work'. Out of a plethora of better ways to do it they happen to pick the worst because they simply fail to understand the significance of the random source.
XML is like violence. If it doesn't solve the problem, use more.
It doesn't affect the security of RSA overall, but it strongly affects the security of certain keys, rendering them totally compromised.
Think about it. A flaw in random number generation may well result in several people independently picking the same factor for their public key. Just run euclid's GCD algorithm on all pairs of public keys, which is O(n^2 * m) where n is the number of keys and m is their average length. Poof, all the ones that managed to 'accidentally' share a factor with another one pop out with their factors since a public key is just two big prime numbers multiplied together. Game over for those keys.
Steps to exploit:
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.
Need a Python, C++, Unix, Linux develop
They've identified that there MAY be a problem.
But they haven't identified the source of the problem.
Is it a certain make/model of Toyota?
Is it a certain rotor from a manufacturer that is in different makes/models?
Is it user error?
Until they identify the source (sources?) of the problem then they cannot say that X is "broken". Because X seems to work in 998 out of 1,000 cases.
So what is the difference between the 998 cases and the 2 cases?
is too important to be left to chance."
Robert R. Coveyou
From what I know about RSA, the security comes from having 2 large secret prime numbers (call them P and Q).
From reading this new paper, what these guys have been able to do is to take a pair of public keys and identify if one or both of the large secret prime numbers is the same between both keys. Am I reading things right, is this what they have found?
And just how dangerous is it in the real world? I would assume that unless you can find (using this new discovery) a public key where one or both of P and Q match a key you already have the private half of, you cant decrypt.
I trust my self-signed certificate.
I have found there are just two ways to go.
It all comes down to livin' fast or dyin' slow. -REK, Jr.
"No reason to be trusted in the first place (being self signed)."
At first this struck me as wrong. Mostly because all CA certificates are self signed.
The I found a question, "why don't the CAs sign each other's certificates?"
It's possible, they just never do it.
Is it perhaps that they don't trust each other!
If they don't trust each other why should we trust them ?
They will complain that '/dev/random is too slow (implicitly not realizing the urandom option)'
Please help me understand this bit. It sounds as if you would prefer urandom over random. I'm not skilled in randomness on Linux, so I checked Wikipedia (emphasis mine):
[...] A counterpart to /dev/random is /dev/urandom ("unlocked"/non-blocking random source) which reuses the internal pool to produce more pseudo-random bits. This means that the call will not block, but the output may contain less entropy than the corresponding read from /dev/random. While [/dev/urandom] is still intended as a pseudorandom number generator suitable for most cryptographic purposes, it is not recommended for the generation of long-term cryptographic keys. [...]
That, to me, sounds as if one should not use urandom if random is as all feasible.
So what's the deal here?
"Good news, everyone!"
It does not matter the strength of your public key if nobody knows to demand it.
THIS! This is the core problem! Everybody knows email, and most people know that you shouldn't share your password with others, but nooobody knows about proper signatures and how to work with them.
If each and every digital signature out there was useless, how much of our total bandwidth would be compromised?
The painful answer is, at most the percentage that is signed in the first place, which is a drop in the proverbial ocean.
Cory Doctorow has a statement about obscurity being a far bigger threat to authors than piracy, and I posit that an analog can be drawn for obscurity of security practices, the population at large, and privacy/security.
It's hopeless to encrypt all your email unless your peers (including granny and junior) knows how to process such email, and knows to be suspicious of unsigned communications. If only some of the globally popular communications services would have the guts to enable, and indeed, enforce this. (Google and Facebook, I'm looking at you.) Yeah I know, they wouldn't be able to stay in *business* if they did that (which nicely highlights what, or rather who, the "product" really is).
"Good news, everyone!"
I know about at least one public key that was intentionally created very weak, that is, one that is easily crackable.
Why was it made? As a part of "hacking" competition.
I wonder how many of the keys they found were bad were never used for anything serious, like the one I mentioned.
Apparently, they took the list of keys offline. So how do I know if my key is compromised?