Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Differential Fault Analysis by examples

So, after more than a year without writing anything here, I was bored today and thought it would be nice to share a new piece on attacking cryptographic implementations here 🙂

Differential Fault Analysis (DFA) attacks are part of what is known as fault injection attacks. This is, they are based on forcing a cryptographic implementation to compute incorrect results and attempt to take advantage from them. With fault injection attacks (also often called active side channel attacks) one can achieve things like unauthenticated access to sensitive functionality, bypassing secure boot implementations, and basically bypassing any security checks an implementation performs.

With DFA attacks, one is able to retrieve cryptographic keys by analyzing correct/faulty output pairs and comparing them. Of course, this assumes you are able to inject faults somehow... which is often true in hardware implementations: gaming consoles, STBs, smart cards, etc. At the software level, one can achieve similar things by debugging the implementation and changing data or by patching instructions... but this is something we have been doing for a long time, haven't we? 🙂 I often say that fault injection attacks are the analog version of 'nopping' instructions out in a program, although we often do not know exactly what kind of faults we are injecting (i.e. we often miss a fault model, but we still successfully attack implementations in this way).

There are ways to protect against this kind of attack as an application programmer, but this is not the objective of this post. In the remainder of this post, I will explain two powerful DFA attacks on two modern cryptographic algorithms: RSA and (T)DES. For some information on protecting from these attacks as a programmer, take a look at these slides. If there is some interest, I will outline the most common techniques to perform fault attacks in a future post.

DFA on RSA-CRT

I've explained this one a number of times, and I even posted a challenge I created for CP Europe, but the attack itself I only explained in Spanish. So we know RSA uses big big numbers and performs a modular exponentiation over them. However, modular exponentiation algorithms tend to be expensive in computing time so people try to find ways to make them faster. In any case, most implementations have an execution time that is linear with the key size, which means that when you double the key size the exponentiation time doubles as well.

This is where RSA-CRT comes to the rescue. This way of implementing RSA is based on splitting the exponentiation in two halves. For this, they make use of the Chinese Remainder Theorem, which basically says that you can compute a result modulo by splitting it into two computations modulo p and q respectively.

So, in RSA we need to compute , but what we actually do is computing intermediate results modulo p and q and then combining them. So we compute and , and we combine them to obtain the whole result like this:

Now, imagine you are able to modify one of the two exponentiations, for instance you modify and get instead. Now, if we subtract the two results, c and c', we get the following:

Obviously, many of these terms are the same on both sides, and thus we can simplify this result a lot:

And, oh surprise, this number is a multiple of one of the primes. Thus, if we compute the Greatest Common Divisor of c-c' and n, we obtain the common factor p. From there we can compute the other prime, q, by just dividing n/p. And with this we know all the information we need to obtain the private key d. This attack is referred to as the Bellcore attack, due to the fact that it was published by Bellcore labs in 1996, and is a deadly attack against RSA implementations using CRT and not protecting themselves sufficiently.

There are also other DFA attacks on other implementations of RSA, however they are more difficult to understand and require many more faults than the attack outlined here. If you are interested, I'm sure you can find many examples in the literature. Otherwise, feel free to contact me 😉

DFA on (Triple)DES

As a second example, I will quickly describe how DFA attacks on DES work, so that you do not have the impression that only RSA is vulnerable to this kind of attacks. Let's first remind how a DES round looks like:

 

Where the F function looks like this:

Now, imagine you are able to know the input/output pair of the F function. Since the key is used only 6 bits at a time, you can easily try out each one of the 8 sub keys (64 possibilities for each of them) and find whether the related output bits match or not. This only requires 8 6-bit bruteforce attacks (9 bits in total) to obtain the whole round key. Obviously, this is not possible... that's precisely why you XOR it with the other half of the state and add more rounds to the algorithm: you don't want people to be able to break it so easily!

However, let's assume we can inject a fault in the input of this function for the last round (or a fault during the execution of the previous round, which leads to the input of the function for the last round).

Now, from the output of the algorithm, we can obtain two pairs of inputs to the F function: correct and faulty inputs.

Additionally, the other two halves give us the result after the XOR for the two executions: good and bad execution. However, the value that has been XORed with them is computed during round 14 (i.e. two rounds before the end) and has not been affected by our fault injection attack.

Thus, this value is unmodified, and if we XOR the two left halves we get the difference between the good and the faulty output of the F function. So, we have:

- Correct input

- Faulty input

- XOR of correct and incorrect output

Now, remember that I said that only 6 bits of the key are used each time. And they pass through the S-boxes, and then they go into the P permutation. Now, since we have these input/output relations, we can use the correct and incorrect inputs, XOR them with a 6 bit key guess and perform the S-box lookup.

Then we XOR these two results, and we have the output difference as well. It turns out (and here is the magic) that thanks to the S-box structures only a few values for the sub key will match. Thus, this allows us to reduce the entropy of the key.

If we repeat this a few times, then we can reduce the list of possible keys to one. Or alternatively, we can give a point to each key that matches at every attempt. Then we get a number of these faults, perform this process for each of them, and then check the highest score: this is our key.

If you repeat this process with round 15 instead of 16, then you get enough information for a full DES key. If you have Triple DES, then you need to move over to the inner DES and repeat these two steps again. Alternatively, if input and output to the DES/TDES are known you can stop when you still miss the last round key, and bruteforce the last portion of it (just 8 bits).

Final thoughts

As I said before, not only DES and RSA are susceptible to DFA attacks. In the literature, one can find several DFA attacks for AES, Camellia, elliptic curve implementations, etc.

For an application running under the control of an attacker (being it a hardware implementation such a smart card or other types of implementations) it is important to apply adequate countermeasures in order to protect the keys.

State-of-the-art countermeasures at the software level typically include double-checking results, adding time variation to the algorithm so that the attacker cannot predict the point of injection and in general adding redundancy in order to detect the attacks and react accordingly.

Hopefully this post helps raise awareness on this kind of attacks 🙂 Any feedback is more than welcome!