Claude Carlet
email: claude.carlet@univ-paris8.fr

Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Christopher Goyet
email: christopher.goyet@lip6.fr

Guénaël Renault
email: guenael.renault@lip6.fr

Analysis of the Algebraic Side Channel Attack

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 in order to explain and to characterize the algebraic phase of these attacks. We study more general algebraic attacks based on Gröbner methods. We show that the complexity of the Gröbner basis computations in these attacks depends on a new notion of algebraic 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 sufficient condition of weakness under an ASCA. This new invariant does not require any sophisticated algebraic techniques to be defined and computed. Thus, for cryptographic engineers without an advanced knowledge in algebra (e.g. Gröbner basis techniques), this invariant may represent an interesting tool for rejecting weak S-boxes.

Introduction

Algebraic Side Channel Attacks (ASCA) are a new kind of attack recently introduced in [RSVC09] by Renauld, Standaert and Veyrat-Charvillon. It is a natural combination of classical algebraic cryptanalysis and side channel attacks which take full advantage of both classical attacks. It should be mentioned that several methods combining side channel and algebraic attacks (see [START_REF] Bogdanov | Improved Side-Channel Collision Attacks on AES[END_REF][START_REF] Bogdanov | Algebraic Methods in Side-Channel Collision Attacks and Practical Collision Detection[END_REF] for the first algebraic collision attacks) or differential attacks (see [START_REF] Schramm | A new class of collision attacks and its application to DES[END_REF][START_REF] Handschuh | Blind Differential Cryptanalysis for Enhanced Power Attacks[END_REF][START_REF] Bogdanov | Multiple-Differential Side-Channel Collision Attacks on AES[END_REF]) have already been suggested. As for these methods, the main idea of ASCA is to begin with an on-line phase where leakage information is recorded by a side channel, and to end with a powerful off-line phase where this data is used by algebraic cryptanalysis to recover the key. In contrary to standard Differential Power Analysis, the goal of the on-line phase is not to recover directly a bit of the key but it is only to catch a lot of partial information on the intermediate data manipulated during the encryption. Thus, all the leakages of all the cipher rounds are potentially useful. Contrary to the articles [SWP03, SLFP04, HP06, Bog07, BKP08, Bog08, MME10], ASCA could succeed with the observation of a single encrypted plaintext and would work with completely masked implementations. During this online phase, a leakage model is selected, for example a common leakage model is the Hamming weight of data transiting on a bus (see for instance [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Akkar | Power Analysis, What Is Now Possible[END_REF] for a discussion of this model). Next, the off-line phase makes use of the collected leakage information in an algebraic attack. In the present study, the side channel information is assumed to be reliable for use in the algebraic attack phase, which is not the case with real measures because of the presence of noise. Even though recent works have shown how algebraic approaches may deal with errors ([OKPW10, AC10]), our goal is to start to explain and to understand the efficiency of ASCA, and more precisely the algebraic phase of ASCA with reliable leakage information. This algebraic attack phase consists of modeling the cryptosystem and the leakage model by a system of polynomial equations. Solving this system is equivalent to recovering the bits of the key. In classical algebraic cryptanalysis, solving the system of equations representing a modern block cipher remains a source of speculation because of the complexity of solving such polynomial systems. On the contrary, the system of equations obtained with the algebraic collision attacks ([Bog07, BKP08]) has been well detailed so that the complexity of resolution of such systems is well understood. On the other hand, in the ASCA context, the leakage model seems to provide enough information to efficiently solve in practice the system of equations, but the apparent simplicity of this solving step remained unexplained and its computational complexity was not enough analyzed.

In [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF] and [START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF], algebraic side-channel attacks are evaluated against 8-bit implementations of PRESENT and AES. The main leakage model studied is the Hamming weight model. Thus, the authors of [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF] (as in [START_REF] Handschuh | Blind Differential Cryptanalysis for Enhanced Power Attacks[END_REF]) assume the knowledge of the Hamming weights of some intermediate computations. The system of equations representing the block cipher and the leakage model is translated into a satisfiability problem and solved by a SAT solver. Under these assumptions, this attack seems very powerful. Indeed, the key is always recovered in less than one minute if all the 8-bit Hamming weights after the XORs (in AddRoundKey and MixColumns functions) and after the substitution layers are known for a 31round PRESENT and for a 10-round AES. When fewer Hamming weights are known, the number of consecutive rounds with Hamming weights is an important criterion for a successful attack. There are also some effective attacks in unknown plaintext/ciphertext sit-uations or against masked implementations. It is clear that the known Hamming weights allow to exclude most of the possible values of the key, however, the success rate of these attacks depends on several parameters: the amount of available information, the leakage function or the shape of the system of equations. All these results are also very dependent on the heuristics used in the SAT solver, and so the experiments are very difficult to explain when SAT solver techniques are used.

The main goal of this article is to explain the effectiveness of this attack, to describe the criterion of success and therefore to find the theoretical conditions to prevent algebraic side channel attacks. To achieve this goal, Gröbner techniques are used instead of a SAT solver because of their computation without heuristics and so, more stable and more understandable. We also assume the same hypothesis as in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF], particularly that an initial on-line phase provides a sequence of leakage information, and we only focus on the algebraic cryptanalysis phase. Furthermore, we do not discuss about side channel countermeasures, and we refer to [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF] for detailed discussions. We show in section 2 that the complexity of the Gröbner basis computation in these attacks depends on a new notion of algebraic immunity and on the distribution of leakage information. This Algebraic Immunity with Leakage is defined by the degree and also the number of lowest degree relations which are given by a black box (S-Boxes, Key derivation, etc) and its leakage information. This new algebraic immunity is completely related to the complexity of the Gröbner basis computation and thus, represents a good criterion for effective Gröbner attacks. From this theoretical study and this new criterion, we deduce a new invariant, which could also be connected to SAT solvers efficiency. For a given block cipher, this invariant, denoted by N B , is easily computed by a local study of the black boxes B defining the cryptosystem. In contrary to the Algebraic Immunity with Leakage, this computation does not require any knowledge of advanced algebra which may be more useful for cryptographic engineers who are not fluent with Gröbner basis techniques. More precisely, if we denote by B the black box, L the leakage model, l a value of the function L, and n the bus size, then the invariant is the function N B (l) giving the cardinality of the corresponding set {x ∈ F n 2 s.t. L(x, B(x)) = l}. We prove that the number of linear relations given by the leakage l is greater or equal than 2n+1-N B (l) (in practice, this bound is often achieved). Thus, from this new invariant, we deduce a sufficient condition for the weakness of a black box under a Gröbner attack with leakage. This condition corresponds to the case where the black box is such that N B (l) is small for a lot of values of l. We verify this condition in practice by using Gröbner basis techniques and some of the best SAT solvers. Thus, this invariant may be seen as a general algebraic sufficient condition (independent of the solving strategy) for an effective algebraic side channel attack. Even if this invariant does not provide a theoretical necessary condition of weakness, we successfully describe several scenarios of unsuccessful Gröbner and SAT solver attacks when N B (l) is large. For example, if the S-boxes are replaced by functions maximizing the function N B then both algebraic attacks become impractical. The same holds when all leakage data maximizes N B .

