New Retail Crypto Hole: Check Your Keys <b>Now</b>

A new cryptographic hole revealed this week will impact one in 500 encryption keys, will be fairly hard for cyberthieves to find and will almost certainly be patched quickly. Still, it raises fundamental questions about encryption reliance. The group of cryptography researchers described an encryption hole that hits RSA especially hard, and at least one major chain is taking this very seriously.

Although the flaw involves encryption key components that are supposed to be unique, an examination by the SSL Observatory found them to be far from it. One security specialist at a major retailer said his chain was studying the report but found no reason to panic. "My opinion is that we are safe, for at least a little while. Even if our keys shared a modulus with someone else, the researchers notified everyone affected they could find, and most retailers are pretty easy to find," said the retail cryptographer, who asked that her name not be used. "The bigger concern is internal keys, ones they couldn't survey. Without their data of 'weak keys,' we can't be sure we aren't using any. But they can't responsibly publish the list. All owners of certificates do not know today if their keys are weak or not, and they have no way of finding out just by examining them."

While stressing that the chance for this flaw to be used by bad guys was remote, the security specialist said that if it is used, the implications are pretty frightening. "Think what this means for PCI. A bad guy who has secretly been recording encrypted traffic to retailers, and with the resources to replicate this research, now has the possibility of decrypting it," she said.

The researchers stressed that they tried to contact many victims—including many retailers—but that problems with contact information on security certificates (shocked we are that security certificates aren't as helpful as the vendors say they are) made it difficult. The retail security exec echoed those concerns. "Some owners of certificates have been notified that their keys are weak and some of those have taken action. But more than half of the most seriously affected certificate owners did not even acknowledge contact by the SSL Observatory. People are still using insecure key generation mechanisms to generate new certificates."

Bruce Schneier, a security consultant and bestselling author of several cryptography and security books, described the newly reported hole as "probably not significant. The bad guys would have to replicate the experiment and find the weak keys."

The security report—available in full geeky details—lays out the mathematical problem. "More worrisome is that, among the 4.7 million distinct 1024-bit RSA moduli that we had originally collected, more than 12,500 have a single prime factor in common. That this happens may be crypto-folklore, but it was new to us, and it does not seem to be a disappearing trend. In our current collection of 7.1 million 1024-bit RSA moduli, almost 27,000 are vulnerable, and 2048-bit RSA moduli are affected, as well. When exploited, it could affect the expectation of security that the public key infrastructure is intended to achieve."

It wasn't only RSA encryption that was at issue, but the report said it was the most at risk. "Among the ElGamal and DSA keys, we found a few duplicates with unrelated owners. This is a concern because, if these owners find out, they may breach each other's security. It pales, however, compared to the situation with RSA. Of 6.6 million distinct X.509 certificates and PGP keys containing RSA moduli, [270,000] share their RSA modulus, often involving unrelated parties. Of 6.4 million distinct RSA moduli, 71,052 occur more than once, some of them thousands of times."It gets worse. "More seriously, we stumbled upon 12,720 different 1024-bit RSA moduli that offer no security. Their secret keys are accessible to anyone who takes the trouble to redo our work. Assuming access to the public key collection, this is straightforward compared to more traditional ways to retrieve RSA secret keys.

"What surprised us most is that many thousands of 1024-bit RSA moduli, including thousands that are contained in still valid X.509 certificates, offer no security at all. This may indicate that proper seeding of random number generators is still a problematic issue," the report said.

The paper points out some issues that need attention, but it also overreaches, such as when it said that "0.2 percent of the keys offer no security." Actually, they offer roughly the same security as the lock on your front door: It will discourage millions of casual walk-ins, even though it won't stop a professional thief who has targeted your house.

The major retail security exec said she had a plan for minimizing her chain's exposure. "My first-glance reaction is not to panic needlessly. I plan to wait for researchers to identify a key generation system that avoids the current pitfalls, then rotate my keys on their normal schedule. I might exercise a 'compromised key scenario' for practice, but not out of fear. That would all change if the facts get worse, of course."

The retail security exec said the cause of the problem is partially sloppy retail IT procedures. The same chains at risk because of that sloppiness will likely remain at risk when the fixes are published, due to the probability of more sloppiness.

"The weak keys and collisions were likely caused by using the default configurations of some key generators and (that chain's IT team) not properly following directions to install it in a secure fashion. This means they likely did not properly seed their random number generators," she said. "Someone will identify these poor configurations and publish them. This will allow organizations to check their systems and, if their configuration is the same, they should reconfigure their key generation system and replace all their keys. Many shops who originally failed to follow the instructions for careful installation of their systems will also fail to heed these warnings."

Any security risk is only dangerous to the extent that cyberthieves have the means to exploit the hole and, indeed, do so. "Some bad guys are likely to begin trying to replicate their work, if they haven't already. But it will take them some amount of time before they hit a goldmine. There may be a few weak keys identified rapidly, leading to a couple of minor public embarrassments," the retail cryptography expert said. "If it's revealed that a certificate authority's signing key was among those compromised, that will be big news, along the lines of the now-defunct DigiNotar. If you currently use 1024-bit RSA keys, it's likely the future recommendation will be to replace them with 2048-bit (or larger) keys. Some shops will react very quickly and are probably replacing every key this week. There will be minor fallout as some mistakes will be made in the rush."

She also had a good suggestion: "This is a good time to review your 'Key Compromise Plan.' You did create a Key Compromise Plan as a part of your PCI compliance work, didn't you?" she asked. "If you received a notification from the SSL Observatory to replace your weak keys, and haven't acted upon it yet, do so now. There will likely be recommendations forthcoming to re-install updated versions of certain key generating software packages, and to generate new keys after they've been installed. That will likely be the best time to act."

Considering how much effort has already gone into rainbow tables and the like, we can be reasonably sure there are currently thieves who have created those tools and are running them on every public key they can find. That means for the one in 500 at risk, they really are at risk.