The randomised table S (x) requires 256 bytes in RAM.

3.4 ShiftRows

No modi¬cation is required.

3.5 MixColumns

Using 03 · x = (02 · x) • x, the MixColumns operation can be written as follows

(¬rst line):

s0,c ← (02 · s0,c ) • (02 · s1,c ) • s1,c • s2,c • s3,c

Therefore, we must be able to compute P (02·x) from P (x). For any x = xh xl ∈

{0, 1}8, from x = (0 xl ) • (xh 0) we have:

02 · x = (02 · (0 xl )) • (02 · (xh 0))

and using equation (1), we obtain:

P (02 · x) = XT8 P (02 · (0 xl )), P (02 · (xh 0) (2)

Therefore, for all x ∈ {0, 1}8 where x = xh xl , we de¬ne the following two

tables (4-bit to 8-bit):

p’1 (xl )

ML(xl ) := P 02 · 0 1

MH(xh ) := P 02 · p’1 (xh ) 0

2

A New DPA Countermeasure Based on Permutation Tables 283

which gives for any xl , xh ∈ {0, 1}4 :

ML(p1 (xl )) = P 02 · ( 0 xl )

(3)

MH(p2 (xh )) = P 02 · ( xh 0)

Using equations (2) and (3), given P (x) = p2 (xh ) p1 (xl ), we can therefore

compute P (02 · x) as follows:

P (02 · x) = XT8 (ML(p1 (xl )), MH(p2 (xh )))

For simplicity, given P (x) = xh xl , we denote:

D2 (xh xl ) = XT8 ML(xl ), MH(xh )

so that for any x ∈ {0, 1}8 :

P (02 · x) = D2 (P (x)) (4)

The ¬rst line of the MixColumns operation with permuted data can therefore be

written as:

s0,c ← XT8 D2 (s0,c ), XT8 D2 (s1,c ), XT8 s1,c , XT8 (s2,c , s3,c )

and the other three lines are implemented analogously. The storage of the two

ML and MH tables requires 32 bits of RAM.

3.6 InvShiftRows

The algorithm remains the same.

3.7 InvSubBytes

This is similar to the SubBytes algorithm: we de¬ne the following randomised

permutation S ’1 :

S ’1 (x) = P (S ’1 (P ’1 (x)))

Therefore, the InvSubBytes operation on the permuted state variables is com-

puted using table S ’1 (x) as follows:

si,j ← S ’1 (si,j )

Note that one can generate the randomised table S ’1 (x) from S(x) only, so

that it is not necessary to store S ’1 (x) in ROM, using the fact that:

S ’1 = P —¦ S ’1 —¦ P ’1 = (P —¦ S —¦ P ’1 )’1 .

284 J.-S. Coron

3.8 InvMixColumns

The ¬rst line of the InvMixColumns operation is as follows:

s0,c ← (0e · s0,c ) • (0b · s1,c ) • (0d · s2,c ) • (09 · s3,c )

We have the following relations in GF(28 ):

0b = 09 • 02, 0d = 0c • 01, 0e = 0c • 02 (5)

Therefore only two tables for computing the multiplication by 09 and 0c are

required, from which multiplication by 0b, 0d and 0e can be computed without

additional tables. More precisely, for all x ∈ {0, 1}4, we build the following 4-bit

to 8-bit tables:

p’1 (xl )

TL(xl ) := P 09 · 0 1

TH(xh ) := P 09 · p’1 (xh ) 0

2

p’1 (xl )

RL(xl ) := P 0c · 0 1

RH(xh ) := P 0c · p’1 (xh ) 0

2

Storing those four tables requires 64 bytes in RAM. Then, as in section 3.5,

writing x = P (x) = xh xl = p2 (xh ) p1 (xl ), we obtain:

P (09 · x) = XT8 TH(xh ), TL(xl )

P (0c · x) = XT8 RH(xh ), RL(xl )

As previously we denote:

D9 (xh xl ) = XT8 TH(xh ), TL(xl )

Dc (xh xl ) = XT8 RH(xh ), RL(xl )

Using equations (5), we also denote:

Db (x) = XT8 (D9 (x), D2 (x))

Dd (x) = XT8 (Dc (x), x)

De (x) = XT8 (Dc (x), D2 (x))

The ¬rst line of the InvMixColumns operation can then be rewritten as follows:

s0,c ← XT8 De (s0,c ), XT8 Db (s1,c ), XT8 Dd (s2,c ), D9 (s3,c )

and the other three lines are rewritten analogously.

3.9 SubWord

The SubWord operation on the modi¬ed state variables is implemented like the

SubByte operation.

A New DPA Countermeasure Based on Permutation Tables 285

3.10 RotWord

The RotWord operation remains unmodi¬ed.

3.11 Xor with Rcon

Let

R(i) = 02i’1

for all 1 ¤ i ¤ 10. We have R(0) = 01 and R(i) = 02 · R(i ’ 1) for all 1 ¤ i ¤ 10.

Therefore, letting R (i) := P (R(i)), we have:

R (i) = P (R(i)) = P (02 · R(i ’ 1)) = D2 (R(i ’ 1))

Therefore the Rcon constant can be computed using the function D2 (x) de¬ned

in section 3.5.

4 Security