Hidden Math Flaw Jeopardizes Millions of Online Transactions
|
|
Sometimes everything you know proves to be wrong. CREDIT: Nomad Soul/Shutterstock.com |
Updated at 5:30 p.m. ET Wednesday.
Mathematicians based in Switzerland and the United States have discovered a small but substantial flaw in some of the most commonly used digital encryption schemes, a flaw that could undermine the security of online retailing and communication.
Most encryption schemes rely on the random selection of large prime numbers to generate "public" and "private" keys that can authenticate online secure transactions. But in a paper released yesterday (Feb. 14), the researchers showed that among certain encryption schemes, a significant number of those large prime numbers are not random at all, placing public keys based on them at risk.
"This comes as an unwelcome warning that underscores the difficulty of key generation in the real world," researcher James P. Hughes told the New York Times, which along with the Electronic Frontier Foundation was the first to report the discovery.
The researchers did not speculate on the cause of the lack of randomness. At the moment, there is little the average person can do about the problem.
Undone by arithmetic
The encryption schemes with the biggest flaws, the researchers found, were those based on the RSA 1024-bit algorithm, which uses two large prime numbers to generate a public key and a private key. As with all public-key encryption schemes, someone wishing to send a secret message to a recipient uses the recipient's public key to encrypt the message, which can be decoded only by the recipient's private key.
Using the ancient Greek mathematician Euclid's simple but effective method of factoring numbers, Hughes and his fellow researchers proved that two out of every thousand RSA-1024-bit-based public keys shared one large prime number as a factor — far more than would occur if the numbers were truly random.
"We stumbled upon 12,720 different 1024-bit RSA moduli [out of 6.4 million studied] that offer no security," the researchers wrote in their paper. "Their secret keys are accessible to anyone who takes the trouble to redo our work. ... 1024-bit RSA provides 99.8 percent security at best."
"Some people may say that 99.8 percent security is fine," Hughes, who participated independently in the research from his home in Palo Alto, Calif., told the Times.
Not good enough
But 99.8 percent security is definitely not good enough for online transactions. Let's assume that a major online retailer processes half a million purchase transactions per day. If one out of every 500 of those transactions were hijacked by cybercriminals, that would amount to roughly 10,000 compromised sessions — in which credit-card and personal data could be stolen — every single day.
"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," wrote the authors of the paper, which they half-jokingly referred to as a "sanity check."
The researchers, who apart from Hughes were based at the École Polytechnique Fédérale de Lausanne in Switzerland, found that encryption schemes based on the 2048-bit RSA algorithm were also affected by the lack-of-randomness flaw, though to a smaller degree.
However, encryption schemes based on the Diffie-Hellman algorithm, which uses only one randomly generated number, were not affected by lack of randomness. Hence the paper's odd title, "Ron was wrong, Whit is right."
Ron Rivest, along with Adi Shamir and Leonard Adleman, formulated the RSA algorithm at the Massachusetts Institute of Technology in 1978. (The three went on to found the RSA security company, which is still based near Boston.)
Update: Other security researchers have added to these findings.
Nadia Heninger, a computer scientist at the University of California, San Diego, wrote on Princeton University's Freedom to Tinker tech blog that she and three colleagues had done similar research — and had discovered twice the rate of public keys that could be compromised, at 0.4 percent.
"However, there's no need to panic as this problem mainly affects various kinds of embedded devices such as routers and VPN devices, not full-blown web servers," Heninger wrote. "Don't worry, the key for your bank's website is probably safe."
Heninger's team used a different methodology than the Lausanne team, so they could both end up being right.
Meanwhile, well-known security researcher Dan Kaminsky praised the Lausanne team's work, but said that the problems it discovered were dwarfed by the much bigger problem of human error and mismanagement in handling digital certificates.
"What the data from this survey says, unambiguously, is that most keys on the Internet today have no provenance that can be trusted, not even through whatever value the CA [Certificate Authority] system affords," Kaminsky wrote on his blog .
For Kaminsky, and for many other security researchers, the entire system of digital certificates, which was set up on the mid-1990s when the Internet was relatively minuscule, is the problem.
