ńņš. 2 |

bytes. More formally, the partial function sc [y] is entirely determined by a re-

duced number of unknown bytes. We can exploit this restricted dependency by

constructing collisions on all the y values for distinct values of the c triplet. In

other words :

Property 1. There exists c and c two triplets of constants such as for all y

values between 0 and 255, we have : sc [y] = sc [y]. In this case, we say that we

have a collision.

20 M. Minier

In fact, the number of obtained collisions is 256, one for each y value.

Under the heuristic assumption that the unknown constants depending on

the key and on the c triplet behave as random functions, then, by the birthday

paradox, if we take a C set of 216 c triplets, the probability to obtain a collision

is non negligible.

This property can be extended to mount an eļ¬cient four-rounds distinguisher

by adding a fourth round at the bottom of the three previous rounds.

3.2 The Four-Rounds Distinguisher

We consider the deciphering of the fourth round in the following way (see

ļ¬gure 2) :

s

Sh

ift

S Ro

ws ā’

Su 1

bB

yte

Ļ„+Ī“

s ā’1

ā’1

ey

ndK 1

u

dRo ā’

t0 d ns

A um

Col

t1

T

Mix

t2

t3

Fig. 2. The Extension to a Fourth Round

We denote by T the output block after the fourth round and we denote by

(t0 , t1 , t2 , t3 ) the last column of T marked on the ļ¬gure 2. We can express the

byte s as s = S ā’1 [(0E Ā· t0 + 0B Ā· t1 + 0D Ā· t2 + 09 Ā· t3 ) + Ī“] where S represents

the AES S-box and Ī“ a constant depending on the subkey of the fourth round.

We have the following property :

Property 2. There exists a collision between sc [y] and sc [y] if and only if for

all y values between 0 and 255, we have :

0E Ā· tc + 0B Ā· tc + 0D Ā· tc + 09 Ā· tc = 0E Ā· tc + 0B Ā· tc + 0D Ā· tc + 09 Ā· tc .

0 1 2 3 0 1 2 3

To simplify the notations we denote 0E Ā· tc + 0B Ā· tc + 0D Ā· tc + 09 Ā· tc by Ļ„ c [y].

0 1 2 3

Ļ„ c [y] is a function of y entirely determined by 6 unknown bytes depending on

the key and by 4 additional unknown bytes depending on both the key and the

c values.

The following four inner rounds distinguisher is tested on a limited number

of y values, a set Ī of 16 values is suļ¬cient, the number of false alarms being

negligible in this case.

A Three Rounds Property of the AES 21

ā“ Select a C set of about 216 c triplet values and a subset of {0 Ā· Ā· Ā· 255}, say

for instance a Ī subset of 16 y values.

ā“ For each c triplet value, compute the Lc = (0EĀ·tc +0BĀ·tc +0DĀ·tc +09Ā·tc )yāĪ .

0 1 2 3

ā“ Check wether two of the above lists, Lc and Lc are equal.

The computations made at the secund step of this distinguisher (16 linear

combinations of the outputs) represent substantially less than one single AES

execution.

This four-rounds distinguisher requires about 220 chosen inputs Y, and since

the collision detection computations (based on the analysis of the corresponding

T values) require less operations than the 220 4-inner rounds computations, the

complexity of the distinguisher is less than 220 AES encryptions for a probability

of success equal to 1/2 (due to the birthday paradox).

4 The āNew Three-Rounds Propertyā

We describe, in this section, a ānewā three-rounds property derived from the

previous one that permits to obtain an higher number of collisions. For more

clarity, we use the same notation than the previous one. In this ānew propertyā,

the number of initial active bytes in the last Y column has been modiļ¬ed.

Here, we deļ¬ne two active bytes y and c0 instead of one (the y byte) before.

In this case, the c triplet becomes a pair of bytes deļ¬ned by cp = (c1 , c2 ). Let

us explain how those two active bytes cross three inner rounds (see ļ¬gure 3) :

c

ā“ After the ļ¬rst round, the y ā’ z0p [y, c0 ] one to one function is independent

from the value of the cp triplet and is entirely determined by one key byte,

due to the eļ¬ect of the ShiftRows operation. The same property holds for

z1 , z2 and z3 . So, the quartet of bytes (z0 , z1 , z2 , z3 ) is a function of the

y and c0 values entirely determined by four key-dependent bytes.

ā“ After the second round, each of the four bytes ri [y, c0 ], i = 0..3 is a one to

one function of the corresponding zi [y, c0 ] byte entirely determined by one

single unknown byte that is entirely determined by cp and the key. The

quartet of bytes (r0 , r1 , r2 , r3 ) of R marked on ļ¬gure 3 is a function of

(z0 , z1 , z2 , z3 ) entirely determined by four key-dependent and c-dependent

bytes.

ā“ After the third round, the s byte marked on ļ¬gure 3 can be expressed

as a function of the (r0 , r1 , r2 , r3 ) quartet of bytes entirely determined by

one key-dependent byte depending on the subkey of the round.

As in the section 3.1, we can deduce that the s byte at the end of the third

round is a function of y and c0 entirely determined by 5 key-dependent bytes

and 4 key-dependent and cp -dependent bytes. We can also exploit this restricted

dependency between the s byte and the two active bytes y and c0 by deļ¬ning a

new kind of collision :

22 M. Minier

y

Su

c0

Y bB

Sh y

c1

ift tes

Ro

c2 S(y)

ws

first round S(c0)

4 keyā’dependent bytes ns

lum S(c1)

Co

z0 y

Mix oundKe S(c2)

z1 R

Add

Z

z2 Su

b

Sh Byte

z3

ift

Ro s

second round

ws S(z0)

4 key and cā’dep. bytes S(z1)

ns

r0 lum S(z2)

Co y

Mix oundKe

r1 S(s3)

R

R

Add

r2

Su

r3 b

Sh Byte

third round ift

Ro s S(r0)

1 keyā’dep. byte ws S(r1)

s S(r2)

s

mn

olu S(r3)

S C y

Mix oundKe

R

Add

Fig. 3. The Other Three Inner Rounds Property

Property 3. There exists cp and cp two pairs of constants such as for all y and

c0 values between 0 and 255, we have : scp [y, c0 ] = scp [y, c0 ]. In this case, we

say that we have a collision.

The number of obtained collisions is (256)2 , one for each y and c0 value.

This ānewā property is due to the very symmetric and parallel structure of

the AES in the byte position level.

We verify the veracity of this property by computer experiments.

Unfortunately, this property could not be used to mount a more eļ¬cient four-

rounds distinguisher than the one presented in section 3.2. Indeed, the number

of cp pairs used in the distinguisher and the probability of success depend on

only the four intermediate cp -dependent bytes. The number of such bytes is the

same for the property of the section 3.1 and the ānewā one in depict of the bigger

number of obtained collisions.

So, we do not ļ¬nd a more eļ¬cient distinguisher that permits to use this

stronger property and to improve an attack. We use the same distinguisher than

the one described in section 3.2.

A Three Rounds Property of the AES 23

5 The Bottleneck Attack on a Seven-Rounds Version of

the AES with Key Lengths Equal to 192 and 256 Bits

Using 232 Chosen Plaintexts

Even if the new property could not be used to improve the four-rounds

distinguisher described in section 3.2 and so the bottleneck attack, we give a

short description of this known cryptanalysis. So, we are going to recall, in

this section, how the four inner rounds distinguisher of the section 3.2 could

be extended to mount a seven-rounds attack on the AES with a 192 or a 256

bits key.

The seven-rounds version of the AES is depicted in ļ¬gure 4. The seventh

round is here considered as the last round (i.e. it doesnā™t contain the Mix-

Columns operation). X represents a plaintext block and V the corresponding

ciphertext. The four previous rounds are surrounded at the top by one initial

