Soutenance de thèse de Christopher Goyet

*** Veuillez m'excuser pour les réceptions multiples ***


Bonjour à tous,

j'ai le plaisir de vous convier à ma soutenance de thèse, intitulée

Cryptanalyse algébrique par canaux auxiliaires.

qui aura lieu

le mercredi 7 novembre 2012 à 14h30
au LIP6 (Campus de Jussieu), salle 25-26-105,

Rapporteurs
Aline GOUGET (Expert Cryptographie, Gemalto)
François-Xavier STANDAERT (Professeur, Université
catholique de Louvain)

Examinateurs:
Jean-Claude BAJARD (Professeur, Université Pierre et Marie Curie)
Claude CARLET (Professeur, Université Paris 8)

Directeurs:
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)
Encadrant Industriel:
Olivier ORCIÈRE (Expert en cryptographie -- Thales communications & security)


Des plans d'accès au campus sont disponibles sur le site de l'UPMC
(http://www.upmc.fr/fr/universite/campus_et_sites/a_paris_et_en_idf/jussieu.html). L'accès à la salle de soutenance se fera par le premier étage de la tour
26.

La soutenance sera suivie d'un pot auquel vous êtes cordialement invités.


Résumé [English version below]
-------------------------------------------
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.

Abstract
------------
Algebraic cryptanalysis is a technique consisting in modeling a
cryptographic primitive with a system of multivariate polynomial
equations whose solutions give the secret key.
The goal of this thesis is to evaluate how external information can
significantly speed up the resolution. We assume that external
information is obtained by side channel, i.e. by physical measures, or
by an anomalous behavior caused by active attacks with fault injection
or even by the presence of malware.

Applied to asymmetric cryptography, this work led to the publication
of a new attack against DSA-like signature schemes. Inspired by
implicit factorization of May and Ritzenhofen, this new attack
requires that the ephemeral keys used to sign several messages share a
given number of bits without necessarily knowing the value of the
shared bits. As an example of our results, only 4 LSBs shared on each
ephemeral keys of 100 signed messages are enough to make a
never-failing attack and that with 32 LSBs shared, the method needs
only 8 signed messages.

On the other hand, with regard to the block ciphers, we present a
theoretical study of "Algebraic Side Channel Attacks" (ASCA) in order
to explain the effectiveness of the algebraic phase of these attacks
and then we deduce theoretical conditions for resistance. We mainly
use Gröbner basis method for the solving step rather than SAT solver
to control the complexity of this attack. Then we show that the
complexity of the Gröbner basis computation in these attacks depends
on a new notion of algebraic immunity and the distribution of
information leakage.

Finally, we extend the ASCA by considering various leakage models and
by studying the influence of these models on the effectiveness of the
solving step.

Bien cordialement,
Christopher Goyet