RSA security flawed say researchers after collecting duplicate public keys
Crypto experts conduct search of millions of X.509 certificates
By Ellen Messmer | Network World US | Published: 10:01, 15 February 2012
Cryptography researchers collected millions of X.509 public key certificates that are publicly available over the web and found what they say is a shockingly high frequency of duplicate RSA-moduli keys.
"We performed a sanity check of public keys collected on the web," the researchers state in their paper, published today and titled "Ron was wrong, Whit is right".
The researchers, who include Arjen Lenstra, James Hughes, Maxime Augier, Joppe Bos, Thorsten Kleinjung and Christophe Wachter, note in the paper that they found a shockingly high number of duplicate secret keys in what is supposed to be unique random number generation in RSA-based moduli.
Related Articles on Techworld
The researchers said in an examination of 6.4 million distinct X.509 certificates and PGP keys containing RSA moduli, 71,052 (1%) occur more than once, some of them thousands of times. "Overall, over the data we collected, 1024-bit RSA provides 99.8% security at best," the paper states. "More seriously, we stumbled upon 12,720 different 1024-bit RSA moduli that offer no security. Their secret keys are accessible to anyone who takes the trouble to redo our work."
The researchers summarised their findings by saying, "We find the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security."
They also said their research showed that crypto based on "single-secret" cryptosystems like ElGamal or DSA, based on Diffie-Hellman, is less risky than cryptosystems based on RSA. Hence the research paper’s title, "Ron was wrong, Whit is right," is an oblique reference to Whitfield Diffier, the cryptographer, and Ron Rivest, the co-inventor of the RSA algorithm.
RSA has no immediate comment to the paper. It was not possible to immediately reach the researchers Arjen Lenstra or James Hughes.
Some cryptographers say the paper is impressive in its scope.
"It is interesting. And great research," commented Bruce Schneier, cryptography expert. He said the research paper “is mainly a demonstration of the truism that random number generation is hard to do."
As to whether these research findings will cause a panic run away from the RSA crypto technology, he said, "No. But it will, like an Italian cruise ship running aground off the coast of Italy, make people wary of cruising – or maybe countries that begin with the letter 'I.'"
The researchers of the "Ron was wrong, Whit is right" paper say they will be presenting more about the findings at an upcoming conference.
They also said due to the difficulty in contacting individuals whose public key certificates they say are at risk, they have decided to put their project data "under custody" so that if anyone wants to exploit the current situation, they would have to redo the work, both the data collection and the calculation.