round X ā’ Y, composed by an initial key addition followed by one round

and at the bottom by two ļ¬nal rounds : T ā’ U and U ā’ V.

The attack method is a combination between the four-rounds distinguisher

presented in section 3.2 and an exhaustive search of some keybytes or combi-

nation of keybytes of the initial and the two ļ¬nal rounds. The attack described

here uses the fact that, in the equations provided by the four-rounds distin-

guisher, there is a variables separation in terms which involve one half of

the 2 last rounds key bytes and terms which involve a second half of the 2

last round key bytes in order to save a 280 factor in the exhaustive search

complexity.

5.1 Extension at the Beginning

The distinguisher of section 3.2 could be extended by one round at the beginning

using the same method than the one proposed by the authors of Rijndael in the

initial paper [DR98] and ļ¬rst applied to the algorithm Square.

The main idea used here is that if, in the initial key addition, the 4 key bytes

(denoted by kini = (k0,0 , k0,1 , k0,2 , k0,3 )), added with the four bytes (x0 , x1 , x2 , x3 )

of the plaintext X marked in ļ¬gure 3, are known then it is possible to partition

the 232 plaintexts into 224 subsets of 28 plaintexts values satisfying the condi-

tions of section 3.2 (i.e. (c0 , c1 , c2 ) stay a triplet of constants and y is the active

byte).

So, if all the 232 possible plaintexts are encrypted for all the possible values of

the (x0 , x1 , x2 , x3 ) quartet (the other 12 bytes being taken equal to a constant),

the 232 plaintexts could be partitioned, according to the value of kini , into 224

subsets of 28 plaintexts according the values of y (which are known up to an

unknown constant linked with the ļ¬rst round key byte). Those subsets are such

that the y byte takes all possible values between 0 and 255 and the c = (c0 , c1 , c2 )

triplet is composed of three constant values, diļ¬erent and unique for each of the

224 subsets, the 12 other Y bytes are constant and all those constant values are

the same for all subsets.

Those 232 plaintexts give the corresponding 232 ciphertexts V .

24 M. Minier

x0

x1

X

x2

x3

Distinguisher on 4 rounds

y

c0

Y

c1

c2

...

t0

t1

T

t2

t3

U

V

Fig. 4. Attack on Seven Rounds of the AES

5.2 Extension at the End

Each of the t0 , t1 , t2 , t3 bytes can be expressed as a function of four bytes of the

V ciphertext and ļ¬ve unknown key bytes (i.e. four of the ļ¬nal round subkey and

one linear combination of the penultimate round subkey). So, in order to improve

the key exhaustive search on the two last rounds, the equations of collisions are

ācutedā in two parts as follows :

A Three Rounds Property of the AES 25

Ļ„1 = 0E Ā· tc + 0B Ā· tc and Ļ„2 = 0D Ā· tc + 09 Ā· tc

c c

0 1 2 3

With this notation the equation of collision Ļ„ c = Ļ„ c described in property 2

could be expressed as Ļ„1 + Ļ„2 = Ļ„1 + Ļ„2 , i.e. Ļ„1 + Ļ„1 = Ļ„2 + Ļ„2 . Ļ„1 depends

c c c c c c c c

on t0 and t1 and Ļ„2 depends on t2 and t3 . Now, due to the fact that the last

round of the AES does not contain the MixColumns operation, t0 and t1 could

be expressed, as shown on ļ¬gure 3, as a function of 8 ciphertext bytes and 10 key

bytes of the two last rounds denoted by kĻ„1 . In the same way, t2 and t3 depend

on 8 ciphertext bytes and on 10 key bytes of the two last rounds denoted by kĻ„2 .

This remark permits to share in two parts the key exhaustive search and to

improve the attack on a seven rounds-version of the AES by a factor 280 .

5.3 Outline of the Attack

An eļ¬cient exhaustive search of the kini , kĻ„1 and kĻ„2 keys could be performed

in the following way:

First step :

Cipher the 232 chosen plaintexts for all possible values of the quartet

(x0 , x1 , x2 , x3 ).

Second step :

For kini from (0,0,0,0) to (255,255,255,255) do

Partition the (256)4 chosen plaintexts

into (256)3 Īc sets according the value of the triplet c

Choose into those (256)3 Īc sets 216 values of c

For each value of the (c , c ) pair do

For kĻ„1 from (0, Ā· Ā· Ā· , 0) to (255, Ā· Ā· Ā· , 255) do

Compute the values of (Ļ„1 ā• Ļ„1 )y=0Ā·Ā·Ā·15 from the ciphertexts

c c

Put them in a table Tkini ,c ,c [kĻ„1 ]

End For

For kĻ„2 from (0, Ā· Ā· Ā· , 0) to (255, Ā· Ā· Ā· , 255) do

Compute the values of (Ļ„2 ā• Ļ„2 )y=0Ā·Ā·Ā·15 from the ciphertexts

c c

Look in the table Tkini ,c ,c [kĻ„1 ] if the same values appear

If yes, verify the same computation for all the y values

If equality for all y values, return (kini , kĻ„1 , kĻ„2 )

Else continue

End If

End For

End For

End For

Since the above procedure tests whether the exist collisions inside a random

set of 2562 of the 2564 possible sc [y] functions, the probability of the procedure

to result in a collision, and thus to provide kini , kĻ„1 and kĻ„2 is high (say about

1/2). In other words, the success probability of the attack is about 1/2.

The ļ¬rst step could be made independently and requieres 232 chosen plain-

texts and 232 AES executions.

26 M. Minier

The complexity of the secund step is about 2144 operations less expensive than

AES executions. Its probability of success is about 1/2. This attack provides 20

bytes of information on the last and penultimate key values.

5.4 How to Improve this Attack Using the Lucksā™ Property of the

Key Schedule for a 192 Bits Key

We can improve, by using the particular property of the key schedule described

by S. Lucks in [Luc00], the complexity of the attack by a little factor in the

case of a key length equal to 192 bits. Indeed, the attack presented by S. Lucks

permits to limit the key exhaustive search to only 8 kĻ„2 bytes instead of the 10

initial bytes because the knowledge of the two ļ¬rst columns of the last subkey

determines completely, taking into account the eļ¬ect of the last ShiftRow, the

two others bytes of the penultimate subkey that compose kĻ„2 .

6 Conclusion

We have shown in this paper that there exists a strong collision property on

three inner AES rounds due to some partial byte oriented functions induced by

the AES cipher. This property is stronger than the one used in the bottleneck

attack even if this new bottleneck property could not be extend in a better four

rounds distinguisher that the one used in the known attack.

Maybe, there is a better way to exploit this new restricted dependency but

we do not ļ¬nd how to extend it.

References

[AES99] http://www.nist.gov/aes

[CP02] N. Courtois and J. Pieprzyk, āCryptanalysis of Block Ciphers with Overde-

ļ¬ned Systems of Equationsā. In Asiacryptā™02, Queenstown, New Zealand,

Lecture Notes in Computer Science 2501, Springer-Verlag, 2002.

J. Daemen, V. Rijmen, āAES Proposal : Rijndaelā, The First Advanced

[DR98]

Encryption Standard Candidate Conference, N.I.S.T., 1998.

J. Daemen, V. Rijmen, The Design of Rijndael. Springer-Verlag, 2002.

[DR02]

[FKS+ 00] N. Ferguson, J. Kelsey, B. Shneier, M. Stay, D. Wagner and D. Whit-

ing, āImproved Cryptanalysis of Rijndaelā. In Fast Software Encryptionā™00,

New York, United State, pp. 213-230. Lectures Notes in Computer Science

1978, Springer-Verlag, 2000.

H. Gilbert, M. Minier, āA Collision Attack on 7 rounds of Rijndaelā. In The

