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.
Any possibility for information to be handed over to them is always worth the low odds.
Twitter supports and protects racists - by smearing their critics with the "Hate Speech" label.
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.
Since this is /., I of course did not RTFA, but...
It should be noted that RSA's security is dependent on Factoring a very large number m (~10^300 or more) which is the product of 2 prime numbers - let's say a and b.
It should be obvious that not all choices for "a" and "b" are good ones. For example if a=3, it's likely the very first thing that an attacker would try when attempting to factor the number. In number theory there are various theorems for factoring when the factors of a number have very special conditions (e.g. one factor is much smaller than the other, or whatever). I would guess that the article is simply an audit of existing crypto-software to make sure that these conditions on a and b were checked before generating m. Sounds like not all of them correctly verified that the primes they were choosing were good ones.
I chalk this up to coding error (more precisely a requirements omission), rather than a flaw in the actual crypto-system.
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
One time pad.. just commit the other half your encoded file to memory, and you're sweeet!
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?
how hard would it be to modify the generation algorithm to perform the same tests they ran and redo the generation until a key passes the test?
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!"
Is there currently an easy way to determine if a/our key(s) are weak in this way and should be replaced?
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.
The whole issue of trust conferred by certificates is wrong. It assumes that because I have the some certificate I am who I claim to be and further that I am trustworthy. A rogue agent can use the certificate without authority because they have access to it internally. It certainly doesn't infer that the agent is trustworthy. The whole model relies on people who have something to gain by deception certifying each other are trustworthy.
"I would like to float one possible explanation that involves a simple, but subtle way to attack computer security: using malware injection to subvert a computer system's random number generation process. All that is necessary is to insert code that intercepts calls to the system's random number generator and replaces the proper returned value with a number generated by an algorithm crafted by the attacker. This algorithm would be designed to have a relatively small state space, producing say only a few million or even billion possible results. These would appear random enough to simple inspection, but the attacker could test the limited number of possible keys generated using the cooked algorithm to find the correct key, thus defeating all security. Note that this attack does not require the infected computer transmit stolen keys, or logged passwords. Indeed the malware need not communicate with the outside world in any way, making detection very difficult.
I propose that the Lenstra research may have found a signature of this attack in operation. That is, the weakness in the substituted random number generator on infected machines may have caused the duplications." (from Diceware blog, with permission)
Apparently, they took the list of keys offline. So how do I know if my key is compromised?