The first talk on Monday afternoon at EuroCrypt'13 was given by Nicolas Veyrat-Charvillon on "Security Evaluations Beyond Computing Power - How to Analyze Side-Channel Attacks you Cannot Mount?" (with B. Gérard and F.-X. Standaert as coauthors). The paper addresses an issue faced by certification labs that have to assess the security of a device against side channel attacks: In certification you know everything about the device that you are attacking, you know the key that you're attacking but if, after having made a certain effort, the side-channel attack doesn't yield the correct key you want to know how far away of the correct key you are.
Let's look at the example of a side channel attack on AES: After the attack, you have for each 0<=i<16 word of the state a probability distribution Di that contains the probability of every possible value for this word. So you can compute for all of the possible 2128 keys their probability as returned by the attack. In particular, you can compute the probability of the most likely key and the probability of the correct key. (Of course, a real attacker wouldn't know the correct key; you know the correct key only because you're a certification lab staging an attack on something you already know.) The big question that remains is: How many other keys have a probability higher than the correct key? If the certification lab can answer that question with a good enough approximation, then they know how much additional effort is needed to complete the attack by brute force.
The stupid way to answer that question is to check the probabilities of all 2128 keys. But of course, if you were able to do that, you wouldn't need a side-channel attack in the first place, you could just brute force AES. The authors present in their paper the first feasible method to answer this question with a reasonably good approximation. Their primary idea is to arrange all the possible keys in a suitable hyper cube representation where they can make suitable time-memory trade-offs in the arrangement. This enables effective carving out of key candidate volumes that all have bigger or smaller probability. So they only have to keep track of the size of the carved out volumes and, when the remaining volume is small enough, they have their answer.
Obviously, being able to tell how much additional brute force effort is needed after a failed side-channel attack is important for certification labs to make a qualified judgement about the device's security. So the biggest remaining question for follow-up work in this direction is: Does the remaining brute-force effort relate to the additional number of traces that need to measured, stored & processed for a pure side-channel attack to be successful? Would the attacker be better of continuing with more measurements instead of brute-forcing at the end?
Let's look at the example of a side channel attack on AES: After the attack, you have for each 0<=i<16 word of the state a probability distribution Di that contains the probability of every possible value for this word. So you can compute for all of the possible 2128 keys their probability as returned by the attack. In particular, you can compute the probability of the most likely key and the probability of the correct key. (Of course, a real attacker wouldn't know the correct key; you know the correct key only because you're a certification lab staging an attack on something you already know.) The big question that remains is: How many other keys have a probability higher than the correct key? If the certification lab can answer that question with a good enough approximation, then they know how much additional effort is needed to complete the attack by brute force.
The stupid way to answer that question is to check the probabilities of all 2128 keys. But of course, if you were able to do that, you wouldn't need a side-channel attack in the first place, you could just brute force AES. The authors present in their paper the first feasible method to answer this question with a reasonably good approximation. Their primary idea is to arrange all the possible keys in a suitable hyper cube representation where they can make suitable time-memory trade-offs in the arrangement. This enables effective carving out of key candidate volumes that all have bigger or smaller probability. So they only have to keep track of the size of the carved out volumes and, when the remaining volume is small enough, they have their answer.
Obviously, being able to tell how much additional brute force effort is needed after a failed side-channel attack is important for certification labs to make a qualified judgement about the device's security. So the biggest remaining question for follow-up work in this direction is: Does the remaining brute-force effort relate to the additional number of traces that need to measured, stored & processed for a pure side-channel attack to be successful? Would the attacker be better of continuing with more measurements instead of brute-forcing at the end?
No comments:
Post a Comment