News for hackers. Stuff that matters.
Re:Ron was Wrong, Whit is Right by a1k0n on Tuesday February 14, 2012 @03:45PM (#3591732)
It was mentioned in the nytimes article, and in retrospect it's fairly obvious: you use the Euclidean algorithm.

If you have n1=p q1 and n2=p q2, so that the prime p is shared between them, then gcd(n1,n2) = p. That only takes a few iterations of bignum modulos to solve.

Re:Ron was Wrong, Whit is Right by nohat on Tuesday February 14, 2012 @04:56PM (#3591968)
Ah, 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.
Re:Ron was Wrong, Whit is Right by a1k0n on Tuesday February 14, 2012 @05:11PM (#3592015)
Hm, that's possible. A comprehensive search over 4 million pairs would be O(16 trillion) operations, so perhaps they gain something by reusing intermediate steps of the gcd, or something? Good point, I'm not sure. The brute-force solution is still not out of the question for a modestly large map-reduce cluster.
Re:Ron was Wrong, Whit is Right by notaddicted on Tuesday February 14, 2012 @05:51PM (#3592171)
Yeah, regarding going ahead with the "naive" search, I'm coming up with a price of 5k to 15k on Amazon EC2 using the cluster compute 8XL instances, and under a month using 10 machines.
Re:Ron was Wrong, Whit is Right by nohat on Tuesday February 14, 2012 @09:00PM (#3592671)
Considering the potential value of some of those rsa keys, that is a quite minimal investment. This might be an in the wild danger pretty quickly.
Re:Ron was Wrong, Whit is Right by tptacek on Tuesday February 14, 2012 @10:18PM (#3592843)
The chances of any one key being compromised are very, very low.

If this is a pattern of simple software flaws, or something environmental like keys generating during cold start entropy starvation, the likelihood of pulling a truly valuable key out of that soup are even lower: generally (not always, but generally) the more valuable keys are generated using very well known software, and under tight process constraints.

So basically you get ~10k random certs that allow you to MITM ~10k random sites. It's not nothing, but criminals have better ways of monetizing attacker effort.

Re:Ron was Wrong, Whit is Right by nohat on Wednesday February 15, 2012 @09:14PM (#3597076)
A lot does depend on the actual circumstances for the bad RNG. If you had a good method of recognizing the valuable sites (anything involving money or maybe email?) it might be more practical considering a botnet would be just fine for this sort of computation.