Direction de recherche : Jean-Charles FAUGÈRE
Co-encadrement : RENAULT Guénaël

Cryptanalyse algébrique par canaux auxiliaires

La cryptanalyse algébrique consiste à modéliser une primitive cryptographique par un système d'équations polynomiales dont la résolution permet de retrouver la clef secrète. L'objectif de cette thèse est d'évaluer comment une information extérieure permet d'accélérer significativement la résolution. Nous supposons que l'information extérieure est obtenue par canal auxiliaire, c'est-à-dire par des mesures physiques, ou bien suite à un comportement anormal provoqué par des attaques actives du type injection de fautes, ou bien encore à cause de la présence d'un logiciel malveillant.

Appliqués à la cryptographie asymétrique, ces travaux ont conduit à la publication d'une nouvelle attaque contre les schémas de signature de type DSA. Inspiré par la factorisation implicite de May et Ritzenhofen, cette attaque suppose que les clefs éphémères utilisées pour construire les signatures de plusieurs messages donnés partagent un certain nombre de bits en commun dont les valeurs sont inconnues. Par exemple, seulement 4 LSBs partagés sur les clefs éphémères de 100 messages signés sont suffisants pour obtenir une attaque avec taux de réussite de 100% et lorsque 32 LSBs sont partagés, cette méthode ne nécessite plus que 8 messages signés.

En ce qui concerne les chiffrements par blocs, nous présentons une étude théorique des "Algebraic Side Channel Attacks" (ASCA) qui explique l'efficacité de ces attaques et qui permet de proposer des conditions théoriques de résistance. Afin de maitriser la complexité de cette attaque, nous utilisons principalement des techniques de résolution par base de Gröbner plutôt que par solveur SAT. Nous montrons ainsi que la complexité d'une résolution par base de Gröbner dépend d'une nouvelle notion d'immunité algébrique et de la distribution des informations de fuite.

Enfin, nous étendons les ASCA en considérant différents modèles de fuite et étudions l'influence de ces modèles sur l'efficacité de l'étape de résolution.

Soutenance : 07/11/2012

Membres du jury :

Aline GOUGET (Expert Cryptographie, Gemalto) [Rapporteur]
François-Xavier STANDAERT (Professeur, Université catholique de Louvain) [Rapporteur]
Jean-Claude BAJARD (Professeur, Université Pierre et Marie Curie)
Claude CARLET (Professeur, Université Paris 8)
Jean-Charles FAUGÈRE (Directeur de Recherche INRIA, Centre Paris-Rocquencourt)
Guénaël RENAULT (Maître de Conférences, Université Pierre et Marie Curie)
Olivier ORCIÈRE (Expert en cryptographie, Thales communications & security)

Publications 2011-2012

• 2012
  • Ch. Goyet : “Cryptanalyse algébrique par canaux auxiliaires”, soutenance de thèse, soutenance 07/11/2012, direction de recherche Faugère, Jean-Charles, co-encadrement : Renault, Guénaël (2012)
  • C. Carlet, J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Analysis of the algebraic side channel attack”, Journal of Cryptographic Engineering, vol. 2 (1), pp. 45-62, (Springer) (2012)
  • J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Attacking (EC)DSA Given Only an Implicit Hint”, Selected Areas in Cryptography, vol. 7707, Lecture Notes in Computer Science, Windsor, Canada, pp. 252-274, (Springer) (2012)
• 2011
  • J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Algebraic Side Channel Analysis”, COSADE'11: The 2^nd International Workshop on Constructive Side-Channel Analysis and Secure Design, Darmstadt, Germany, pp. 1-6 (2011)