Team : PolSys

Departure date : 11/30/2012

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.

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)

- 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 Berlin / Heidelberg), (ISBN: 2190-8508) (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)
- Ch. Goyet : “Cryptanalyse algébrique par canaux auxiliaires”, these, defence 11/07/2012, supervision Faugère, Jean-Charles, co-supervision RENAULT Guénaël (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, GermanyFraunhofer SIT, pp. 1-6 (2011)

- J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Algebraic Side Channel Analysis”, COSADE'11: The 2