Researchers find flaw in key generation with popular cryptography
Small percentage of public keys in sample found online were not randomly generated as they should be, paper says.
A group of researchers has uncovered a flaw in the way public keys are generated using the RSA algorithm for encrypting sensitive online communications and transactions.
They found that a small fraction of public keys--27,000 out of a sample of about 7 million--had not been randomly generated as they should be. This means it would be possible for someone to figure out the secret prime numbers which were used to create the public key, according to The New York Times, which reported on the research today.
The research was led by James P. Hughes, an independent cryptology expert based in Palo Alto, Calif., and Arjen K. Lenstra, a Dutch mathematician who teaches at the Ecole Polytechnique Federale de Lausanne in Switzerland. The researchers are scheduled to present their paper in August at a cryptography conference in Santa Barbara, Calif.
"We performed a sanity check of public keys collected on the Web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated," the researchers wrote in their paper (PDF). "We found that 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."
The public keys in question have been removed from a publicly accessible database to prevent someone from exploiting the weakness, according to the Times. To ensure the integrity of their security systems, Web sites will need to make changes on their end, the report said.
It's not known if anyone else has stumbled upon the weakness, which is a possibility, the researchers note.
"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 paper says. "It may shed new light on NIST's (National Institute of Standards and Technology) 1991 decision to adopt DSA as digital signature standard as opposed to RSA, back then a 'public controversy'..."