**Master thesis by Florian Delporte**

### Abstract

In 2009, Mathieu Renauld and François-Xavier Standaert proposed new kinds of

powerful attacks combining Algebraic Attacks with Side-channel Attack (SCA). As ex-

ample of such attacks, they used a Bayesian template attack against Present. The results

of this attack were very good since they managed to recover the correct key with only

one SCA.

Based on these results, one could wonder if any SCA could be used for these attacks

and if some additional steps would be required to be compatible with an Algebraic

Attack. To answer this question, we will perform an Algebraic Side-channel Attack

(ASCA) using a very simple yet powerful SCA: the Correlation Power Analysis.

This attack analyzes the power traces recorded from a cryptographic device in order

to compute the correlation between these traces and the hypotheses. These n best hy-

potheses can then be inserted into the Algebraic Attack to find the correct hypothesis.

The problem of a Correlation Power Analysis is that its performance degrades when

the traces are too noisy or when there is not enough data. These poor performances

introduce impossibilities in the Algebraic Attack by rejecting the correct hypothesis key.

This means that when the performances of the SCA degrade, the Algebraic Attack

is unable to correct these errors and the performance of the constructed ASCA cannot

be better than the Correlation Power Analysis.

Based on this ascertainment, we proposed several properties that a SCA needs to

respect in order to be a good candidate for an ASCA:

These attacks should never introduce impossibilities in the Algebraic Attack by being

very efficient even when the side-channel traces are noisy or when there are not enough

power traces. Or the SCA could use an additional step to detect the impossibilities

before sending its results to the Algebraic Attack.

The candidate should be able to extract information about the cryptographic device

during all the encryption process and not only at a specific moment such as in a typical

Correlation Power Analysis.

Finally, we stated that a good ASCA should be able to perform a tradeoff between

the amount of side-channel traces and the computation time of the Algebraic Attack in

order to find the correct solution every time with sometimes a long computation time

when the traces are not good enough.

An additional goal of this master thesis is the presentation of an automated tool

called CryptoSAT allowing to describe a cryptographic algorithm by a Satisfiability

Problem (SAT) problem. This tool will be used in order to construct the SAT problem

defining the Present block cipher. In this work we will show how easy it is to use this

tool.

The code of Present for CryptoSAT is available for download.

The project was supervised by Nikita Veshchikov.

The director of the project is Olivier Markowitch.