'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

Continue Reading