RSA is firing back at researchers who claim in a paper that its\u00a0flagship crypto system is damaged goods. But the report is still difficult to dismiss.\tMy colleague Ellen Messmer\u00a0wrote about RSA's reaction, saying, "EMC's RSA\u00a0security\u00a0division struck back by saying the paper's results don't indicate a fundamental flaw in the RSA algorithm but more likely a problem with implementing it." From her report:\tAri Juels, chief scientist for RSA, told Network World that "the study is useful" as it pertains to the "failures of crypto protocols during random-number generation." But he faults its core idea that the RSA algorithm is somehow fundamentally flawed.\t"I'd say all cryptography relies on good true random-number generation. And when that goes wrong, the protocol breaks," Juels says. He faults the conclusions of the paper that there was something intrinsically wrong with the RSA algorithm. The paper might have found that the RSA algorithm "might be a little less robust than another one," but "it's obviously not a problem with the RSA algorithm, it's the way the keys were generated."\tHe said this is not an issue that goes unrecognized today in industry, and Intel is in fact building a fast random-number generator in its upcoming Ivy Bridge chip.\tRSA was not apprised of the paper before it appeared online.\tIn its formal statement, RSA did not dispute specifics in the paper, which was authored by Arjen Lenstra, James Hughes, Maxime Augier, Joppe Bos, Thorsten Kleinjung and Christophe Wachter. The paper sought to look at the security tied to millions of public X.509 certificates that they collected across the web. Based on the data they collected, they concluded "1,024-bit RSA provides 99.8% security at best."\tThe research group of cryptographers said they collected 6.4 million distinct X.509 certificates and PGP keys containing RSA moduli, and in analyzing their enormous cache, found duplicate RSA-moduli keys about 1% of the time.\t"More seriously, we stumbled upon 12,720 different 1,024-bit RSA moduli that offer no security," the researchers said in their paper, which is titled "Ron was wrong, Whit was right" a reference to Ron Rivest, co-inventor of the RSA algorithm, and noted cryptographer\u00a0Whitfield Diffie. The paper leveled a devastating critique against RSA as fundamentally flawed.\tI must say though, having combed through this paper myself, that these are some of the most illustrious cryptographers in the world. They are not given to FUD\u00a0or thinly-drawn conclusions. They also go out of their way to point out that this is not a sky-is-falling issue for users -- yet.\tThe full report is available here. Also, there's a decent breakdown of the findings in the Freedom To Tinker blog. Here are some bits from that post:\tWe have been able to remotely compromise about 0.4% of all the public keys used for SSL web site security. The keys we were able to compromise were generated incorrectly--using predictable "random" numbers that were sometimes repeated. There were two kinds of problems: keys that were generated with predictable randomness, and a subset of these, where the lack of randomness allows a remote attacker to efficiently factor the public key and obtain the private key. With the private key, an attacker can impersonate a web site or possibly decrypt encrypted traffic to that web site. We've developed a tool that can factor these keys and give us the private keys to all the hosts vulnerable to this attack on the Internet in only a few hours.\tDigging\u00a0deeper\tIf any pair of RSA moduli\u00a0N1\u00a0and\u00a0N2\u00a0share, say, the same prime factor\u00a0p\u00a0in common, but have different second factors\u00a0q1\u00a0and\u00a0q2, then we can easily factor the moduli by computing their greatest common divisor. On my desktop computer, computing the GCD of two 1024-bit RSA moduli took about 17\u00b5s.\tFor the mathematically inclined, I'll explain how we were able to use this idea to factor a large collection of keys.\tThe simplest way that one might try to factor keys is by computing the GCD of each pair of RSA moduli. A back of the envelope calculation shows that doing a GCD computation for all pairs of moduli in our data sets would take 24 years of computation time on my computer.\tInstead, we used an idea\u00a0Dan Bernstein\u00a0published in the Journal of Algorithms in 2005 for factoring a group of integers into coprimes which allowed us to do the computation in a few hours on a desktop computer, in a few lines of Python. The algorithm is no great secret: a long stream of published papers has worked on improving these ideas.\tThe main mathematical insight is that one can compute the GCD of a single modulusN1\u00a0with every other modulus\u00a0N2,\u2026,Nm\u00a0using the following equation:\tgcd(N1,N2\u2026Nm) = gcd(N1, (N1*N2*\u2026*Nm\u00a0mod N12)\/N1)\tThe secret sauce is in making this run fast--note that the first step is to compute the product of all the keys, a 729 million digit number. We were able to factor the SSL data in eighteen hours on a desktop computer using a single core, and the SSH data in about four hours using four cores.\tThe bottom line\tThis is a problem, but it's not something that average users need to worry about just yet. However, embedded device manufacturers have a lot of work to do, and some system administrators should be concerned. This is a wake-up call to the security community, and a reminder to all of how security vulnerabilities can sometimes be hiding in plain sight.