From this new theoretical point of view, we analyze the precedent results on ASCA which were heuristic. To simplify and to keep the point of view of [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF], we mostly study the 8-bit Hamming weight leakage, but we also consider the Hamming distance which is a more general model. The results presented in Section 3.2 and in Annex A show that, with the Hamming weight model, the AES, PRESENT, CAMELLIA and SMS4 S-boxes are very weak with respect to this invariant: N B is often small and the number of linear equations is on average 8 per S-box. With the Hamming distance model, ASCA is much more difficult and we show that, in this case, N B is often large and the number of linear equations is on average between 1 and 2 per S-box. The local study of these S-boxes shows that these two models of leakage information can be used to partly linearize the polynomial system of equations. Moreover, if N B is very small then few input or output bits of the S-box can be recovered. In section 4, these local results are used to explain the recovery of the key bits. Especially in the case of consecutive leakage in the Hamming weight model, the subkey bits can be easily deduced from previously recovered bits. Or else, we show that the system of equations representing the block cipher and the Hamming weight information contains enough linear equations to be efficiently solved: the probability of obtaining at least 64 (resp. 130) linear relations is about 50% for PRESENT (resp. AES) for example. Moreover, we show that if the number of rounds increases, the number of linear relations which provide subkey bit increase (see Section 4.3). Consequently, this work fully explains the efficiency of the attack. Thanks to this understanding, an efficient solving strategy is developed for Gröbner attacks (Section 4). In the case of the Hamming distance model, the attacks are much less efficient because N B is larger in average, and the expected number of linear equations is very low (see Section 3.3). In section 5, the conditions for preventing algebraic side channel attacks are also discussed, and it seems that one of the safest way to design a block cipher resistant against all kinds of attacks is to increase the bus size.

Algebraic Cryptanalysis and side channel information

The basic principle of Algebraic Cryptanalysis is to model a cryptographic primitive by a set of algebraic equations over a finite field. The system of equations is constructed in such a way as to have a correspondence between the solutions of this system, and the secret information of the cryptographic primitive (for instance, the secret key of a block cipher). There are different ways to solve such a polynomial system : SAT solver, Gröbner basis, XSL([CP02]) etc. In this article, we particularly use the Gröbner basis method, a powerful tool for solving a polynomial system. We refer to [BFS04, [START_REF] Bardet | Étude des systèmes algébriques surdéterminés[END_REF][START_REF] Bardet | Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems[END_REF] for a discussion on the complexity of Gröbner basis computation of overdetermined algebraic equations over finited fields. The Faugère's F4 and F5 [START_REF] Faugère | A New Efficient Algorithm for Computing Gröbner bases (F4)[END_REF][START_REF] Faugère | A New Efficient Algorithm for Computing Gröbner bases without reduction to zero (F5)[END_REF] algorithms are the most efficient algorithms to compute Gröbner basis, so in our experiments we used the efficient implementation of F4 by Magma software [START_REF] Bosma | The MAGMA algebra system: the user language[END_REF]. These algorithms have been successfully applied against a number of multivariate schemes [START_REF] Faugère | Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases[END_REF][START_REF] Faugère | Cryptanalysis of 2R -Schemes[END_REF][START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF][START_REF] Faugère | Cryptanalysis of MinRank[END_REF] and in stream cipher cryptanalysis [START_REF] Courtois | Algebraic Attacks on Stream Ciphers with Linear Feedback[END_REF][START_REF] Ars | Applications des bases de Gröbner en cryptographie[END_REF], but they stay unpractical against bloc ciphers [START_REF] Courtois | Cryptanalysis of Block Ciphers with Overdefined Systems of Equations[END_REF][START_REF] Cid | An Analysis of the XSL Algorithm[END_REF]. Indeed, the size of the corresponding algebraic system is so huge (thousand of variables and/or equations with high degree) that nobody is able to predict correctly the complexity of solving such polynomial systems. The degree of these equations stay high because of non-linear substitution-box layers (S-Boxes) and the multitude of rounds. One of the main goals of algebraic attacks is to describe these S-Boxes by low degree equations. The number of such equations gives a criterion to evaluate the block cipher resistance against algebraic attacks and it is called Algebraic Immunity ([AA05, AF05, Ars05, AK06, FM07, Car09, Car10]).

In algebraic side channel attack, we also assume the knowledge of additional information obtained by side channel, for instance Hamming weights of intermediate values. In the polynomial system modeling of our problem we take into account this assumption. In particular, we see each round of the block cipher as successive black boxes operating on n-bit data (i.e. n is the size of the bus). From the knowledge of the polynomial systems representing such a black box and the corresponding Hamming weight leakages, one can model the complete block cipher with leakages as a block diagonal system of equations (each block corresponding to a round). This definition of the model by splitting the different steps of size of n bits is used in our strategy for solving the entire system and it turns out that this algebraic system updated with equations corresponding to the leakage is easier to solve in practice. We will show in this section that the presence of this additional information may give rise to a number of independent linear relations. These relations enable us to mount an effective algebraic attack and that leads us to define a new notion of Algebraic Immunity with Leakage.

From now on, to make this study more general, the S-boxes, or any vectorial boolean function is seen as a black box, denoted by B in the following. Let n be the bus size of B, X 1 , . . . , X n and Y 1 , . . . , Y n be respectively its input and output bits. To restrict the study to solutions with coefficients in the field F 2 (and not in its algebraic closure F 2 ), we always add the set of polynomials S Field Eq. = {X 2 i -X i , Y 2 i -Y i , 1 ≤ i ≤ n} (corresponding to the classical field equations) into the polynomial systems. We will denote by I Field Eq. the ideal of F 2 [X 1 , . . . , X n , Y 1 , . . . , Y n ] generated by the set S Field Eq. . Finally, the subset

S B = {F 1 , . . . , F k B } ⊂ F 2 [X 1 , . . . , X n , Y 1 , . . . , Y n ]
is the finite set of Boolean functions defining the outputs of B as a (explicit or implicit) function of its inputs.

Algebraic Immunity for Block ciphers

The notion of Algebraic Immunity often refers to stream ciphers and boolean functions, but in this article, we make reference to the Algebraic Immunity extended to boolean vectorial functions (sometimes called "graph algebraic immunity"). This definition slightly varies from one article to the next. Thus, we first remind the definition of the Algebraic Immunity which we are going to use and we give an algorithm to compute it (see [AA05, AF05, Ars05, AK06, FM07, Car09, Car10]).

The Algebraic Immunity is defined as the lowest degree of algebraic relations of a Boolean vectorial function. More formally, let B : F n 2 → F n 2 be a black box and

I B ⊂ F 2 [X 1 , . . . , X n , Y 1 , . . . , Y n ]
the ideal generated by the equations representing B and the field equations:

I B = S B ∪ S Field Eq.
Definition 1 The Algebraic Immunity of B is defined by AI(B) = min{deg(P ), P ∈ I B \ I Field Eq. } Remark 1 The number of such lowest degree relations is also an important invariant related to I B , and it is always computed at the same time as the Algebraic Immunity.

To obtain the Algebraic Immunity of a black box B, we could compute a Gröbner basis of I B with respect to a graded order([AF05]):

Theorem 1 The reduced Gröbner basis G B of I B with respect to a graded order contains a linear basis of the lowest relations of B (i.e. the polynomials P ∈ I B such that deg(P ) = AI(B)).

Proof Every f ∈ I B is reduced to zero by a Gröbner basis of I B . Thus, there is a polynomial g ∈ G B such that the leading monomial LM (g) of g divides LM (f ). As we have a graded monomial order, deg(g) = deg(LM (g)) and deg(f ) = deg(LM (f )). Thus, deg(g) ≤ deg(f ) and we prove that G B contains a linear generated family of the lowest relations of B. Then the definition of a reduced Gröbner basis implies that the linear generated family is a linearly independent family.

Example 1 The Algebraic Immunity of the function calculating the inverse over F 2 8 (e.g. AES S-box) equals 2. Indeed, the inverse function is represented by a set of 39 quadratic equations over F 2 ([CP02]) as well as over F 2 8 ([Ars05]).

Algebraic Immunity of S-boxes with Leakage

In the previous section, the concept of Algebraic Immunity is defined as the lowest degree of algebraic relations of a Boolean vectorial function. In the ASCA context, we are looking for the lowest degree relations of B with leakage information (e.g. Hamming weights, Hamming distances). Therefore, we need to introduce a slightly different notion of Algebraic Immunity to take the leakage into account. To do so, for every value l of the leakage model, we consider the ideal I l of F 2 [X 1 , . . . , X n , Y 1 , . . . , Y n ] generated by the equations representing B, the field equations S Field Eq. and by L l the set of equations representing the leakage information l, namely:

I l = S B ∪ L l ∪ S Field Eq. .
From this ideal we can define this new notion of algebraic immunity.

Definition 2 Let B be a black box and l the value of the leakage model L. The Algebraic Immunity With Leakage, denoted by AI L (B, l), is defined by

AI L (B, l) = min{deg(P ), P ∈ I l \ I Field Eq. }
The number of linearly independent relations in I l with degree AI L (B, l) will be denoted by #AI L (B, l).

Similarly to the general notion of Algebraic Immunity, the relations of lowest degree can be explicitly obtained by the computation of a Gröbner basis of I l with respect to a graded order (see [START_REF] Ars | Applications des bases de Gröbner en cryptographie[END_REF]).

An other important invariant related to I l is the number of points in the associated variety V (I l ), i.e. the set of common roots of the polynomials in I l . This number which depends on the black box B and on the value l of the leakage function L, is also linked to our Algebraic Immunity With Leakage and it will be denoted by N B (l): Definition 3 N B (l) is defined as the number of points of the variety V (I l ). In other words, N B (l) is equal to the cardinality of the set {x ∈ F n 2 s.t. L(x, B(x)) = l}

We will show in Section 3 below that AI L (B, l) is equal to 1 in the cases of Hamming weight and Hamming distance model. In this particular situation where AI L (B, l) is equal to one (ie. there is at least one linear equation in the Ideal I l ), we prove the following relation between #AI L (B, l) and N B (l):

Proposition 1 Let n be the bus size of B. If AI L (B, l) is equal to 1 and N B (l) is non-zero then N B (l) ≥ 2n + 1 -#AI L (B, l) .
Proof As observed in Definition 3, we have N B (l) = #V (I l ). Since I l contains the field polynomials, it is radical. Its variety V (I l ) is a subset of F n 2 and, from the Nullstellensatz, we have #V (I l ) = dim( F2[X1,...,Xn,Y1,...,Yn]

I l ) = dim(Span(m α : α ∈ N 2n , m α / ∈ LT(I l )))
From this set of generating monomials, we only keep the set F of monomials which have a degree less than or equal than one:

F = {m : deg(m) ≤ 1 and m / ∈ LT(I l )} We have #V (I l ) ≥ dim(Span(F )). Now, let E = {m : deg(m) ≤ 1} and G = {m : deg(m) ≤ 1 and m ∈ LT(I l )}. It is clear that F is the set of monomials in E which are in LT(I l ) and G is the set of the monomials in E which are not in LT(I l ), thus the set E is equal to the following disjoint union E = F G. Finally, #V (I l ) ≥ dim(Span(F )) = dim(Span(E)) -dim(Span(G)) = 2n + 1 -#AI L (B, l)
We have defined the Algebraic Immunity with Leakage and showed its relation with N B (l). In the next section, these results will be useful to study two examples of leakage models: the Hamming weight and the Hamming distance leakage models.

Two common leakage models: the Hamming weight model and the Hamming distance model

In [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF] and [START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF], algebraic side-channel attacks are evaluated against implementations of the block ciphers PRESENT and AES in 8-bit PIC microcontrolers. The main leakage model studied is the Hamming weight model, that is the number of bits set to 1 being processed at a given time (see for instance [START_REF] Chari | Towards Sound Approaches to Counteract Power-Analysis Attacks[END_REF][START_REF] Akkar | Power Analysis, What Is Now Possible[END_REF] for a discussion of this model). Thus the authors of [RS09, RSVC09] assume the knowledge of the Hamming weights of some intermediate computations. In this section, we also assume that a first on-line phase already provided leakages as the Hamming weights or the Hamming distances of the input and output of a black box B. The Algebraic Immunity with Leakage is of great help to study the influence of this additional information on the system of equations generated by B. Actually, we prove that the Algebraic Immunity with Leakage of B with Hamming weight model or with Hamming distance model is equal to 1 for every possible black box B which is exceptionally small. Moreover, we show that there are at least two independent linear equations in the case of Hamming weight model.

The system of equations corresponding to the Hamming weight

First of all, we need to describe the system of equations representing the Hamming weight of the data x = (x 1 , x 2 , . . . , x n ) ∈ F n 2 . Note that if the Hamming weight of x is equal to w then any product of w + 1 bits is always null, which corresponds to the following system: R w :

i∈I X i = 0 : I ⊂ {1 . . . n} s.t. |I| = w + 1
and there is only one product of w bits which is 1, which corresponds to the following system:

T w :    J⊂{1...n} s.t. |J|=w   j∈J X j   = 1   
These two facts are sufficient to represent the Hamming weight model by the system of equations

L w = R w ∪ T w (1)
Example 2 For instance, the system of equations

L 1 = {x 1 x 2 = x 1 x 3 = x 1 x 4 = x 2 x 3 = x 2 x 4 = x 3 x 4 = 0, x 1 + x 2 +x 3 +x 4 = 1} is satisfied only by x = (x 1 . . . x 4 ) ∈ F 4 2 such that HW (x) = 1 :
The only sets L w which contain a linear equation are the sets L w with w = 0 or w = 1. When w > 1, these sets L w do not contain linear equations. Now that we have formulated the system of equations representing the Hamming weights, we are able to study the Hamming weight leakage model. We will show that the addition of these systems of equations representing the Hamming weight to the system modeling a black box B could give a lot of linear equations.

Hamming weight model leakage

We study the Algebraic Immunity With Leakage in the case of the Hamming weight model (see Section 2.2). So, we consider the ideal I win,wout of F 2 [X 1 , . . . , X n , Y 1 , . . . , Y n ] generated by the equations representing B, the field polynomials S Field Eq. and by L win , L wout the equations representing the Hamming weights w in , w out respectively (see the definition of L w (1)), namely:

I win,wout = L win ∪ L wout ∪ S B ∪ S Field Eq.
In this case, the Algebraic Immunity With Leakage of the black box B with Hamming weight leakage is denoted by AI L (B, w in , w out ) and the number of linearly independent relations in I win,wout with degree AI L (B, w in , w out ) is denoted by #AI L (B, w in , w out ).

We now prove that AI L (B, w in , w out ) = 1, and #AI L (B, w in , w out ) ≥ 2, i.e. that I win,wout contains at least two independent linear polynomials. This result is a consequence of the fact that there is always a linear relation in the ideal generated by the equations describing the Hamming weight. Although these two linear relations are not really useful in an algebraic attack, this result shows that the situation is completely different with the classical algebraic immunity.

Lemma 1 Let w ∈ {0, . . . , n}. The ideal I hw (w) ⊂ F 2 [X 1 , . . . , X n ], generated by L w (1) and by S Field Eq. , always contains the linear polynomial

X 0 + • • • + X n + (w mod 2)
(2)

Proof The system of equations L w (1) defines the set

V (w) = {x ∈ F n 2 s.t. HW (x) = w} = HW -1 (w).
Then, the radical ([CLO07]) ideal I hw (w) contains all polynomials vanishing on V (w) (which is the variety of I hw (w) over F 2 ). Clearly, the linear polynomial (2) vanishes on V (w), hence it must be in I hw (w).

We can now prove the following result :

Proposition 2 Let G be the Gröbner basis of the ideal I win,wout for a graded monomial order. Then G contains at least 2 independent linear polynomials.

Proof With the same notation as in lemma 1, we could note that there exist (w in , w out ) ∈ N 2 such that I win,wout = I B + I hw (w in ) + I hw (w out ). According to Lemma 1,

f = X 1 + • • • + X n + (w in mod 2) ∈ I win,wout f = Y 1 + • • • + Y n + (w out mod 2) ∈ I win,wout
then there is g ∈ G such that the leading monomial LM (g) of g divides LM (f ), the leading monomial of f . As I win,wout is a proper ideal, LM (g) = LM (f ) = X i , i depending on order, and as the monomial order is a graded order, g is a linear polynomial. The same holds for f . Thus, the Algebraic Immunity with Leakage is always 1 and there are at least 2 independent linear polynomials when Hamming weight equations are added to the system of equations corresponding to B. It is quite natural that these two linear relations are in the ideal I l since they correspond to information added by the leakage. But, it is important to see that these results are general. They do not depend on the bus size n and on the black box B. What is more interesting is the fact that, when the black box is fixed as a S-box, the number of linear independent relations is (in general) larger than 2 (see Section 6 and Appendix A). The aim of the analysis done in this paper is to study the impact of these linear relations on an algebraic attack. For instance, when the Hamming weight of the inputs is equal to 0, we have X 1 = X 2 = • • • = X n = 0, and the Y i are given by (y 1 , . . . , y n ) = B(x 1 , . . . , x n ) = B(0, . . . , 0). In this case, the Gröbner basis computation gives:

