1. Correlation Power Analysis on AES

1.1 Background

• Wikipedia page on correlation and dependence
• Advanced Encryption Standard
• GNU Octave documentation

1.2 Setup

Open a terminal, go to your local home directory:

and execute these commands:

If you garbled up the sources or trace data, you can re-download the source code archive for the CPA attack and extract it again.

The directory contains electromagnetic traces (taken at contact with an FPGA, hence the 0cm suffix), AES code, a leakage model, and a CPA attack. All code is written for MATLAB or GNU Octave. Octave is free software, and is capable of running most of MATLAB code. It might not always be as performant as MATLAB, but does a very good job for us. In order to execute code with octave, start its interactive gui shell by typing this command in the terminal:

This should fire up the octave main window. Inside the octave shell, type

to execute the attack, and check whether it works. The result should look like this:

Here are some hints for working with Octave:

• If you don't end a command with a semicolon (;), the result will be printed out in the console!
• Use commands plot, var, etc. (use help var to get help on the function plus syntax). In the gui, you can right-click on a variable in your current work-space in order to plot its contents directly.
• Octave is matrix-oriented. The transpose of matrix tab_Obs is tab_Obs'. The dimension of a matrix is size(tab_Obs).
• You can select a sub-matrix using parenthesese: tab_Obs(1:1000,:) is the campaign with only the 1000 first traces.
• If for some reason, you clobber tab_Obs, simply reload it using load 'tab_Obs_0cm.mat';.

In the following, you will need to edit the octave source files. You can open them in the octave gui by just double clicking on the file name in the small explorer window on the left. You can also use your favorite text editor (gedit, vim, emacs, atom, ...) if it is installed on the machine. These are the source files in the cpa directory:

• aes.m contains the cryptographic algorithm AES,
• cpa.m contains the core of the CPA attack,
• InvSbox.m contains a function to compute the inverse of the AES S-Boxes,
• main.m contains the top level script that reads in the measurement data and executes the attack.

1.3 Exercises

Recall the basic ideas of the Correlation Power Analysis (CPA) attack and try to understand the Octave code running the attack. The goal of this exercise is to analyse and understand the attack strength and its conditions by changing some parameters or parts of the implementation of the attack.

A) S-Boxes. Try other S-Boxes (notice that in the original code S-Box Nr. 2 is used). Is the AES implementation serial or parallel?

B) Alignment. Compare the CPA curves with the raw EM traces. Where is the last round? Some illustrations are given in the two plots below: all the curves, and the variance of the curves.

Now, before running the attack, try to disalign the traces by shifting the rows of tab_Obs individually by a random amount. For this exercise, create a file named disalign.m containing a function that takes the observation matrix and a maximum shift amount and that returns the distorted observation matrix:

In order to implement this function, check out the documentation of octave's unifrnd and shift commands.

• How does the best correlation change with the shift amount when running the attack on distorted data?
• Can you think of a protection against such attacks based on your observations?

C) Partial attack. Instead of taking into account a whole byte of deciphered data, run the attack by using only a single bit of data. For this purpose, you will need to change the code in the file csa.m. You may want to consider the documentation for bit manipulation commands. Can you still extract the correct key?

In a second step, create a parameterized version of the attack that will consider between 1 and 8 bits of data. For this exercise, copy the attack code csa.m to a file named csa_bits.m and implement the attack:

• How many entries do will you need for the hamming weight table?
• What changes are needed to truncate I5 and F5 to n bits?
• How does the best correlation value change with the number of considered bits?

D) Incomplete model. In principle, the attack considered in this exercise requires that the attacker knows the encryption algorithm in order to be able to come up with a suitable prediction on the leakage. We wish to explore if the attack works even if we have partially wrong or incomplete information on the implementation:

Modify the implementation of the S-box in the file InvSubBytes_Sbox.m (or, better, copy the file to InvSubBytes_Sbox_faulty.m and change the copy). For example, by altering some or all of the entries in the lookup table. Try small to large modifications and test if the attack still works.

In a second step, do the same for the Shift Rows step of AES by modifying the table invShiftRows_sbox in the file cpa.m.

• How do the modifications affect the effectiveness of the attack?
• What are your conclusions with respect to the design principles "security by obscurity" and "security by clarity"?

2. Differential Power Analysis on DES

The goal of this exercise is to realize a DPA attack on already acquired traces, and to compare different power consumption models (mono-bit, Hamming distance on one nibble, etc.) The power traces you'll use have been acquired by the Sécurité Matérielle lab of Télécom ParisTech (département COMELEC, équipe SEN), in april 2006, and used for the international "DPA contest" organized by Télécom ParisTech. This contest targets DES.

2.1 Background

• Data Encryption Standard (DES)
• Python documentation
• To try out some code, it can be useful to open an interactive python session, just type python in your shell. It can also be used to display the documentation of a python function or object, e.g. help(range).

2.2 Setup

Go to your local home directory:

Execute the following commands to get the sources for this exercise:

If you messed up with the files, you can re-download the source code archive for the DPA attack and extract it in your home directory.

2.3 Exercises

A) Understanding the code. Open the file dpa_des.py with a text editor and quickly read through the code.

• At which point of the DES encryption does the attack take place?
• Is the attack based on clear text or on cipher text?
• How many bits are used to calculate the leakage function?

Open the file dpa.py, which contains the code of the main attack procedure. There are five procedures that you need to implement:

1. accumulate(trace, sbox, key_hypothesis)
2. compute_mean_traces()
3. compute_diff_traces()
4. compute_max_diff_traces()
5. display_key_results()

Try to understand the role of each of these functions.

B) Implementing the analysis. Implement the above functions. You can use the functions display_trace() and display_diff_trace() in order to debug your code. You can run the analysis from your shell with the command

which will run the script with 1000 traces or by typing

The correct (1st round) key should be: 38 0B 3B 26 00 0D 19 37 (in hexadecimal).

C) Weaker leakage model. Change the code such that the number of considered bits for the leakage model can be changed as a parameter of the analysis (between 1 and 4). How does the result change for the same number of traces? How many traces are needed to get the correct key?

3. Advanced Attacks

If you still have time, you may want to heck out the website of the 1st DPA contest, in particular the "hall of fame" section, where the best attacks are presented. The winning attack of the 1st edition of the DPA contest is based on maximum likelyhood. An overview of the approach can be found on the slides of the presentation by Christophe Clavier. The source code of the attack is available here.