Research paper claims ‘1024-bit RSA provides 99.8% security at best'
By Ellen Messmer, Network World
February 14, 2012 06:14 PM ET
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.
CRYPTO NEWS: Start-up with heavy Russian connections offers crypto authentication service
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," the researchers say in their paper. "Their secret keys are accessible to anyone who takes the trouble to redo our work."
The researchers summarized 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 Diffie, 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 and author of a number of books, including his recent one, "Liars and Outliers." 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 our work, both the data collection and the calculation."
|"Come out from man foul spirit!|
WHAT IS THY NAME!?!"
And he said unto him,
"...our name is legion...for we are many..."
Gospel of Mark, Chapter 5, Verses 8 & 9
|Patriotism is your conviction|
that your country is
superior to all others because
you were born in it.
George Bernard Shaw