Crypto Researcher Arjen Lenstra Shares Thoughts on Paper Blasting RSA Cryptosystem

What a week for the RSA cryptosystem! A group of prominent researchers published a paper blasting it as woefully insecure, RSA said there’s nothing wrong with the RSA algorithm, it’s an implementation issue mainly with random-number key generation, and now the cryptography researcher behind the paper, Arjen Lenstra, signs off the week with a few thoughts about it all.

BACKGROUND: RSA brushes off crypto research findings that RSA algorithm is flawed

“If properly implemented, RSA is fine,” said Lenstra, the well-known crypto researcher who worked with James Hughes, Maxime Augier, Joppe Bos, Thorsten Kleinjung and Christophe Wachter on the remarkable project that included examining millions of X.509 public-key certificates that are publicly available over the Web.

That study (explained in the “Ron is wrong, Whit is right” paper) had the researchers examining 6.4 million distinct X.509 certificates and PGP keys containing RSA moduli, and “we stumbled upon 12,720 different 1024-bit RSA moduli that offer no security.” They said that “their secret keys are accessible to anyone who takes the trouble to redo our work.”

The paper concluded: “Overall, over the data we collected, 1024-bit RSA provides 99.8% security at best.” It also compared RSA to “single secret” cryptosystems such as ElGamal and DSA, based on Diffie-Hellman (DH), saying these are “less risky” than cryptosystems based on RSA.

“The recommendation is to use a cryptosystem that is appropriate for the environment where it will be used,” said Lenstra in an email exchange with Network World. “If the environment cannot provide enough entropy during the key set-up, then RSA becomes a tricky choice. RSA itself is fine — it is the way it us used/implemented/whatever you want to call it, that is the problem. Other crypto (DSA and such) have that too, but in subtly different ways.”

The concept of “entropy” in the science of cryptography is roughly analogous to “uncertainty,” he says, based on mathematical outcomes. “Lots of tricks have been invented, but getting enough entropy on a device is still a very tricky problem,” he points out.

Lenstra said, “Apparently, the consideration that adequate entropy needs to be present when generating RSA keys has not consistently been taken into account (most commonly on embedded devices, but unfortunately not only in those environments). As far as I can tell, everyone is in full agreement on this issue.”

As far as there being a “clear distinction between RSA and Diffie-Hellman based methods such as ElGamal and (EC)DSA,” Lenstra points out, the research outlined in the paper underscores “that the effects of poor entropy are different for the two types of methods: for the latter, the parties using the same poor entropy can breach each other’s security (as it may result in identical keys), for the former anyone may be able to breach the security of any pair of parties that use poor entropy (namely, if it results in non-identical but intersecting keys — the latter does not occur for the DH-type methods). As far as I’m aware, this distinction has not been pointed out before.”

Lenstra added: “I do not know to what extent it has played a role in NSA’s Suite B cryptography,” and the National Security Agency’s decision to recommend ECDSA “may have been entirely based on issues related to key size and uncertainty of extrapolation thereof, which is a bit curious given how straightforward it is.”

The researcher continued: “It is not a failure of RSA — indeed, everyone knows that RSA key set-up should only be done when adequate entropy is present — but it is a consideration that one may want to take into account. This is in full agreement with RSA’s recommendation to ensure good implementation and to follow best practices.”

The research group is not planning any further activities specifically along the lines of what it has just done, and has moved all its data offline and “stored everything in a secure location,” Lenstra said. He said “it is not at all our main activity or interest but it was just a toy project based on our curiosity” and “our initial findings (which we cannot share) were such that we looked at it at a somewhat wider scale than we had originally intended.”

Some sources intimate that NSA may have conducted a similar research project to that described in the “Ron is wrong, Whit is right” paper, though this wasn’t for public consumption. Lenstra said he’s not surprised the NSA would have done a similar project on its own, but he doesn’t know anything about it.

Ellen Messmer is senior editor at Network World, an IDG publication and website, where she covers news and technology trends related to information security.

Read more about wide area network in Network World’s Wide Area Network section.