<<

. 2
( 7)



>>

In summary, the s byte depends on only 5 key-dependent bytes and 4 c-dependent
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
( 7)



>>