Team : ALMASTY
Localisation : Campus Pierre et Marie Curie
Sorbonne Université - LIP6
Boîte courrier 169
Couloir 24-25, Étage 4, Bureau 413
4 place Jussieu
75252 PARIS CEDEX 05
Tel: +33 1 44 27 47 28, Jerome.Courtois (at) null
: Jean-Claude BAJARD Co-supervision
: Lokmane Abbas-Turki
Study of cryptosystem implementation leaks in random RNS arithmetic
The goal of this thesis is to understand the randomness behavior of Hamming distances produced by an ECC (Elliptic Curve for Cryptography) cryptographic system when using a RNS (Residue Number System) representation with the random moduli method. We will speak of strong analysis for an analysis that recovers the key of a cryptosystem. We define a weak analysis in the case where candidate keys are eliminated.
We shows what level of resistance brings the method of random moduli against different side-channel attacks like DPA (Differrential Power Analysis), CPA (Correlation Power Analysis), DPA of the second order and MIA (Mutual Information Analysis). We provide an understanding of Hamming distances distribution. Following this, we add the Gaussian hypothesis on Hamming distances. We use MLE (Maximum Likelihood Estimator) and a strong analysis to have a better understanding of the level of random brought by the method of random moduli.
If attacks are possible with the MLE, it is because there are perhaps strong relationships between the Hamming distances considered as random variables. We seeks to quantify this level of dependence on Hamming distances. Then, staying in the Gaussian hypothesis, we will notice that it is possible to construct a type of DPA that we called DPA square based on covariance instead of the average as in classical DPA. But that remains very greedy in traces of observation especially since in many protocols using an ECC, one uses a key only once. We strives to show that there is information on few traces of Hamming distances despite the randomization of the moduli. For this, we do an MLE by conditioning on one of the Hamming distances with a weak analysis.
To make the statistic analysis, we use here Graphics Processing Unit (GPU) tools on a very large number of small size matrices. We talk about Batch Computing. The LDLt proved to be insufficient to completely solve the problem of conditioned MLE . We present work on the improvement of a diagonalization code of a symmetric tridiagonal matrix using the principle of Divide & Conquer developed by Lokmane Abbas-Turki and Stéphane Graillat. We present a generalization of this code, optimizations in computation time and an accuracy improvement of computations in simple precision for matrices of size lower than 32.
: 09/10/2020 - 10hJury members
Pierre-Alain Fouque - Université de Rennes I, IRISA. [Rapporteur]
Florence Merlevéde - Université Paris-Est-Marne-La-Vallée, LAMA. [Rapporteur]
Stephane Vialle - CentraleSupelec, LRI, Université de Paris-Saclay. [Rapporteur]
Caroline Fontaine - CNRS/Université de Paris-Saclay, LSV. [Examinateur]
Karine Heydemann - Sorbonne Université, Paris, LIP6. [Examinateur]
Emmannuel Prouff - ANSSI, Paris. [Examinateur]
Jean-Claude Bajard - Sorbonne Université, IMJ-PRG. [Directeur]
Lokmane Abbas-Turki - Sorbonne Université, LPSM. [Co-Encadrant]