4 1 1

We also de¬ne the 4-bit to 4-bit permutations:

p12 (x) = p1 (p’1 (x)) (10)

2

p21 (x) = p2 (p’1 (x)) (11)

1

and we store those two permutation tables in RAM. Then we can de¬ne the

function:

XT2 (x , y ) := p21 (XT1 (p12 (x ), p12 (y )))

4 4

From equations (10) and (11) we obtain that for all xh , yh ∈ {0, 1}4:

XT2 (p2 (xh ), p2 (yh )) = p21 (XT1 (p1 (xh ), p1 (yh )) = p21 (p1 (xh • yh )) = p2 (xh • yh )

4 4

Therefore, the XT2 function takes the same values as the XT2 table de¬ned in

4 4

Section 3.2. The advantage is that only 16 bytes of RAM are necessary to store

the permutation tables p12 and p21 instead of 128 bytes for the previous XT2 4

table.

A New DPA Countermeasure Based on Permutation Tables 289

Double and Add for InvMixColumns

6.3

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

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

In this section we show how to avoid the four tables TL, TH, RL and RH, using

a Double and Add method. More precisely, using the existing D2 function (see

equation (4)) we de¬ne the following functions:

D4 (x ) := D2 (D2 (x ))

D8 (x ) := D2 (D4 (x ))

D9 (x ) := XT8 (D8 (x ), x )

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

Dc (x ) := XT8 (D8 (x ), D4 (x ))

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

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

Therefore no additional table is required beyond the already de¬ned ML and

MH tables. 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.

6.4 Security

As for our basic permutation table countermeasure, all the intermediate variables

that appear in the time-memory tradeo¬ variants have the uniform distribution:

Lemma 2. For a ¬xed key and input message, every intermediate byte that is

computed in the course of the randomised AES algorithm with any of the three

time-memory trade-o¬s has the uniform distribution in {0, 1}8.

Therefore, the three previous time-memory tradeo¬s are secure against ¬rst-

order DPA.

7 Implementation

We summarise in Table 1 the timings observed and RAM needed for each AES

operation. The timings are based on an implementation in C on a 2 GHz lap-

top under Linux. The RAM requirements are based on Tables 2 and 3 in Ap-

pendix. These timings show that the new countermeasure is reasonably e¬cient,

as it is only roughly four times slower than AES with masking countermeasure,

for a comparable amount of memory. We note that the time-memory tradeo¬s

enable to spare 272 bytes in RAM compared to our basic permutation table

countermeasure.

290 J.-S. Coron

Table 1. Timings obtained using a C implementation of AES without countermeasure,

with masking countermeasure, and with proposed countermeasure: basic permutation

table, and with time-memory trade-o¬s, on a 2 GHz laptop under Linux

Countermeasure Timing (µs) RAM (bytes)

AES encryption without countermeasure 2.2 214

AES encryption with masking 4.0 474

AES encryption with basic permutation tables 11 778

AES encryption with permutation tables + trade-o¬s 27 570

AES decryption without countermeasure 4.0 214

AES decryption with masking 9.5 474

AES decryption with basic permutation tables 23 842

AES decryption with permutation tables + trade-o¬s 42 570

8 Conclusion

We have described a new countermeasure against DPA for AES, that does not

use random masking. Our countermeasure is provably secure against ¬rst order

DPA, and reasonably e¬cient compared to the classical random masking coun-

termeasure. We have also described three time-memory tradeo¬s to reduce the

RAM requirement; this can be useful for smart-card implementations.

Acknowledgments. Thanks to Christophe Clavier for suggesting the “Double

and Add” approach in Section 6.3.

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. Springer, Heidelberg (2001)

2. Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards Sound Approaches to

Counteract Power-Analysis Attacks. In: Wiener, M. (ed.) CRYPTO 1999. LNCS,

vol. 1666. Springer, Heidelberg (1999)

3. Coron, J.S.: Resistance against Di¬erential Power Analysis for Elliptic Curve Cryp-

tosystems. In: Ko¸, C.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292“302.

c¸

Springer, Heidelberg (1999)

4. Daemen, J., Rijmen, V.: The Design of Rijndael: AES - The Advanced Encryption

Standard. Springer, Heidelberg (2002)

5. Golic, J.D., Tymen, C.: Multiplicative Masking and Power Analysis of AES. In:

Kaliski Jr., B.S., Ko¸, C.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523. Springer,

c¸

Heidelberg (2003)

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

CRYPTO 1999. LNCS, vol. 1666. Springer, Heidelberg (1999)

7. Kocher, P., et al.: DES and Other Cryptographic processes with Leak Minimiza-

tion for smartcards and other cryptosystems. US 6,278,783 B1, June 3 (1999),

http://www.cryptography.com/technology/dpa/licensing.html

8. IBM Corporation, Space-e¬cient, side-channel attack resistant table lookups. Ap-

plication Patent 20030044003

A New DPA Countermeasure Based on Permutation Tables 291

9. 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)

10. Oswald, E., Schramm, K.: An E¬cient Masking Scheme for AES Software Im-

plementations. In: Song, J.-S., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS,

vol. 3786, pp. 292“305. Springer, Heidelberg (2006)

11. Rao, J.R., Rohatgi, P., Scherzer, H., Tinguely, S.: Partitioning attacks: Or How to

rapidly Clone Some GSM Cards. In: Proceedings of the 2002 IEEE Symposium on

Security and Privacy (2002)

12. Wolkerstorfer, J., Oswald, E., Lamberger, M.: An ASIC implementation of the AES

SBoxes. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol. 2271. Springer, Heidelberg

(2002)

A AES Pseudo-code

Cipher(byte in[16], byte out[16], word w[44])

begin

byte state[16]

state=in

AddRoundKey(state,w[0,3])

for round=1 to 9

SubBytes(state)

ShiftRows(state)

MixColumns(state)

AddRoundKey(state,w[round*4,(round+1)*4-1])

end for

SubBytes(state)

ShiftRows(state)

AddRoundKey(state,w[40,43])