Calculation Based on the Fourier Transform

Jean-S´bastien Coron1 , Christophe Giraud2 , Emmanuel Prou¬2 ,

e

and Matthieu Rivain1,2

1

University of Luxembourg

jean-sebastien.coron@uni.lu

2

Oberthur Technologies

{c.giraud,e.prouff,m.rivain}@oberthurcs.com

Abstract. At CHES 2006, a DPA countermeasure based on the Fourier

Transform was published. This generic countermeasure aims at protect-

ing from DPA any S-box calculation used in symmetric cryptosystems

implementations. In this paper, we show that this countermeasure has a

¬‚aw and that it can be broken by ¬rst order DPA. Moreover, we have

successfully put into practice our attack on two di¬erent S-box imple-

mentations. Finally, we propose an improvement of the original counter-

measure and we prove its security against ¬rst order DPA.

1 Introduction

The processing of a cryptographic algorithm on a physical device may leak infor-

mation about the manipulated data. To exploit this information, Side Channel

Attacks (SCA) were introduced in 1996, cf. [8]. It is today composed of a large va-

riety of attacks that di¬er in the attack model, the nature of the side channels they

target or the leakage treatments they perform. The Di¬erential Power Analysis

(DPA) introduced in [9] is probably the one which has received the most attention

in the literature. This attack has indeed been demonstrated to be very powerful

against unprotected cryptographic implementations, where it allows the attacker

to recover the value of a secret key with only a few leakage measurements. Roughly

speaking, a DPA is a statistical attack that correlates a physical leakage with the

values of particular intermediate variables (called sensitive variables in this pa-

per) that depend on both a public value and the secret key. To avoid information

leakage and its exploitation by DPA, the manipulation of sensitive variables must

be protected by adding countermeasures to the algorithm.

A very common countermeasure to protect block cipher implementations from

DPA is to mask every sensitive variable with a randomly generated variable

(called mask) and then to perform the calculations by only manipulating the

masked variable and/or the mask. When such a technique is applied, a problem

occurs which is usually referred in the literature as the mask correction Problem.

It relies on the di¬culty of masking the calculation of non-linear sub-functions

(e.g. the so-called S-boxes), without ever manipulating an intermediate variable

that depends on sensitive data. Many papers have been published that aim at

providing a solution to this problem (see for instance [1,7,10,11,12]). At CHES

E. Oswald and P. Rohatgi (Eds.): CHES 2008, LNCS 5154, pp. 1“14, 2008.

c International Association for Cryptologic Research 2008

2 J.-S. Coron et al.

2006, Prou¬, Giraud and Aumˆnier proposed in [11] a solution that may be of

o

particular interest when the input/output dimensions of the function to protect

are small and when the masks values are regenerated many times during the

algorithm processing. Moreover, the solution is provided together with a proof of

security that allows the reader to formally validate its security. In this paper, we

show that contrary to what is claimed in [11], a DPA attack can be successfully

mounted against this countermeasure. We exhibit the ¬‚aw upon which our attack

is based and we present how to successfully exploit it to recover the value of a

secret parameter. Finally, we propose an improvement of the countermeasure

proposed in [11] and we prove its security versus DPA in a realistic model.

2 Preliminaries

In the rest of the paper, we say that a variable is sensitive with respect to DPA

(shortened to sensitive variable in the context of the present paper) if it is a

non-constant function of a plaintext and a secret key. A DPA (also called ¬rst

order DPA in the literature when it is compared to higher order DPA) exploits

the leakage about a single intermediate sensitive variable. Hereafter, we recall

the formal de¬nition of the security against DPA (see for instance [2,4,11]).

De¬nition 1. A cryptographic algorithm is said to be secure against DPA if all

its intermediate variables are independent of any sensitive variable.

Conversely, an algorithm is said to admit a ¬rst order ¬‚aw if one of its interme-

diate variables depends on a sensitive variable.

A common countermeasure against DPA is to add (by bitwise or modular

addition) a random value called the mask to each sensitive variable. Masks and

masked variables propagate throughout the cipher in such a way that every

intermediate variable is independent of any sensitive variable. This strategy,

called ¬rst order masking, ensures that the instantaneous leakage is independent

of any sensitive variable, thus rendering DPA ine¬ective.

As pointed out for instance in [6,1], the tricky part when masking the im-

plementation of an algorithm is to deal with the following problem, called mask