I 0,wout = I B + I hw (0) + I hw (w out ) = I B + I hw (0) = X 1 , . . . , X n , Y 1 + y 1 , . . . , Y n + y n
which means that all the X i and Y i are fixed by the resolution. In this case, the number of independent linear equations is maximal. This (trivial) example corresponds to the case where the input (or output) is fixed by the leakage. These are the only cases where one can show that there are more than two linear relations in I l without fixing the black box B.

When the black box B is fixed, the number of independent linear equations depends on the Hamming weight ordered pair of the input and output, and we already show with Proposition 1 that it is linked to the number of points which satisfy this couple. Thus, N B (Definition 3) in the case of the Hamming weight model is denoted by N B (w in , w out ) and it is explicitly given by Remark 2 N B (w in , w out ) is related to the likelihood P(HW (x) = w in and HW (B(x)) = w out ) of the pair (w in , w out ). Indeed, if we assume an equiprobability distribution of input bytes, this likelihood equals 2 -n N B (w in , w out ).

In the particular case of an 8-bit bus size, Proposition 1 gives that #AI L (B, w in , w out ) is always greater than or equal to 17-N B (w in , w out ) when N B (w in , w out ) is non-zero. Section 6 and Appendix A show that, for a lot of usual S-Boxes, N B (w in , w out ) is often small in the Hamming weight leakage model, and the interesting Hamming weight pairs are the ones such that N B (w in , w out ) is small. Indeed, in this case, the constraints on the X i and Y i variables are strong, and we obtain several linear equations (see Proposition 1). Moreover, if the integer N B (w in , w out ) is very small (typically ≤ 6 for an 8-bit bus) then some bits can even be fixed, this will be discussed in Section 4.3.

Remark 3 Note that there are a lot of linear relations because there are two Hamming weight leakages around B. If only one Hamming weight leakage (input or output) is added to the equations of B then the number of solutions satisfying this condition is equal to the binomial n w and is generally (if w = 0, n) too big to fix some bits and to obtain interesting linear equations. This situation is very similar to the Hamming distance model (see Section 3.3).

The next section studies the Hamming distance leakage which is a more general model than the Hamming weight model. Its main purpose is to study the relevance of the Algebraic Immunity with Leakage and the proposed invariant N B with a different leakage model.

Hamming distance leakage model

The Hamming distance model is often more suited than the Hamming weight model to describe the power consumption of a device (see [START_REF] Brier | Correlation Power Analysis with a Leakage Model[END_REF] or [START_REF] Mangard | Power Analysis Attacks : Revealing the Secrets of Smart Cards[END_REF] for instance). Indeed, the power consumption of a microcontroller, for instance with CMOS technology, is typically described by the number of modified bits in registers or buses (due to the presence of many connected components: capacitors, logic/sequential cells etc...). The consumption of a transition from a value x to a value y is then modeled by HD(x, y) = HW (x ⊕ y).

The measured leakages in real devices strongly depend on the implementation. Thus, many different scenarios could be considered with the Hamming distance leakage model (for instance, the distance could be measured between different points). The aim of this analysis being to study the influence of additional information on the algebraic solving step, we do not necessarily seek the most realistic scenarios. Instead, we especially want to check the relevancy of the proposed analysis. In the ASCA context, similar to the Hamming weight model (Section 3.2), we will first assume that an initial on-line phase provides the Hamming distances between input and output of a black box B. We refer to Section 6 for a discussion about this assumption and consideration of other models.

As before, the Algebraic Immunity with Leakage is equal to 1 for every black box B. This is a consequence of Lemma 1 since the system of equations representing an Hamming distance is the system (1) where we substitute X i ⊕ Y i for X i . Indeed, if we consider the ideal

I d ⊂ F 2 [X 1 , . . . , X n , Y 1 , . . . , Y n ]
generated by the equations representing B, the field equations and by L d (1) the equations representing the Hamming weight d of the XOR between the input and the output, namely:

I d = L d (X 1 + Y 1 , . . . , X n + Y n ) ∪ S B ∪ S Field Eq.

then we have the following proposition

Proposition 3 Let G be the Gröbner basis of the ideal I d for a graded monomial order. G contains at least one linear polynomial.

Proof According to Lemma 1, we know that the ideal I d always contains the polynomial

f = (X 0 + Y 0 ) + • • • + (X n + Y n ) + (d mod 2) ∈ I d
The rest of the proof is similar to the proof of Proposition 2.

Then there is always at least one linear equation when the Hamming distance equations are added to the system of equations corresponding to B. In the same way as previously, there could be many more in function of the Hamming distance. Once again, by Proposition 1, the number of independent linear equations is linked to the number of points which satisfy this Hamming distance. Thus, we define N B in the case of the Hamming distance by

N B (d) = #{x ∈ F n 2 s.t. HD(x, B(x)) = d}
Unfortunately, in contrary to the Hamming weight model, there is rarely more than one linear polynomial in the Gröbner basis, what is due to N B (d) which is larger than previously (see Section 6 for the experiments done for PRESENT and AES).

In the next section we will study more precisely the influence of the number of independent linear relations on the complete solving.

Solving the complete system modeling the block cipher

As explained in Section 2, the problem is modeled by a system of equations which has a particular block diagonal structure. More precisely, it is composed of blocks of equations which correspond to the cipher rounds with the leakage information. Each block is composed of systems of equations corresponding to the black boxes (Sboxes, MixColumns) and leakages of corresponding input and output data. We can split the complete system into small systems and locally study each of them. This local study is described in Section 3. We showed that the equations of the leakage model with the equations modeling one black box could yield a lot of low degree equations, such as linear equations, or could even give values of intermediate variables. Thanks to this particular structure, we have developed an efficient solving strategy.

Solving Strategy

The inputs of our off-line problem can be seen as a finite sequence L of values corresponding to the leakages of the successive 8-bit black boxes of the block cipher. In order to efficiently solve the complete polynomial system, we first seek the elements in L that provide the greatest possible number of linear relations. To do so, according to Section 3, we sort the sequence L by increasing N B . Following this order, the polynomial systems corresponding to the first elements are those that provide the most linear equations. Thus, rather than computing directly a Gröbner basis of the complete system, we first compute Gröbner bases of some of these smaller systems. In a second step, we solve the complete system with the additional linear relations computed during the first step. This strategy based on splitting allows us to have better control on the maximal degree reached during the second step.

Remark 4 This strategy allows us to select some of the leakage ordered pairs in L, in particular one could reject the leakages with large N B and small confidence in their measurements during the on-line phase.

A Sufficient Condition of Success

In the last step of the solving strategy, a polynomial system with several independent linear equations has to be solved. The efficiency of this step is strongly correlated with the number of these linear relations. More precisely, the efficiency heavily depends on the number n 35 47 56 64 69 78 90 P(R P RESEN T ≥ n) 99% 90% 70% 50% 30 % 10% 1% Fig. 1 Probability to obtain more than n linear equations with one PRESENT's round of independent linear relations between the inputs and the outputs of the black boxes B.

For computational feasibility, it is assumed that the dispersion through a round of a block cipher is so important that the rounds are supposed to be independent. The black boxes of the same round are also supposedly independent. Thus, under this assumption, for a given block cipher based on a black box B, the total number of linear relations only depends on the local study around B done in Section 2. From this local study, one can compute the distribution of the number of linear equations coming from the study of the polynomial system of one round. Example with the block cipher PRESENT and Hamming weight leakage model. In this example, the black box B is the 8-bit S-box built from two PRESENT S-boxes. From the study of the probability distribution of the random variable L P RESEN T (see Section 6) measuring the number of linear relations obtained from the local study of B, one can see that half of the possible leakage values provide at least 8 linear independent relations. Thus, the expected number of linear equations obtained from the substitution layer of one round is equal to 8 × E(L P RESEN T ) 64 for PRESENT and represents a practical behavior. Hence, the expected number of linear equations is about the same size as the block length for one round and n × k for the complete system with n rounds with leakages.

From the probability distribution of L P RESEN T , we computed the distribution of the random variable R P RESEN T measuring the number of linear relations obtained with all S-boxes and all Hamming weight leakages of one round of PRESENT. Figure 1 shows some of these results. According to them, the probability of obtaining at least 64 linear relations is about 50% with PRESENT. Thus, the expected number of linear equations has a high probability of being reached even with a small number of rounds with leakage information.

Considering these results, we propose a sufficient condition for an effective Algebraic Side Channel Attack. This condition is defined in a very simple way. Indeed, the local study of the non-linear part of a block cipher seen as a black box done in Section 3 gives an easy way to estimate the total number of low degree equations. This local study relies on the new notion of Algebraic Immunity with Leakage, which is itself linked to the function N B as proved in Section 2. This function is very easy to compute from the definition of the black box and provides the following general condition.

Sufficient condition of success Let B be an n-bit black box. If N B (l) (see Definition 3) is small enough (say less than n) for half of the possible leakages l then a block cipher based on B is vulnerable to an Algebraic Side Channel Attack with Gröbner Basis method.

In a Gröbner basis point of view, this condition implies (from Proposition 1) that at least half of the leakages provide more than n independent linear relations. Thus, the final polynomial system will be at least "half" linearized and (generally) easy to solve. In practice, this condition of success has been successfully applied for different black boxes constructed from S-boxes of wellknown block ciphers. For instance, we showed that N B is often small for PRESENT S-box with the Hamming weight leakage model, which explained the linearization of the full system of equation.

This sufficient condition of success can be expressed more precisely in practice by mean of a complexity bound. Indeed, the proposed invariant N B can be used to compute the complexity of the exhaustive search on inputs (and outputs) of the corresponding layer. Recall that N B (l) is equal to the number of possible input (or output) values for a black box B giving the leakage l. Thus, for a given n-bit black box B, the number of possible values decreases from 2 n to N B (l) thanks to the leakage l. For a fixed encryption and for a given layer with black boxes B 1 to B m with the corresponding known leakage l 1 to l m , the cost of exhaustive search on this layer is precisely equal to m i=1 N Bi (l i ). When the possible values of N B are (almost) evenly distributed, the expected value of N B is also a very good indicator and could be used to compute the average complexity of the exhaustive search of an input and an output of a round. Once more, we could assume that the rounds, as well as the boxes of a given round, are independent. Thus, the expected number of possible input values of the layer is E(N B ) m with m the number of boxes per rounds. In this case, the sufficient condition of success could be restated by saying that the block cipher is vulnerable to ASCA if this expected value implies that the complexity to recover the secret key is less than the assumed computing power of an attacker. This is usually the case in practice for PRESENT with the Hamming weight leakage model, where we have E(N B ) 12.29 and the average complexity of the exhaustive search of the layer input is E(N B ) 8

2 29 (by comparison with a complexity of 2 64 without leakage information). This condition is only sufficient because it does not consider implications from one leakage to the entire system and the ability of tools such that SAT solvers to exploit them.

Such a condition of success explains why it is possible to attack a block cipher when all the leakages of all the rounds are known and gives a first complexity bound for this attack. On the other hand, the authors of [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF] showed that three or four consecutive leakages rounds are sufficient to quickly solve the complete polynomial system (see annex B where we reproduce the experimental results presented in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF]). Counting the number of linear equations given by these rounds is not sufficient to explain the efficiency of the method, in particular for the unknown Plaintext and Ciphertext scenario and the similarity between these results and those obtained in the known PC scenario. Moreover, the sufficient condition expressed in terms of exhaustive search can be improved by taking into account the implications between different rounds. Thus, in the next section, we study the particular situation where the leakages correspond to a few consecutive rounds.

Consecutive leakages

First we consider the basic case of two face to face black boxes B 1 and B 2 of consecutive rounds (Figure 2). The best case is when N Bi (i = 1 and 2) is small enough (<< n the bus size), such that the linear relations coming from the local study at B 1 and B 2 successfully fixed intermediate bits. For example, assume that two face to face bits y i and x j in the output of B 1 and the input of B 2 (see Figure 2) are known by the local study of B 1 and B 2 with Hamming weight leakages. The complete system of equations contains the equations modeling the permutation layer and the bitwise XOR (see Section 2), hence, during the second step of the strategy, the subkey bit k j is easily deduced from the knowledge of the value of y i and x j . Once a subkey bit is fixed, other subkey bits in other rounds can be found with the key schedule equations.

Remark 5 This point of view explains why it is harder to successfully attack the problem with unknown plaintext and ciphertext when we do not know such consecutive leakages (see Appendix B when the number of rounds of Hamming weight information is less than 15 for PRESENT, and less than 5 for AES).

Following our sufficient condition and the study done in this section, the solving efficiency is due to a small N B in average for the black box B. In the following, we exhibit a family of black boxes which are as far removed as possible from the condition of success and we

x 1 xn x j y 1 yn y i k 1 k j kn . . . . . . K Perm. B 1 B 2
Fig. 2 Example of two consecutive rounds verify experimentally that they are more resistant to algebraic side channel attacks. The condition of success exhibited in this section is not a necessary condition but the results of the next section tend to show that it is very close to be criterion of success.

Characterization of a family of resistant S-Boxes

Generally in the design of block ciphers using a substitution-permutation networks, S-boxes are the nonlinear part. Thus, the S-boxes must be carefully chosen to make the cipher resistant against cryptanalysis. In our attacks, the S-boxes (seen as black boxes) leak information from the manipulated data. In this section, we only consider the situation covered by the Hamming weight model (i.e. a leakage l will be a couple of values corresponding to the Hamming weight of the input and output of the black box B). For the distance model a study is done, for example, in [START_REF] Prouff | DPA Attacks and S-Boxes[END_REF]. The knowledge of this additional information enables us to model this cipher component by a system of equations containing #AI L linear relations. As seen in Section 3.2, #AI L clearly depends on the Hamming weight pairs but also on the black box. The expected value of the number of such linear relations is very large (greater than 7). These S-boxes are weak for our attacks and we are looking for a criterion for more resisting S-boxes. We study the influence of the black box on our criterion N B (w in , w out ), which is linked to #AI L (B, w in , w out ). For that, we study the extreme case represented by the family of S-Boxes in complete contradiction with the sufficient condition of success exhibited in Section 4.2.

Since N B (w in , w out ) is explicitly given as the cardinality of the sets {x ∈ F n 2 s.t. HW (x) = w in and HW (B(x)) = w out }, it is clear that a bijective black box B maximizing N B (w in , w out ) for every possible pair (w in , w out ), must be such that the sets HW -1 (w in ) and B -1 (HW -1 (w out )) have precisely the same elements. Moreover, in this case, we have

N B (w in , w out ) = n w in = n w out
Indeed for all w ∈ N and for all bijective black box B, we have

#HW -1 (w) = n w and #B -1 (HW -1 (w)) = n w
Actually, a bijective black box B maximizing N B (w in , w out ) for every possible pair (w in , w out ), must satisfy

w in = w out or w in = n -w out
Then such black box factors into

B(x) = π(x) ⊕ f (HW (x))(1, . . . , 1)
where π is a permutation stable under the Hamming weigth and f is a boolean function such that f (HW (x)) = f (n -HW (x)).

Example 3 The following table describes such an optimal 4-bit S-Box:

x 0 1 2 3 4 5 6 7 8 9 A B C D E F B(x) 0 8 1 C 2 6 9 B 4 5 3 D A E 7 F Therefore, there are optimal black boxes in the sense of maximizing N B for every possible leakage, and experiments confirm that some of them are more resistant to our attacks. However, it seems that such black boxes are not resistant to differential and linear cryptanalysis. In the particular case of an even bus size, we are able to prove the following proposition: Proposition 4 Let n be an even number and let assume that the leakage model is the Hamming weight one. The n-bit black boxes in a complete contradiction with the sufficient condition of success (see Section 4.2) for an ASCA, i.e. satisfying HW -1 (w in ) = B -1 (HW -1 (w out )), are not resistant to linear cryptanalysis. Actually, affine components exist for these Sboxes.

Proof Let B be an n-bit black box verifying the assumptions of the proposition. In this case, we already saw that

N B (w in , w out ) = n w in = n w out
Thus, w in = w out or w in = n -w out which implies that w out ≡ w in mod 2 in the case where n is an even integer. Hence we have (1, . . . , 1) • B(x) = (1, . . . , 1) • x and the nonlinearity of B is equal to 0.

In the case where n is an odd number, we could find some ASCA-resistant black boxes with a linearity slightly less than 2 n . However, all these found black boxes stay weak against linear cryptanalysis. Hence, the question arises of determining whether ASCA optimally resistant S-boxes can reach a good nonlinearity. But we were not able either to prove the inexistence of ASCA optimally resistant black boxes with a strong resistance against linear cryptanalysis, in spite of the following rewriting using the Krawtchouk polynomials K n,w , which establishes a relation between the function N B and the Walsh coefficient (essential for computing the linearity of a box). Krawtchouk polynomials are classical orthogonal univariate polynomials over the rationals associated with the binomial distribution. They are defined by

K n,w (X) = n j=0 (-1) j X j n -X w -j
We have K n,w (0) = n w and for all a ∈ F n 2 , we have

x∈F n 2 |HW (x)=w (-1) a•x = K n,w (HW (a)) (3)
By the inverse Fourier transform, we deduce from (3) that for all w = 0, . . . , n,

a∈F n 2 K n,w (HW (a))(-1) a•x = 2 n if HW (x) = w 0 otherwise
Finally, for all w, w = 0, . . . , n, we have

N B (w, w ) = #{x ∈ F n 2 |HW (x) = w, HW (B(x)) = w } = 2 -2n a,b,x∈F n 2 K n,w (HW (a))K n,w (HW (b))(-1) a•x+b•B(x) = 2 -2n a,b∈F n 2 K n,w (HW (a))K n,w (HW (b))B W b (a)
where

B W b (a) := x∈F n 2 (-1) a•x+b•B(x) be the Walsh transform of B.
Actually, as already proposed in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF], it seems that one of the safest way to design a substitution box resistant to all kinds of attacks is to increase the bus size. Indeed, N B (w in , w out ) also depends on the bus size n, and for all bijective black boxes, since N B (w in , w out ) defines a partition of F n 2 we have

(win,wout)∈N 2 N B (w in , w out ) = 2 n
This shows that, in general, N B (w in , w out ) grows exponentially as n increases.

Experiments

In this part we show that the condition of success from Section 4.2 is supported by the experiments (positive and negative) we performed for PRESENT, AES and for the resistant S-box given in Section 5. Following our model described in Section 2, we build a complete system of polynomial equations as a function of the target cipher (PRESENT or AES) and as a function on the sequence L of leakage information which are taken into account. Since Magma [START_REF] Bosma | The MAGMA algebra system: the user language[END_REF] provides an efficient implementation of the Faugère F4 algorithm, we use this computer algebra system for our experiments. For the SAT attacks, we use CryptoMiniSat [SNC09], glucose2, glueminisat, and plingeling which are the winners of the SAT Race 2010 and SAT Race 2011.

Experiments against PRESENT using the Hamming weight model

Here, the leakage comes from the inputs and outputs of S-boxes (we see two consecutive 4-bit PRESENT Sboxes as an 8-bit one).

PRESENT is a very simple Substitution-Permutation Network designed by Bogdanov et al. [BKL + 07] for hardware efficiency and for extremely constrained environments. The non-linear layer uses a single 4-bits S-box S which is applied 16 times in parallel in each round. The action of this box is given by the following table.

x 0 1 2 3 4 5 6 7 8 9 A B C D E F S[x] C 5 6 B 9 0 A D 3 E F 8 4 7 1 2

Following the situation of [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF], we assume that the device leaks the Hamming weights of the values commuting on its 8-bit bus. In this case, two S-boxes are processed at the same time, which is represented by a 8bit black box B. From the definition of B one can easily deduce the table 3 giving N B (w in , w out ) in function of the input/output couples. We compare this table with the one (see Table 4) given #AI L (B, w in , w out ) in function of the same couples. One can see that N B (w in , w out ) can give a good indicator when we are interested in maximizing the number of independent linear polynomials #AI L (B, w in , w out ) during an algebraic attack. Even if #AI L (B, w in , w out ) is not rigorously inversely proportional to N B (w in , w out ) it is close to be the case. A counterexample for this reciprocity is given by N B (3, 3) = 12 which is less than N B (2, 4) = 18 but #AI L (B, 3, 3) = 5 < #AI L (B, 2, 4) = 8. Assume that the probability of appearing of an input byte of the 8-bit black box B is 1/256. With Figures 3 and4, we can easily compute the probability distribution of the random variable L B measuring the number of linear relations that we obtain by adding the leakage information to our system. The Figure 5 presents a chart providing the probabilities P(L B = k) inside the sectors labeled by k. The integers k that give null probability are not shown. We could note that the prob- ability that at least 8 independent linear relations are produced is about 50%. Moreover, the expected value of L B is 7.9.

We also compare Table 3 with the one given the number of fixed bits (see Table 6) in function of the input/output couples. One can see that when N B is small the number of fixed bits can be large. We will now use all this knowledge to explain the experiments behaviors observed during an algebraic attack of PRESENT under different scenarios.

As in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF], the knowledge of all Hamming weight pairs from the 31 rounds of PRESENT always leads to successful SAT solver and Gröbner attacks, in both cases known and unknown plaintext and ciphertext. Note that in this experiment, we already must apply our solving strategy (4.1). More precisely, we first have to successively compute the Gröbner basis of each round before computing the last Gröbner basis of the whole system. Indeed, if we try to directly compute the Gröbner basis of the system of equations modeling the initial problem, then the maximum degree reached during the computation is too big, and the computation is very slow.

Similar experiments allow us to check Remark 3: we explained that an important condition is the knowledge of the couple of Hamming weights around the S-box. So, we performed attacks on PRESENT with only the Hamming weights of input (or output) data of all S-Boxes. Our Gröbner basis solving strategy and SAT solvers are much less efficient, rather than failed, in this situation (which is very similar to the HD scenario). Indeed, without the knowledge of the plaintext and ciphertext, SAT solvers and Gröbner attacks always failed. It confirms that a large N B , which could not fix enough intermediate bits (see Section 4.3), is not able to find subkey bits. Otherwise, if the plaintext and ciphertext were known, the low number of linear equations often allow some SAT solvers to recover the key. However, the solving step is very long with all used SAT solvers (once again comparable to the HD model) and the Gröbner attack fails with an out of memory if we take much than 2 or 3 rounds. These experiments confirmed the necessity of always using weight couples.

Other experimental results confirmed that the number N B (w in , w out ) is a very good indicator to sort interesting Hamming weight couples for an ASCA. These experiments have checked Remark 4 for PRESENT. More precisely, one can reject the leakages (w in , w out ) with large N B (w in , w out ) without consequences on the success rate. Conversely, if we reject the leakages (w in , w out ) with small N B (w in , w out ) then all Gröbner basis attacks and all SAT attacks failed.

Following the condition of success, we also designed theoretically more resistant S-boxes in Section 5. Experiments with PRESENT, where we use such S-boxes as a substitute for original S-boxes, are also intractable (with both SAT and Gröbner ) which confirm that these S-boxes are much more resistant to this kind of attack.

