It’s always slightly disorienting and confusing when a story about something as esoteric as weak encryption keys produced by poor random number generators makes its way into the real world and begins scaring the citizens. This can lead to confusion and worry about whether everyone’s online banking sessions and purchases of Canadian pharmaceuticals are safe. To help allay those concerns, here are some things you need to know about the new research on weak RSA keys and its implications.
Is the RSA algorithm broken?
No. The algorithm itself is not the problem here. What the research team from the University of Michigan and University of California San Diego and the separate team from the Ecole Polytechnique Federale de Lausanne found were a small number of weak or repeated RSA public keys. Those keys are the result of implementation errors on the part of the device manufacturers or the developers of the software packages that include the crypto bits. If the RSA algorithm–or any other cryptosystem–is implemented poorly, then the result can be keys that don’t have enough randomness to withstand brute-force cracking attempts, or keys that are used in more than one device, as in a stock firmware image.
Can attackers use these weak or repeated keys against individual users?
Possibly. However, in order to do that, the attacker would need a lot of things to line up correctly, including being able to locate and intercept a session associated with a specific user and key. That’s certainly not out of reach for some classes of attacker, but it’s not an imminent threat in most cases. “The implication of this is a local rather than a global question,” said Paul Kocher of Cryptography Research. “There are a large number of keys that have no economic value to anyone. If someone can break those, there’s no traffic to decrypt. But it only takes one or two important keys to have a real impact.” To put it another way: “Maybe the bad guys will get lucky and one of the weak keys will lead to some obvious way to steal money, or trade secrets, or national intelligence. Maybe,” Bruce Schneier wrote in his analysis of the research and threat.
Is the security of major Web sites like banks or retailers broken now?
Define broken. Actually, the research team from Michigan and UCSD said that they hadn’t found any major sites with the weak or repeated keys in their scans. However, they did find some repeated keys that had been signed by certificate authorities, which is not good news. Kocher said he’d want to know how many of the keys had been signed by reputable CAs, something that would be an indicator of how serious the problem is. “Of the keys that had problems, how many were signed by reputable CAs? One that hasn’t been signed by a CA wouldn’t be used for a large customer-facing application,” he said.
Where did these weak or repeated keys come from?
In simple terms, they came from flawed random number generators. RNGs need a few things in order to work correctly, and one of those things is some random input, called entropy, that’s used to seed the RNG. In desktop systems, that’s often collected from things such as random mouse movements or keystrokes. But in embedded devices such as home routers, there’s sometimes not a great way to gather that entropy, especially on initial start-up. So some of the repeated keys come from popular devices with stock keys and the weak keys come from RNGs without enough entropy, which makes the keys factorable, which they shouldn’t be. “This shouldn’t come as a surprise. One of the hardest parts of cryptography is random number generation. It’s really easy to write a lousy random number generator, and it’s not at all obvious that it is lousy. Randomness is a non-functional requirement, and unless you specifically test for it — and know how to test for it — you’re going to think your cryptosystem is working just fine,” Schneier wrote.
Can this problem be fixed?
Yes, but not with a patch or some other simple mechanism. It’s really up to each individual affected vendor to fix whatever issue is causing its specific problem. A vendor who makes a wireless router, for example, may need to push out a new firmware update to all of its deployed devices and then also change the way that it implements its cryptosystem in the manufacturing process so that there aren’t weak or repeated keys. For end users, there’s not much that can be done. The researchers say that they’re going to contact all of the vendors affected by the problem, but that will take some time, as will their response. In the longer term, there are things that should be done. “They have to do more work on getting the entropy right, and that’s not an easy problem,” said Nadia Heninger of UCSD. “We may need to repeat this kind of large-scale scanning. Some of the bugs are really rare and they don’t come up in testing.”
Does this mean we should abandon crypto?
Ah, no. What it means is that crypto implementations, like everything else on earth produced by human people, have flaws, and when those systems are deployed on a large scale, those flaws are magnified. It also means that it’s important for people to review cryptosystems and their implementations, no matter how well-known or understood, before they’re deployed. “You have people who don’t have faith in crypto and don’t use it when they should and other people who have way too much faith in crypto, and each of those is a dangerous way to think,” Kocher said.
Who wrote Stuxnet?
Stop it. Please.