[GM00]

Third Advanced Encryption Standard Candidate Conference. N.I.S.T., 2000.

[Luc00] S. Lucks, āAttackng Seven Rounds of Rijndael Under 192-bit and 256-bit

Keysā. In The Third Advanced Encryption Standard Candidate Conference.

N.I.S.T., 2000.

[MR02] S. Murphy and M. Robshaw, āEssential Algebraic Structure Within the

AESā. In Cryptoā™02, Santa Barbara, United State, Lectures Note in Com-

puter Science 2442, Springer-Verlag, 2002.

DFA on AES

Christophe Giraud

Oberthur Card Systems,

25, rue Auguste Blanche, 92 800 Puteaux, France

c.giraud@oberthurcs.com

Abstract. In this paper we describe two diļ¬erent DFA attacks on the

AES. The ļ¬rst one uses a fault model that induces a fault on only one bit

of an intermediate result, hence allowing us to obtain the key by using

50 faulty ciphertexts for an AES-128. The second attack uses a more

realistic fault model: we assume that we may induce a fault on a whole

byte. For an AES-128, this second attack provides the key by using less

than 250 faulty ciphertexts.

If we extend our hypothesis by supposing that the attacker can choose

the byte aļ¬ected by the fault, our bit-fault attack requires 35 faulty ci-

phertexts to obtain the secret key and our byte-fault attack requires only

31 faulty ciphertexts.

Keywords: AES, DFA, side-channel attacks, smartcards.

1 Introduction

Since Boneh, Demillo and Lipton introduced a cryptanalytic attack in Septem-

ber 1996 based on the fact that errors may be induced on smartcards during the

computation of a cryptographic algorithm to ļ¬nd the key [6], many papers have

been published on this subject. Boneh et al. succeeded in breaking an RSA CRT

with both a correct and a faulty signature of the same message. Lenstra then

improved their attack [9] by ļ¬nding one of the factors of the public modulus

using only one faulty signature of a known message. In October 1996, Biham

and Shamir published an attack on secret key cryptosystems [4] entitled Diļ¬er-

ential Fault Analysis (DFA). In 2000, Biehl, Meyer and MĀØller presented a paper

u

describing two types of DFA attacks on elliptic curve cryptosystems [3] which

were later reļ¬ned by Ciet and Joye [7].

DFA is frequently used nowadays to test the security of cryptographic smart-

cards applications, especially those using the DES. On the 2nd October 2000,

the AES was chosen to be the successor of the DES and, since then, it is used

more and more in smartcards applications. So it seems interesting to investigate

what is feasible on the AES by using DFA. Unfortunately, the DFA attack on

symmetric cryptosystems proposed by Biham and Shamir [4] does not work on

the AES. This is why we work to ļ¬nd a way to attack the AES by using DFA.

On a smartcard, a fault may be induced by its owner in many ways, such as

power glitch, clock pulse or radiation of many kinds (laser, etc...). These external

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 27ā“41, 2005.

c Springer-Verlag Berlin Heidelberg 2005

28 C. Giraud

interventions may induce a fault, but we do not know the real impact on the

computation inside the card. This is why, in this paper, we use two types of fault

models. The ļ¬rst fault model assumes that the fault occurs on only one bit of a

temporary result. Of course such a fault may be diļ¬cult to induce in practice,

so the second fault model assumes that the induced fault may change a whole

byte. The ļ¬rst fault model is the same as the one used in [3, 4, 6] and was put

into practice in 2002 by Skorobogatov and Anderson [13].

In the course of this paper, we describe the AES algorithm before looking

at a DFA attack on the AES by using our ļ¬rst fault model. This attack allows

us to ļ¬nd the AES-128 key by using 50 faulty ciphertexts. We then explain a

more practical DFA attack on an AES-128 by using our second fault model. This

attack allows us to ļ¬nd the key by using less than 250 faulty ciphertexts. Finally

we present the second attack on a real smart card from a practical point of view.

2 AES

In the rest of the paper, we will use the following notations:

ā“ we denote by M the plaintext and by K the AES key,

ā“ M i denotes the temporary cipher result after the ith round and Mj the j th

i

byte of M i ,

ā“ K i denotes the ith AES round key and Kj the j th byte of K i ,

i

ā“ C denotes the correct ciphertext and Cj the j th byte of C,

ā“ D denotes a faulty ciphertext and Dj the j th byte of D.

The following section gives a general description of the AES. For more infor-

mation, the reader can refer to [11, 8].

2.1 General Description

The AES algorithm is capable of encrypting or decrypting data blocks of 128

bits by using cryptographic keys of 128, 192 or 256 bits.

The AES key scheduling provides Nr + 1 round keys. The number of rounds

Nr is dependent on the key length as shown in the following table:

Key length Number of Rounds

AES-128 128 10

AES-192 192 12

AES-256 256 14

A 16-byte temporary result is represented as a two-dimensional array of bytes

consisting of 4 rows and 4 columns. For example, M i = (M0 , ..., M15 ) is repre-

i i

sented by the following array:

DFA on AES 29

M

0

Round Key K

1

Round Round Key K

Nr-1

Round Round Key K

Nr

Round Key K

Final Round

C

Fig. 1. General structure of AES

M0 M4 M8 M12

i i i i

M1 M5 M9 M13

i i i i

M2 M6 M10 M14

i i i i

M3 M7 M11 M15

i i i i

2.2 A Round

The Round function is composed of 4 transformations: SubBytes (SB), ShiftRows

(SR), MixColumns (MC) and a bit-per-bit XOR with a round key. The Final

Round of the AES is composed of the same functions as a classical Round except

that it does not include the MixColumns transformation.

SubBytes. This transformation is a non-linear byte substitution and operates

on each input byte independently. So, we apply the substitution table (S-box)

on each byte of the input to obtain the output.

ShiftRows. The rows of the temporary result are cyclically shifted over diļ¬er-

ent oļ¬sets. Row 0 is not shifted, Row 1 is shifted over 1 byte, Row 2 is shifted

over 2 bytes and Row 3 is shifted over 3 bytes.

MixColumns. Here, the columns of the temporary result are considered as

polynomials over F28 and multiplied modulo x4 + 1 with a ļ¬xed polynomial

a(x) = 03 ā— x3 + 01 ā— x2 + 01 ā— x + 02.

Notice that if we change a byte of the input of SubBytes or of ShiftRows, it

will change one byte of the output. But for the MixColumns transformation,

changing a byte of the input induces a modiļ¬cation of four output bytes.

30 C. Giraud

2.3 Key Scheduling

The Key Scheduling generates the round keys from the AES key K by using 2

functions: the Key Expansion and the Round Key Selection.

Key Expansion. This function computes from the AES key, an expanded key

of length equal to the message block length multiplied by the number of rounds

plus 1.

The expanded key is a linear array of 4-byte words and is denoted by EK[4 ā—

(Nr + 1)] where Nr is the number of rounds. If we denote by Nk the key length

in words, the key expansion is described in the following pseudo code:

KeyExpansion(byte Key[4 ā— Nk ], word EK[4 ā— (Nr + 1)])

{

word temp;

for (i = 0 ; i < Nk ; i + +)

EK[i] = (Key[4 ā— i], Key[4 ā— i + 1], Key[4 ā— i + 2], Key[4 ā— i + 3]);

for (i = Nk ; i < 4 ā— (Nr + 1) ; i + +)

temp = EK[i ā’ 1];

if (i mod Nk = 0)

temp = SubWord(RotWord(temp)) ā• Rcon[i/Nk ];

else if ((Nk > 6) and (i mod Nk = 4))

temp = SubWord(temp);

EK[i] = EK[i ā’ Nk ] ā• temp;

}

where:

ā“ SubWord() is a function that applies the AES S-box at each byte of the

