Ledger Donjon wins Kudelski Crypto Challenge: Behind the scene 3/3 – A bad DFA countermeasure on AES

This post is part of a series of 3 where we give our solutions to the Kudelski CTF. In this post, we give our solution on the 3rd challenge. The first posts can be read here: Kudelski Crypto Challenge 1/3 and Kudelski Crypto Challenge 2/3

For this challenge a remote server was given. It acts as an encryption oracle. It takes a 128-bit block as input and encrypts it using an unknown key. The problem consists in retrieving the key and decrypting the flag.

First of all, we played around with the server asking for encryptions. With a given plaintext 0xA5A5 A5A5 A5A5 A5A5 A5A5 A5A5 A5A5 A5A5, we asked several encryptions.

It can be done for instance through curl, or python requests.

curl -d '{"data":"A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5A5"}' -X POST https://cryptochall.ks.kgc.io/chall3/encrypt

For instance with the plaintext , 3 kinds of answers were observed.

1. A 128-bit hex string (which seems to be the encrypted version of our plaintext using a secret key)

7cddf879aa5a95dfd240ced4d696a9c1

The same 128-bit hex string with a debug message:

7cddf879aa5a95dfd240ced4d696a9c1
Debug info: AES S-box corrupted at index 124

2. The same Debug info message and an Error Message Ciphertext corrupted.... In this case, no ciphertext is output.

Debug info: AES S-box corrupted at index 45
Ciphertext corrupted by S-box corruption, aborting.

This seems to be a countermeasure against DFA (Differential Fault Attack). The AES encryption oracle does not output any faulty ciphertext. So it’s not a classical DFA.

On the other hand this “Debug” info is very convenient. It gives a lot of information:

• When a fault is injected, the fault corrupts an Sbox
• The index of the corruption is also given
• Moreover there are faults which do not affect the output of the AES

From these outputs, it can be assumed that the oracle randomly generates a fault on a Sbox, which is only used in the datapath of the AES state (not on the datapath of the key). This fault is uniformly distributed on all possible Sbox indexes.

This hypothesis is not invalidated by the statistics.

Assuming that for random input and a fixed key, the distribution of each Sbox input during the AES rounds is independent and identically distributed, the probability that a random fault on an Sbox index does not affect the output is:

Obviously, the independence hypothesis is wrong, since these inputs are actually linked by the AES algorithm equations. However AES is designed to mix up the bits during the algorithm, thus it’s not a strong assumption.

This ratio is verified by simulation, and is also verified on the problem, confirming the initial hypothesis.

It’s then possible to apply a kind of Safe Error Attack. Safe Error attacks take advantage of the knowledge that a fault has been successfully injected in the algorithm and has no consequence on the output. This is precisely the case here, and we’ll use this information to retrieve the key.

As soon as we get a ciphertext output with the debug information, it will mean that during the whole computation of the AES, the index given by the debug information has not been used. This trivially removes key hypotheses.

For instance, focusing on the first round,

are computed (where pt denotes the plaintext). With a safe error fault, we can remove one hypothesis for each byte of key. For instance, if the debug index given is 42, the equation

doesn’t hold.

Using several random plaintexts, it’s possible to eliminate all wrong hypotheses of key bytes until there is only one hypothesis left for each key byte.

This algorithm works perfectly and gives the correct value of key.

Of course, it can be applied the exact same way knowing the ciphertext and targeting the last subkeys.

Possible Optimization

Finally several optimizations can be implemented:

At the end of the research, when only a few hypotheses of keys are left, obtaining a new plaintext which removes the last possible key hypotheses is not very likely. In fact, this is the well-known Coupon’s Collector Problem. The expectation of the number of safe error faults is then given for each byte by

Again, not all the outputs can be used as safe error, thus this number has to be multiplied by the inverse probability of getting a safe error when requesting an encryption from the oracle which gives approximately 3000 safe error faults. Finally, one has to retrieve all the bytes, then the expectation of the number of safe error fault is given by the expectation of the max for the 16 bytes which does not seem trivial to compute.

Eliminating the last possible key byte candidates requires the most safe error faults. But for each plaintext, the corresponding ciphertext is available. This allows brute the force attack which would drastically reduce the number of necessary safe error faults.

This can be optimized generating chosen inputs in order to minimize the probability of obtaining a fault error which has already been used for eliminating key candidates.

