Then we factorize

10 349065487636300 + 795285597612250i 0

M± := = .

349065487636300 ’ 795285597612250i

0± 0

We choose k = 48, resulting in » = 222458048101540 and

m = 11210387681441600668869823936886993015607319565640625. After 234

random trials for x, we ¬nally get x = 523712450310834, w = 207632734870715,

and n = 4.2489205976128525372183128649803320961. The Euclidean algorithm

gives us the solution y = 2782001231666122912, z = 1489057773063985790. So

the lift of M± is

⎛ ⎞

311426103887630914544037511835 3132254927569356406015273012423328

⎜ +i766565480745454184887163124346 +i1676530007976242663293697980252510 ⎟

M± = ⎜ ⎟.

⎝ ’3132254927569356406015273012423328 ⎠

311426103887630914544037511835

+i1676530007976242663293697980252510 ’i766565480745454184887163124346

We multiply M± by each of the lifts of the graph generators. Since M± g3 is

divisible by l = 5, g’3 is the last (right-hand) factor of M± . After 2k steps, we

get the whole factorization of M± , which we translate into a factorization of M±

whose indices are 3 -1 2 2 3 1 1 3 1 3 3 3 2 2 3 -1 2 1 1 -3 1 1 1 3 -1 2 -3 2 3 1

-2 -2 -2 1 2 1 1 -3 2 1 2 1 -2 3 -1 3 2 -3 -2 3 1 -2 3 3 2 -3 -1 2 2 2 -1 -3 -1 -3 2 3

1 2 -3 -1 3 2 2 1 3 -2 -3 1 3 -2 -1 -2 3 1 3 2 1 -2 -1 -1 -3 2 1 1 -2 -3. We get the

factorizations of Mω , Mβ1 and Mβ2 the same way. Finally, we put all the pieces

of information together and get the sequence -3 -2 1 1 2 -3 -1 -1 -2 1 2 3 1 3 -2

-1 -2 3 1 -3 -2 3 1 2 2 3 -1 -3 2 1 3 2 - 3 -1 -3 -1 2 2 2 -1 -3 2 3 3 -2 1 3 -2 -3 2 3

-1 3 -2 1 2 1 2 -3 1 1 2 1 -2 -2 - 2 1 3 2 -3 2 -1 3 1 1 1 -3 1 1 2 -1 3 2 2 3 3 3 1 3

1 1 3 2 2 -1 3 2 3 -1 -3 -2 -2 1 3 2 -3 -3 2 3 -2 -3 -3 -2 -1 -2 3 1 1 2 3 2 1 1 -3 1 2

2 1 -2 1 1 2 -3 -2 3 -2 -3 1 1 3 1 2 1 -3 -1 -3 -3 -1 2 3 1 -3 -3 -1 -1 2 -1 3 -2 1 -3

-3 -1 -2 1 1 -2 -1 -1 3 -2 3 2 2 1 -3 -2 -1 -3 -1 -3 -1 3 2 -1 3 3 -2 -1 -2 1 1 2 2 -3

-1 3 2 2 -3 -2 -3 -1 -3 1 -3 -2 -1 3 1 -2 3 -2 3 2 1 3 -2 -2 -3 -3 -2 -2 3 -2 -2 -3 -1 3

1 3 -1 -3 -3 -3 -3 -2 1 3 3 1 -2 3 -1 -2 1 2 -3 1 -2 -2 1 -2 -2 -1 2 2 2 2 2 1 -3 1 1 2

1 1 3 3 -1 3 3 -2 -1 3 1 2 -1 2 3 -1 2 -3 -2 1 -2 1 1 3 -2 2 -2 -3 -2 -1 3 3 -2 -1 3

2 -3 2 3 -2 1 1 1 1 -2 1 1 2 -1 3 -1 -2 -1 -2 -1 -2 -2 3 2 1 3 - 2 -2 -3 -3 -2 3 3 2 1

1 1 1 3 2 -1 -3 2 -3 -2 -1 -3 1 -2 -2 -2 1 -2 -1 -2 -1 2 - 1 -3 -1 -3 -2 -1 -2 -3 -1 -3

-1 2 2 3 3 -2 -2 -2 -3 -1 -1 -1 2 -3 -1 3 -1 2 -3 - 3 that collides with the original

message “This is not for NIST”.

Collisions for Morgenstern Hashes, q = 2 and

B

deg p(x) = 20

Now we give a small example for our collision-¬nding algorithm. The polynomial

we choose to target is p(x) = x20 +x17 +x14 +x13 +x12 +x11 +x9 +x7 +x5 +x3 +

x2 + x + 1. We choose R = 10 and generate random m and b . After 3 random

trials we get m = x9 +x8 +x7 +x6 +x5 +x4 , b = x10 +x8 +x5 +x2 +1 so k = 52,

a = x52 + x48 + x36 + x32 + x30 + x25 + x24 + x22 + x20 + x15 + x14 + x12 + x11 +

x10 + x9 + x4 + x3 + x + 1, b = x51 + x50 + x48 + x47 + x46 + x45 + x44 + x40 + x39 +

x38 + x37 + x36 + x35 + x34 + x32 + x31 + x30 + x29 + x28 + x27 + x25 + x24 + x23 +

Full Cryptanalysis of LPS and Morgenstern Hash Functions 277

x22 + x20 + x19 + x18 + x16 + x11 + x10 + x9 + x8 + x5 + x4 + x3 + x2 + x and n =

x62 +x61 +x59 +x57 +x55 +x53 +x52 +x51 +x50 +x49 +x48 +x46 +x45 +x40 +x37 +