4-byte input to produce an output word,

ā“ RotWord() is a cyclic rotation such that a 4-byte input (a, b, c, d) produces

the 4-byte output (b, c, d, a),

ā“ the round constant word array, Rcon[i], is deļ¬ned by Rcon[i] = (xiā’1 , {00},

{00}, {00}) with xiā’1 being powers of x (x is denoted as {02}) in the ļ¬eld

F28 .

Round Key Selection. This routine extracts the 128-bit round keys from the

Expanded Key.

Example of Key Scheduling for an AES-128.

K

AES Key:

Expanded Key: EK0 EK1 EK2 EK3 EK4 EK5 EK6 EK7 ...

Round Keys: Round Key 0 Round Key 1 ...

DFA on AES 31

where

(EK0 , ..., EK3 ) is the 128-bit AES key K,

ā“

EK4 = EK0 ā• SubW ord(RotW ord(EK3 )) ā• Rcon[1],

ā“

EK5 = EK1 ā• EK4 ,

ā“

EK6 = EK2 ā• EK5 ,

ā“

EK7 = EK3 ā• EK6 , ...

ā“

3 Bit-Fault Attack

In this section, by using a DFA attack where a fault occurs on only one bit of

the temporary cipher result at the beginning of the Final Round, we show how

to obtain the entire last round key, i.e. the AES key for an AES-128. For more

information about this fault model, the reader can refer to [13].

For the sake of simplicity, we describe the attack on an AES using a 128-bit

key.

9

8 10

Key Scheduling Key Scheduling

K

K K

8 9

SR o SB

M M C

MC o SR o SB

Round 9 Round 10

Fig. 2. The last rounds of an AES-128

By deļ¬nition, we have

C = Shif tRows(SubBytes(M 9 )) ā• K 10 (1)

Let us denote by SubByte(Mj ) the result of the substitution table applied on

i

the byte Mj and by Shif tRow(j) the position of the j th byte of a temporary

i

result after applying the ShiftRows transformation.

So, we have from (1)

CShif tRow(i) = SubByte(Mi9 ) ā• KShif tRow(i) , āi ā {0, ..., 15}

10

(2)

If we induce a fault ej on one bit of the j th byte of the temporary cipher result

M 9 just before the Final Round, we obtain a faulty ciphertext D where:

DShif tRow(j) = SubByte(Mj ā• ej ) ā• KShif tRow(j)

9 10

(3)

and for all i ā {0, ..., 15}\{j}, we have:

DShif tRow(i) = SubByte(Mi9 ) ā• KShif tRow(i)

10

(4)

So, if there is no induced fault on the ith byte of M 9 , we obtain from (2) and (4)

CShif tRow(i) ā• DShif tRow(i) = 0 (5)

32 C. Giraud

and if there is an induced fault on Mj , we have from (2) and (3)

9

CShif tRow(j) ā• DShif tRow(j) = SubByte(Mj ) ā• SubByte(Mj ā• ej )

9 9

(6)

Firstly, we determine Shif tRow(j) which is the position of the only non-zero

byte of C ā• D and we thus obtain j. We then use a counting method in order

to ļ¬nd Mj : we guess the single bit fault ej and we ļ¬nd a set of possible values

9

for Mj which verify (6). For each of these values, we increase the corresponding

9

counter by 1. With another faulty ciphertext, the right value for Mj is expected

9

to be counted more frequently than any wrong value, and can thus be identiļ¬ed.

Then we iterate the previous process to obtain all the other bytes of M 9 .

Now, as we know the value of the ciphertext C and the value of M 9 , we can

easily obtain the last round key K 10 from the formula (1) and consequently the

AES key K by applying the inverse of the Key Scheduling to K 10 .

By using 3 faulty ciphertexts with faults induced on the same byte of M 9 ,

we have a 97% chance of having one value left for this byte (cf. appendice A).

So, it is possible to obtain the 128-bit AES key by using less than 50 faulty

ciphertexts.

This attack operates independently on each byte, so if we succeed in inducing

a fault on only one bit on several bytes of M 9 , we reduce the number of faulty

ciphertexts required to obtain the key.

We notice that this attack also operates on the AES-192 and on the AES-256.

In such cases, we obtain the last round key, i.e. the security of the AES-192 is

reduced from 24 to 8 bytes and the security of the AES-256 is reduced from 32

to 16 bytes.

This attack is powerful but requires inducing a fault on only one bit at the

time of a precise event (i.e. at the beginning of the last round) which may be

diļ¬cult in practice.

4 A Second Type of DFA Attack on the AES-128

This DFA attack uses the fault model based on inducing a fault which may

change a whole byte of a temporary result. This attack, which only works on an

AES using a 128-bit key, is divided into 3 steps :

1. we obtain the last 4 bytes of K 9 by exploiting the faulty ciphertexts obtained

when a fault is introduced on K 9 , just before the computation of K 10 ,

2. we obtain another 4 bytes of K 9 by exploiting the faulty ciphertexts obtained

when a fault is introduced on K 8 , just before the computation of K 9 ,

3. ļ¬nally, we obtain the AES key K by exploiting the faulty ciphertexts ob-

tained by introducing a fault on M 8 before entering Round 9 and by using

the 8 bytes of K 9 disclosed in steps 1 and 2.

In smartcard implementations, each round key is computed on-the-ļ¬‚y. In the

following section, āattack on K i ā means that the correct ith round key has been

used for the cipher and that a fault has been induced on this round key before

computing the i + 1th round key which is a faulty round key.

DFA on AES 33

DFA Attack on K 9

4.1

We suppose that we know both the correct ciphertext C and a faulty ciphertext

D of the same plaintext M and that the fault occurs on one of the bytes of

K 9 just before computing K 10 as shown in ļ¬gure 3, where the shaded squares

represent the bytes aļ¬ected by the fault.

We want the fault to occur on one of the last 4 bytes of K 9 . In that case,

two of the last 4 bytes of the faulty ciphertext will be diļ¬erent from those of the

correct ciphertext. We must hence check if this condition is true: if it is not, we

abandon this faulty ciphertext and we generate another faulty ciphertext with

a fault on K 9 and we test it again.

Key Scheduling

Key Scheduling

SR o SB

MC o SR o SB

Round 9 Round 10

Fig. 3. Fault on the 14th byte of the penultimate round key K 9

Now, we will see that it is possible to identify:

ā“ the position j of the byte on which the fault occurred

ā“ and the value ej of this fault.

If we suppose that a fault ej occurs on the j th byte of K 9 (12 ā¤ j ā¤ 15) just

before the Final Round, there will only be one non-zero byte in the ļ¬rst 4 bytes

of C ā• D. If we denote this byte the k th (0 ā¤ k ā¤ 3), j is then deļ¬ned by

j = (k + 1 mod 4) + 12 (7)

By computing C ā• D, we determine k and thus obtain j.

By deļ¬nition, we have:

āi ā {0, ..., 15}, Ci = SubByte(MShif tRowā’1 (i) ) ā• Ki

9 10

(8)

More precisely:

- if i = 0:

Ci = SubByte(MShif tRowā’1 (i) ) ā• SubByte(K(i+1 ā• Ki ā• 0x36 (9)

9 9 9

mod 4)+12 )

- if i ā {1, 2, 3}:

Ci = SubByte(MShif tRowā’1 (i) ) ā• SubByte(K(i+1 ā• Ki

9 9 9

mod 4)+12 ) (10)

We also have for the faulty ciphertext:

Dj = SubByte(MShif tRowā’1 (j) ) ā• Kj ā• ej

9 10

(11)

34 C. Giraud

and

- if k = 0:

Dk = SubByte(MShif tRowā’1 (k) ) ā• SubByte(Kj ā• ej ) ā• Kk ā• 0x36

9 9 9

