# Donjon Ledger CTF 2020: Random Learn

## Introduction

This article presents one way of solving the Random Learn side channel challenge released during the Donjon Ledger 2020 CTF. In side channel challenges, the goal is to retrieve the secret key of a cryptographic algorithm using physical measurements performed while the device was operating (time, power, electromagnetic emanations, temperature…).

Before this competition, our team had almost zero experience with side channel attacks. We learned the basics by reading papers and applying them to the different challenges proposed during the competition. In this article, I describe my understanding of the concepts and techniques we used with a beginner’s point of view. As a consequence, the methodology presented here may appear a bit approximative or even wrong to experienced readers. Do not hesitate to ping me on Twitter if some stuff I write needs to be corrected.

Kudos to my teammate i27, who did an important part of the work for this challenge and took the time to explain me his approach so we could work together to get the flag.

## Initial data

The target for this challenge is an AES execution on a “non-secure” MCU (*Microcontroller Unit*). The following datasets are provided:

`variable_k_p`

: 200000 power traces with random known plaintexts and keys;`unknown_k`

: 200 power traces where known plaintexts have been encrypted with the same unknown key.

The goal is to **retrieve the unknown key** used in the second dataset. It appears that the spirit of the challenge is to use the first dataset to infer some relations between`[power, plaintext, keys]`

and apply them to the second dataset to guess the unknown key. In the next section, we start by working on the first dataset:

## What exactly are we looking at ?

Let’s plot one power trace to get a better idea of which part of the AES execution we are dealing with:

A pattern is repeated 16 times in the power trace. This shows that **each byte of the AES state is manipulated independently**. Moreover, the description of the challenge indicates that the “beginning of the AES execution” was captured, so we are probably somewhere inside the **first round**.

Since it’s a classic approach to target SBox outputs in side channel attacks, I am going to make the hypothesis that the power measurement was performed during the **SubBytes** operation (one pattern = one SBox substitution).

## Correlation Power Analysis (CPA) 101

The fundamental observation exploited in power-based side channel attacks is that, at any point in time, there is a direct relation between the values of the bits transiting on data buses and the power consumption of the device. To put it in a different way, during the AES computation, the power consumption will vary depending on the value of the data manipulated by the algorithm.

One very powerful analysis technique is the **Correlation Power Analysis (CPA)**. Given a sufficient amount of power traces, this technique applies simple, yet powerful statistical tools to extract bytes of an unknown key.

To perform a CPA, you first need to **define a model for the power consumption**. A simple approach that is often used is to model the power consumption at time t as the hamming weight (number of 1 bits) of the data unit (a byte on a 8-bit microcontroller) manipulated at time t.

*Note : The raw byte value can also be chosen in place of the hamming weight. Both are used in the resolution of this challenge and give interesting results.*

Then, you must **pick an intermediate value that you will target** in the cryptographic algorithm. The idea is to choose a value that depends on the key so you can use it to make key guesses later in the attack. In the case of AES, interesting targets can be identified by looking at the SubBytes operation of the first round:

By targeting **a byte of the state at each SBox output**, we can use the CPA to guess the key bytes`K[i]`

one by one. The different steps to perform this attack are the following ones:

- Measure the real power consumption
`P`

for many different plaintexts`pt`

; - For each key guess K_guess:
- Compute the theoretical power consumption
`P_th_guess = hamming(SBox[pt[i]^K_guess])`

for all the plaintexts`pt`

- For each point in time t, compute the correlation between
`P`

and`P_th_guess`

using the Pearson’s coefficient.

- Compute the theoretical power consumption
- The correlation graph that contains the highest correlation value corresponds to
`K_guess = K[i]`

What is really mind-blowing with this attack is that we don’t even need to know at what time`SBox[pt[i]^K[i]]`

is computed on the real power trace. Indeed, the `K_guess`

that yields the highest correlation value gives both the value of `K[i]`

AND the time at which`SBox[pt[i]^K[i]]`

is computed, thanks to the position of the spike.

Given a sufficient amount of power traces, this approach can be used to easily recover the entire key. Colin O’Flynn, the father of the ChipWhisperer, has made an excellent introduction video on the subject. It really helped me a lot to understand a bit of the magic behind side channel attacks. If you are unfamiliar with this topic, I encourage you to watch his video and come back here after.

## First (naive) CPA attempt

Now that we have a bit more background on CPA attacks, let’s get back to the challenge.

The first step of the analysis is to verify on the dataset with known`[plaintext, key]`

that we obtain high correlations at the output of each SBox. We will then be able to use these **leakage points** to perform the CPA attack on the dataset with the unknown key.

As explained in the previous section, we will model our theoretical power consumption at time t as the hamming weight of the byte manipulated at time t.

Let’s start with the first SBox. We compute `P_th = hamming(SBox[pt[0]^K[0]])`

for every plaintext and then calculate the correlation with the real power at each point in time.

Aaaaaaand… it didn’t work. Unfortunately, there is no correlation spike hidden behind baby Yoda. The same results is obtained for the 16 outputs of the SBox. Just in case, we also performed the following tests:

- Model the power with the raw value of the state byte instead of the hamming weight;
- Looking for correlations using the values of the key bytes
`K[i]`

instead of the SBox outputs.

The first test did not give anything interesting. For the second test, none of the key bytes yielded a high correlation except`K[15]`

:

So it seems that we are able to leak the value of`K[15]`

. However, without any more information, we are not going to go very far. At this point, we didn’t really know what was wrong with our approach. But at the same time, the challenge would not be worth 300 points if the classic CPA was working directly.

