Survey is good. Thesis is strange.
(UPDATE: I’ve written quite a bit more about this subject, in the wake of Nadia Heninger posting some fantastic data on the subject.)
Recently, Arjen Lenstra and James Hughes et al released some excellent survey work in their “Ron Was Wrong, Whit Was Right” paper regarding the quality of keys exposed on the global Internet. Rather than just assume proper generation of public key material, this survey looked at 11.7 million public keys in as much depth as possible.
The conclusion they reached was that RSA, because it has two secrets (the two primes, p and q), is “significantly riskier” than systems using “single-secrets” like (EC)DSA or ElGamel.
What?
Let me be clear. This is a mostly great paper, with lots of solid data on the state of key material on the Internet. We’re an industry that really operates without data, and with this work, we see (for example) that there’s not an obvious Debian-class time bomb floating around out there.
But there’s just no way we get from this survey work, to the thesis that surrounds it.
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. What the data from this survey says, unambiguously, is that most keys on the Internet today have no provenance that can be trusted, not even through whatever value the CA system affords. Key Management — as Whit Diffie himself has said — is The Hard Problem now for cryptography.
Whether you use RSA or DSA or ECDSA, that differential risk is utterly dwarfed by our problems with key management.
Is all this risk out of scope? Given that public key cryptography is itself a key management technology for symmetric algorithms like AES or 3DES, and that the paper is specifically arguing for one technology over another, it’s hard to argue that. But suppose we were to say key management is orthogonal to cryptographic analysis, like buffer overflows or other implementation flaws.
This is a paper based on survey work, in which the empirically validated existence of an implementation flaw (12,720 crackable public keys) is being used to justify a design bias (don’t use a multi-secret algorithm). The argument is that multi-secret algorithms cause crackable public keys.
You don’t just get to cite implementation flaws when they’re convenient.
More importantly, correlation is not causation. That we see a small number of bad keys at the same time we see RSA does not mean the latter caused the former. Alas, this isn’t even correlation. Out of 6,185,372 X.509 certificates seen by the survey, 6,185,230 of them used RSA. That’s all of 142 certificates that didn’t. We clearly do not have a situation where the choice of RSA vs. otherwise is random. Indeed, cipher selection is driven by network effects, historical patents, and government regulation, not the roll of the dice even mere correlation would require.
Finally, if we were to say that a cipher that created 12,720 broken instances had to be suspect, could we ever touch ECDSA again? Sony’s Playstation 3 ECDSA Fixed Nonce hit millions of systems around the world. Thus the fault with this whole “multi-secret” complaint — every cipher has moving parts that can break down. “Nothing is foolproof because fools are so ingenious”, as they say. Even if one accepted the single-sample link between multi-secret and RSA, the purportedly safe “single-secret” systems have also failed in the past, in quite larger numbers when you get down to it.
I don’t mean to be too hard on this paper, which again, has some excellent data and analysis inside. I’ve been strongly advocating for the collection of data in security, as I think we operate more on assumption and rumor than we’d like to admit. The flip side is that we must take care not to fit our data to those assumptions.
Apparently this paper escaped into the popular press.
I think the most important question to be asked is — if 0.2% of the global population of RSA moduli are insecure, what about those attached to unexpired certificates with legitimate issuers? Is that also 0.2%, or less?
(There’s no security differential if there was no security to begin with.)
Dan Kaminsky's Blog 
The survey’s abstract indicated two per thousand, or 0.2%, rather than 0.02%.
Not that it makes their conclusion any more logical, but I was surprised by the number of bad keys.
Er, fixed.
I’m not surprised by bad keys, unless they’re attached to otherwise good certs.
Generating truly random numbers is not a trivial issue. Could these .2% vulnerable keys be accounted for by earlier problems with key generation?
How many times have I read about how many bind servers are vulnerable because the servers are not being updated… If you compare the percentage of bind servers that are vulnerable with the percentage of keys that are vulnerable, I am surprised the number isn’t much higher.
I’d really like to know what commonalities (if any) those weak keys share: e.g. are there any specific web hosts over-represented? Specific SSL appliances? Software/versions of software? For all we know there are a few poorly run/built web hosts out there with certificate generating tools responsible for most of these weak certificates. Or these certificates have nothing in common really other than generally weak RNG’s? Not enough data has been released to reach any conclusion yet.
Is there a tool available to test keys? I have quite a number of OpenSSL and GPG public keys and knowing if they’re useless would be useful.
What is the source of these busted keys? Are they just the left overs from when a few distros were generating flawed keys?
As Dan and I just discussed on Twitter, the situation here is very simple: some manufacturers re-use private keys. From the paper, pages 5-6: “…many of the duplications are re-certi cations or other types of unsuspicious recycling of the same key material by its supposedly legal owner.”
It doesn’t matter what algorithm you use if you re-use the private key. The duplicates here just demonstrate how often manufacturers re-use keys. They don’t demonstrate anything about random number generators or anything else mathematical.
All well and good. But implementations should not allow such “naive” re-use in the first place.
I am sorry, but could you pundits even be bothered to actually read the paper? The ingenious insight of this paper is not at all about duplication of private keys but about the implications of non-uniform random number generators for cryptographical weaknesses of multi-secret keys. Not one of your lines actually suggests that you understand what this theoretical weakness of multi-secret keys is.
This is a work by actual cryptographers, guys, not cryptosystem designers unaware of the actual theoretical properties of the ciphers they are using.
Read my post. I’m not talking about duplication of private keys. I’m talking about the specific blame on RSA, as if single secret systems are immune to non-uniform random number generators. The attack basically allows large numbers of n (p*q) to be compared against one another to find repeated p’s or q’s. In a single secret system, instead of a repeated p or a repeated q, you just have a repeated s.
Easier to notice, sure. But deadly nonetheless.
Just because you’re a cryptographer doesn’t mean you understand larger security implications. I am going to make a clarifying post though, mostly because there are some important things to learn from this paper beyond “it’s not just RSA that can’t handle bad RNGs” (a fact that we learned quite well with the Debian bug).
The reason for the emphasis on RSA is that if you find 2 RSA moduli that share a common factor (e.g., n1 = p * q1, n2 = p * q2), it’s trivial to use extended gcd to factor the two moduli and find p, q1, and q2. This apparently occurs in 0.2% of all keys in their dataset.
With something like ECDSA, if two parties have the same public key, then they can almost certainly read each others secrets. However, that doesn’t help a 3rd party in figuring out the private key.
Your point that good random number generation is well taken, and I don’t think this paper makes a very compelling argument for preferring ECDSA over RSA. The NSA’s paper “The case for Elliptic Curve Cryptography” has a stronger argument.
Still it is interesting to read that ~0.2% of RSA keys have different moduli but share a common factor.
There’s more than just reuse of the private key going on. There’s reuse of private key components (regeneration, really, from fixed entropy) and that reuse is remotely detectable and correctable. More later today.
You are being too critical of the paper. These shared prime moduli create exploitable security holes. The data in appendix A clearly show that this is an ongoing problem with new certificates. The identity of vulnerable certificates has not been released for good reason.
“This may indicate that proper seeding of random number generators is still a problematic issue.” Yes, the use of local entropy in seeding RN generators must be improved.
The paper really wants to insist that this is a problem with RSA, which is silly. Bad RNG affects all ciphers. I agree this is an issue though, and I’ll be writing more on this later today.
I agree that, in the face of questionable RNGs, yes, all ciphers will be affected.
The conclusion of the paper is that RSA is particularly vulnerable to this because you may actually hurt some innocent bystander by generating a new key. No other crypto system has this “feature”.
The bottom line is fix your RNG and you can be safer (in the face of a questionable RNG) if you use DSA.
I’d be curious to know if the random source (hardware, TPM, crypto HW card, software-implemented RNG) is even the issue. On a system that provides the greatest possible RNG entropy, if the certificate-issuing library above the crypto primitives is re-using key material, it is not the fault of the RNG. For all we know, that 0.2% of RSA certs in question were created by a single flawed library circulating out there that was compiled with some debug code that never got removed. (Just reading the news accounts, I guess I’d better read the paper too.)
Yes, the conclusion seems like quite an exageration. Consider also the authors’ emotive language in the passage “What surprised us most is that many thousands of 1024-bit RSA moduli … offer no security at all.”
Security professionals take lay people (especially sales & marketing) to task if they ever suggest that such and such is perfectly secure. We all preach that nothing is ever 100% secure. But equally, very few things are 0% secure. So it’s very poor form to describe those keys as providing “no security at all”. It will still take a non-trivial effort to exploit the weaknesses exposed by the authors.
I was baffled by the “two secrets” claim myself. I think the argument is that Alice can use both her p and her q to test against others’ moduli. The chance of a collision (whether good or bad RNGs are used) is much higher with RSA than with “single secret” systems.
But if that is a correct characterization of the argument, it still doesn’t make sense to me. Alice could just as easily generate a p and q (and an r, s, …) to test against the moduli of the world. They don’t have to be her own. That is, collisions of a single prime don’t give any particular advantage that you wouldn’t have if there was no collision.
Anyway, I may be mischaracterizing the argument. Maybe I’m trying to make sense out of something that makes no sense, or maybe I’ve just missed the plot entirely.
Reblogged this on lava kafle kathmandu nepal and commented:
latest prime numbers RSA repitition and possible elevation