How power usage can tumble security
Differential power analysis can break cryptographic keys
Paul Kocher, president of Cryptography Research, was part of the team that developed differential power analysis, a technique for breaking cryptography by observing how much power a system uses. He grew up in Oregon, where his physics professor father would bring him computers to play with. He taught himself programming by figuring out how the hardware worked. While studying at Stanford University to become a veterinarian, he worked part time at RSA Security, where he became fascinated with cryptography and security. After earning his bachelor's degree, he chose the information technology business rather than veterinary medicine.
GCN: How did you make the transition from veterinary medicine to cryptography and security?
KOCHER: My original plan was to become a vet. To be clear, I don't actually have a degree in veterinary medicine. But the perspective of someone who works with living systems is often one of trying to see how a system will respond to a particular stimulus. We don't know how it works, but you can see how it reacts to external stimuli.
The way a lot of security work is done is similar. You have a system [and] you don't really understand what its risks and properties are, what will make it live or die, and you need to figure that out. At some point, the analogy breaks down because living systems are vastly more complicated than any computer system we are working on. But the research process actually is quite similar.
GCN: When did you make the jump?
KOCHER: It was around my senior year of college, when the dot-com boom was just beginning and it became clear that there were a lot of really interesting unsolved problems in computer security that I had spent a few years pursuing. I haven't looked back yet.
GCN: One of your achievements is helping to develop differential power analysis. What is DPA?
KOCHER: It's a technique that lets you analyze measurements of how much electrical power a chip is consuming as it operates, [in order] to figure out what the cryptographic keys are. It is analogous to listening to the clicks coming from a safe to figure out what the combination is, but instead of using sound, you're using electrical power consumption.
It turns out that unless a chip is designed very carefully, it is going to be vulnerable to these kinds of attacks. You can filter out the key from all the other stuff that is going on in the system. Everything that isn't the key falls away, and given even incredibly noisy measurements, you can find the key.
GCN: How do you filter out the noise and make the key stand out?
KOCHER: What you do is make a guess as to what a little bit of the key might be, and then you look and see whether that guess is correlated to the measurements you collect. Everything else in those measurements is going to be uncorrelated, except for the piece you are looking for. If the piece is absent, you will see no correlation at all.
GCN: How do you defend against DPA?
KOCHER: The most effective technique is changing keys frequently and building the protocols in such a way that you never use a key so many times that somebody can start collecting physical information about it. There are some techniques you can use for public-key systems that let you modify the way the private key is represented and used so that information that leaks out of one transaction can't be correlated to what leaks out of subsequent transactions.
There are some techniques that help, but [they] are not complete solutions. You can try to reduce the correlation or add timing noise or other random processes going on, and those can help some. But they do not solve the fundamental issue the way that limiting the use of the key can.
GCN: Where is this type of attack most likely to be used?
KOCHER: It's focused on systems on which the adversary can get some access to at least the power consumption or electromagnetic emanations. Identity cards are an area of major concern. It also is one of the bread-and-butter attacks used by pay-television pirates and people who do counterfeiting. There also are implications where you have server boxes that emanate information through [radio frequency] radiation. But the areas of greatest concern for government folks would be any type of device that can fall into the wrong hands, such as keying devices, identity cards, door entry credentials and network log-in tokens.
GCN: Can information from one token be used to extrapolate information about keys from other tokens?
KOCHER: If the system is designed properly, so that each device has unique keys, there shouldn't be a problem with that. In practice, you could end up with a systemic consequence from one token being compromised. If someone temporarily borrowed a credential, pulled the key out of it and returned it, that copied credential may function for a very long time before somebody recognizes that it is being misused.
GCN: Are there legitimate uses of DPA as a tool?
KOCHER: It primarily is a security concern. There is a legitimate use for it in testing products, both in the design process as well as in the certification process. The tools we make we only sell to legitimate organizations such as testing labs. There is no legitimate reason for the man on the street to be able to do this. The bad guys already know how to do this. It's cheap, it's noninvasive, you can do it with a few thousand dollars' worth of equipment, so there is nothing keeping them from doing it, but the good guys often don't know how to build devices adequately or test them, so it is important to get this capability into the hands of people building the products.
GCN: What is timing analysis?
KOCHER: It is a somewhat related kind of attack, in which instead of measuring power consumption you measure how long it takes a device to do a computation. If you send millions of different messages to a server and look at how its response times vary depending on what you put into the messages, you can learn something about the computations being done. If it is not properly protected, you can figure out what its keys are. That kind of attack is practical to mount over a computer network, but it is easier to protect against by making sure that your response times don't vary.
GCN: Do government standards such as the Federal Information Processing Standards adequately address these techniques?
KOCHER: The U.S. standards that are in effect now do not require any protection at all. In the FIPS 140-2 standard, it is an optional element, but it is not required and vendors haven't been spending very much effort putting in protection. The vast number of devices being used by the government in nonclassified systems are trivially breakable with these techniques. There is a new FIPS 140-3 standard being finalized now, and that will require countermeasures to power-analysis attacks.
In contrast, European standards have required countermeasures for quite a long time. For products being certified under the European Common Criteria, power analysis is the primary thing they are being tested for. So if you are buying products that have been certified under the Common Criteria regime, you will have products that have been well-tested.