Breaking RSA with ChipWhisperer

During this attack we will once again use ChipWhisperer to recover information about the time of program execution. Specifically, we will measure how much does it take to process one bit of a secret key in RSA decryption.

What we deal with here is a classical algorithm of fast raising a number to some power. We use RSA implementation from releases of ChipWhisperer. We must mention here, that for XMEGA computing RSA decryption is a bit of a challenge (very time consuming), so decryption is performed with only last 16 bits of the key, that is actually the same as the plaintext we send to XMEGA. All of those simplifications are made for convenience and educational purposes.

The actual piece of code we exploit:

if(flag){            
bigint_square(&res, &res);
bigint_reduce(&res, r);
if(t & (1<<(8-1))){
bigint_mul_u(&res, &res, &base);
bigint_reduce(&res, r);
}
}

This “if” condition is put in a for loop that goes through the bits of the key. Variable tholds the bit of the secret key. If the bit is ‘1’, multiplication occurs. This makes the time of execution strongly dependent on the key.

Compare power traces for 16-bit keys starting with ‘1000’, ‘1100’, ‘1110’ (bits) and all zeros at the later bits:

Power trace for key ‘1000 0000 0000 0000’
Power trace for key ‘1100 0000 0000 0000’
Power trace for key ‘1110 0000 0000 0000’

We can clearly see that when a bit ‘1’ is processed, the program executes more operations – extra multiplication is made, hence processing of that bit is longer.

Our strategy is simple: we will discover when square and reduce function take place. If the time between two such moments is “short” we know that a bit ‘0’ is processed. If time is “long” that means a bit ‘1’ is processed.

Let’s go to the actual attack. We collect a power trace for key ‘1010 1011 1110 0010’ :

Power trace for key ‘1010 1011 1110 0010’

Using “trial and error” approach we take a pattern from the power trace for key ‘1100 …’ from measurements 1899 to 2106 – it’s a beginning part of the 2nd “pike” in the power trace. Using relative differences, we are looking for repetitions of this pattern in the power trace for the attacked key. Take a look at the plot of those differences:

Differences between fragments of power trace for the attacked key and the pattern.

We can see 16 local minima that correspond to the 16 bits of our key. We take the points in which minima occurred and compute how many iterations there are between them,

Points with minima:

[ 1899  2952  3623  4494  5165  6036  6707  7578  8458  9329 10200 11071  11742 12413 13084 13955] 

Number of iterations between them:

[1053, 671, 871, 671, 871, 671, 871, 880, 871, 871, 871, 671, 671, 671, 871]

A natural guess here is that if the difference is more than 671, the chances are bit ‘1’ is processed. This way we obtain a key ‘1010101111100010’ which is the actual key!

The simplicity of the attack proves that is crucial to use time-invariant implementations of computing functions, especially in the field of cryptography. We easily constructed repeatable attack on one of the most prominent cryptographic algorithms on a weak device.

Source code and Jupyter notebook can be found in our public repository:

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

Leave a Reply

Close Menu