Научны(е)й руководител(и)ь : Jean-Charles FAUGÈRE

Со-руководитель : 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.

Публикации 2011-2012

• 2012
  • Ch. Goyet : “Cryptanalyse algébrique par canaux auxiliaires”, диссертация, Защита диссертаций 07.11.2012, Научны(е)й руководител(и)ь Faugère, Jean-Charles, Со-руководитель : 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)