Thus, we are able to explain the experiments against PRESENT in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF]. In particular, the study in Section 4.3 explained the successful attacks when we know consecutive leakages. Note that the success rates given in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF] in the case of unknown plaintext and ciphertext attacks with randomly distributed leakage information (Appendix B) can be explained by the pigeonhole principle. For the example involving 31 rounds of PRESENT, the success rate is greater than zero when the number of rounds with leakages reaches approximately 15. By the pigeonhole principle, this corresponds to the case where there are at least two consecutive rounds with leakage and thus Section 4.3 explained these experimental results.

Experiments against AES using the Hamming weight model

Here, the 8-bit leakage comes from the inputs and outputs of S-boxes and Mixcolumns.

The same study of the AES S-box B also shows (see Table 7 andTable 8) that N B (w in , w out ) is a very good indicator when we are interested in maximizing #AI L (B, w in , w out ) .

As before, we compute the probability distribution of the random variable L B measuring the number of linear relations that we obtain by adding the leakage information to our system. The chart of the Figure 10 provides the probabilities P(L B = k) inside the sectors labeled by k. The integers k that give null probability are not shown.

Surprisingly, the probability that at least 8 independent linear relations are produced is also about 50%, w in wout 0 1 2 3 4 5 6 7 8 0 0 0 0 0 16 0 0 0 0 1 0 0 10 0 16 6 12 0 0 2 0 10 7 2 3 2 6 10 0 3 16 16 2 0 0 0 2 10 0 4 0 10 0 0 0 0 2 16 0 5 0 16 1 0 0 0 5 8 0 6 0 0 6 1 3 1 6 0 16 7 0 16 0 10 8 16 16 16 0 8 0 0 0 16 0 0 0 0 0 In the same way as PRESENT, we will now use all this knowledge to explain the experiments behaviors observed during an algebraic attack of AES under different scenarios.

As in [START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF] and [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF], the knowledge of all Hamming weight pairs (i.e. around the S-boxes and around the Mixcolumns) from the 10 rounds of AES always leads to successful SAT and Gröbner attacks, in the case of known plaintext and ciphertext. The ASCA in unknown plaintext and ciphertext scenario is effective only with SAT solvers, the Gröbner computation requiring too much memory space.

Note that we only took the Hamming weights of the input and the output of the Mixcolumns step. Thus, The Mixcolumns transformation being a linear step, we also wonder whether its leakage was required. The experiments with only the Hamming weights leakage of the S-boxes (i.e. without leakage from MixColumns) are effective with SAT solvers, even if the solving step is much longer (in average a couple of hours against several dozen seconds).

We also make experiments with the theoretically resistant S-boxes designed in Section 6, which confirm that AES with these S-boxes are more resistant to both SAT and Gröbner attacks.

Experiments against PRESENT and AES using the Hamming distance between input and output of S-Boxes

In this model, similar to the Hamming weight model, we assume that an initial on-line phase only provides the 8-bit Hamming distances between input and output of the S-boxes. It should be noted that using only the Hamming distance between input and output of the S-Boxes seems too restrictive, as well as being not very realistic. Indeed, we should also assume that other distances are known, which of course would increase the efficiency and success rate of the attack. However, this model stays interesting because the purpose of these experiments is above all to confirm the relevance of the proposed criteria.

We already foretold (see Section 3.3) that an ASCA will be much more difficult in this case. Actually, there is always at least one linear equation (see Proposition 3) when the Hamming distance equations are added to the system of equations corresponding to PRESENT or AES S-boxes but, unfortunately, in contrary to the Hamming weight model, there is rarely more than one. This fact can be explained for PRESENT and AES by studying the functions N PRESENT and N AES respectively. The Tables 11 and12 detail the distribution of these functions and the corresponding #AI L for AES and PRESENT S-boxes.

As one can see, the functions N PRESENT and N AES often take very large values. Thus, the number of expected linear relations will be very small. Moreover, one can guess that the number of linear relations for AES will be less than for PRESENT (since there are more large values for N AES than for N PRESENT ). Actually, the expected number of linear relations is about 2.3 for PRESENT and 1.4 for AES S-Boxes (with an assumption on equiprobability distribution of input bytes), which is much less than in the case of the Hamming weight model (between 7 and 8, as seen above). It becomes manifest that a Gröbner attack will be much more difficult in this case. Actually, Gröbner attack in this situation needs too much memory to be practical.

In practice, we were not able to mount a complete Gröbner attack with 31 rounds of PRESENT (an attack on 3 rounds of PRESENT has been successful, but an out of memory error occurs with more rounds). Nonetheless, in known plaintext and ciphertext scenario, the constraints on the intermediate variables given by the Hamming distance equations seem sometimes sufficient for SAT solvers that we used. The solving time seems strongly dependent on the heuristics of the SAT solver and so it is difficult to correlate them to the number of linear equations or their distribution.

On the other hand, as we suspected by studying the function N AES , every ASCA experiments on AES with the Hamming distance leakage model have failed. This fact can be explained by the more complex algebraic structure of AES (including its keyschedule) which seems to avoid ASCA with only the Hamming distances between the inputs and outputs of S-Boxes.

Moreover, the chance to find the value of an intermediate bit is very low, which explains the negative experiments in unknown plaintext and ciphertext scenario in this case.

Experiments against PRESENT using the Hamming distance between consecutive encryptions

An interesting extension would be also to consider the leakages between consecutive encryptions of different plaintexts. This model provides, for a given spot, the Hamming distances between successive encryptions. As usual, we consider the 8-bit Hamming distances between inputs of all S-boxes from two consecutive encryptions with PRESENT, with a fixed secret key. The same goes with the outputs of all S-boxes. As presented in Figure 13, this model provides the Hamming distances HD(x 1 ⊕ k, x 2 ⊕ k) = HD(x 1 , x 2 ) and HD(y 1 , y 2 ) = HD(B(x 1 ⊕ k), B(x 2 ⊕ k)). Thus, at the first round for instance, x 1 and x 2 are bytes of the plaintexts, then we assume that they are known and only the Hamming distance of the outputs are interesting (the same goes with the Hamming distances of inputs at the last round). In this particular case, for given x 1 and x 2 , our invariant N B (d out ) is defined by {k ∈ F 8 2 s.t. HD(B(x 1 ⊕ k), B(x 2 ⊕ k)) = d out }, which is very similar to the previous Hamming distance between input and output of S-Boxes (Section 6.3). For instance, Figure 15 shows the values of N B (d out ) and #AI L (B, d out ) when x 1 =0xD8 and x 2 =0xB1. Notice that the number of linear equations is often large despite the fact that N B is also large. But, many of these equations are just equalities between the 3n unknown bits, hence are useless for fixing bits of the key. In practice, we have only done experiments on the very simple block cipher PRESENT with the fixed plaintexts and the fixed key shown in annexe C. The results are reported in figure 6.4. In the experiments we have done, the SAT solver attacks worked when there are leakages in all PRESENT's rounds, although the computation time can be very different between two instances. Following the condition of success, the exhaustive search on the 64 used bits of the last subkey is reduced to a complexity between 2 41 and 2 50 . The SAT solvers are much faster since they do not only use information of the last round, but also from previous rounds (and especially from the first round) thanks to the simplicity of the PRESENT key schedule.

As in Section 6.3, the Gröbner attack needed too much memory to solve the system with this model. Moreover, leakages on the round, on the last round, plaintext and ciphertext are all mandatory; all attacks without one of these have failed.

Conclusion

In this article we introduced a new criterion for the effectiveness of ASCA. This criterion rely on a new notion of algebraic immunity. In order to simplify the analysis of a given block cipher we introduce an invariant related to this block cipher. This invariant is a function which can be easily defined and computed from the definition of the given block cipher (no need of advanced algebra). From this new invariant we exhibit a sufficient condition of success of an ASCA and we were able to theoretically explain the experiments done by Renauld, Standaert and Veyrat-Charvillon in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF][START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF] by studying the distribution of the values taken by this function. Experimental results confirmed our sufficient condition success and showed that it is a good condition for both effective Gröbner and SAT solver attacks. This understanding allowed us to design S-boxes optimally resistant to ASCA following this condition. However, we observe that these S-boxes are weak for linear and differential cryptanalysis, which confirms, as observed in [START_REF] Renauld | Algebraic Side-Channel Attacks[END_REF], that a large bus size can be prescribed to design a resistant block ciphers. Following our new invariant for a block cipher, and with our experiments, we also show the influence of the leakage model over ASCA. In this paper, we studied the Hamming weight and Hamming distance leakage models, but other good leakage models can be selected. Some results on the influence of the leakage model over ASCA have already been presented (see [START_REF] Renauld | Representation-, leakage-and cipher-dependencies in algebraic side-channel attacks[END_REF]). They are all rely on experimental studies using SAT solvers, we will address the comparison of our approach with them in a future research paper. More generally, extending the attack to deal with erroneous equations is one of our long-range research aims. The well understanding of the algebraic phase of this attack done in this article is already a first step in this direction. where the symbol ≪ correspond to left rotation operation. Because of these definitions, it is easy to see that the four S-boxes have the same Hamming weights distribution. Thus, the Figures 16, 17 and 18 equally correspond to the four S-boxes.

Fig. 3 NFig. 4 #

 34 Fig. 3 N B (w in , wout) where B is two PRESENT S-Boxes

Fig. 5

 5 Fig. 5 P(L B = k) for k with non zero probability and for HW leakages

Fig. 6

 6 Fig. 6 Number of fixed bits with two PRESENT S-Boxes

  Fig. 7 N B (w in , wout) where B is the AES S-Box

Fig. 9

 9 Fig. 9 Number of fixed bits with the AES S-Box

Fig. 12

 12 Fig. 11 HD model and 2 PRESENT's S-Boxes d 0 1 2 3 4 5 6 7 8 N B (d) 0 12 31 48 67 59 32 7 0 #AI L (B, d) 0 5 1 1 1 1 1 10 0 Nb fixed bits 0 0 0 0 0 0 0 1 0 Fig. 12 HD model and AES S-Box

Fig. 13

 13 Fig. 13 Two encryptions with the same key

Fig. 14 Fig. 15

 1415 Fig.14Solving times in second of experiments against PRESENT using the Hamming distance between consecutive encryptions dout 0 1 2 3 4 5 6 7 8 N B (dout) 0 0 32 48 64 64 32 16 0 #AI L (B, dout) 0 0 15 12 9 9 14 20 0 Nb fixed bits 0 0 2 0 0 0 0 0 0 Fig.15HD between 2 consecutive encryptions with PRESENT when x 1 =0xD8 and x 2 =0xB1

A

  Annex : A study of several S-Boxes and 8-bit Hamming weight leakage model In this part, we provide tables showing the distribution of N B for different S-Boxes with the Hamming weight leakage model. All the results show that these S-boxes are weak against an ASCA.A.1 CAMELLIA S-Boxes CAMELLIA [AIK + 00] is a block cipher developed by NTT and Mitsubishi in 2000. It is a Feistel cipher and uses four 8-bit S-Boxes. S-Box1 is given by a table and S-Box2, S-Box3 and S-Box4 are defined using S-Box1 as follows:S-Box2[X] = S-Box1[X] ≪ 1 S-Box3[X] = S-Box1[X] ≪ 7 S-Box4[X] = S-Box1[X ≪ 1]

  Fig. 16 N B (w in , wout) where B is one of the CAMELLIA S-Boxes

Fig. 21 P

 21 Fig. 21 P(L B = k) for k with non zero probability and for HW leakages. The expected value of L B is 7.7.

Fig. 22

 22 Fig. 22 31-round PRESENT, partial WH leakages

Fig. 23

 23 Fig. 23 Success rate of the attacks against an unprotected implementation of the AES in function of the amount of exploited leakages. One round of side-channel information is equivalent to 84 known Hamming weights

  7 N B (w in , wout) where B is the AES S-BoxFig. 8 #AI L (B, w in , wout) where B is the AES S-Box

	P w in P P	P wout P P	0 1 2 3 4 5 6 7 8
		0		16
		1		15	16 14 15
		2		15 14 9 12 13 13 15
		3		16 16 13 2 2 7 12 15
		4		14 8 6 2 2 8 16
		5		16 10 7 2 3 14 15
		6		14 10 12 9 13	16
		7		16	15 15 16 16 16
		8		16
	P	P P	P	P P

  B = k) for k with non zero probability and for HW leakages the MixColumns transformation is seen as a black box and then, contrary to the experiments described in the article[START_REF] Mathieu Renauld | Algebraic Side-Channel Attacks on the AES: Why Time also Matters in DPA[END_REF], previous ASCA are effective against AES even if the MixColumns operation is implemented as a table look-up. This difference of experimental results may be explained by the advances in SAT solvers heuristics.

	AES			2
		3
	6	5.4%
		4.2%			34.7%
	7
	7.8%
						4.6%
	8	7.0%			6.2%	16
		6.2%		5.8%	15
		9	5.4%	5.8%	6.2%	14
		10	12	13
	Fig. 10 P(L

  16 N B (w in , wout) where B is one of the CAMELLIA S-Boxes Fig.17#AI L (B, w in , wout) where B is one of the CAMEL-Fig. 18 P(L B = k) for k with non zero probability and for HW leakages A.2 SMS4 S-Box SMS4 [Off06] is a block cipher used in the Chinese WLAN National Standard. It uses an 8-bit S-Box given by a table. The following Figures show its Algebraic Immunity with Hamming weights Leakage.Fig. 19 N B (w in , wout) where B is the SMS4 S-box Fig. 20 #AI L (B, w in , wout) where B is the SMS4 S-box

	SMS4		5			3			CAMELLIA		3	2
											5		11.3%
		7	6	4.6% 4.2%	25.3%		2		6		4.6%	26.5%
				3.9%		8.9%				8.5%
		8		7.0%			4.6%	16		7	3.9%	3.1% 5.0%	16
				6.2%		6.2%					9.3%	8.2%	15
			9		10	13.6%	11 4.6% 1.9% 12 4.6% 3.5% 13	14	15		9		10	11 5.4% 4.6%	12 5.8% 3.1%	13	14
										P P w in	P P wout P P	0 1 2	3	4	5	6 7 8
											0		0 0 0	0	0	1	0 0 0
											1		0 0 1	1	4	2	0 0 0
											2		0 1 4	7	9	4	1 2 0
											3		0 2 7 12 10 14 8 3 0
											4		1 2 6 23 16 14 7 1 0
											5		0 2 6	8	21 11 5 2 1
											6		0 0 2	3	9	7	7 0 0
											7		0 1 1	2	1	3	0 0 0
											8		0 0 1	0	0	0	0 0 0
	P P w in	P 0 P P wout P 1 2 3 4 5 6 7 8	0 1 2 3 4 5 6 7 8 16 16 14 14 16 16 14 11 11 10 15 14 16 14 3 2 2 13 16 13 5 6 2 3 9 16 16 15 12 6 2 7 9 14 14 10 9 12 12 16 16 15 16 15 16 16	P w in P P 0 P P wout P 1 2 3 4 5 6 7 8	0 1 2 3 4 5 6 7 8 16 16 16 13 15 16 13 10 8 13 16 15 15 10 5 7 3 9 14 16 15 11 2 3 3 10 16 15 11 9 3 6 12 15 16 15 14 8 10 10 16 16 15 16 14 16
	LIA S-Boxes

N B (w in , wout) = #(HW -1 (w in ) ∩ B -1 (HW -1 (wout))) = #{x ∈ F n 2 s.t. HW (x) = w in and HW (B(x)) = wout}

Acknowledgments

This work has greatly benefited from highly relevant comments of anonymous reviewers. The authors would like to thank them sincerely for their suggestions that improved this paper. They also thank O. Orcière for his rereadings and for his constructive comments.