(12)

- if k ā {1, 2, 3}:

Dk = SubByte(MShif tRowā’1 (k) ) ā• SubByte(Kj ā• ej ) ā• Kk

9 9 9

(13)

It is easy to see, from (8) and (11), that the value of the fault ej is equal to

Cj ā• Dj .

We have now identify the position j of the byte on which the fault occurred

and the value ej of this fault. Let us see how to use this information to obtain

the value of Kj .

9

From (9), (10), (12) and (13), we have the equation

Ck ā• Dk = SubByte(Kj ) ā• SubByte(Kj ā• ej )

9 9

(14)

We know the value of Ck ā• Dk and the value of ej . So, we search the possible

values x ā {0, ..., 255} which satisfy the equation

Ck ā• Dk = SubByte(x) ā• SubByte(x ā• ej ) (15)

We obtain Kj and Kj ā• ej as solutions to (15). So, if we obtain another faulty

9 9

ciphertext with a fault ej (ej = ej ) which occurs on the same byte j of K 9 , we

obtain Kj and Kj ā• ej as solutions. This allows us to deduce the value of Kj

9 9 9

because it is the only value that appears in both solution.

With this attack, we obtain the values of the last 4 bytes (K12 to K15 ) of the

9 9

round key K 9 with 32 faulty ciphertexts on average.

Attack on K 8

4.2

Now, we will see how to obtain the 4 bytes K8 to K11 . We use faulty ciphertexts

9 9

obtained when the fault ej occurred on one byte of K 8 (lets say the j th byte)

before Round 9.

We want the fault to occur on one of the last 4 bytes of K 8 . If it is the case,

there will only be one zero byte in the last 4 bytes of C ā• D. So we test this

Key Scheduling Key Scheduling

SR o SB

MC o SR o SB

Round 9 Round 10

Fig. 4. Fault on the 14th byte of the antepenultimate round key K 8

DFA on AES 35

condition and if it is false, we generate another faulty ciphertext with a fault

induced on K 8 and we test it again.

As in section 4.1, we will:

ā“ identify the position j of the byte on which the fault occurred

ā“ and obtain the value ej of this fault.

If we denote by l the position of the zero byte in the last 4 bytes of C ā• D

(12 ā¤ l ā¤ 15), j is then deļ¬ned by

j = (l ā’ 1 mod 4) + 12 (16)

Now, we know on which byte of K 8 the fault occurred.

We have, for the faulty ciphertext D:

Dj = SubByte(MShif tRowā’1 (j) ) ā• Kj ā• ej if j = 12

9 10

(17)

Dj = SubByte(MShif tRowā’1 (j) ā• ej ) ā• Kj ā• ej if j = 12

9 10

and for the correct ciphertext:

Ci = SubByte(MShif tRowā’1 (i) ) ā• Ki āi ā {0, ..., 15}

9 10

(18)

ā“ If j = 12, we easily obtain the value of ej which is equal to Cj ā• Dj .

ā“ But, if j = 12, the ShiftRows transformation does not aļ¬ect the 12th byte

and we cannot directly obtain the value of the fault ej . We only know that

Cj ā• Dj = SubByte(a) ā• SubByte(a ā• ej ) ā• ej (19)

for a certain 8-bit value a. In this case, we guess the fault ej and we look

for a value a which satisļ¬es (19). If such a value exists, we assume that our

guess may be correct and we keep it as a possible value for the fault ej . We

obtain between 107 and 146 diļ¬erent possible values for ej depending on the

value of Cj ā• Dj ; the average is about 127.

Now, we have identify the position j of the byte on which the fault occurred

and the value ej of this fault if j = 12 or a set of possible values if j = 12. Let

us see how to use this information to obtain the value of Kj .8

If we induce a fault on Kj (12 ā¤ j ā¤ 15), the 4 bytes of the faulty 9th round

8

key at position (j ā’ 1 mod 12) + 4n, n ā {0, 1, 2, 3}, are diļ¬erent from the bytes

at the same position of the correct 9th round key K 9 . These four diļ¬erences

between the correct and the faulty 9th round key are equal and we denote this

diļ¬erence fj .

If we denote k = (j ā’ 1 mod 4) + 12, we have Kk ā• fj as the value of the k th

9

byte of the faulty 9th round key.

So, we have:

- if j = 14:

Djā’2 = SubByte(MShif tRowā’1 (jā’2 ā• SubByte(Kk ā• fj )

9 9

mod 4) )

mod 4

(20)

ā•Kjā’2 mod 4 ā• 0x36

9

36 C. Giraud

- if j ā {12, 13, 15}:

Djā’2 = SubByte(MShif tRowā’1 (jā’2 ā• SubByte(Kk ā• fj )

9 9

mod 4) )

mod 4

(21)

ā•Kjā’2 mod 4

9

And we obtain from (9), (10), (20) and (21):

Cjā’2 ā• Djā’2 = SubByte(Kk ) ā• SubByte(Kk ā• fj )

9 9

(22)

mod 4 mod 4

As we know the value of Kk from the previous attack (section 4.1), we can

9

easily ļ¬nd the value of fj which satisļ¬es (22).

Moreover, Kjā’1 mod 4 ā• fj is the value of the (j ā’ 1 mod 12)th byte of the

9

faulty 9th round key. So, we have for the faulty Key Scheduling:

- if j = 13:

SubByte(Kj ā• ej ) ā• Kjā’1 ā• 0x36 = Kjā’1 ā• fj

8 8 9

(23)

mod 4 mod 4

- if j ā {12, 14, 15}:

SubByte(Kj ā• ej ) ā• Kjā’1 = Kjā’1 ā• fj

8 8 9

(24)

mod 4 mod 4

and for the correct Key Scheduling:

- if j = 13:

SubByte(Kj ) ā• Kjā’1 ā• 0x36 = Kjā’1

8 8 9

(25)

mod 4 mod 4

- if j ā {12, 14, 15}:

SubByte(Kj ) ā• Kjā’1 = Kjā’1

8 8 9

(26)

mod 4 mod 4

We obtain from (23), (24), (25) and (26):

fj = SubByte(Kj ā• ej ) ā• SubByte(Kj )

8 8

(27)

With the value of fj previously obtained from (22), we ļ¬nd all the possible values

Kj which satisfy (27).

8

As in section 3, we use a counting method in order to ļ¬nd the correct Kj . 8

The right Kj can be obtained quickly when j = 12 because we know the value

8

of the fault ej . However, if j = 12 it is more diļ¬cult because there are many

possible values for ej (between 107 and 146). Although we need more faulty

ciphertexts to determine K12 than to determine K13 , K14 or K15 , the number

8 8 8 8

required is relatively low. We need approximately 13 faulty ciphertexts from the

same plaintext to obtain K12 and only 2 to obtain K13 , K14 or K15 (by using

8 8 8 8

simulation, we ļ¬nd that we have a 90% chance of success to determine K12 if 8

we use 10 faulty ciphertexts and this percentage grows up to 99% if we use 13

faulty ciphertexts).

Finally, to obtain K8 , K9 , K10 and K11 , we use the following formula:

9 9 9 9

Ki = Ki+4 ā• Ki+4 āi ā {8, ..., 11}

9 8 9

(28)

At this step, we have obtained the last 8 bytes of the penultimate round key K 9

by using about 240 faulty ciphertexts.

DFA on AES 37

Key Scheduling

Key Scheduling

SR o SB

MC o SR o SB

Round 9 Round 10

Fig. 5. Fault on the 11th byte of M 8

DFA Attack on M 8

4.3

Before entering Round 9, we assume that a fault on one byte of M 8 has been

induced. As we have determined the last 8 bytes of K 9 , we want the fault to

occur on a byte of M 8 which will be XORed with one of the last 8 bytes of K 9