correction Problem:

Problem 1. Let F be a (n, m)-function (that is a function from Fn into Fm ).

2 2

From a masked input Z • R1 ∈ Fn , the mask R1 ∈ Fn and an output mask

2 2

R2 ∈ Fm , compute F (Z) • R2 without introducing any ¬rst order ¬‚aw.

2

3 Secure S-Box Calculation Based on the Fourier

Transform

In [11], an algorithm claimed to solve Problem 1 is proposed. The method is

based on the involutivity property of the Fourier Transform. Before describing

it, let us ¬rst recall some basics about the transformation itself.

Attack and Improvement of a Secure S-Box Calculation 3

Algorithm 1. Computation of an arithmetically masked S-box output from a boolean

masked input

Inputs: A masked input Z = Z • R1 , the input mask R1 and a lookup table F

˜

Output: The 3-tuple ((’1)(Z•R2 )·R1 F (Z) + R3 mod 2n , R3 , R2 ) where R2 and R3 are

random values.

1. Pick up three n-bit randoms R2 , R3 and R4

2. result ← 2n R3 + R4

3. for a from 0 to 2n ’ 1 do

T1 ← SSP(a, Z) [T1 = (’1)a·Z ]

4.

T2 ← Z • a [T2 = Z • a]

5.

T2 ← T2 • R2 [T2 = Z • a • R2 ]

6.

[T2 = (’1)R1 ·(Z•a•R2 ) ]

T2 ← SSP(R1 , T2 )

7.

[T2 = (’1)a·Z•R1 ·(Z•a•R2 ) ]

T2 ← T1 — T2

8.

[T2 = F (a)(’1)a·Z•R1 ·(Z•a•R2 ) ]

T2 ← T2 — F (a)

9.

F (i)(’1)i·Z•R1 ·(Z•i•R2 ) ]

