Cryptanalyse algébrique par canaux auxiliaires
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
Algebraic Side Channel Attacks (ASCA) are a new kind of attack presented at CHES2009 by Renauld and Standaert. They showed thatside-channel information leads to effective algebraic attacks, butthese results are mostly experiments strongly based on a SAT-solver. In this talk, we will present a theoretical study which explains andcharacterizes the algebraic phase of these attacks. We study a moregeneral algebraic attack based on Grobner basis methods. We show thatthe complexity of the Grobner basis computations in these attacksdepends on a new notion of algebraic immunity that we define, and onthe distribution of the leakage information of the cryptosystem. Weillustrate this analysis by two examples of attacks on block-ciphersAES and PRESENT with usual leakage models: the Hamming weight and theHamming distance models. Finally, a new criterion for effectivealgebraic side channel attacks is defined. This easily computablecriterion unifies both SAT and Grobner attacks. This criterion alsorestricts the choice of resisting S-Box against ASCA. At CHES 2009, Renauld, Standaert and Veyrat- Charvillon introduced a new kind of attack called algebraic side-channel attacks (ASCA). They showed that side-channel information leads to effective algebraic attacks. These results are mostly experiments since strongly based on the use of a SAT solver. This article presents a theoretical study to explain and to characterize the algebraic phase of these attacks. We study more general algebraic attacks based on Gröbner meth- ods. We show that the complexity of the Gröbner basis com- putations in these attacks depends on a new notion of alge- braic immunity defined in this paper, and on the distribution of the leakage information of the cryptosystem. We also study two examples of common leakage models: the Hamming weight and the Hamming distance models. For instance, the study in the case of the Hamming weight model gives that the probability of obtaining at least 64 (resp. 130) linear relations is about 50% for the substitution layer of PRESENT (resp. AES). Moreover if the S-boxes are replaced by functions maximizing the new algebraic immunity criterion then the algebraic attacks (Gröbner and SAT) are intractable. From this theoretical study, we also deduce an invariant which can be easily computed from a given S-box and provides a suffi- cient condition of weakness under an ASCA. This new invari- ant does not require any sophisticated algebraic techniques to be defined and computed. Thus, for cryptographic engi- neers without an advanced knowledge in algebra (e. G. Gröb- ner basis techniques), this invariant may represent an inter- esting tool for rejecting weak S-boxes. We describe a lattice attack on DSA-like signature schemes under the assumption that implicit infor- mation on the ephemeral keys is known. Inspired by the implicit oracle of May and Ritzenhofen presented in the context of RSA (PKC2009), we assume that the ephemeral keys share a certain amount of bits without knowing the value of the shared bits. This work also extends results of Leadbitter, Page and Smart (CHES2004) which use a very similar type of partial information leakage. By eliminating the shared blocks of bits between the ephemeral keys, we provide lattices of small dimension (e. G. Equal to the number of signatures) and thus obtain an efficient attack. More precisely, by using the LLL algorithm, the complexity of the attack is polynomial. We show that this method can work when ephemeral keys share certain amount of MSBs and/or LSBs, as well as contiguous blocks of shared bits in the middle. Under the Gaussian heuristic assumption, theoretical bounds on the number of shared bits in function of the number of signed messages are proven. Experimental results show that we are often able to go a few bits beyond the theoretical bound. For instance, if only 2 shared LSBs on each ephemeral keys of 200 signed messages (with no knowledge about the secret key) then the attack reveals the secret key. The success rate of this attack is about 90% when only 1 LSB is shared on each ephemeral keys associated with about 400 signed messages.
Abstract FR:
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 es signatures de plusieurs messages donnés partagent un certain nombre de bits en commundont les valeurs sont inconnues. 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. Nous utilisons principalement des techniques de résolution par base de Gröbner plutôt que par solveur SAT quand cela est possible. 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.