after M C ā—¦ SR ā—¦ SB. Due to the ShiftRows and MixColumns transformations,

we know that if we induce a fault on M12 , M1 , M6 or on M11 (resp. on M8 ,

8 8 8 8 8

M13 , M2 or on M7 ), the result of these bytes after M C ā—¦SR ā—¦SB will be XORed

8 8 8

with K12 to K15 (resp. K8 to K11 ). So, we want a fault to occur on one of these

9 9 9 9

8 bytes of M 8 and to test if this happens, we look at the faulty ciphertext: if

only the 4 bytes (D12 , D9 , D6 , D3 ) (resp. (D8 , D5 , D2 , D15 )) diļ¬er from (C12 ,

C9 , C6 , C3 ) (resp. (C8 , C5 , C2 , C15 )) of the correct ciphertext, this shows that

the fault occurred on one of the 4 bytes (M12 , M1 , M6 , M11 ) (resp. (M8 , M13 ,

8 8 8 8 8 8

M2 , M7 )).

8 8

In the following, let (D12 , D9 , D6 , D3 ) be diļ¬erent from (C12 , C9 , C6 , C3 ).

We guess the fault ej (1 ā¤ ej ā¤ 255) and we list all the 4-byte values V which

verify one of the following equations:

SB(M C(V ) ā• K12ā’15 ) ā• SB(M C(V ā• (0, 0, 0, ej )) ā• K12ā’15 ) = T R12ā’15

9 9

SB(M C(V ) ā• K12ā’15 ) ā• SB(M C(V ā• (0, 0, ej , 0)) ā• K12ā’15 ) = T R12ā’15

9 9

SB(M C(V ) ā• K12ā’15 ) ā• SB(M C(V ā• (0, ej , 0, 0)) ā• K12ā’15 ) = T R12ā’15

9 9

SB(M C(V ) ā• K12ā’15 ) ā• SB(M C(V ā• (ej , 0, 0, 0)) ā• K12ā’15 ) = T R12ā’15

9 9

(29)

where K12ā’15 denotes the 4-byte value (K12 , K13 , K14 , K15 ) and T R12ā’15 the

9 9 9 9 9

4-byte value (C ā• D)Shif tRow(12ā’15) = (C12 ā• D12 , C9 ā• D9 , C6 ā• D6 , C3 ā• D3 ).

So, if we apply the same reasoning to another faulty ciphertext which diļ¬ers

from the correct ciphertext on (D12 , D9 , D6 , D3 ), we obtain another list of 4-

byte values. There will only be one 4-byte value present in both lists and this

will be the correct value of the last 4 bytes of the temporary result before the

MixColumns transformation in Round 9.

Proceeding in the same way with two diļ¬erent faulty ciphertexts in which

(D8 , D5 , D2 , D15 ) diļ¬er from (C8 , C5 , C2 , C15 ), we obtain the correct 8th to

11th bytes of the temporary result before the MixColumns transformation in

Round 9.

Having now identiļ¬ed the last 8 bytes of the temporary cipher result before

the MixColumns transformation in Round 9, we apply MixColumns to these 8

bytes. We then XOR the result with the corresponding bytes of K 9 (i.e. K8 to 9

K15 ) and we apply SR ā—¦ SB. This result is a part of the correct temporary result

9

38 C. Giraud

before the XOR with K 10 . So, we XOR it with the corresponding bytes of the

ciphertext C to obtain the bytes K2 , K3 , K5 , K6 , K8 , K9 , K12 and K15 .

10 10 10 10 10 10 10 10

Using the known bytes of K 9 , we obtain 6 other bytes of K 10 by the following

relations:

K13 = K9 ā• K13

10 10 9

K11 = K15 ā• K15

10 10 9

K10 = K6 ā• K10

10 10 9

(30)

K14 = K10 ā• K14

10 10 9

K7 = K11 ā• K11

10 10 9

K 4 = K8 ā• K 8

10 10 9

Finally, we ļ¬nd the last 2 unknown bytes of K 10 by a very fast exhaustive

search and we obtain the AES key from K 10 by applying the inverse of the Key

Scheduling.

Theoretically, we obtain the full AES key by using less than 250 faulty ci-

phertexts.

5 Remark

The previous number of required faulty ciphertexts was determined by supposing

that the fault location cannot be chosen, i.e. the position of the fault is uniformly

distributed among the 16 bytes of a chosen temporary result. If we suppose that

we can choose the byte where the fault is induced, we need on average 35 faulty

ciphertexts to recover the secret key by using our bit-fault attack and only 31

faulty ciphertexts by using our byte-fault attack (we need 8 faulty ciphertexts to

perform the fault attack described in section 4.1, 19 to perform the one described

in section 4.2 and 4 to perform the one described in section 4.3).

6 In Practice

We implemented the algorithmic part of the second attack on an AES-128 and,

by simulating faults on random bytes of K 8 , K 9 and M 9 , we found the whole

AES key by using 250 faulty ciphertexts. This was easily done on a computer

but we were yet to discover if our second attack could be successfully put into

practice on a smart card.

By using a microscope, a modiļ¬ed camera ļ¬‚ash and a computer, we attacked

an AES-128 on an 8-bit smart card (to make the attack easier, we used a known

AES code). Firstly, we had to ļ¬nd out where the light ļ¬‚ash was most eļ¬cient

on the surface of the chip and then we had to synchronize the ļ¬‚ash with the

operations we wanted to disturb.

We even succeeded in inducing a fault for nearly every execution of the AES,

we needed a lot of tries to obtain a āgoodā faulty ciphertext. Indeed, most of

the time, the induced fault aļ¬ected 4 or 8 bytes of the temporary result.

To recover the key, we needed numerous tries: more than 1000 AES executions

were required.

DFA on AES 39

If we had had a laser we could have shortened the length of the ļ¬‚ash and

hence obtained a āgoodā faulty ciphertext more frequently by disturbing the

chip for a very short time, i.e. during the treatment of only one byte.

This experience demonstrates that AES on smart cards must now be imple-

mented not only with SPA/DPA countermeasures but also with DFA counter-

measures.

7 Conclusion

Although DFA on the DES is a well-known attack, it is impossible to directly

apply Biham and Shamirā™s attack to the AES as the latter does not have the

Feistel Structure. This paper extends the operative ļ¬eld of diļ¬erential fault at-

tacks by describing how to perform two diļ¬erent DFA attacks on the AES. Each

of these attacks allow us to obtain the full AES key in the case of a 128-bit

key length. We note that it is possible to put the second attack into practice on

smart cards. However, it is easy to avoid both attacks. For example, this can be

done by doubling the last two rounds and by checking if the two outputs are

equal.

Acknowledgments

I would like to thank Mathieu Ciet for his valuable comments as well as Erik

Knudsen for many helpful discussions. The practical attack would never have

been possible without the help of Hugues Thiebeauld. Finally, I am really grateful

to Julia Bradley for her help and support during the writing of this paper.

References

1. R. Anderson and M. Kuhn. Tamper Resistance - a Cautionary Note. In Proceedings

of the 2nd USENIX Workshop on Electronic Commerce, pages 1ā“11, 1996.

2. R. Anderson and M. Kuhn. Low cost attacks on tamper resistant devices. In

B. Christianson, B. Crispo, T. Mark, A. Lomas, and M. Roe, editors, 5th Security

Protocols Workshop, volume 1361 of Lecture Notes in Computer Science, pages

125ā“136. Springer-Verlag, 1997.

3. I. Biehl, B. Meyer, and V. MĀØ ller. Diļ¬erential Fault Analysis on Elliptic Curve

u

Cryptosystems. In M. Bellare, editor, Advances in Cryptology ā“ CRYPTO 2000,

volume 1880 of Lecture Notes in Computer Science, pages 131ā“146. Springer-

