Weakness Found In Widely-used Online Encryption Method
February 16, 2012

Weakness Found In Widely-used Online Encryption Method

A team of U.S and European cryptanalysts has discovered an unexpected vulnerability in the encryption system commonly used to provide privacy and security to online shopping, banking, e-mail and other Internet transactions, according to a recent New York Times report.

The weakness, which the scientists said involve a small but not insignificant number of cases, pertains to the way the system generates the random numbers used to prevent hackers from unscrambling digital messages.

The researchers found that these random numbers, which are associated with the encryption keys, were not always random enough. As a result, hackers could use public keys to guess the corresponding private keys that are used to decrypt data — something previously thought impossible.

The potential danger of this flaw is that even though the number of users affected by it may be relatively small, its existence could serve to undermine confidence in the security of Web transactions, the researchers wrote in a report about their findings.

Furthermore, while this potential problem can affect the transactions of individual Internet users, there is nothing an individual alone can do about it.  Rather, the operators of large Web sites would need to make changes to ensure the security of their systems, the researchers said.

Encryption systems require that a user first create and publish the product of two large prime numbers, in addition to a third number, to generate a public “key.”  The original numbers are kept secret.   To encrypt a message, the receiver uses a formula that contains the public number.  Practically speaking, only someone with knowledge of the original prime numbers could decode the message.

However, for the system to provide ample security, it is vital that the secret prime numbers be generated randomly, so an outside party could not simply guess or estimate the correct number.  The researchers discovered that in a small, but notable, number of cases, the random number generation system failed to work correctly.

“We checked the computational properties of millions of public keys that we collected on the web,” wrote James Hughes, an independent Silicon Valley cryptanalyst who worked with a team of researchers led by Arjen Lenstra, a respected Dutch mathematician and professor at the École Polytechnique Fédérale de Lausanne in Switzerland.

“The majority does not seem to suffer from obvious weaknesses and can be expected to provide the expected level of security. We found that on the order of 0.003% of public keys is incorrect, which does not seem to be unacceptable. We were surprised, however, by the extent to which public keys are shared among unrelated parties.”

The value of ensuring that encryption systems do not have undetected flaws cannot be overstated, given the heavy reliance of online commerce system on the secrecy provided by the public key cryptographic infrastructure.

The researchers made their findings public on Tuesday because they believe the flaw is of immediate interest to the operators of Web servers that rely upon the public key cryptography system.

“This comes as an unwelcome warning that underscores the difficulty of key generation in the real world,” wrote Hughes.

“Some people may say that 99.8 percent security is fine,” he said.

That would mean as many as two out of every thousand keys would not be secure.

The researchers examined public databases of 7.1 million public keys used to secure online banking transactions, e-mail messages and other secure data transactions.  They used the Euclidean algorithm, an efficient way to identify the greatest common divisor of two integers, to examine the public key numbers.

They found that a small percentage of those numbers were not truly random, making it possible to determine the underlying secret keys used to generate the public key.

The researchers said they “stumbled upon” nearly 27,000 different keys that offered no security whatsoever.

“Their secret keys are accessible to anyone who takes the trouble to redo our work,” the researchers wrote in their report.

To prevent this from happening, one of the organizations that had collected the public keys has removed the information from the Internet, and taken additional steps to protect the data from theft.

The researchers used several databases of public keys, including one at the Massachusetts Institute of Technology and another created by the Internet privacy rights group Electronic Frontier Foundation (EFF).  The foundation´s database comes from a project dubbed the SSL Observatory, which was originally designed to investigate the security of the digital certificates used to safeguard encrypted data transmitted between Internet users and Web sites.

“We were very careful: we did not intercept any traffic, we did not sniff any networks,” Mr. Hughes wrote.

“We went to databases that contained public information and downloaded public keys.”

Although the researchers are not sure why the random number generators had produced flawed results, they noted the problem occurred in more than the work of one software developer.

They also noted that since they were able to discover the fault, perhaps  others with less benevolent intent had as well.

“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 researchers wrote.

The researchers acknowledged that the publication of results that could potentially undermine the security of encryption keys was risky unless the parties were first notified, but noted that the way they discovered the flaw made identifying potentially vulnerable parties difficult.

“The quagmire of vulnerabilities that we waded into makes it infeasible to properly inform everyone involved, though we made a best effort to inform the larger parties and contacted all e-mail addresses recommended or specified in still-valid affected certificates,” they wrote.

“The fact that most certificates do not contain adequate contact information limited our options. Our decision to make our findings public, despite our inability to directly notify everyone involved, was a judgment call.”

There have been cases in the past where failure of random number generators has undermined Internet security.  For instance, in 1995, researchers at the University of California, Berkeley, identified a flaw in the way the Netscape browser generated random numbers, which could allow an eavesdropper to decode encrypted messages.

Last year, a group of computer hackers found that Sony had made a critical error in not using a random number in the algorithm used by the security system of the PlayStation 3, making it possible to identify the secret key used to protect the system´s digital content.

Dr. Hughes, Lenstra and colleagues´ full report, entitled “Ron Was Wrong, Whit Is Right,” in reference to public key cryptography pioneers Ron Rivest and Whitfield Diffie, was submitted this week for publication at a cryptography conference to be held in August.


On the Net: