News for hackers. Stuff that matters.
Re:Flaw found in online encryption method by bo1024 on Tuesday February 14, 2012 @03:16PM (#3591613)
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 understand (and don't think they really explain), but somehow they use the fact that there's lots of keys to find ones with common factors, which allows you to factor both of them. This sounds basically like the Euclidean algorithm but I couldn't tell what method they're using to find them.

Re:Flaw found in online encryption method by jalapeno_dude on Tuesday February 14, 2012 @03:29PM (#3591662)
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) and then calculate the gcds of all pairs of keys. (Presumably they were slightly more clever than this, but it doesn't really matter--doing this is still vastly easier than factoring even a single public key). Whenever they found a gcd that wasn't equal to 1, they'd cracked (at least) 2 keys. And it turns out that roughly 0.2% of the keys could be cracked in this way (for a total of 12720 1024-bit moduli).

As far as I can tell, the problem isn't with RSA itself, but with whatever algorithms are used to pick two random primes to multiply and produce the key (or moduli, whatever)--they don't have high enough entropy and output duplicates ~0.2% of the time.

Re:Flaw found in online encryption method by robrenaud on Tuesday February 14, 2012 @05:38PM (#3592118)
Is it possible/likely that many of these bad pairs are from this debian/openssl bug?

http://taint.org/2008/05/13/153959a.html

Re:Flaw found in online encryption method by serialx on Tuesday February 14, 2012 @08:53PM (#3592654)
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.

pp. 15 http://eprint.iacr.org/2012/064.pdf

Re:Flaw found in online encryption method by lambda on Wednesday February 15, 2012 @12:37AM (#3593171)
They explicitly excluded the Debian/OpenSSL blacklisted keys from their sample before checking for shared factors.