result ← result [result = (2n R3 + R4 )

10. T2

i∈{0,a}

11. end

12. result ← result [result = (’1)(Z•R2 )·R1 F (Z) + R3 mod 2n ]

n

13. return (result, R3 , R2 )

For every (n, m)-function F , the Fourier transform F of F is de¬ned for every

Z = (Z0 , · · · , Zn’1 ) ∈ Fn by:

2

F (a)(’1)a·Z ,

F (Z) = (1)

a∈Fn

2

n’1

where · denotes the scalar product de¬ned by a · Z = i=0 ai Zi .

It is well known that this transformation is involutive, which means that

F = 2n F or equivalently that:

1

F (a)(’1)a·Z , Z ∈ Fn .

F (Z) = (2)

2

2n

a∈Fn

2

Let R1 , R2 , R3 and R4 be 4 random masks belonging to Fn , and let Z denotes

2

a sensitive variable. The algorithm proposed in [11] to process F (Z)+R3 mod 2n

securely from Z = Z • R1 and R1 , implements the right-hand side calculus of

˜

the following relation (which is a slightly modi¬ed version of Relation (2)):

(’1)(Z•R2 )·R1 F (Z) + R3 mod 2n

⎢⎛ ⎞⎥

⎢ ⎥

⎢1 ⎥

= ⎣ n ⎝R + 2n ⎠¦

a·Z•R1 ·(Z•a•R2 )

F (a)(’1) mod 2 , (3)

2 n a∈F2

where R = 2n R3 + R4 .

4 J.-S. Coron et al.

Let SSP denote the signed scalar product X, Y ’ (’1)X·Y , let denote the

addition modulo 22n and let — denote the multiplication of two values belonging

to {’1, 1}. We recall hereafter the algorithm proposed in [11] to process the

right-hand side of (3) securely.

Finally, it is proposed in [11] to use the method described in [5] in order to

transform the arithmetic masking of the output of Algorithm 1 into a boolean

masking.

The authors of [11] had proposed a proof of security versus DPA for the

countermeasure de¬ned by Algorithm 1, but as we will see in the next section,

the proof is ¬‚awed and the countermeasure is not secure against DPA.

4 DPA against the Fourier Transform Based S-Box

Calculation

4.1 First Order Flaw

Unlike what is claimed in [11], the implementation of Algorithm 1 is not immune

against DPA. Indeed, the variable V = a · Z • R1 · (Z • a • R2 ) processed at

Step 8 brings information about the sensitive variable Z (recalling Z = Z • R1 ).

To exhibit the dependency between V and Z, let us ¬rst rewrite V as follows:

V = a · Z • R1 · (Z • a • R2 )

= a · (Z • R1 ) • R1 · (Z • a • R2 )

= a · Z • R1 · (Z • R2 ) .

The relation above shows that the intermediate variable V equals the sensitive

variable a·Z (a being a loop index) masked with the scalar product R1 ·(Z •R2 ).

Since R2 is uniformly distributed and is independent of both Z and R1 , then so

does the variable Z •R2 . The ¬‚aw of the method proposed in [11] comes from the

fact that the scalar product of two uniformly distributed random variables does

not output an uniformly distributed random variable. For example, the product

b1 · b2 of two random bits b1 and b2 equals 0 with probability 3/4, and equals

1 with probability 1/4. More generally, for n-bit random variables we have the

following lemma.

Lemma 1. Let X and Y be two random variables uniformly distributed over Fn

2

and mutually independent. Then the scalar product X · Y satis¬es

1 1

Pr[X · Y = 0] = + n+1 . (4)

22

Proof. We have:

P [X · Y = 0] = P [X = 0] · P [X · Y = 0|X = 0] + P [X = 0] · P [X · Y = 0|X = 0] .

Since the Boolean function y ∈ Fn ’ x · y is linear and not null for every

2

x = 0, we have #{x · y = 1} = #{x · y = 0} = 2n’1 . This, together with the

fact that X and Y are independent, implies P [X · Y = 0|X = 0] = 1 . Since

2

2n ’1

P [X · Y = 0|X = 0] = 1 and P [X = 0] = 2n , we deduce (4).

Attack and Improvement of a Secure S-Box Calculation 5

Remark 1. In the security proof conducted in [11], it is stated that the uniform

distribution of X and Y implies the one of X · Y . We show in Lemma 1 that this

assertion is actually wrong.

Lemma 1 implies that the distribution of R1 · (Z • R2 ) has a bias 2n+1 with

1

respect to the uniform distribution. Since the sensitive variable a · Z is masked

with a biased mask, the variable V de¬ned in (4) leaks information on a · Z. This

information can be used to recover Z by DPA.

4.2 DPA Attack

A DPA attack [9] targets the leakage L(b) generated by the processing of a

sensitive bit b in order to recover information about a secret which we denote

here by k . It can be performed with only a few information about the leakage

and it actually only assumes that the expectation of L(b) depends on the value

of b. Let us ¬rst recall the outlines of the attack in the general case where b can

be expressed as:

b = f (X, k ) , (5)

where f is a Boolean function and X is a public variable.

Description. To perform a DPA, the target algorithm is executed several times,

say N , for a sequence of values (xi )i¤N taken by X. For each execution, the

attacker measures the leakage li generated by the processing of b. Then, the

resulting leakage measurement sequence (li )i¤N is involved to (in)validate a key

hypothesis k on k . For such a purpose, the attacker ¬rst computes the se-

quence of guesses (bi )i¤N which are the predicted values of the bit b processed in

the successive executions: namely, for every i ¤ N we have bi = f (xi , k). Then,

the leakage measurements are separated in two categories: the ones for which

the predicted bit bi is equal to 1, and the ones for which it is equal to 0. Finally,

the so-called di¬erential ”k corresponding to the di¬erence between the mean

values of the two sets is computed:

N N

i=1 bi — li i=1 (1 ’ bi ) — li

’

”k = . (6)

N N

i=1 (1 ’ bi )

i=1 bi

If the key hypothesis is correct then the expectation satis¬es:

E[”k ] = E[L(1)] ’ E[L(0)] . (7)

If the key hypothesis is incorrect then a ratio ± ∈ [0, 1] of the bi ™s is wrongly

predicted and the expectation of the di¬erential satis¬es:

E[”k ] = (1 ’ 2±) E[L(1)] ’ E[L(0)] . (8)

Since ± is usually around 1 , we have E[”k=k ] 0. This implies that, for a

2

su¬ciently large N , the correct key hypothesis is such that ”k is of maximum

amplitude.

6 J.-S. Coron et al.

Remark 2. Depending on the function f , it may happen that the correct key

hypothesis is not the single one for which ”k is of maximum amplitude. Indeed,

a key hypothesis such that ± = 1 also results in a di¬erential of maximal ampli-

tude. According to (6), this di¬erential and the one corresponding to the correct

key hypothesis have exactly the same amplitude but have opposite signs. To dif-

ferentiate them the attacker needs to determine the polarity of E[L(1)]’E[L(0)].

DPA Attack Exploiting a Biased Mask. Let us now consider the case where

the target bit b is masked, namely:

b = f (X, k ) • R , (9)

where R is a random bit.

If R is uniformly distributed over F2 , then no successful DPA attack is possible.

Indeed, in that case b equals 0 (resp. 1) with probability 1 independently of

2

k . Conversely, when the distribution of R is biased compared to the uniform

distribution, then the distribution of b depends on f (X, k ), which renders DPA

possible. In the following, we denote by µ = 0 the bias such that P [R = 0] = 1 +µ.

2

The DPA works in the same way as in the unmasked case. The sequence

of guesses is still de¬ned as bi = f (xi , k) (since R is not predictable) and the

di¬erential ”k is computed according to (6). The randomization provided by R

implies that the bit e¬ectively processed equals f (xi , k ) with probability 1 + µ.

2

One deduces that, for the correct key hypothesis, a portion 1 + µ of the bi ™s is

2

correctly predicted while a portion 1 ’ µ is wrongly predicted in average. This

2

implies that the expectation of the di¬erential for the correct key hypothesis

satis¬es:

1 1

+ µ E[L(1)] ’ E[L(0)] + ’ µ E[L(0)] ’ E[L(1)] ,

E[”k ] =

2 2

that is:

E[”k ] = 2µ — E[L(1)] ’ E[L(0)] .

1

Hence the expectation of ”k is divided by a factor 2µ compared to an unpro-

tected implementation (this also holds for the di¬erentials ”k obtained for wrong

key hypotheses “ see Appendix A “ ). This implies, according to the analysis

in [3], that the number of required leakage measurements is roughly multiplied

1

by ( 2µ )2 . A more detailed analysis is conducted in Appendix A where we give

the exact distribution of ”k , assuming that the leakage noise has a Gaussian

distribution.

As a result, Lemma 1 implies that a DPA on Algorithm 1 exploiting the ¬‚aw

exhibited in Section 4.1 is expected to require about 22n times more leakage

measurements than a DPA when no masking is used. Since Algorithm 1 is only

interesting for a small value of n (e.g. n = 4), this factor is not prohibitive.

4.3 DPA Attack on the Flaw

In this section, we apply the DPA attack described in Section 4.2 in order to

exploit the ¬‚aw exhibited in Section 4.1. More precisely, our attack targets a bit

Attack and Improvement of a Secure S-Box Calculation 7

b which is a scalar product a · Z masked with a biased mask R = R1 · (Z • R2 ),

˜

that is

b=a·Z •R . (10)

We recall that a refers to a loop index in Algorithm 1 and that its value can be

chosen by the attacker among {0, · · · , 2n ’ 1}. The sensitive variable Z is the

sensitive S-box input and it can be written as a function of a public variable X

and a piece of secret data k . The way our attack is performed depends on this

function which can take several forms. In the sequel we consider two usual cases.

The ¬rst one is referred as the linear case and assumes:

Z =X •k .

This occurs for instance in AES and in FOX algorithms for the ¬rst round S-box

calculation.

The second case, referred as the non-linear case, assumes the existence of a

non-linear transformation φ such that:

Z = φ(X • k ) .

This occurs for instance in the AES algorithm implemented using the composite

¬eld method [10,11] (see [11, §4.1] for details). In that case, φ is the non-linear

(8, 4)-function which from a ∈ F256 processes d ∈ F16 according to the notations

of [10,11].

The Linear Case. We consider here the case where the targeted bit can be

expressed as b = a · (X • k ) • R that is:

b= a·X •a·k •R . (11)

The bit b in (11) only depends on one secret binary value a · k . Therefore, a

DPA on b will provide at most one bit of information on k . Hence, recovering

the whole secret k requires to perform a DPA attack on b for t di¬erent loop

indices a0 , ..., at’1 .

When mounting a DPA attack on b for a particular loop index a, the sequence

of guesses can only take one of the two following forms: (a · xi )i or (a · xi • 1)i .

According to (6), these two sequences result in two di¬erentials that are opposite

one to each other. The attacker does not know a priori which of these di¬erentials

correspond to the correct key hypothesis. Indeed, depending on the device, the

polarity (’1)s of the good di¬erential ”a·k may be positive or negative. In

other terms, the DPA allows the attacker to recover the value of a · k • s, where

k and s are unknown.

Since the polarity s is the same for all the loop indices a, then performing t

DPA attacks for t di¬erent loop indices a0 , ..., at’1 provides the attacker with

a system of t equations and n + 1 variables (the polarity bit s and the n bits

of k ). Solving this system requires to have at least t = n + 1 equations. After

choosing n indices ai having linearly independent vectorial representations in Fn 2

and after de¬ning an = a0 • a1 , it can be checked that solving the system allows

the attacker to unambiguously determine the value of k .

8 J.-S. Coron et al.

The Non-linear Case. We now consider the case where b satis¬es:

b = a · φ(X • k ) • R . (12)

For a non-linear φ, the attack is analogous to a classical DPA on some output

bit of e.g. a DES or AES S-box [9]. The non-linearity of φ ensures that for the

correct key hypotheses a peak of maximal amplitude will appear while for most

other key hypothesis no peak will appear. This enables to fully recover k .

In this section, we have described how to exploit the leakage on a sensitive bit

which is masked with a biased random bit. In the linear case, the attack requires

to perform n + 1 DPAs while only one DPA is needed in the non-linear case. In

the following section, we present experimental results for these two attacks.

5 Experimental Results

We put into practice the attacks described in Section 4.2 for two S-box implemen-

tations on an 8-bit smart card. Both attacks exploited the power consumption

resulting from several S-box calculations.

Regarding the linear case, we performed the attack on the S-box calculation of

FOX algorithm during the ¬rst round protected by the method described in [11].

In this case, the sensitive bits we targeted are of the form a · (X • k ) • R, where

a, X, k ∈ F4 . Following the outlines of the attack described in Section 4.3 for

2

the linear case, we have applied 4 + 1 DPAs on ¬ve di¬erent loop iterations of

Algorithm 1, namely one DPA for every a ∈ {1, 2, 4, 8, 3}.

3

Figure 1.a represents the value of i=0 ”ai ·k , where ai = 2i , obtained af-

ter 20 000 executions of the algorithm. The full black curve corresponds to the

correct subkey value k and the dotted black curve corresponds to the com-

plementary of this value. As expected, these two candidates are such that the

highest peaks of the di¬erential vectors ”ai ·k are either all positive or all neg-

ative, hence leading to the highest amplitudes for 3 ”ai ·k . As explained in

i=0

Section 4.3, we then computed the di¬erential ”a·k for a = a0 • a1 = 3. Fig-

ure 1.c illustrates this computation. The polarity of the highest peak of ”3·k

being negative, one deduces that the correct subkey value k corresponds to the

full black curve in Figure 1.a.

Figures 1.b and 1.d represent respectively the convergence of the peak of

maximal amplitude for 3 ”ai ·k and for ”3·k according to the number of

i=0

power consumption measurements. By analyzing these curves, we deduce that

the value of the 4-bit subkey k is recovered by using about 8 000 executions of

the algorithm.

Regarding the non-linear case, we attacked the AES S-box calculation using

the composite ¬eld method in order to perform the inversion in F4 instead of F8

2 2

and the method of [11] to protect this inversion (see [11, § 4.1] for more details).

In that case, the targeted bit is of the form a · φ(X • k ) • R where X, k ∈ F8 , 2

a ∈ F2 and φ : F2 ’ F2 . Figure 2.a represents the value of the di¬erentials ”k ™s

4 8 4

for k ∈ F8 and a = 1, when 200 000 executions of the algorithm are used. It can

2

be seen that the correct subkey k (plotted in black) is easily distinguishable.

Attack and Improvement of a Secure S-Box Calculation 9

10

1.5

8

1 6

”ai ·k )

