Breaking AES using CPA

In this post we will discuss how to recover the key from the first round of AES (Advanced Encryption Standard). Despite the fact that this encryption algorithm is widely used, standardized for many years and considered safe, it is enough to collect several dozens of power traces to break the key out of a weak implementation. In this post we focus on AES with 128-bits long key, but the attack is easily portable to other key sizes.

We are still using our simple leakage model with Hamming weight for CPA. We know that in AES the first 16 bytes are xor’ed with the key and then there is a substitution phase, in which bytes of the state are replaced by the output from Sbox lookup with those state bytes as index. We will look for correlation between the weights of those Sbox outputs and the points of the power trace. We expect to get high correlation when the value from Sbox comes up on the data bus.

We use implementation of AES provided by ChipWhisperer firmware for XMEGA, originally from avr-cryptolib. Let’s look at some power trace with 24000 samples:

Example power trace of AES execution for a random block of plaintext and a random key

We can observe first couple of rounds of AES in the power trace. Let’s recall how the data is encrypted: AES starts with a 4×4 matrix consisting of 16 bytes of a plaintext called state. The key is extended with scheduling algorithm to 11 keys (for AES-128). The state is xored with the first key (which is actually the same as the input key) and then there is performed 9 rounds of byte substitution, shifting rows, mixing columns and adding round keys to the state. In the final, 10th round operations are the same except there is no column mixing.

We focus on byte substitution, which is simply a function that takes one byte as input and returns other byte as the output. This function is non-linear and can be (and usually is) implemented as a lookup table.

In the first round of AES there is a point (or points) in the power trace when there is some output from the Sbox on the data bus determined by a byte from the plaintext (which we know) and a byte of the key (which we don’t know). For every possible byte of the key (256 options) we find those points using correlation between Hamming weight of the output and the power trace, and then we choose bytes of the key for which the correlation is the highest. We could also look for correlations on xor of the bytes of the plaintext with the bytes of the key or even use both those models, however this approach is sufficient to recover the key and we want to show that not only xor leaks information in CPA.

To check if our model is right we fix some key, collect 100 power traces for random plaintexts and compute correlation between points and the Hamming weight of the known output of the Sbox.

Correlation between the points of the power trace and the Hamming weight of the output of the Sbox

We can see a spike around sample 2750 – it is probably the moment when output of the Sbox lands on the data bus.

Now we can use a fairly standard CPA to recover the key byte that produces the Sbox output that correlates with our power measurements at this point-of-interest the most. We continue for other key bytes, until the whole key is recovered:

Best guesses for byte 0: 
a5 (0.852759625848)
a4 (0.476955094591)

Best guesses for byte 1:
20 (0.825959919864)
21 (0.542856710106)

...

Real key: a52041c23b0b5a55cce574134888f464
Best guess: a52041c23b0b5a55cce574134888f464

In the future posts we will discuss some countermeasures that can be applied to prevent this attack.

All the source code and Jupyter notebooks for this post can be found in our repository:

https://gitlab.com/myrelabs/devblog/tree/master/chipwhisperer/firmware/AES_CPA

Leave a Reply

Close Menu