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

No security at all...?

[icebike]

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.

Re:No security at all...?

[Spykk]

If what that quote says is true and you could derive the secret key from the public key then one could say that the key is worse than no security at all. Public keys are, by definition, public. They are generally available to the public at large on keyservers like http://pgp.mit.edu./ You wouldn't need to intercept any messages because you could use the public key to encrypt any number of examples. The false sense of security presented by encrypting something with one of these flawed keys would make them very dangerous indeed.

Re:No security at all...?

[uncmathguy]

Surely if the authors found these useless keys, a bad guy could too, using the same publicly available lists of keys. Or am I missing something? Once the bad guys know which keys are bad, anything "secured" with those keys would be vulnerable. Sounds like "no security at all" is about right. Of course people who don't want to go through the few hours it took the authors to search the public keys would still not be able to access your transmissions, but those aren't the people for which the security is put into place.

Re:No security at all...?

[Omnifarious]

Flaw in random number generator + euclid's algorithm = known factors for public keys = totally broken public key.

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.

Re:No security at all...?

[ceoyoyo]

Worse, the attacker could sign things that looked like they came from you.

Re:No security at all...?

[icebike]

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...?

[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:No security at all...?

[Omnifarious]

They did find the underlying numbers. The article basically tells you exactly what they did. They mention Euclid's algorithm and for anybody who knows how RSA works, it's obvious what they did. And what they did would result in them discovering the underlying numbers directly.

Re:No security at all...?

[petermgreen]

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/

Re:No security at all...?

[postbigbang]

Pseudo-random number generation is a problem that's been seen before. That numerous machines can be at a point where their seed is odd means that an additional factor, like a time-date hash, could re-randomize the key, thus reducing the attack set.

I wonder if it's specific to one platform or another....

Re:No security at all...?

[TheRealMindChild]

This isn't about psuedo-number generation, it is about using a seed that is easy to determine.... like 0.

The claim that random number generation using the timer/tick count can be easily guessed is, at best, misleading. Your application has no idea what services are running, what priorities they are running at, etc, and to discover those would add even more entropy to the situation as it takes even more unknown amount of system time to determine their impact

Re:No security at all...?

[muckracer]

> Worse, the attacker could sign things that looked like they came
> from you.

Hey, I wrote that!! :-O

Slow down

[Effugas]

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>

Re:Slow down

[Z00L00K]

And how can we trust the certificate authorities these days?

The current model is sensitive to security breaches at the CA:s and the general public has no control over which CA that is playing under the cover with which government.

Where is this finger pointing?

[kanoalani]

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.

Re:Where is this finger pointing?

[viperidaenz]

Is that the one along the lines of
int rand() {
return 3;// completely random seed, chosen by a roll of a dice
}

Re:Where is this finger pointing?

[hawguy]

Pretty sure this is the debian bug where the relevant packages for whatever reason decided to use a static number for the rng seed. There is an xkcd which pokes fun at this.

Oh good, it's not too late to post the obligatory XKCD link:

http://xkcd.com/221/

Re:Where is this finger pointing?

[Anonymous Coward]

First, if this were the Debian bug, I feel like they would have said so. I assume there is some other issue. I could be wrong though.

My understanding of the Debian bug was that the OpenSSL key generation code had a bug where /dev/random (or /dev/urandom, whichever it actually used) was being read incorrectly but in a way that happened to work. The line that read the random seed appeared to be dead code despite happening to accidentally read in the random seed, so the Debian maintainer for the package deleted the line. The randomizer was also seeded with the PID of the process, so there was still some randomness (i.e. the bug was not made obvious by the exact same key getting generated every time), but little enough that brute forcing all of the keys became trivial.

See this blog article for a description of the events. Another blog post linked to this bug report in which the OpenSSL team claims the bug is in Valgrind/Purify, not in OpenSSL. I have not recently tried to read the code in detail, so I do not remember if there is actually a right way to fix the Valgrind/Purify warnings.

This needs a car analogy!

[khasim]

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.

Re:This needs a car analogy!

[karnal]

But at some point you want to fix the source, as it's cheaper and easier from a security (and a physical) perspective to fix it there.

To take your example into account - say Toyota is building a line of Camry cars out of building X. 998 of 1000 have good brakes. They are interested in fixing the cars that are broken, but they're also going to launch an investigation as to why they're broken in the first place. In this case, could be a bad supplier shipping slightly out of spec parts; could be a worker on the line who is dissatisfied with his/her job. That's where fixing the system comes into play - if the system works as it should, then there's no cars to fix (in an ideal world - and that's what we try to get to with security as well.)

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.

This is pretty bad

[Omnifarious]

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.

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 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:This is pretty bad

[fatphil]

This is the third time you've posted your totally useless (or "naive" as Lenstra calls it in his paper) algorithm. Your technique would take 10 years (I trust Lenstra's estimate, I've not verified it myself) on his data set.

Re:Can someone explain this to me?

[YoungHack]

The process of finding that one of P or Q matches actually tells you that P or Q. That means instantly that both public keys can be factored. Hence both private keys can be determined. You don't need prior knowledge of either private key ahead of time, just the public keys.

Re:Can someone explain this to me?

[russotto]

So are these keys a sign of weaknesses in specific implementations of RSA key generation or could they have arisen by pure chance due to 2 random number generators picking the exact same number (or is it a combination of both)?

The primes for RSA-1024 should be 512 bits long. There are about 2^502 primes 512 bits long. By birthday paradox statistics, we should expect a collision in approximately every 2^251 choices, which is considerably less than 2 in 1000.

So no, it's not chance.

(all numbers extremely approximate)

No reason to be trusted in the first place

[rdebath]

"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 ?

Re:Self-signed certificates

[TheLink]

And you may trust it more than you trust a CA signed cert.

It does not matter the strength of your public key

[KlaymenDK]

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).

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.

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

[Man Eating Duck]

Frequently seeding /dev/urandom with /dev/random is a compromise.

That is interesting, how often is "frequently"? Can you increase randomness significantly by seeding from urandom, say, every 100 reads from random? Does this question even make sense? :)

I tried to google for more details, but my search terms returned a lot of noise.

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

[John Hasler]

> That is interesting, how often is "frequently"?

IIRC urandom reseeds itself whenever there is entropy available but free runs when entropy runs out instead of blocking as random does. Thus until the entropy pool runs dry the two are the same.