x31 +x29 +x28 +x26 +x25 +x24 +x23 +x16 +x15 +x13 +x12 +x10 +x6 +x5 +x3 +1.

The polynomial n has three factors n1 = x56 +x54 +x53 +x50 +x48 +x46 +x44 +

x40 +x36 +x34 +x33 +x30 +x29 +x22 +x20 +x18 +x13 +x11 +x7 +x6 +x5 +x3 +1,

n2 = x4 +x3 +x2 +x+1 and n3 = x2 +x+1 which are all of even degrees. For each

factor ni we compute ± such that ±2 +±+1 ≡ 0 mod ni and use this value and the

continued fraction algorithm to recover (ci , di ) such that c2 +d2 +ci di ≡ 0 mod ni :

i i

we get (c1 , d1 ) = (x + x + x + x + x + x + x + x + x13 + x11 + x8 +

26 25 24 21 20 18 16 14

x6 + x5 + x + 1, x28 + x23 + x21 + x19 + x15 + x13 + x10 + x7 + x5 + x4 + x2 + x + 1),

(c2 , d2 ) = (x, x2 + 1) and (c3 , d3 ) = (x, 1).

Combining these partial results we get c = x51 + x50 + x47 + x41 + x40 + x36 +

x31 + x27 + x26 + x25 + x24 + x23 + x22 + x20 + x18 + x17 + x16 + x14 + x12 +

x11 + x10 + x9 + x7 + x4 and d = x51 + x50 + x49 + x48 + x47 + x45 + x44 + x43 +

x42 + x39 + x36 + x33 + x31 + x30 + x29 + x27 + x26 + x25 + x22 + x21 + x20 +

x18 + x17 + x16 + x14 + x13 + x9 + x7 + 1.

We can verify that

(a2 + b2 + ab) + (c2 + d2 + cd)x = (1 + x)2k

and (a, b, c, d) ≡ (1 + x)k (1, 0, 0, 0) mod p. We factorize the lifted matrix and,

using the indices of the generators given in Section 5, we get the following colli-

sion with the void message: 0 2 0 2 0 1 2 1 2 1 2 1 2 0 2 0 2 0 2 0 2 0 1 0 2 0 2

1021010210121212102101201010102101202120201

2 0 2 0 1 0 2 1 2 1 0 2 0 1 0 1 2 0 2 0 2 0 2 0 1 2 1 0 2 0 2 1 0 1.

A New DPA Countermeasure Based on

Permutation Tables

Jean-S´bastien Coron

e

University of Luxembourg

jean-sebastien.coron@uni.lu

Abstract. We propose and analyse a new countermeasure against Dif-

ferential Power Analysis (DPA) for the AES encryption algorithm, based

on permutation tables. As opposed to existing AES countermeasures, it

does not use random masking. We prove that our new countermeasure is

resistant against ¬rst-order DPA; we also show that it is quite e¬cient

in practice.

1 Introduction

The AES [4] encryption algorithm is with DES the most widely used encryption

algorithm. However, it is easy to see that without modi¬cation, AES is vulnerable

to Di¬erential Power Analysis as introduced by Kocher et al. in [6,7]. A DPA

attack consists in extracting information about the secret key of a cryptographic

algorithm, by studying the power consumption of the electronic device during the

execution of the algorithm. The attack was ¬rst described on the DES encryption

scheme, but it was soon understood that the attack could easily be extended

to other symmetrical cryptosystems such as the AES, and also to public-key

cryptosystems such as RSA and Elliptic-Curves Cryptosystems [3].

A common technique to protect secret-key algorithms against side-channel

attacks consists in masking all data with a random integer, as suggested in

[2]. The masked data and the random integer are then processed separately and

eventually recombined at the end of the algorithm. An attacker trying to analyse

power consumption at a single point will obtain only random values; therefore,

the implementation will be secure against ¬rst-order Di¬erential Power Analysis

(DPA). In order to obtain valuable information about the key, the attacker must

correlate the power consumption at multiple points during the execution of the

algorithm; this is called a High Order Di¬erential Power Analysis (HO-DPA);

such attack usually requires a much larger number of power consumption curves,

which makes it infeasible in practice if the number of executions is limited (for

example, by using a counter). Many AES countermeasures have been described

based on random masking [1,5,9,10,12].

In this article we propose a di¬erent countermeasure against DPA for AES,

based on permutation tables. The main di¬erence with existing AES counter-

measures is that it avoids random masking; in practice this can be an advantage

because random masking is subject to numerous patents [7]. We prove that our

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 278“292, 2008.

c Springer-Verlag Berlin Heidelberg 2008

A New DPA Countermeasure Based on Permutation Tables 279

countermeasure is resistant against ¬rst-order DPA (like the random masking

countermeasure) and we show that its e¬ciency is comparable to that of the

random masking countermeasure.

It works as follows: at initialisation time a randomised permutation table is

generated in RAM; this permutation table is then applied to the message and

to the key; then all intermediate variables that appear during the course of

the algorithm remain in permuted form; eventually the inverse permutation is

applied to obtain the resulting ciphertext.

We also describe a technique to reduce the RAM consumption of our per-

mutation table countermeasure, at the cost of increasing the running time. Our

technique is based on a compression scheme proposed in [11] for the classical

random masking countermeasure; here we adapt this scheme to permutation ta-

bles. We show that this variant is also secure against ¬rst-order DPA. Finally, we

also provide the result of implementations that show that our countermeasure

is reasonably e¬cient in practice, as it is only roughly four times slower than