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.

Join the CSO newsletter!

Error: Please check your email address.

More about IDGLANNational Security AgencyNSAPGPRSA

Show Comments

Featured Whitepapers

Editor's Recommendations

Solution Centres

Stories by Ellen Messmer

Latest Videos

  • 150x50

    CSO Webinar: Will your data protection strategy be enough when disaster strikes?

    Speakers: - Paul O’Connor, Engagement leader - Performance Audit Group, Victorian Auditor-General’s Office (VAGO) - Nigel Phair, Managing Director, Centre for Internet Safety - Joshua Stenhouse, Technical Evangelist, Zerto - Anthony Caruana, CSO MC & Moderator

    Play Video

  • 150x50

    CSO Webinar: The Human Factor - Your people are your biggest security weakness

    ​Speakers: David Lacey, Researcher and former CISO Royal Mail David Turner - Global Risk Management Expert Mark Guntrip - Group Manager, Email Protection, Proofpoint

    Play Video

  • 150x50

    CSO Webinar: Current ransomware defences are failing – but machine learning can drive a more proactive solution

    Speakers • Ty Miller, Director, Threat Intelligence • Mark Gregory, Leader, Network Engineering Research Group, RMIT • Jeff Lanza, Retired FBI Agent (USA) • Andy Solterbeck, VP Asia Pacific, Cylance • David Braue, CSO MC/Moderator What to expect: ​Hear from industry experts on the local and global ransomware threat landscape. Explore a new approach to dealing with ransomware using machine-learning techniques and by thinking about the problem in a fundamentally different way. Apply techniques for gathering insight into ransomware behaviour and find out what elements must go into a truly effective ransomware defence. Get a first-hand look at how ransomware actually works in practice, and how machine-learning techniques can pick up on its activities long before your employees do.

    Play Video

  • 150x50

    CSO Webinar: Get real about metadata to avoid a false sense of security

    Speakers: • Anthony Caruana – CSO MC and moderator • Ian Farquhar, Worldwide Virtual Security Team Lead, Gigamon • John Lindsay, Former CTO, iiNet • Skeeve Stevens, Futurist, Future Sumo • David Vaile - Vice chair of APF, Co-Convenor of the Cyberspace Law And Policy Community, UNSW Law Faculty This webinar covers: - A 101 on metadata - what it is and how to use it - Insight into a typical attack, what happens and what we would find when looking into the metadata - How to collect metadata, use this to detect attacks and get greater insight into how you can use this to protect your organisation - Learn how much raw data and metadata to retain and how long for - Get a reality check on how you're using your metadata and if this is enough to secure your organisation

    Play Video

  • 150x50

    CSO Webinar: How banking trojans work and how you can stop them

    CSO Webinar: How banking trojans work and how you can stop them Featuring: • John Baird, Director of Global Technology Production, Deutsche Bank • Samantha Macleod, GM Cyber Security, ME Bank • Sherrod DeGrippo, Director of Emerging Threats, Proofpoint (USA)

    Play Video

More videos

Blog Posts

Market Place