Verlag, 2000.

4. E. Biham and A. Shamir. Diļ¬erential Fault Analysis of Secret Key Cryptosystem.

In B.S. Kalisky Jr., editor, Advances in Cryptology ā“ CRYPTO ā™97, volume 1294

of Lecture Notes in Computer Science, pages 513ā“525. Springer-Verlag, 1997.

5. J. BlĀØmer and J.-P. Seifert. Fault based cryptanalysis of the Advanced Encryption

o

Standard. In R.N. Wright, editor, Financial Cryptography ā“ FC 2003, volume 2742

of Lecture Notes in Computer Science. Springer-Verlag, 2003.

40 C. Giraud

6. D. Boneh, R.A. DeMillo, and R.J. Lipton. On the Importance of Checking Cryp-

tographic Protocols for Faults. In W. Fumy, editor, Advances in Cryptology ā“

EUROCRYPT ā™97, volume 1233 of Lecture Notes in Computer Science, pages 37ā“

51. Springer-Verlag, 1997.

7. M. Ciet and M. Joye. Elliptic Curve Cryptosystems in the Presence of Permanent

and Transient Faults. In Designs, Codes and Cryptography, 2004. To appear.

8. J. Daemen and V. Rijmen. The Design of Rijndael. Springer-Verlag, 2002.

9. A.K. Lenstra. Memo on RSA Signature Generation in the Presence of Faults.

Manuscript, 1996. Available from the author at akl@Lucent.com.

10. D.P. Maher. Fault Induction Attacks, Tamper Resistance, and Hostile Reverse

Engineering in Perspective. In R. Hirschfeld, editor, Financial Cryptography ā“ FC

ā™97, volume 1318 of Lecture Notes in Computer Science, pages 109ā“121. Springer-

Verlag, 1997.

11. National Institute of Standards and Technology. FIPS PUB 197: Advanced En-

cryption Standard, 2001.

12. G. Piret and J.-J. Quisquater. A Diļ¬erential Fault Attack Technique Against SPN

Structures, with Application to the AES and Khazad. In C.D. Walter, C.K. KoĀø,

Āø c

and C. Paar, editors, Cryptographic Hardware and Embedded Systems ā“ CHES

2003, volume 2779 of Lecture Notes in Computer Science, pages 77ā“88. Springer-

Verlag, 2003.

13. S. Skorobogatov and R. Anderson. Optical Fault Induction Attack. In B. Kaliski

Jr., C.K. KoĀø, and C. Paar, editors, Cryptographic Hardware and Embedded Sys-

Āø c

tems ā“ CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages

2ā“12. Springer-Verlag, 2002.

A The First Attack in More Details

If a message M is ciphered by using an AES-128 and if a one-bit fault ej is

induced on Mj , we obtain a faulty ciphertext D. We then have the following

9

equation:

CShif tRow(j) ā• DShif tRow(j) = SubByte(Mj ) ā• SubByte(Mj ā• ej )

9 9

(31)

For each faulty ciphertext we perform 8.28 tests, i.e. for all values of x between

0 and 255 and for ej ā {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80}, we test

if the following equality holds :

CShif tRow(j) ā• DShif tRow(j) = SubByte(x) ā• SubByte(x ā• ej ) (32)

There is no solution to (32) if CShif tRow(j) ā• DShif tRow(j) = 185, so this value

can be excluded right away. By consecutively ļ¬xing the left hand side of (32)

with the 254 possible values {1, .., 255}\{185} and by testing all possible pairs

(x, ej ), we ļ¬nd that the number of possible values for Mj varies from 2 to 14;

9

the average is about 8.

If we assume that we are in the worst case, then we obtain 14 possible values

for Mj for each faulty ciphertext.

9

DFA on AES 41

If we obtain another faulty ciphertext with an induced fault on Mj we obtain

9

another set of possible values for Mj . In each set we have the correct value of

9

Mj , so to identify this value the other 13 values must be diļ¬erent from each

9

other.

If we denote by A the set of these 13 values obtained with the ļ¬rst faulty

ciphertext and by B the set of the possible values obtained with the second faulty

ciphertext except the correct value of Mj , we have only one possible value left

9

for Mj with probability :

9

P2 = P (A ā© B = Ć˜)

= P (|A ā© B| = 0)

ā āā ā

255 ā ā 255 ā’ 13 ā

ā ā—

13 13 (33)

ā ā2

=

255 ā

ā

13

50%

With a third faulty ciphertext with an induced fault on Mj we obtain yet another

9

set of 14 possible values for Mj . If we denote by C this set without the correct

9

value of Mj , we have only one possible value left for Mj with probability :

9 9

P3 = P (A ā© B ā© C = Ć˜)

= P (|A ā© B ā© C| = 0)

min{|A|,|B|}

P (|A ā© B| = k, |A ā© B ā© C| = 0)

= k=0

13

= k=0 P (|A ā© B| = ā ā P (|A ā© Bāā© C| = 0 ā |A ā© B| = ā

k) ā— /ā k)

ā āā ā

255 ā ā 13 ā ā 255 ā’ 13 ā ā 255 ā ā 255 ā’ k ā (34)

ā ā— ā— ā—

k 13 ā’ k k

13 13

13

ā—ā āā ā

ā ā2

= k=0

255 ā ā 255 ā

255 ā ā

ā ā—

k 13

13

97%

Reļ¬ned Analysis of Bounds Related to Linear

and Diļ¬erential Cryptanalysis for the AES

Liam Keliher

Department of Mathematics and Computer Science,

Mount Allison University,

Sackville, New Brunswick, Canada

lkeliher@mta.ca

Abstract. The best upper bounds on the maximum expected linear

probability (MELP) and the maximum expected diļ¬erential probability

(MEDP) for the AES, due to Park et al. [23], are 1.075 Ć— 2ā’106 and

1.144 Ć— 2ā’111 , respectively, for T ā„ 4 rounds. These values are simply

the 4th powers of the best upper bounds on the MELP and MEDP for

T = 2 [3, 23]. In our analysis we ļ¬rst derive nontrivial lower bounds

on the 2-round MELP and MEDP, thereby trapping each value in a

small interval; this demonstrates that the best 2-round upper bounds are

quite good. We then prove that these same 2-round upper bounds are

not tightā”and therefore neither are the corresponding upper bounds for

T ā„ 4. Finally, we show how a modiļ¬ed version of the KMT2 algorithm

(or its dual, KMT2-DC), due to Keliher et al. (see [8]), can potentially

improve any existing upper bound on the MELP (or MEDP) for any

SPN. We use the modiļ¬ed version of KMT2 to improve the upper bound

on the AES MELP to 1.778 Ć— 2ā’107 , for T ā„ 8.

Keywords: AES, Rijndael, SPN, provable security, linear cryptanalysis,

diļ¬erential cryptanalysis, MELP, MEDP, KMT2, KMT2-DC.

1 Introduction

During the past few years, several papers have appeared dealing with the prov-

able security of substitution-permutation network (SPN) block ciphers against

linear and diļ¬erential cryptanalysis [3, 6, 7, 9, 10, 11, 12, 22, 23, 24]. Most of these

results have been applied to the Advanced Encryption Standard (AES) [5]ā”

each new result has demonstrated greater provable security against one or both

of these attacks.

Exhibiting provable security against linear and diļ¬erential cryptanalysis re-

quires proving that the maximum expected linear probability (MELP) and the

maximum expected diļ¬erential probability (MEDP), respectively, are small over

This work was funded by the Natural Sciences and Engineering Research Council

of Canada (NSERC).

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 42ā“57, 2005.

c Springer-Verlag Berlin Heidelberg 2005

Reļ¬ned Analysis of Bounds Related to Linear and Diļ¬erential Cryptanalysis 43