The most probable hypothesis is that they are some **mitigations to prevent the SBox outputs from leaking**. Since, the description mentions a “non-secure MCU”, those potential mitigations are likely implemented at the software level. Time for a bit of Googling !

## Masking schemes

After doing some research on the subject, it appears that there are indeed a lot of ways to protect an AES implementation against CPA attacks. One popular family of mitigations is called “masking”. In masking schemes, the idea is to randomly **split every sensitive intermediate variable** occurring in the computation into n+1 shares, where n is called the masking order. An example of a masked AES with order 1 is used in the section 2.5 of the article *Study of Deep Learning Techniques for Side-Channel Analysis and Introduction to ASCAD Database*. Since the order of the mask is 1 in this example, each byte of the sensitive data is split into two parts:

Assuming that the AES implementation in this challenge is protected with a similar masking scheme (this assumption may be wrong), let’s see if we get some results by performing a second order attack on the dataset.

## Looking for order 2 leakage points

In second order attack, the idea is to combine two points (t1, t2) of the power trace where the masked values are manipulated to remove the effect of the masking. For the combining function, two main candidates seem to be used:

- Absolute Difference:
`D(t1, t2) = |P(t2) - P(t2)|`

- Centered Product:
`CP(t1, t2) = (P(t2)-E[P(t2)])*(P(t1)-E[P(t1)])`

where`E[P(t)]`

is the mean of the power P at time t

The authors of the article *Statistical Analysis of Second Order Differential Power Analysis* argue that the Centered Product often yields better results. Let’s try to apply that approach to our power traces.

Once again we start by attacking the output of the first SBox. To do so, we compute the Centered Product`CP(t1, t2)`

for every`(t1, t2)`

couple and look for high correlations with `P_th = SBox[pt[0]^K[0]]`

. Since we are attacking the first SBox, we can save some computing time by just looking at the beginning of the trace (`t < 200`

).

*Note: You may wonder why we use the raw byte value instead of the hamming weight for the power model. Actually, we tried and used both during the CTF, but overall the raw byte value gave better correlations in most cases.*

Nice, the approach seems to work ! We found some interesting correlations around `(23, 143)`

. Let’s see what happens if we repeat the experiment on the second SBox output:

The best leakage point is`(23,243)`

for the second SBox. We obtain`t1 = 23`

once again, it cannot be a mere coincidence ! This seems to confirm that the AES is protected with a masking scheme with the mask applied at`t1 = 23`

and the masked value manipulated during `t2`

at the output of each SBox.

Now that we know that the masking is applied around `t1 = 23`

, we can fix the value of t1 and compute `t2`

for each SBox.

If we plot all the`t = t2`

lines on top of any power trace, we can see that they match the output of each SBox:

## Leaking the unknown key

Thanks to the work done on the first dataset with known`[plaintext, key]`

, we have 16 leakage points`L[0], L[1], ..., L[16]`

that we can use to guess the value of each key byte on the second dataset.

For each unknown key byte`K[i]`

, we use the leakage point`L[i] = (t1_i, t2_i)`

to perform a CPA attack as described at the beginning of the article. The only difference is that here we have already chosen the points in time that should give the highest correlation using the first dataset.

For each key guess K_guess:

- Compute the theoretical power consumption
`P_th_guess = SBox[pt[i]^K_guess]`

(raw byte model) for all the plaintexts`pt`

- Compute the Centered Product
`CP = CP(t1_i, t2_i)`

for all the plaintexts - Compute the correlation between
`CP`

and`P_th_guess`

- The highest correlation should correspond to
`K_guess = K[i]`

Mmmmh, it seems that only some of the bytes are correct… Our approach does not work perfectly; probably because we only have 200 power traces for the unknown key. Still, it feels like we are pretty close to the solution and after all these efforts, we are not going to go home without the flag.

Time to get a bit dirty.

## Using the (Brute)Force

First of all, we know that the AES key is the flag of the challenge, therefore it should be composed of printable characters.

Then, we observed that when modifying the number of traces`N`

used to compute the leakage points, the second coordinate `t2`

of some of these points would vary while others would remain unchanged. For instance:

`N = 10000 => L[12] = (24, 1727) => K[12] = ' ' (0.201208)`

`N = 50000 => L[12] = (24, 1716) => K[12] = g (0.27219)`

But:

`N = 10000 or N = 50000 => L[2] = (24, 396) => K[2] = a (0.299622 > 0.25)`

This shows that the location of the leakage point is unstable for some SBox.

Another observation we made by experimenting a bit, was that using the hamming distance instead of the raw bytes during the CPA could sometimes give interesting results.

Therefore, we wrote a short script to do the CPA on all the points of a rectangle around each computed leakage point L, using both the raw byte value and the hamming weight. The idea is that if we are able to guess enough bytes of the key this way, we will be able to bruteforce the missing bytes by performing AES using a known`[plaintext, ciphertext]`

couple.

It worked ! We are now pretty confident about 9 bytes of the key and have few candidates for 3 other bytes. This is more than enough information to perform a quick dirty inefficient AES bruteforce with Python on a known`[plaintext, ciphertext]`

couple:

## Conclusion

After a lot of paper reading and experimentation, we manage to solve this challenge with no prior side channel experience. Thanks to the Donjon Ledger team for organizing this CTF and providing such a great learning opportunity.

On a side note, it’s likely that the second order CPA was not the intended solution. Indeed, the title and set-up of the challenge were more hinting toward a template / machine learning based solution. Moreover, we obviously abused the fact that the key was composed of printable characters in our approach. I hope that other write ups will be published so we can have more details about the intended solutions.

One more thing. While I was writing this article, I stumbled upon something that could have saved me a bit of time during the challenge:

Well, I guess I need to do crypto more often…