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

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./ [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.

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.

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

[ceoyoyo]

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

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: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

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