Supervision : 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.

2019-2020 Publications

• 2020
  • J. Courtois : “Étude des fuites d’implémentations de cryptosystème en arithmétique RNS randomisée”, thesis, phd defence 09/10/2020, supervision Bajard, Jean-Claude, co-supervision : Lokmane, Abbas-Turki (2020)
• 2019
  • J. Courtois, L. Abbas‑Turki, J.‑C. Bajard : “Resilience of randomized RNS arithmetic with respect to side-channel leaks of cryptographic computation”, IEEE Transactions on Computers, vol. 68 (12), pp. 1720-1730, (Institute of Electrical and Electronics Engineers) (2019)