If all of the noise about weak RSA keys and compromised cryptosystems in the last few days has done anything, it’s to confirm what many in the cryptography community have known for quite a long time: When it comes to implementing cryptosystems, there are a whole lot of people doing it wrong. However, experts say the new research showing large numbers of repeated and weak crypto keys is a good reminder of not only how hard it is to get this stuff right, but also how many different ways it can go wrong.
Over the course of the past couple of days, two separate teams of researchers have published new data from large-scale experiments on which they collected huge volumes of public encryption keys and then assessed their strength through various methods. One of the teams did this by comparing each individual key against all of the others to see whether there were duplicates in the data set. There were, and lots of them. The team, comprising researchers from the University of Michigan and the University of California at San Diego, found 59,000 duplicate keys, or about 1 percent of its data set. The researchers also looked for keys that were factorable due to weak entropy and found that about half of one percent of the SSL and SSH public keys they collected fit that description.
The other team, working independently, also found a large number of weak RSA keys and concluded that the security offered by some systems that rely on RSA-based cryptosystems is not nearly as strong as has been believed.
“We checked the computational properties of millions of public keys that we collected on the web. 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. For ElGamal and DSA sharing is rare, but for RSA the frequency of sharing may be a cause for concern. 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,” the second team wrote in its paper, “Ron was wrong, Whit is right”.
Most of what the team from Michigan and UCSD found is attributable to weak keys found in embedded devices such as routers and VPN boxes. Those devices often don’t have good methods for generating the desired amount of entropy that’s needed to generated strong cryptographic keys, said Nadia Heninger, one of the researchers who worked on the project. In other cases, the devices may have a stock firmware image installed at the factory that might include a set key.
“I would say this particular problem is an implementation issue. It’s a hard problem,” said Heninger, a postdoctoral fellow in the Department of Computer Sciences and Engineering at UCSD. “Given the choice between a weak key and a repeated key, both of these are bad. The problems with repeated keys are much more widespread than factorable keys. We found more than fifty thousand that were repeated because of bad entropy and more than five hundred thousand that were repeated because they were the default on some device.”
The RSA algorithm relies on both a public and private key. One of the ways that public keys are generated is by taking a seed value and using it to generate two large prime numbers and then using the product of those two primes as the key. If the seed value is either predictable or generated with too little entropy, then the resultant key could be factorable. And if an attacker can factor the key, then bad things happen.
However, cryptographers say that the new research, while important, shouldn’t have people running for the hills.
“The fact that people are using bad random number generators has been known for a long time,” said Paul Kocher, a noted cryptographer and the president and chief scientist at Cryptography Research. “What’s neat about these research results is that they collected a huge set of keys and found a small but non-trivial set of keys that had these particular problems. There’s something frightening about the fact that you can just sit down and think about a scary security bug like this and then go out and find it in a lot of places. It’s a sign of how many things are being done badly.”
The implications of the research for individual users are fairly small. It’s the device manufacturers and system designers who need to take a look at what they’re doing and address the way they’re implementing these cryptosystems.
“Most products don’t get any kind of security review at all,” Kocher said. “Doing seeding well is one of those things that’s device-specific. The toolkits can’t solve that problem for you and it’s one of the issues that’s left to the integrators of the devices. It’s a small but significant population of devices that has problems. The RSA algorithm depends on the implementer to generate the underlying prime numbers in the proper way. It defers this important issue to the implementer, and packages like OpenSSL then defer it to the person making the particular device.
“Part of the issue that’s going on here is that seeding strongly is non-trivial on an appliance that needs to generate a key on its first power-up because it hasn’t had time to collect entropy yet.”
Fixing the issues found by Heninger and her team and the other team led by Arjen Lenstra of the Ecole Polytechnique Federale de Lausanne in Swizterland is not a trivial matter and it’s not something that can be done quickly.
“We have to do more work on getting the entropy right, and that’s not an easy problem,” Heninger said. “It’s not going to be easy. There are ways to do it, but it’s going to require some work.”
It’s also important to remember, Kocher said, that the problems identified by the research teams are just a small subset of the security issues that affect devices and systems that have crypto implementations. Any one of those issues could be just as serious, if not more so, than the weak or repeated keys.
“This is looking at one narrow security bug that can affect devices,” he said. “There are huge numbers of sites and devices that have bugs that allow attackers to bypass the crypto. If you have a bug that results in a buffer overflow that lets you bypass the crypto somehow, that’s equally catastrophic. If you start asking the question of how many devices there are out there that people think are doing crypto right that actually aren’t, it’s a huge number.
“It’s almost a law of nature that people will build complicated systems that will fail badly,” Kocher said.
