Sep 06

Algebraic side-channel attacks: Use of SAT solvers with non-profiled attacks.

Master thesis by Florian Delporte


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

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.