It’s only a few weeks now before the annual security conference that bears the initials of the first commercial implementers of cryptographic security outside the government security sector. Just in time for RSA, a team of researchers based in Switzerland say they have uncovered evidence of a new flaw in the way public keys are generated using the RSA algorithm. Those researchers include a certain, notable Dutch professor who used to make hacker headlines of his own back in the day.
Although the Swiss team’s conclusions are being questioned by some respected names, their data indicates one more reason why commonly used implementations of SSL encryption may be prone to failure, and should perhaps not be trusted at all.
Now a professor at Lausanne, Switzerland’s prestigious EPFL, Arjen K. Lenstra is the co-author of a new paper released by the non-profit International Association for Cryptologic Research (PDF available here). Entitled simply “Ron was wrong, Whit was right” (an explanation of its meaning in a moment), the paper presents itself as “a sanity check of public keys collected on the Web.”
The paper’s contention is that, probably as a result of poorly implemented random number generators, cryptographic systems that rely on “multiple secrets” (the defining feature of the RSA technique co-devised by Ron Rivest, the “Ron” in the paper’s title) tend to include prime number factors that are identical more often than they should be. By design, “single secret” systems (the defining feature of the Diffie-Hellman protocol co-devised by Whitfield Diffie, the “Whit” in the title) would never encounter such potential for defect.
Prof. Lenstra’s team examined a total of 6.6 million publicly accessible X.509 certificates and PGP keys. While all of them were distinct from one another, about 270,000 of them shared an RSA modulus – the product of one of the two or more random prime numbers used in the generation of the key. And among the 6.4 million RSA moduli the team collected, some 71,052 – about 1.1% of the sample – occurred more than once.
And some 12,720 1024-bit moduli could easily be factored down to produce the complete key.
“The lack of sophistication of our methods and findings make it hard for us to believe that what we have presented is new, in particular to agencies and parties that are known for their curiosity in such matters,” the team writes. Perhaps it’s why the U.S. Government’s NIST Institute made a determination in 1991 to use digital signature algorithms (DSA) instead of RSA, they add. “Factoring one 1024-bit RSA modulus would be historic. Factoring 12,720 such moduli is a statistic. The former is still out of reach for the academic community (but anticipated). The latter comes as an unwelcome warning that underscores the difficulty of key generation in the real world.”
Lenstra and company presented a graph depicting a chain of events demonstrating the impact of insecure keys in a system of keyrings. In the graph, there are two sets of existing moduli (keys), each of which is produced with two large prime numbers. Each prime is represented by a letter. A series of new keys is generated, represented by the red keys on the top. PQ is a new key that’s perfectly safe, and added to the left (safe) group. AB is generated next, but it happens to share both prime factors with an existing key AB – because, as the team discovered, it can.
As new keys LR, ES, and GJ are generated, they share one prime factor with existing keys. In the process, like contestants on some reality content, formerly safe keys EF, GH, and JK are forced out of the left group and into the unsafe group. The graph’s intention is to demonstrate that the number of new keys that are generated unsafe render existing keys just as unsafe, which in turn renders a subsequent wave of keys unsafe, and so on.
In an analysis of the Lenstra group’s paper published yesterday, while security researcher Dan Kaminsky praised the group’s data collection process, he cast a very skeptical eye upon its conclusions. Specifically, Kaminsky disputes whether the 12,720 vulnerable public keys they found is evidence of a design flaw in RSA – as even their title suggests – as opposed to a flaw in implementation, perhaps one brought on through the random number generation process.
“This is a paper based on survey work, in which the empirically validated existence of an implementation flaw (12,720 crackable public keys) is being used to justify a design bias (don’t use a multi-secret algorithm),” writes Kaminsky. “The argument is that multi-secret algorithms cause crackable public keys. You don’t just get to cite implementation flaws when they’re convenient. More importantly, correlation is not causation. That we see a small number of bad keys at the same time we see RSA does not mean the latter caused the former. Alas, this isn’t even correlation.”
Kaminsky notes the Lenstra group’s own data, which indicates that of the nearly 6.2 million X.509 certificates they tested, all of 142 did not use RSA. “We clearly do not have a situation where the choice of RSA vs. otherwise is random,” Kaminsky goes on. “Indeed, cipher selection is driven by network effects, historical patents, and government regulation, not the roll of the dice even mere correlation would require.”
The implication there being that if Lenstra were to apply the same techniques to test classes of keys other than RSA, he might get similar results.
Kaminsky is the researcher widely credited with having identified an exploitable flaw in the Internet’s DNS system – a flaw which engineers stealthily averted in 2008 without alerting the public, and without giving malicious users an opportunity to strike first. Some say that revelation may conceivably have saved the Internet. Lenstra’s earlier work with DigiCrime, Inc. included a period where he “lampooned,” to use his own term, the security research industry, including by posting satirical stories – such as the one about hackers breaking into the Mars Rover’s guidance system to make it spread graffiti on Martian rocks – that some sources treated as fact.
CORRECTION: Prof. Arjen Lenstra is not the same Prof. Lenstra who teaches at Eindhoven University in the Netherlands. I confused the two Profs. Lenstra in an earlier draft; the error was entirely mine, and I apologize to both professors.
