>/posts/Side-Channel Attacks X Sword of Secrets - Extracting AES Keys $

In the last episode

In the last episode, we covered how to prepare the shunt resistor and connect it to the target circuit, and then used that setup to perform a basic SPA attack. This time, using the same measurement setup but with some more advanced math, we'll go much further. We're going to attempt something that might seem nearly impossible: recovering the full AES key!

Math theorem

AES is strongly non-linear, so there is no practical way to derive the key directly from a plaintext/ciphertext pair. However, power consumption can correlate with intermediate values processed during AES, such as the output of the S-box. This allows us to attack the key byte by byte instead of trying to guess all 128 bits at once. This is the basic idea behind CPA/DPA. Depending on whether we can observe leakage during encryption or decryption, we can target intermediate values from the first or last round. The last round is particularly interesting because it doesn't contain the MixColumns operation, which makes the relationship between individual state bytes and key bytes easier to model.

- Ok, but how does sniffing power consumption lead us to the correct key?
- No worries, we will explain it

Since the AES S-box is a well-known public structure, we can calculate and predict its output for every possible input.

- Ah yeah, great, I can do that too, so what's the deal?
- Be patient

For every possible value of a key byte, from 0x00 to 0xFF, we can calculate the corresponding S-box output for each known input byte. In other words, we have 256 different key hypotheses. Each hypothesis produces a different sequence of predicted intermediate AES values. Then, for each predicted value, we calculate its Hamming weight.

- Hamming weight, what's that?
- Well, in simple terms, it's just the number of ones within a byte

I.e. HW(b10101010) = 4.

The reason we care about Hamming weight is that, in many digital circuits, power consumption is statistically related to the number of bits being processed or changing. It is not a perfect model of the physical device, but it gives us something extremely useful: a numerical prediction that we can compare with our measurements.

Now that we have captured a bunch of traces, we can try to guess the first key byte. For each of the 256 possible key byte values, we calculate the hypothetical S-box output and its Hamming weight for every trace. This gives us a predicted power-consumption vector for each key hypothesis.

We then calculate the correlation between each hypothesis and the actual measured power consumption at every sample point in our traces. If one particular key byte hypothesis produces a noticeably higher correlation than the others, there is a good chance that we have found the correct key byte.

We can then repeat exactly the same process for the remaining 15 bytes.

- Great, so after all these calculations we have MAYBE 1 guessed byte, that's 15 left...
- That's correct, but if you haven't noticed yet, by this way we exchanged the \(2^{128}\) problem for \(16*256*2000\) (in case of 2000 traces), and it's \(2^{13} * 10^3\), which is still smaller than the full key space and also which is most important; calculating AES with one byte changed destroys the entire output, while in a CPA attack you can guess even 14 bytes and bruteforce the remaining 2 with relatively small effort.

The important part is that we are no longer searching through the entire 128-bit key space. Instead, we independently test 256 hypotheses for each of the 16 key bytes against our measurements. With 2000 traces, this means evaluating roughly:

$$ 2^{128} > 16*256*2000 $$ $$ 2^{128} > 2^4*2^8*2*10^3 $$ $$ 2^{128} > 2^{13}*10^3 $$ $$ 2^{128} > 2^{13}*10^3 /2^{13} $$ $$ 2^{115} >> 10^3 $$

Of course, this is a simplified comparison because calculating a CPA correlation is not equivalent to testing a single AES key. Still, it demonstrates why side-channel leakage changes the problem so dramatically. Instead of treating the AES key as one indivisible 128-bit secret, we exploit physical leakage to recover information about individual bytes.

Hardware Setup

Once we're done with the math explanation, we can jump straight into its practical application. First of all, I desoldered the C2 capacitor located right after the LDO. Since the DUT is supplied by the CW Husky directly after the regulator, we don't really care about C3 located before the LDO. OK, to be honest, this wasn't the first thing I did. Initially, I captured a bunch of traces while the capacitor was still smoothing out the power fluctuations I was trying to measure, which cost me some time. Removing it significantly improved the visibility of the signal and made the measurements much more useful.

Here is what the full setup looks like:

Final destination

The next thing we need to do is somehow trigger an encryption or decryption operation. Luckily, we have the source code for at least part of our target device, and we know that it tries to decrypt some data once we send the SOLVE command over UART. The ChipWhisperer Husky also supports 3.3 V UART, so we can connect it directly to the target using the visible red and yellow wires. Here is the UART communication:

>SOLVE
>MAGICLIB{No one can break this! 0x20000}
>Invalid Header

It looks like the decryption takes place after the first task has been checked and its response has been printed. Knowing this, we can trigger the capture near the end of the first task by matching the final part of its UART output. Therefore, scope.UARTTrigger.setpatternmatch(0, "0x20000}") gives us a good starting point. Here is the captured trace:

The next step is to capture a few more traces and check whether the measurements are reproducible. The screenshots below demonstrate that they are. Here are four traces overlaid on top of each other:

Even though a single trace doesn't immediately look like anything familiar, things become much clearer once we capture and compare a larger number of them. A repeating structure corresponding to the 10 regular AES rounds starts to become visible.

Looks like we're ready to perform a CPA attack. It took around 15 minutes to calculate all the key byte candidates, but eventually we got a complete key:

And it fails:

:X

Something clearly has to be wrong. And obviously, there was.

Because the IC used in Sword of Secrets doesn't expose a clock pin that we can use to synchronize our captures, the individual measurements are slightly shifted relative to one another. This is a serious problem for CPA: correlation is calculated sample by sample, so the same operation needs to occur at approximately the same sample index across all traces.

If one trace contains the interesting operation at sample 1448 while another contains it at sample 1450, we're effectively correlating different moments in time. Even a relatively small amount of jitter can therefore destroy an otherwise visible correlation peak. Here is a comparison of the traces before and after the required alignment:

Once the traces were properly aligned, it was time for another 15 minutes of calculations.Here are difference between non-aligned and aligned traces:

And there we are:

The full AES key was extracted simply by listening to the target's power consumption. It still feels almost impossible when you think about it: we never read the key directly from memory, never dumped it from the firmware, and never broke AES itself. Instead, we observed a physical side effect of the computations performed by the device and used statistics to reconstruct the secret byte by byte.

Finally, the correctness of the recovered key was confirmed by the author of the challenge themselves!