4

0.5

2

”ai ·k

0

i

0

-2

Max(

i

-0.5 -4

-6

-1

-8

-10

-1.5

60 100 120 140

20 40 80 160

0 180 200

200 500

100 800

600 700

300 400

0

Number of plaintexts (x100)

Time

(a) Value of the di¬erentials ”ai ·k . (b) Convergence of ”ai ·k .

i i

6

0.2

5

0.1

4

0

3

Max(”3·k )

-0.1 2

”3·k

1

-0.2

0

-0.3

-1

-0.4

-2

-0.5 -3

-4

-0.6

60 100 120 140

20 40 80 160

0 180 200

200 500

100 800

600 700

300 400

0

Number of plaintexts (x100)

Time

(c) Value of the di¬erential ”3·k . (d) Convergence of ”3·k .

Fig. 1. Practical DPA attack “ the linear case

Figure 2.b represents the convergence of the maximum peak amplitude for

the di¬erentials according to the number of power consumption measurements.

The analysis of these curves shows us that the value of the 8-bit subkey k is

recovered after about 100 000 executions of the algorithm.

6 An Improved Version of a Secure S-Box Calculation

In the following we propose an improvement of Algorithm 1 that allowsto circumvent

the ¬‚aw depicted in Section 4.1 and also leads to a more e¬cient implementation.

The new algorithm is still a secure calculation of a Fourier Transform but it is

based on a slightly modi¬ed version of (3) which we rewrite in the following form:

(’1)R2 F (Z) + R3 mod 2n

⎢⎛ ⎞⎥

⎢ ⎥

⎢1 ⎥

= ⎣ n ⎝R + mod 22n ⎠¦ , (13)

F (a)(’1)R2 •a·Z•a·R1

2

a∈Fn

2

where Z = Z • R1 , R2 ∈ F2 , (R1 , R3 , R4 ) ∈ (Fn )3 and R = 2n R3 + R4 .

2

10 J.-S. Coron et al.

2

0.3

1.8

0.2

1.6

0.1 1.4

Max(|”1·k |)

1.2

0

”1·k

1

-0.1 0.8

0.6

-0.2

0.4

-0.3

0.2

0

-0.4

60 100 120 140

20 40 80 160

0 180 200

200 500

100 800

600 700

300 400

0

Number of plaintexts (x1000)

Time

(b) Convergence of |”1·k |.

(a) Value of the vectors ”1·k .

Fig. 2. Practical DPA attack “ the non-linear case

After a brief look at (13) (and before the deeper analysis conducted later on

in this section), we can notice that the sensitive variable a · Z is now masked

with the uniformly distributed random bit R2 . Furthermore, it may be noticed

that the exponent in the summation in (13) involves less operations than in (3).

Let us denote by SP the function X, Y ’ X·Y and by SFT the function X, T ’

F (X)(’1)T . As we prove in this section, Algorithm 2 implements (13) securely.

Algorithm 2. First order Secure S-box calculation

Inputs: A masked value Z = Z • R1 and the mask R1

˜

Output: The 3-tuple ((’1)R2 F (Z) + R3 mod 2n , R3 , R2 ), where R2 and R3 are random

values.

1. Generate a random bit R2

2. Generate two n-bit random R3 and R4

3. result ← 2n R3 + R4

4. for a from 0 to 2n ’ 1 do

T1 ← SP(a, Z) [T1 = a · Z]

5.

T1 ← T1 • R2 [T1 = R2 • a · Z]

6.

T2 ← SP(a, R1 ) [T2 = a · R1 ]

7.

T ← T •T [T = R • a · Z]

8.

[T1 = F (a)(’1)R2 •a·Z ]

T1 ← SFT(a, T1 )

9.

R2 •i·Z

result ← result T1 [result = (2n R3 + R4 )

10. i∈{0,a} F (i)(’1) ]

11. end

12. result ← result [result = (’1)R2 F (Z) + R3 mod 2n ]

n

13. return (result, R3 , R2 )

E¬ciency Analysis. Although Algorithm 2 is more secure than Algorithm 1,

it is also faster. For each loop, Algorithm 2 requires two XORs, two calls to the

function SP and one call to the lookup table SFT. Therefore, for each loop Algo-

rithm 1 performs 2 extra multiplications compared to Algorithm 2. Combining

Attack and Improvement of a Secure S-Box Calculation 11

this result with the fact that function SP is slightly faster than function SSP,

we deduce that our method is faster than the one proposed in [11].

Security Analysis. In Table 1, we list the intermediate variables of Algorithm 1

that involve a sensitive variable. The values which only depend on the loop

counter or on a random value are obviously omitted.

Table 1. The di¬erent sensitive values manipulated during Algorithm 2

Step Instruction Masked Value M ask(s)

5.1 register ← Z Z R1

← SP(a, Z) a·Z a · R1

5.2 T1

← T1 • R2 R2 • a · Z R2 • a · R1

6 T1

← T1 • T2 R2 • a · Z

8 T1 R2

F (a)(’1)R2 •a·Z

← SFT(a, T1 )

9 T1 R2

F (i)(’1)R2 •i·Z (R2 , R3 , R4 )

result ← result T1 (2n R3 + R4 )

10 i

result ← result (’1)R2 F (Z) + R3 mod 2n

11 n R3

As it can be checked in Table 1, the intermediate variables manipulated at

Steps 5.1, 6, 8, 9, 10 and 11 are additively masked with a uniformly distributed

random variable (resp. R1 , R2 • a · R1 , R2 , R2 , R3 ||R4 and R3 ) which is in-

dependent of the sensitive variable. Those intermediate variables are therefore

independent of the sensitive variable Z.

The intermediate variable at Step 5.2 can be rewritten a · Z • a · R1 . When a

equals 0, this variable equals 0 whatever Z and R1 . Otherwise, for every a = 0

the variable a · R1 is uniformly distributed and independent of Z. We deduce

that a · Z • a · R1 (and hence a · Z) is independent of Z whatever a.

Therefore, we have proved that all the intermediate variables manipulated

during the execution of Algorithm 1 are independent of Z, which implies that

our method is secure against ¬rst order DPA.

7 Conclusion

In this paper, we have shown that a provably secure DPA countermeasure pub-

lished at CHES 2006 has a ¬‚aw. We have explained how this ¬‚aw can be exploited

to mount an e¬cient attack on S-box implementations protected by this coun-

termeasure. Our attack is not only theoretical since we have successfully put it

into practice on two di¬erent S-box implementations: the AES S-box using the

composite ¬eld method and the FOX S-box.

Finally, we have proposed an improvement of the CHES 2006 countermeasure

for which we prove the resistance against ¬rst order DPA. Moreover we showed

that our improvement is not only more secure but can also be implemented more

e¬ciently than the original countermeasure.

12 J.-S. Coron et al.

References

1. Akkar, M.-L., Giraud, C.: An Implementation of DES and AES, Secure against

Some Attacks. In: Ko¸, C.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS,

c¸

vol. 2162, pp. 309“318. Springer, Heidelberg (2001)

2. Bl¨mer, J., Guajardo, J., Krummel, V.: Provably Secure Masking of AES. In: Hand-

o

schuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 69“83. Springer,

Heidelberg (2004)

3. Clavier, C., Coron, J.-S., Dabbous, N.: Di¬erential power analysis in the presence

of hardware countermeasures. In: Paar, C., Ko¸, C.K. (eds.) CHES 2000. LNCS,

c¸

vol. 1965, pp. 252“263. Springer, Heidelberg (2000)

4. Coron, J.-S., Prou¬, E., Rivain, M.: Side Channel Cryptanalysis of a Higher Or-

der Masking Scheme. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS,

vol. 4727, pp. 28“44. Springer, Heidelberg (2007)

5. Goubin, L.: A Sound Method for Switching between Boolean and Arithmetic Mask-

ing. In: Ko¸, C.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp.

c¸

3“15. Springer, Heidelberg (2001)

6. Goubin, L., Patarin, J.: DES and Di¬erential Power Analysis “ The Duplication

Method. In: Ko¸, C.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 158“172.

c¸

Springer, Heidelberg (1999)

7. Gueron, S., Parzanchevsky, O., Zuk, O.: Masked Inversion in GF(2n ) Using Mixed

Field Representations and its E¬cient Implementation for AES. In: Nedjah, N.,

Mourelle, L.M. (eds.) Embedded Cryptographic Hardware: Methodologies and Ar-

chitectures, pp. 213“228. Nova Science Publishers (2004)

8. Kocher, P.: Timing Attacks on Implementations of Di¬e-Hellman, RSA, DSS, and

Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104“113.

Springer, Heidelberg (1996)

9. Kocher, P., Ja¬e, J., Jun, B.: Di¬erential Power Analysis. In: Wiener, M.J. (ed.)

CRYPTO 1999. LNCS, vol. 1666, pp. 388“397. Springer, Heidelberg (1999)

10. Oswald, E., Mangard, S., Pramstaller, N., Rijmen, V.: A Side-Channel Analysis

Resistant Description of the AES S-box. In: Gilbert, H., Handschuh, H. (eds.) FSE

2005. LNCS, vol. 3557, pp. 413“423. Springer, Heidelberg (2005)

11. Prou¬, E., Giraud, C., Aumonier, S.: Provably Secure S-Box Implementation Based

on Fourier Transform. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS,

vol. 4249. Springer, Heidelberg (2006)

12. Rivain, M., Dottax, E., Prou¬, E.: Block Ciphers Implementations Provably Secure

Against Second Order Side Channel Analysis. Cryptology ePrint Archive, Report

2008/021 (2008), http://eprint.iacr.org/

A Distribution of the Di¬erentials

In this section, we investigate the distribution of the di¬erential ”k when the

attack targets a masked bit b = f (X, k ) • R where R is a random bit satisfying

P [R = 0] = 1 + µ. Our analysis includes the unmasked case by setting µ to 1 .

2 2

We make the usual assumption that the leakage has a Gaussian distribution:

δ

L(b) ∼ N μ ’ (’1)b , σ 2 , (14)

2

Attack and Improvement of a Secure S-Box Calculation 13

where μ, δ and σ are constants and δ equals E[L(1)] ’ E[L(0)].

The leakage measurement li obtained for the ith encryption can thus be ex-

pressed as:

δ

li = μ ’ (’1)bi +ri + ·i , (15)

2

where, for the ith encryption, bi is the unmasked value of b (i.e. bi = f (xi , k )),

ri is the mask value and ·i is the noise in the leakage measurement.

We make the additional assumption that for every key hypothesis k, the se-

quence of guesses satis¬es: #{i; bi = 0} = #{i; bi = 1} = N/2. This assumption

is realistic since the functions f (·, k) are usually balanced (i.e. #{x; f (x, k) =

1} = #{x; f (x, k) = 0}) and since the xi ™s are usually uniformly distributed. It

allows us to rewrite (6) as:

N

2

”k = ’ (’1)bi li . (16)

N i=1

This relation together with (15) leads to:

N N

δ 2

’

bi +bi +ri

(’1)bi ·i

”k = (’1)

N N

i=1 i=1

⎛ ⎞

N N N

δ⎜ ri ⎟

2

(’1) ’ (’1) ⎠ ’

ri

(’1)bi ·i

⎝

=

N N i=1

i=1 i=1

bi =b bi =b

i i

Recalling that ± is the ratio of the bi ™s that are wrongly predicted (i.e. ± =

#{i; bi = bi }/N ) and after rewriting (’1)ri as 1 ’ 2ri , we get:

⎛ ⎞

N N N

2δ ⎜ ⎟ 2

”k = δ(1 ’ 2±) + ri ’ ri ⎠ ’ (’1)bi ·i .

⎝

N N i=1

i=1 i=1

bi =b bi =b

i i

Since ri is distributed over F2 with P [ri = 1] = 1/2 ’ µ then for every I ⊆

{1, · · · , N }, the sum i∈I ri has a binomial distribution with parameter (#I,

1/2 ’ µ). Moreover, since ·i has a Gaussian distribution N (0, σ 2 ), then the sum

N

i=1 (’1) ·i has a Gaussian distribution N (0, N σ ). This way, we obtain:

bi 2

4σ 2 2δ 1 2δ 1

”k ∼ N δ(1 ’ 2±), B ±N, ’ µ ’ B (1 ’ ±)N, ’ µ

+ .

N N 2 N 2

After approximating B(n, p) by N (np, np(1 ’ p)) (which is almost exact when

n ≥ 30, np > 5 and n(1 ’ p) > 5), we ¬nally get:

4σ 2 + δ 2 (1 ’ 4µ2 )

”k ∼ N 2µ — δ(1 ’ 2±), .

N

14 J.-S. Coron et al.

This relation shows that the biased masking results in a reduction of the

expectation of ”k and in an increase of its variance. The expectation is divided

by a factor 1/2µ while its variance is multiplied by a factor 1 + δ 2 (1 ’ 4µ2 )/σ 2 .

When the leakage signal-to-noise ratio is low, i.e. σ δ, then the biais has a weak

in¬‚uence on the variance and its main e¬ect is the reduction of the expectation.

According to [3] this results in an increase of the number of required leakage

measurements by a factor (1/2µ)2 . If the leakage signal-to-noise ratio is not that

low, the increase of the variance is signi¬cant and the number of required leakage

measurements is multiplied by (1/2µ)2 1 + δ 2 (1 ’ 4µ2 )/σ 2 .