Encryption System Flaw Threatens Internet Security
by George Lawton
Researchers have found a vulnerability that affects an encryption system widely used to provide security for e-mail, e-commerce, e-banking, and other online services.
Independent cryptography consultant James P. Hughes and Swiss Federal Institute of Technology Lausanne researchers led by professor and security expert Arjen K. Lenstra identified a weakness in the popular RSA-algorithm-based public-key encryption system. This flaw could let hackers recognize and recreate poorly generated encryption keys, and use them on the Web.
The problem lets hackers take advantage of a feature of the algorithm and of poorly generated random prime numbers, which are used to generate cryptographic keys, to decode keys for some traffic encrypted by the RSA algorithm.
The percentage of affected keys on the Web is small. However, concern is great because they are widely employed in public-key encryption techniques that verify website authenticity, enable the safe exchange of confidential information, and protect financial transactions.
This could threaten some transactions and reduce trust in Web security, Hughes said.
Inside the Public-Key System
In public-key systems, messages are encrypted — in a process that often occurs within routers — with public keys. They can be decrypted only with corresponding private keys. The public keys are widely distributed, but only the recipient of a transmission holds the private key.
The RSA algorithm generates the public and private keys by multiplying two large, randomly chosen prime numbers and then using Euler's totient function to generate the public key and a multiplicative inverse function to generate the private key.
The process is designed to make it too time-consuming and expensive to determine the private key from the public key.
Thus, generating random numbers is a key part of these systems and the quality of random-number generation is critical.
There are various ways to generate random numbers, such as using measurements of random physical phenomena. Computational approaches generate pseudorandom numbers, which can be used instead of true random numbers in many applications.
In 1995, research identified a flaw in the random-number generator (RNG) that Netscape used for public-key encryption. This made it easier to crack the encryption.
Last year, hackers also reported finding a weakness in the RNG that helped encrypt content on the Sony PlayStation. This let them access and share games and movies that were supposedly protected.
The Research
To find possible problems with cryptographic keys, Hughes, Lenstra, and their team worked with public-key databases that the MIT and the Electronic Frontier Foundation, a digital rights advocacy organization, created from publicly available online information. Hughes emphasized that they gathered no data by intercepting Web traffic.
The researchers found that in some cases, public-key encryption systems' RNGs produced the same "random" numbers for multiple encryption-key users. Hughes noted that effective RNGs are not supposed to do this.
In one case, a router vendor reused a combination of the same nine random numbers to generate 600 keys.
The researchers said the RSA algorithm enabled them to use a greatest-common-divisor (GCD) algorithm to analyze keys for different users that were generated by problematic RNGs.
They relatively quickly identified the keys' largest common factors, which in turn told the researchers the prime numbers used to generate them.
Hackers could use this information to decipher the keys themselves.
Public-key encryption schemes other than RSA use different key-generation algorithms, which don't enable GCD analysis to determine the random prime numbers used to generate keys.
Hughes, Lenstra, and their team identified the reuse of supposedly random prime-numbers in about 27,000 of the 7.1 million keys tested. Thus, the absolute number of keys affected throughout the Internet could be considerable, said Hughes.
Almost all of the affected keys have been implemented in the past five years, reflecting the proliferation of routers and switches with weak RNGs.
Ramifications
Hackers could take advantage of being able to decipher encryption keys in several ways.
For example, being able to use encryption keys that are supposedly private could let hackers impersonate a legitimate website and direct a victim trying to access the site to an IP address that the attackers control.
The site to which the victims are redirected could infect them with malware and even turn them into zombies that become part of botnets.
Once their website is communicating with a victim, the hackers could steal usernames and passwords and install back doors that could let them access the compromised systems at any time.
Hackers could also launch man-in-the-middle attacks, allowing them to sit between communicating parties and intercept their transmissions.
According to Hughes, there is no evidence that hackers have exploited the vulnerability in the wild yet.
He explained that his team made its findings public because the issue is of immediate concern and could be solved only by rethinking random-number generation techniques.
Hughes said he wanted to communicate directly with developers of the software that could be affected by the problem but in many cases couldn't identify them.
"When I first read the paper, I found it very exciting," said Whitfield Diffie, cryptography expert and vice president for information security and cryptography at the Internet Corporation for Assigned Names and Numbers. "The thought that someone else's key could compromise yours … seemed beguilingly sinister."
"As I thought about it," he continued, "I realized that you really have to have a bad random-number generator for this problem to appear."
MIT professor Ron Rivest, one of the RSA algorithm's developers, noted that problems with random number generators have been documented in the past.
"What is new about their paper is the analysis of the frequency with which poor keys are generated in practice," he said. "I don't believe that any of these issues affect the long-term viability of RSA or of other cryptosystems."
