Attack and Improvement of a Secure S-Box
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,

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,

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.

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.

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 .