Table 1. Previous upper bounds on the MELP and MEDP for the AES

MELP MEDP Range of rounds

2ā’24 [7] 2ā’24 [7] T ā„2

2ā’75 [9] 2ā’75 [10] T ā„7

2ā’92.4 [11, 12] 2ā’95.1 [12] T ā„9

2ā’96 [24] 2ā’96 [24] T ā„4

1.06 Ć— 2ā’96 [22] 1.06 Ć— 2ā’96 [22] T ā„4

1.075 Ć— 2ā’106 [23] 1.144 Ć— 2ā’111 [23] T ā„4

T core cipher rounds (typically T = R ā’ 1 or T = R ā’ 2, where R is the to-

tal number of rounds). Since exact computation of these values often appears

to be infeasible, researchers have focused on bounds. A suļ¬ciently small up-

per bound corresponds to a data complexity that is prohibitively large, since

the data complexity is proportional to the inverse of the corresponding MELP /

MEDP [19, 20]. Note that bounds often appear in pairsā”one each for the MELP

and MEDPā”because of the well-known duality between linear and diļ¬erential

cryptanalysis [1, 17]. Table 1 summarizes the upper bounds that have been de-

rived for the AES prior to the current paper. 1 2

The best upper bounds in Table 1 (last row), due to Park et al., are in fact

the 4th powers of the best upper bounds on the MELP and MEDP for T = 2,

namely 48,193,441 ā 1.44 Ć— 2ā’27 and 234 ā 1.23 Ć— 2ā’28 , respectively [3, 23]. In

79

252

fact, Park et al. show that the 4th power of any upper bound on the 2-round

MELP / MEDP for the AES is an upper bound on the MELP / MEDP for

T ā„ 4 (this also follows from the work of Sano et al. [24]). Therefore the 2-round

MELP and MEDP are important values for analyzing the resistance of the AES

to linear and diļ¬erential cryptanalysis.

In this paper we ļ¬rst derive nontrivial lower bounds on the 2-round MELP

and MEDP for the AES, namely 1.638 Ć— 2ā’28 and 1.656 Ć— 2ā’29 , respectively,

thereby trapping each value in a small interval; this demonstrates that the best

2-round upper bounds are quite good.3 Second, we prove that these same 2-round

upper bounds are not tightā”and therefore neither are the corresponding upper

bounds for T ā„ 4. Third, we show how a modiļ¬ed version of the KMT2 algorithm

(or its dual, KMT2-DC), due to Keliher et al. (see [8]), can potentially improve

any existing upper bound on the MELP (or MEDP) for any SPN. We use the

modiļ¬ed version of KMT2 to improve the upper bound on the AES MELP

1

The results in [7] were not applied to the AES, but the values in the ļ¬rst row of

Table 1 are the upper bounds that would have resulted.

2

The almost identical bounds in [24] and [22] were apparently obtained indepen-

dently.

3

After the presentation of this paper, we learned that the same lower bounds had

previously been obtained by Chun et al. [3].

44 L. Keliher

to 1.778 Ć— 2ā’107 , for T ā„ 8. (The KMT2 / KMT2-DC algorithm computes

upper bounds on the MELP / MEDP āfrom scratchā; the modiļ¬cation involves

incorporating existing upper bounds that are superior to those computed directly

by KMT2 / KMT2-DC in order to reļ¬ne the former.)

1.1 The Advanced Encryption Standard (AES)

The Advanced Encryption Standard (AES) is a U.S. block cipher standard se-

lected in 2000 after an open submission and evaluation process. The AES is the

SPN Rijndael, designed by Joan Daemen and Vincent Rijmen [5]. A single AES

round (minus the subkey mixing) is depicted in Figure 1.

32ā’bit LT 32ā’bit LT 32ā’bit LT 32ā’bit LT

Fig. 1. One AES round

The AES has a block size of 128 bits. The substitution stage consists of 16

identical 8 Ć— 8 s-boxes (the same s-box is used in all rounds). The linear transfor-

mation comprises two steps: a byte permutation, and the parallel application of

four copies of a maximally diļ¬usive 32-bit linear transformation (see Remark 4).

The number of rounds varies according to the key length as follows: 128-bit

key ā’ 10 rounds, 192-bit key ā’ 12 rounds, 256-bit key ā’ 14 rounds.

1.2 Assumption of Independent Subkeys

In analyzing the resistance of block ciphers to linear and diļ¬erential cryptanal-

ysis, it is standard to assume that each subkey is chosen independently and uni-

formly from the set of all possible subkeys.4 We adopt this approach. Because of

the complexities introduced by most key schedules, the values relevant to linear

and diļ¬erential cryptanalysis are rarely calculated for the true distribution of

subkeysā”this remains an interesting and largely unexplored area of study.

2 Linear and Diļ¬erential Cryptanalysis

Linear and diļ¬erential cryptanalysis are generally considered to be the most

powerful attacks on block ciphers. Linear cryptanalysis, due to Matsui [16], is

a known-plaintext attack that exploits the existence of relatively large expected

4

Some authors use AES* to denote the AES modiļ¬ed by this assumption.

Reļ¬ned Analysis of Bounds Related to Linear and Diļ¬erential Cryptanalysis 45

linear probability (ELP) values over T core cipher rounds. Diļ¬erential cryptanal-

ysis, due to Biham and Shamir [2], is a chosen-plaintext attack that exploits the

existence of relatively large expected diļ¬erential probability (EDP) values over T

core rounds. Typical values of interest are T = R ā’ 1 and T = R ā’ 2.

The remainder of this section deals with background concepts related to

linear and diļ¬erential cryptanalysis of SPNs. We use N to denote the block size,

n to denote the s-box input/output size, and M to denote the number of s-boxes

per round (so M = N ). We assume that the same linear transformation and

n

sequence of s-boxes are used in each round (the s-boxes within a round may or

many not be identical). It is easy to generalize to the situation in which the

linear transformation and s-boxes diļ¬er from round to round.

2.1 Linear and Diļ¬erential Probability

Deļ¬nition 1. Let B : {0, 1}d ā’ {0, 1}d , and let a, b, āx, āy ā {0, 1}d be

ļ¬xed. If X ā {0, 1}d is a uniformly distributed random variable, then the linear

probability LP (a, b) and the diļ¬erential probability DP (āx, āy) are deļ¬ned as

2

LP (a, b) = (2 Ā· ProbX {a ā¢ X = b ā¢ B(X)} ā’ 1)

DP (āx, āy) = ProbX {B(X) ā• B(X ā• āx) = āy} .

If B is parameterized by a key, k, we write LP (a, b; k) and DP (āx, āy; k),

respectively, and the expected linear probability ELP (a, b) and expected diļ¬er-

ential probability are deļ¬ned as

ELP (a, b) = EK [LP (a, b; K)]

EDP (āx, āy) = EK [DP (āx, āy; K)] ,

where K is a random variable uniformly distributed over the space of keys.

We view LP, ELP, DP, or EDP values as entries in a 2d Ć— 2d table in the

obvious way. The values a and b in Deļ¬nition 1 are called input and output

masks, and the values āx and āy are called input and output diļ¬erences. For

our purposes, the mapping B in Deļ¬nition 1 will be bijective, and will be an

s-box, a single encryption round, or a sequence of consecutive encryption rounds.

Lemma 1. Let B : {0, 1}d ā’ {0, 1}d be bijective, and let a, b, āx, āy ā {0, 1}d .

Then

LP (a, u) = LP (u, b) = 1 (1)

uā{0,1}d uā{0,1}d

DP (āx, āu) = DP (āu, āy) = 1 . (2)

āuā{0,1}d āuā{0,1}d

Proof. The proof of (1) derives directly from Parsevalā™s Theorem [18]. The proof

ńņš. 2 |