Another interesting track is to implement the same algorithm tracking remaining possible hypotheses of byte of keys not only on the first subkey, but on all subkeys’ bytes and take advantage of the key schedule equations. This may be difficult since, the intermediate values cannot be known for sure since they depend on the plaintext and also on previous keys.

Does this attack actually work in a general case?

Short answer: NO

Let me elaborate on this. In this attack scenario, we used the following property:

“When a fault occurs on an Sbox index, if this index is used during the encryption then the ciphertext will be faulty”.

We actually used the contrapositive version: “When a fault occurs on an Sbox index, if the encryption is not faulty then the index has not been used during the encryption”.

In fact, this property does not hold!

It’s possible to find a specific fault index on the Sbox and a couple of key and plaintext such that the index is actually used and the ciphertext is correct.

To retrieve such an example, here is how we proceed. We’re looking for a quadruplet (index, fault, key, plaintext) having this property

The search space is very large, and generating random values for ages does not give any results.

Focusing only on the first round of AES, we have to retrieve a fault on the Sbox such that the faulty Sbox on the second round will compensate the fault on the first one.

A less brutal strategy is then used, focusing on the following part of the datapath:

Subbytes(Mixcolumns(Subbytes(x₀,x₁,x₂,x₃))). We’re looking for x₀,x₁,x₂,x₃ and a fault on the subbytes, such that:

The impact of AddRoundkey and Shiftows will be easily compensated afterwards.

Knowing the fixed points of Mixcolumns, it’s even easier:

Mixcolumns(x,x,x,x) = (x,x,x,x) for a given x in {0,…,255}. We finally only have to retrieve the x and the (index,fault). We end up with a couple.

It appears that sbox[143] = 115 and sbox[115] = 143.

Then, the fault which makes sbox[143] = 143 or sbox[115] = 115 does the job.

We then have

• Sbox’(143,143,143,143) = (143,143,143,143)
• Mixcolumns(143,143,143,143) = (143,143,143,143)
• Sbox’(143,143,143,143) = (143,143,143,143)

and

• Subbytes(143,143,143,143) = (115,115,115,115)
• Mixcolumns(115,115,115,115) = (115,115,115,115)
• Subbytes(115,115,115,115) = (143,143,143,143)

We finally need to put this into AES, compensating the effect of shiftrows and choosing the correct byte for the key to get the correct input in subbytes. We chose to insert this in the first 2 rounds. The first addroundkey makes the 4 attacked bytes equal to 143, and some of the other bytes in the key are such as the targeted 4-bytes of the second subkey are zero.

For instance:

The Sbox is faulted such that Sbox[143] ^= 0xFC

The red bytes are such that the first addroundkey gives (143,143,143,143),the blue bytes of the key are chosen such that the 4 targeted bytes of the second subkey are 00, and the orange byte is chosen randomly. If we choose 00, we end up with another bytes in the encryption which is 143 and makes the ciphertext faulty.

We tend to think this is the only situation where one fault on a Sbox index is compensated later in the algorithm while we have absolutely no proof of this.

Finally, the probability to get such a situation is very low. If ever it appears, the search would end up with no solution on at least one byte of the key. It would be then possible to bruteforce it or to re-run the attack with other plaintexts…

Is such a scenario realistic?

This attack has never been published. One can argue that it applies only on a very weird implementation, and thus would not apply on real world implementation. Indeed, from a security perspective, avoiding to output faulty ciphertext prevents classic DFA attacks. Providing the attacker with the “debug” info by giving the faulty Sbox index is clearly not a good idea security-wise.

However, one can imagine scenarios where such an attack would apply, for example, a hardware based implementation where the Sbox would be stored in a memory. An attacker would be able to induce faults into this memory (using a laser for instance). The implementation would have a verification mechanism to avoid a faulty output.

In order to implement the attack, the attacker only needs to know on which index the Sbox has been faulted. This could happen in several situations. A possible scenario is the following.

The attacker would first characterize the spatial positions (on the circuit) of each Sbox index.

Then in the attack phase, he would have to induce a fault on the memory, finally knowing the position of Sbox index, he would either obtain no output (faulty ciphertext), or a safe error fault.

As fault attacks are not 100% reproducible, the attacker would have to compute statistics on each spatial point to deduce if a given plaintext and a given position give either a safe error fault or a faulty ciphertext.

Other ways to deduce index of faults could be used such as Side Channel Information whilst spatial prior characterization seems to be the most practical use case for this attack.

The code can be found in our GitHub.