Leak study of cryptosystem implementations in randomized RNS arithmetic

Étude des fuites d'implémentations de cryptosystème en arithmétique RNS randomisée On parlera d'analyse forte pour une analyse qui permet de retrouver la clef d'un système cryptographique et d'une analyse faible dans le cas où on élimine des clefs candidates. Le but de cette thèse est essentiellement la compréhension du comportement de l'aléa des distances de Hamming produites par un système cryptographique de type ECC (Elliptic Curve for Cryptography) quand on utilise une représentation RNS (Residue Number System) avec la méthode des moduli aléatoires. Le Chapitre 2 introduit les différentes notions nécessaires à la compréhension de ce document. Il introduit brièvement l'algorithme de multiplication modulaire (Algorithme de Montgomery pour RNS) qui a inspiré la méthode des moduli aléatoires. Puis il décrit l'algorithme qui génère les séquences de distances de Hamming nécessaires à notre analyse. Ensuite il montre quel niveau de résistance apporte la méthode des moduli aléatoires contre différentes attaques classiques comme DPA (Diferential Power Analysis), CPA (Correlation Power Analysis), DPA du second ordre et MIA (Mutual Information Analysis). On apporte une compréhension de la distribution des distances de Hamming considérées comme des variables aléatoires. Suite à cela, on ajoute l'hypothèse gaussienne sur les distances de Hamming. On utilise alors le MLE (Maximum Likelihood Estimator) et une analyse forte comme pour faire des Template Attacks pour avoir une compréhension fine du niveau d'aléa apporté par la méthode des moduli aléatoires. Le Chapitre 3 est une suite naturelle des conclusions apportées par le Chapitre 2 sur l'hypothèse gaussienne. Si des attaques sont possibles avec le MLE, c'est qu'il existe sans doute des relations fortes entre les distances de Hamming considérées comme des variables aléatoires. La Section 3.2 cherche à quantifier ce niveau de dépendance des distances de Hamming. Ensuite, en restant dans l'hypothèse gaussienne, on remarquera qu'il est possible de construire une type de DPA qu'on a appelé DPA square reposant sur la covariance au lieu de la moyenne comme dans la DPA classique. Mais cela reste très gourmand en traces d'observation d'autant que dans de nombreux protocoles utilisant une ECC, on utilise une clef qu'une seule fois. La Section 3.4 s'efforce de montrer qu'il existe de l'information sur peu de traces de distances de Hamming malgré la randomisation des moduli. Pour cela, on fait un MLE par un conditionnement sur l'une des distances de Hamming avec une analyse faible. Le dernier Chapitre 4 commence par introduire brièvement les choix algorithmiques qui ont été faits pour résoudre les problèmes d'inversion de matrices de covariance (symétriques définies positives) de la Section 3.2 et l'analyse des relations fortes entre les Hamming dans la Section 3.2. On utilise ici des outils de Graphics Processing Unit (GPU) sur un très grand nombre de matrices de petites tailles. On parlera de Batch Computing. La méthode LDLt présentée au début de ce chapitre s'est avérée insuffisante pour résoudre complètement le problème du MLE conditionné présenté dans la Section 3.4. On présente le travail sur l'amélioration d'un code de diagonalisation de matrice tridiagonale utilisant le principe de Diviser pour Régner (Divide & Conquer) développé par Lokmane Abbas-Turki et Stéphane Graillat. On présente une généralisation de ce code, des optimisations en temps de calcul et une amélioration de la robustesse des calculs en simple précision pour des matrices de taille inférieure à 32.