Would it be valuable to set up a service that could check your public keys against a database of others checking for common factors? Or just better to fix the entropy problems and assume the problem doesn't exist anymore?
Flaw found in online encryption method
21–30 of 37 posts
Re: Flaw found in online encryption method
#22Earlier quoted context omitted.
Yeah, and I think they did not do a very good job explaining it in the paper. Perhaps they assume more familiarity than I have. But as far as I can tell, the result is that, of public keys collected "in the wild" show more duplication than should be expected, so the random number generation schemes used are not "random" enough. Is that it, or is there more to the story? (Edit) No, there's more. I don't quite understa…
As far as I can tell, this is what they're doing: if two different keys have a factor in common (i.e. A=PQ, B=PR), then you can use Euclid's algorithm (which just requires repeated subtraction, and is thus really easy) to find P (=gcd(A,B)), and then just use division to find Q (=A/P) and R (=B/P) easily. So what the researchers did, apparently, was to gather all the RSA public keys they could find (6 million or so)…
Is it possible/likely that many of these bad pairs are from this debian/openssl bug?
Re: Flaw found in online encryption method
#23Earlier quoted context omitted.
They do, but they abbreviate it (R.S.A.) To clarify, is this a flaw only in RSA, or RSA and DSA?
the source paper linked in the article says DSA is not affected.
No it certainly does not. This source linked paper in fact says the opposite. Taking time to read the paper results in a fun experiment without any cryptographic breaks. Low entropy randoms = bad keys, for all Asymmetric and Symmetric keys.
Re: Flaw found in online encryption method
#24This is not about some new vulnerability. It is a survey of collected public keys. The main security-relevant conclusion is that some key generators are not using enough entropy. Dr. Lenstra is a co-author of the paper (so it shouldn't be dismissed on the weakness of the reporting). The NY Times and Markoff should both be ashamed for publishing such a misleading article, particularly the title.
I really don't think it is about not using enough entropy. I think that someone took a shortcut and reused private keys without realizing that they were compromising their public keys by doing so.
No, the owners of the vulnerable keys are by all appearances unrelated.
Re: Flaw found in online encryption method
#25Earlier quoted context omitted.
They didn't describe the technique, but the fact that the paper has the keyword "Euclidean algorithm" makes it pretty obvious--they just gathered a list of public keys, took the gcd of all the pairs, and whenever they found a gcd not equal to one, they'd cracked both keys out of that particular pair. See my earlier comment.
I took the 'the straightforward approach would require about ten core-years and would not scale well' to mean they had a more efficient method.
They do, but does it matter? Ten core-years is not a forbidding threshold.
Re: Flaw found in online encryption method
#26Oh these researchers don't understand PR (public relations). Here's an amusing way they could get one hundred fold the publicity that they're getting now without (technically) lying.
They cracked 12720 RSA keys. They could reveal the secret modulus in half the cases (6360 RSA keys) without giving away any indication of how they're doing it.
What they could have done is set up a website titled "RSA Cracker" which reveals one key every 3 minutes over a 2 week period.
At the end of 2 weeks, they could shut down the website without explanation.
Can you imagine the media frenzy that would ensue?
Re: Flaw found in online encryption method
#27Earlier quoted context omitted.
I really don't think it is about not using enough entropy. I think that someone took a shortcut and reused private keys without realizing that they were compromising their public keys by doing so.
No, the owners of the vulnerable keys are by all appearances unrelated.
Huh, I did my back of the envelope wrong when I first decided that wasn't plausible.
Here is a better back of the envelope.
Suppose that we're using a random number generator that has 4 billion possible internal states. (We're using a C integer under the hood.) Suppose that we're having it generate random 256 bit integers, which we then test for primality. The probability of these integers being prime is about 1/log(2256), or about 1/177. So we have around 2.4 million possible prime numbers we can generate from this generator.
A key has 2 of these primes, therefore 2 random keys have 4 possible combinations of their primes that could match, for about 1 chance in 600k of matching. Given n keys, there are roughly n*n/2 possible pairs of keys which might match. It turns out that if you have about 570,000 keys in your overall pool which was made by the same bad algorithm, you'd expect to have roughly 27,000 possible matches.
This is scary. What is even more scary is that if you can identify the bad algorithm in common in this pool of poor choices, it is quite doable to enumerate all possible primes that could be a key. And then rather than just being able to compromise 0.2% of the published keys, you can relatively easily compromise about 4% of them instead.
If they haven't already done so, I would expect interested parties to identify the bad algorithms in widespread use, and enumerate likely to be used primes. The NSA is obvious, but criminal parties with access to a botnet can also perform this operation.
Re: Flaw found in online encryption method
#28This is not about some new vulnerability. It is a survey of collected public keys. The main security-relevant conclusion is that some key generators are not using enough entropy. Dr. Lenstra is a co-author of the paper (so it shouldn't be dismissed on the weakness of the reporting). The NY Times and Markoff should both be ashamed for publishing such a misleading article, particularly the title.
"The New York Times and Markhoff should both be ashamed for publishing such a misleading article, particularly the title"
Yeah, it's definitely misleading but that's the news these days. They have an audience and it's pretty broad. So yeah, to us this is misleading but when you take the audience of the Technology section of the NYT as a whole you really can't expect them to understand anything more complex than the explanation they gave. They're obviously writing for the lowest common denominator here. It sucks but this is nothing new for any publication when it comes to reporting on subjects few people really have a deep understanding of. I don't think this is such a terribly misleading article on the whole. Had this been published in a cryptography journal or some really specialized publication then I'd see where shame would come into play.
Re: Flaw found in online encryption method
#29Earlier quoted context omitted.
As far as I can tell, this is what they're doing: if two different keys have a factor in common (i.e. A=PQ, B=PR), then you can use Euclid's algorithm (which just requires repeated subtraction, and is thus really easy) to find P (=gcd(A,B)), and then just use division to find Q (=A/P) and R (=B/P) easily. So what the researchers did, apparently, was to gather all the RSA public keys they could find (6 million or so)…
Is it possible/likely that many of these bad pairs are from this debian/openssl bug? http://taint.org/2008/05/13/153959a.html
None of the newly found a ected moduli are blacklisted (cf. [24]). Based on this brief analysis,
we conclude that the problem reported in the main body of this paper persists and that the
99.8% security level of 1024-bit RSA moduli is further reduced.
Re: Flaw found in online encryption method
#30Earlier quoted context omitted.
I took the 'the straightforward approach would require about ten core-years and would not scale well' to mean they had a more efficient method.
They do, but does it matter? Ten core-years is not a forbidding threshold.
Not really - it does make a difference between amateur attackers and professional, but the potential value is high enough that there will probably be plenty of well funded attackers.