‘RSA algorithm flawed’ report is difficult to dismiss

RSA is firing back at researchers who claim in a paper that its flagship crypto system is damaged goods. But the report is still difficult to dismiss.

My colleague Ellen Messmer wrote about RSA’s reaction, saying, “EMC’s RSA security division 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:

Ari 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.

“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.”

He 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.

RSA was not apprised of the paper before it appeared online.

In 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.”

The 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.

“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 Whitfield Diffie. The paper leveled a devastating critique against RSA as fundamentally flawed.

I 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 or 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.

The 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:

We 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.

Digging deeper

If any pair of RSA moduli N₁ and N₂ share, say, the same prime factor p in common, but have different second factors q₁ and q₂, 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µs.

For the mathematically inclined, I’ll explain how we were able to use this idea to factor a large collection of keys.

The 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.

Instead, we used an idea Dan Bernstein published 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.

The main mathematical insight is that one can compute the GCD of a single modulusN₁ with every other modulus N₂,…,N_m using the following equation:

The 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.

The bottom line

This 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.