GOYET Christopher

PhD graduated
Team : PolSys
Departure date : 11/30/2012

Supervision : Jean-Charles FAUGÈRE

Co-supervision : RENAULT Guénaël

Algebraic Side Channel Analysis

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.

Defence : 11/07/2012

Jury members :

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)

Departure date : 11/30/2012

2011-2012 Publications