Author's posts

Jun 27

Simple Power Analysis on RSA

The goal of this project was to demonstrate a side-channel attack against a simple
cryptographic protocol implemented on an embedded system. Side-channel attacks target
the implementation rather than the cryptographic algorithm and attempt to recover secret
values, such as keys, using different kinds of measurements.

This project was accomplished by Meunier Laurent, Orinx Cédric, Rigas Theofanis and Vanspouwen Tristan. Their report explains all details about this project, they also make available all the source code, so you can repeat their experiments. They have also made a short video [high quality] demonstration of their work, it quickly demonstrates what can be done using their setup. At the end their result show how easy it is to recover a secret key using simple power analysis on an unprotected device.

This project was done in 2016-17 for the course of Embedded Systems Design given by professor Gilles Geeraerts, the project was supervised by Nikita Veshchikov.

 

 

Oct 27

Block cipher in ECB mode

Here is yet another Tux image in bmp format encrypted using a block cipher in ECB mode. Once again, it shows us that it is not secure. The top left picture is the original, while the 3 other images are generated by encrypting image data using PRESENT-80 block cipher with 3 different keys.

This small exercise was suggested by Nikita Veshchikov during the exercise sessions of the course “Introduction to Cryptography” given by Professor Olivier Markowitch.

The C++ code by Jérôme Hellinckx is available and you can try it for yourself.

tuxtux_ecb_0

tux_ecb_1tux_ecb

Oct 07

Les codes de Huffman adaptatifs

Comparaison des implantations possible et des complexités théorique et
effective.
Comparaison des algorithmes FGK et Lamda.

Contacts: Yves Roggeman

Oct 07

Les « Variable Length Arrays » (VLA) en C, C++ et d’autres langages Algol-like

Limites, implantation sous-jacente, efficacité.
Évolution du concept et analyse des arguments pro et contra pour C++17.

Contacts: Yves Roggeman

Oct 07

Comparaison des « threads » dans les standards Java 8 et C++14.

Choix des structures, des primitives.
Efficacité, limites, aisance d’usage.

Contacts: Yves Roggeman

Oct 07

Le « shuffling » pseudo-aléatoire

Comparaison de performances théoriques et d’implantations.
Algorithme de Fisher-Yates (dit de Knuth).

Contacts: Yves Roggeman

Oct 07

La génération de permutations

Comparaison de performances théoriques et d’implantations.
Algorithmes de Heap et de Steinhaus–Johnson–Trotter.

Contacts: Yves Roggeman

Oct 07

Comparaison de manipulations de grands entiers.

Implantations de Montgomery versus Toom-Cook, par exemple.
Étude des choix de Gnu MPFR.

Contacts: Yves Roggeman

Sep 07

A Reverse Engineering Tool for Static Analysis Which Performs Equational Reasoning on X86 Assembly Code

Master thesis by Marien Bourguignon

Abstract

Kevin Coogan and Saumya Debray, two researchers focused on digital reverse engi-
neering, identified an issue within that field, and exposed it in a paper titled Equational
Reasoning on x86 Assembly Code[1]. They stated that, while there is a great amount of
tools able to perform reverse engineering analysis on high-level source code, there is a
lack of such tool able to used on assembly code. The aim of this thesis is to show how the
tool proposed in the aforementioned paper, which performs equational reasoning on x86
traces with the intend of improving their readability, could be extended to also perform
static analysis. In this context, two additional issues have to be solved: Modelising the
non-linear control flow, and deciding whether or not specific pointers are aliased. The
former is solved using the static single assignment form, the later is handled thanks to
a pointer analysis.
When performing manually what the static analysis tool would do, one can notice
how the readability of its output has decreased compared to the one working on traces.
This is due to the fact that the φ-functions introduced by the static single assignment
form does not clearly show which control structure has led to its existence, but also
because of the undecidability of the pointer analysis problem, which implies that the
used algorithm will only be able to provide approximative results.

The project was supervised by Nikita Veshchikov.

The director of the project is Olivier Markowitch.

Sep 06

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

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.