Description
Date depot: 1 janvier 1900
Titre: Attaque algébrique par canaux auxiliaires. Calcul efficace des petites racines des systèmes polynômiaux
Directeur de thèse:
Jean-Charles FAUGÈRE (LIP6)
Encadrant :
Guénaël RENAULT (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
1 Cryptanalyse algébrique
En Cryptologie [19] un problème fondamental est l’évaluation de la sécurité des algorithmes de chiffrement ; pour cela plusieurs méthodes générales ont été proposées (cryptanalyse linéaire, différentielle, . . . ) et depuis quelques années une nouvelle méthode a suscité l’intérêt des cryptologues : il s’agit de la Cryptanalyse Algébrique. L’idée est de modéliser le cryptosystème par un système d’équations polynômiales dont la résolution permet de retrouver la clé secrète ou le message en clair ; dans un deuxième temps il s’agit d’évaluer, de manière théorique et pratique, la complexité de la résolution de ce système. L’objectif de cette thèse est d’évaluer comment une information extérieure permet d’accélérer significativement les méthodes de cryptanalyse algébrique. Le sujet de cette thèse se situe donc à l’interface du Calcul Formel (ou Computer Algebra en anglais) et de la Cryptologie.
Pour cette thèse on supposera que l’information extérieure apportée au système étudié résulte d’une attaque physique, aussi appelée attaque par canaux auxiliaires ('Side Channel Attack' en anglais) : suite à des mesures physiques (avec un oscilloscope ou instrument permettant la mesure du champ magnétique), on supposera qu’un certain nombre de bits (de la clé secrète par exemple) sont connus. Une extension naturelle est de prendre seulement comme hypothèse que des relations entre certains bits sont connues. Il faut noter, toutefois, qu’on ne s’intéressera pas à la réalisation des mesures physiques car il existe maintenant des banques de données comme dpacontest contenant des mesures réelles. L’utilisation d’information externe sera appliquée aux deux grands domaines de la cryptographie, à savoir la cryptographie symétrique (ou cryptographie à clé secrète) et la cryptographie asymétrique (ou cryptographie à clé publique. À ce jour, peu de travaux utilisant des méthodes algébriques excepté pour le système de chiffrement à clé publique RSA (problème de la factorisation d’un entier connaissant une partie des facteurs). Le travail a effectuer est donc de nature assez différente selon les cas.
2 Attaque algébrique et attaque par canaux auxiliaires
Dans le domaine des clés symétriques (algorithmes à clé secrète), on traitera les deux exemples suivants : l’algorithme AES (algorithme par bloc) et l’algorithme Trivium (algorithme par flot). Ces deux exemples sont bien adaptés à l’étude des attaques algébriques. Dans le domaine des clés asymétriques, on étudiera les méthodes fondées sur les courbes elliptiques et la difficulté du logarithme discret. L’idée sera donc de combiner les attaques algébriques classiques et les attaques par canaux auxiliaires de la façon suivante : dans un premier temps, on obtient des informations supplémentaires utilisant un certain nombre de mesures. Ensuite l’attaquant traduit ces informations (éventuellement de nature probabiliste) en un système d’équations polynômiales ; on résout ensuite ce système en utilisant un algorithme efficace de calcul des bases de Gröbner [11] (par exemple les algorithmes F4 ou F5 [16, 17]) ce qui permet de retrouver la clé secrète du cryptosystème. On pourra également coupler cette technique avec des méthodes récentes [13, 14] permettant d’utiliser des techniques différentielles en addition des méthodes algébriques.
Il est clair que tous les systèmes algébriques obtenus de cette façon ne peuvent être résolu efficacement. Cependant, certaines études préliminaires [20] ont montré qu’il était possible d’améliorer les attaques par canaux auxiliaires sur AES en utilisant les bases de Gröbner. Lorsqu’on aura identifié comment utiliser efficacement les informations issues de mesures physiques on donnera une liste possible de contre-mesures. Si le temps le permet on s’intéressera également aux systèmes de chiffrement fondés sur les courbes elliptiques. Il n’existe à ce jour que peu de publications dans le domaine mais certains auteurs [21] ont étudié la difficulté du problème du logarithme discret lorsqu’une information partielle est donnée sur la clé : si on connaît des bits consécutifs de la clé alors on peut résoudre beaucoup plus efficacement le problème du logarithme discret. Une généralisation possible est d’obtenir des résultats similaires lorsqu’on ne connaît des bits non consécutifs de la clé.
3 Calcul des petites racines d’un système algébrique et applications à RSA
Le cryptosystème RSA repose sur la difficulté de factoriser un grand entier N = p q. Il est aujourd’hui l’un des cryptosystèmes le plus utilisé et le plus étudié. L’objectif de cette seconde partie de la thèse est d’étudier le problème de la recherche des petites racines des systèmes algébriques avec comme application une attaque de RSA. Cette attaque repose donc également sur l’allégement des contraintes de la cryptanalyse en supposant connue une partie des bits des facteurs p ou q. Plus exactement, certaines attaques du cryptosystème RSA reposent sur la réso
Doctorant.e: Goyet Christopher