. 1
( 7)



>>

Lecture Notes in Computer Science 3373
Commenced Publication in 1973
Founding and Former Series Editors:
Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen


Editorial Board
David Hutchison
Lancaster University, UK
Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA
Josef Kittler
University of Surrey, Guildford, UK
Jon M. Kleinberg
Cornell University, Ithaca, NY, USA
Friedemann Mattern
ETH Zurich, Switzerland
John C. Mitchell
Stanford University, CA, USA
Moni Naor
Weizmann Institute of Science, Rehovot, Israel
Oscar Nierstrasz
University of Bern, Switzerland
C. Pandu Rangan
Indian Institute of Technology, Madras, India
Bernhard Steffen
University of Dortmund, Germany
Madhu Sudan
Massachusetts Institute of Technology, MA, USA
Demetri Terzopoulos
New York University, NY, USA
Doug Tygar
University of California, Berkeley, CA, USA
Moshe Y. Vardi
Rice University, Houston, TX, USA
Gerhard Weikum
Max-Planck Institute of Computer Science, Saarbruecken, Germany
Hans Dobbertin Vincent Rijmen
Aleksandra Sowa (Eds.)



Advanced
Encryption Standard “
AES

4th International Conference, AES 2004
Bonn, Germany, May 10-12, 2004
Revised Selected and Invited Papers




13
Volume Editors

Hans Dobbertin
Ruhr-University of Bochum
Cryptology and IT Security Research Group
Universit¤tsstrasse 150, 44780 Bochum, Germany
E-mail: Hans.Dobbertin@ruhr-uni-bochum.de

Vincent Rijmen
Graz University of Technology
Institute for Applied Information Processing and Communications (IAIK)
Inffeldgasse 16a, 8010 Graz, Austria
E-mail: vincent.rijmen@iaik.tugraz.at

Aleksandra Sowa
Ruhr-University of Bochum
Horst Görtz Institut für Sicherheit in der Informationstechnik
Universit¤tsstrasse 150, 44780 Bochum, Germany
E-mail: Aleksandra.Sowa@hgi.ruhr-uni-bochum.de




Library of Congress Control Number: 2005928447


CR Subject Classi¬cation (1998): E.3, F.2.1-2, I.1.4, G.2.1

ISSN 0302-9743
ISBN-10 3-540-26557-0 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-26557-3 Springer Berlin Heidelberg New York


This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, speci¬cally the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on micro¬lms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer. Violations are liable
to prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
springeronline.com
© Springer-Verlag Berlin Heidelberg 2005
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Scienti¬c Publishing Services, Chennai, India
Printed on acid-free paper SPIN: 11506447 06/3142 543210
Preface



This volume comprises the proceedings of the 4th Conference on Advanced En-
cryption Standard, ˜AES ” State of the Crypto Analysis,™ which was held in
Bonn, Germany, during 10“12 May 2004.
The conference followed a series of events organized by the US National In-
stitute of Standards and Technology (NIST) in order to hold an international
competition to decide on an algorithm to serve as the Advanced Encryption
Standard (AES). In 1998, at the ¬rst AES conference (AES 1), 15 di¬erent algo-
rithms were presented, discussed, reviewed and veri¬ed. A second conference was
organized in April 1999, and by August 1999 only ¬ve candidates were still in the
running: MARS, RC6, Rijndael, Serpent and Two¬sh. After a further conference
devoted to veri¬cation, testing and examination of the candidate algorithms in
order to prove their performance and security, one winning algorithm remained.
The encryption scheme Rijndael, designed by the Belgian cryptographers Joan
Daemen and Vincent Rijmen, was selected in 2000 to become the successor to
the famous DES (Data Encryption Standard) and it is now the Advanced En-
cryption Standard.
Like DES before it, AES is going to become a de facto world standard for the
encryption of data. The security of Internet applications, for instance, is already
depending today and, in view of the increasing implementation, will depend in
future even more on AES. Analysis of the cryptographic strength of AES belongs
therefore certainly to the most important topics in cryptology. A recent key re-
covery approach, by solving a complicated system of quadratic equations, which
is due to Courtois and others, has caused a big debate. Previously, approaches
of this kind were considered as purely theoretical, and hopeless in practice. The
big unanswered question is whether the addition of newly proposed techniques
has changed or can change this situation.
Four years after the National Institute of Standards and Technology chose Ri-
jndael to be the Advanced Encryption Standard, leading experts and scientists
from all over the world were invited to discuss ” critically but constructively ”
the strengths and weaknesses of Rijndael, and to look for solutions that will make
it a strong information encryption formula for the next two, ¬ve, ten, or maybe
dozens of years. The intentions of the AES4 conference organizers were to present
the most recent ideas and results on the cryptanalysis of the AES, and to stimu-
late future research on the important open questions about the perspectives and
limits of new cryptanalytic approaches.
The response to the conference was excellent. Ten submission were selected
for presentation. The programme included six keynote addresses (invited talks),
given by Yvo Desmedt from Florida State University, Vincent Rijmen from the
IAIK, Graz University of Technology and Cryptomathic, Carlos Cid from Royal
Holloway, University of London, Nicolas T. Courtois from Axalto Smart Cards,
VI Preface

Jean-Charles Faug`re from the University of Paris VI/INRIA, France, and John
e
Kelsey from the National Institute for Standards and Technology. As a novum,
AES4 introduced for the ¬rst time a closing panel discussion on the future of
Rijndael and cryptography, moderated by Peter Welchering from the German
Scienti¬c Press Conference. Researchers took the opportunity to present their
opinions and suggestions on the cipher weaknesses, known and unknown attacks,
and the future of their work. John Kelsey remarked that most of the practical
problems are usually other than the weaknesses of a cipher. Nevertheless, as
Nicolas T. Courtois argued, there is still ˜plenty of work™ to do. Carlos Cid and
Vincent Rijmen emphasized the necessity to make the current research transpar-
ent, to make it popular and understandable and to let other people know ˜what
we are talking about™ (Vincent Rijmen).
We would like to thank Aleksandra Sowa, the Managing Director of the Horst
G¨rtz Institute (HGI) for IT security at the Ruhr University of Bochum. She
o
did an excellent job as General Chair by organizing the AES4 conference with
the help of our young colleagues from the Chair for IT Security and Cryptology
(CITS).
We are also grateful to NIST and Cryptomathic for supporting this event,
and, last but not least, we would like to thank all the committee members for
their work.

April 2005 Hans Dobbertin and Vincent Rijmen
Organization



AES4 was organized by the Ruhr University of Bochum, in cooperation with the
Graz University of Technology and NIST.



General Chair
Aleksandra Sowa Horst G¨rtz Institute, Ruhr University Bochum
o



Program Co-chairs
Hans Dobbertin Horst G¨rtz Institute, Ruhr University Bochum
o
Vincent Rijmen Graz University of Technology



Program Committee
Don Coppersmith IBM
Nicolas T. Courtois Axalto Smart Cards
Lars R. Knudsen Technical University of Denmark
Matt Robshaw Royal Holloway, University of London



Sponsoring Institutions
Cryptomathic A/S, ˚rhus
A
NIST
Table of Contents



Cryptanalytic Attacks and Related Results
The Cryptanalysis of the AES - A Brief Survey
Hans Dobbertin, Lars Knudsen, Matt Robshaw . . . . . . . . . . . . . . . . . . . . 1

The Boomerang Attack on 5 and 6-Round Reduced AES
Alex Biryukov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

A Three Rounds Property of the AES
Marine Minier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

DFA on AES
Christophe Giraud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Re¬ned Analysis of Bounds Related to Linear and Di¬erential
Cryptanalysis for the AES
Liam Keliher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42


Algebraic Attacks and Related Results
Some Algebraic Aspects of the Advanced Encryption Standard
Carlos Cid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

General Principles of Algebraic Attacks and New Design Criteria for
Cipher Components
Nicolas T. Courtois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

An Algebraic Interpretation of AES’128
Ilia Toli, Alberto Zanoni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84


Hardware Implementations
E¬cient AES Implementations on ASICs and FPGAs
Norbert Pramstaller, Stefan Mangard, Sandra Dominikus,
Johannes Wolkerstorfer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

Small Size, Low Power, Side Channel-Immune AES Coprocessor:
Design and Synthesis Results
Elena Trichina, Tymur Korkishko, Kyung Hee Lee . . . . . . . . . . . . . . . . 113
X Table of Contents

Other Topics
Complementation-Like and Cyclic Properties of AES Round Functions
Tri Van Le, R¨diger Sparr, Ralph Wernsdorf, Yvo Desmedt . . . . . . . . . 128
u

More Dual Rijndaels
avard Raddum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142


Representations and Rijndael Descriptions
Vincent Rijmen, Elisabeth Oswald . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

Linearity of the AES Key Schedule
Frederik Armknecht, Stefan Lucks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

The Inverse S-Box, Non-linear Polynomial Relations and Cryptanalysis
of Block Ciphers
Nicolas T. Courtois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170


Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
The Cryptanalysis of the
AES - A Brief Survey

Hans Dobbertin1 , Lars Knudsen2 , and Matt Robshaw3
1
Cryptology and IT Security Research Group,
Ruhr-University of Bochum, Germany
Hans.Dobbertin@ruhr-uni-bochum.de
2
Department of Mathematics,
Technical University of Denmark,
DK-2800 Lyngby, Denmark
Lars.R.Knudsen@mat.dtu.dk
3
France T´l´com Research and Development,
ee
38“40 rue de G´n´ral-Leclerc, 92794 Issy Moulineaux, France
ee
Matt.Robshaw@francetelecom.com


Abstract. The Advanced Encryption Standard is more than ¬ve years
old. Since standardisation there have been few cryptanalytic advances de-
spite the e¬orts of many researchers. The most promising new approach
to AES cryptanalysis remains speculative, while the most e¬ective at-
tack against reduced-round versions is older than the AES itself. Here
we summarise this state of a¬airs.



1 Introduction
In January 1997 the National Institute of Standards and Technology (NIST) ini-
tiated the search for a replacement for the Data Encryption Standard (DES) [28].
The requirements for the new standard, to be called the Advanced Encryption
Standard (AES), were that it should be:
“ a 128-bit block cipher with the choice of three key sizes of 128, 192, respec-
tively 256 bits,
“ a public and ¬‚exible design,
“ at least as secure as two-key triple-DES, and
“ available royalty-free worldwide.
At the conclusion of this standardisation e¬ort, with many man-years of
cryptanalytic and implementation expertise provided from around the world,
Rijndael, developed by Joan Daemen and Vincent Rijmen [11], was a popular
choice to become the AES. In November 2001 the AES e¬ort came to its conclu-
sion with the publication of FIPS 197 [29], and today the AES is fast becoming
a vital component of the digital infrastructure.
The proceedings of the Fourth AES Conference that follow in this volume
re¬‚ect ongoing research e¬orts into the security and performance of the AES. In
this short article, we brie¬‚y review some promising “ but unsuccessful “ attempts
to compromise this elegant cipher.
H. Dobbertin, V. Rijmen, and A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 1“10, 2005.
c Springer-Verlag Berlin Heidelberg 2005
2 H. Dobbertin, L. Knudsen, and M. Robshaw

2 AES Design
The AES has been described so often and is, by now, so familiar that a brief
overview of the AES design will su¬ce for our purposes.
The AES is a classic substitution/permutation or SP-network that requires
10, 12, or 14 rounds of encryption; the exact number depending on the length of
the key. The AES is byte-oriented and heavily reliant on operations in the ¬eld
GF(28 ). Conceptually, the AES is best described with the sixteen bytes of the
128-bit input block a0 a1 . . . a14 a15 being arranged in a (4 — 4) matrix of bytes:

a0 a4 a8 a12

a1 a5 a9 a13

a2 a6 a10 a14
a3 a7 a11 a15


Using the nomenclature of FIPS 197, a typical round of the cipher
uses the following operations, “SubBytes”, “ShiftRows”, “MixColumns” and
“AddRoundKey”. The ¬nal round has a slightly di¬erent form and omits the
MixColumns operation.
Encryption begins with an AddRoundKey operation, then computation con-
tinues for a given number of rounds, with each round using the four operations
taken in the order above. In SubBytes each byte is replaced by a byte from an
invertible S-box. In ShiftRows the rows (of bytes) are shifted a number of byte
positions to the left. The top row is not shifted, the second row is shifted by one
position, the third by two, and the fourth row by three. In MixColumns the four
bytes in each column are mixed by pre-multiplying the four-byte vector by a
¬xed, invertible, (4 — 4)-matrix over GF(28 ), that is derived from an MDS code.
MixColumns has the property that if two input vectors di¬er in s bytes, then
the output vectors di¬er in at least 5 ’ s bytes, where 1 ¤ s ¤ 4. Each round
closes with AddRoundKey where 16 round-key bytes are exclusive-or™ed to the 16
data bytes. Each round uses all four operations except the last round when the
operation MixColumns is omitted. We refer to [29] for more details on this and
other aspects of the algorithm.
The key schedule for the AES is relatively simple. It takes the user-supplied
key of 16, 24, respectively 32 bytes and returns what is called an ExpandedKey
of 16 — 11, 16 — 13, and 16 — 15 bytes respectively. The details can be found
in [13, 29].



3 The Components
By design, Rijndael, and therefore by extension the AES, is a very structured
cipher. This very clean structure has at least two attractive consequences:
The Cryptanalysis of the AES - A Brief Survey 3

1. It is possible to provide a simple explanation for the intended e¬ect of each
cipher component. The most striking consequence is that we can derive solid
reassurance for the resistance of the AES to basic di¬erential [4] and lin-
ear [23] cryptanalytic attacks.
2. The implementor is provided with a wide range of implementation options.
This is evidenced by the attractive performance pro¬le of the AES across a
wide range of environments.

We will explore the ¬rst consequence in this article.

3.1 The S-Box
The cryptographic strength or weakness of the AES depends strongly on the
choice of S-box. While it is likely that we would view the S-box as a single
entity, it has three distinct components; inversion over GF(28 ) which is naturally
augmented to handle the zero input, transformation by a GF(2)-linear map L,
and addition of a constant c = 0x63. Thus, up to a GF(2)-a¬ne modi¬cation,
the S-box S(x) of the AES is the inversion in the multiplicative group of GF(28 ):

S(x) = A(1/x) (with the convention 1/0 = 0), (1)

where A(x) = L(x) + c is a GF(2)-a¬ne permutation of GF(28 ).
The cryptographic advantages of 1/x on GF(2n ) have been known for some
time. It realizes the best known properties of bijective S-box constructions with
respect to the following properties:

Degree. All S-box component functions (i.e. non-zero linear combinations of
Boolean coordinate functions of the S-box) have degree n ’ 1.
The degree of all non-zero component functions of a non-constant power
function xd is the Hamming weight of the binary representation of the re-
mainder of d modulo 2n ’ 1. Thus the maximal degree n ’ 1 is achieved if,
and only if, up to cyclotomic equivalence, d = ’1 = 2n ’ 2 = 2 (1 + 2 +
22 + ... + 2n’2 ) mod (2n ’ 1). On the other hand it is well known that each
component function of a one-to-one S-box has at most degree n ’ 1.
Resistance to linear attack. Low correlation between S-box component func-
tions and a¬ne Boolean functions.
The absolute value of the correlation between any non-zero component func-
tion of 1/x and any a¬ne Boolean function is bounded by 2’n/2’1 for even
n. This can be shown by using the famous Hasse bound for the number of
points on elliptic curves. It is an open problem whether this bound can be
improved. We mention that for odd n, the bound 2’n’1/2 is attained by 1/x
and this is known to be optimal.
Resistance to di¬erential attack. The designer™s dream “for each prescribed
input di¬erence one can derive no information about the S-box output dif-
ference” is almost achieved.
For characteristic 2, di¬erences coincide with sums. Thus the number of pos-
sible output di¬erences for pre-scribed input di¬erence is at most 2n’1 . If this
4 H. Dobbertin, L. Knudsen, and M. Robshaw

bound is achieved then the S-box is called almost perfect nonlinear (APN),
and in this case each output di¬erence is attained precisely two times. If n
is odd then 1/x is APN, while 2n’1 ’ 1 is the number of output di¬erences
for even n. The latter is due to the fact that 1/x is linear on GF(4). It is not
known if there is any APN one-to-one S-box for even n.

These properties of inversion are preserved under a¬ne modi¬cations and
are therefore valid for the S-box of the AES. The net result is an exceptional
resistance to di¬erential and linear cryptanalysis. In [11] it is shown that any
four-round di¬erential characteristic has a probability of less than 2’150 and that
any four-round linear characteristic holds with a correlation less than 2’75 . These
bounds are su¬cient to conclude that the basic attacks based on di¬erential and
linear cryptanalysis will not succeed against the AES.
While the resistance of the AES to advanced attacks or those using di¬eren-
tials and/or linear hulls remains open, there have been a series of results that
explore these issues [8, 18, 19, 20, 21, 30, 31, 7, 32, 33, 34, 5]. However there seems
little chance of a major breakthrough in this direction.


3.2 Rearranging Components
While the structure of Rijndael received cryptanalytic attention during the AES
process, (see Section 4) it was only at the tail end of that process that a dif-
ferent kind of observation began to be explored. These observations are based
on alternative representations of components, or the entireity, of the AES. Some
researchers have considered a continued fraction representation of AES encryp-
tion [16] while others have considered the concept and implications of dual Ri-
jndaels [3, 35]. Other observations have been concerned with the way AES oper-
ations are presented [25, 26].
Clearly, operations such as SubBytes and ShiftRows trivially commute with
one another. Indeed, properties such as these were used by the AES designers to
show how AES decryption could be written in a form that more closely resembled
encryption. However a more fundamental re-writing is also possible. While it is
typical to take the S-box as a single entity, we have already observed that it
consists of three separate components; the augmented inversion mapping 1/x, the
linear map L, and addition of the constant 0x63. Concern about the algebraic
simplicity of the inversion operation over GF(28 ) lead the designers to introduce
a mixing function (the linear map L) over GF(2), while concern that the input
0 would be mapped to 0 through the two combined operations lead to the ¬nal
addition of the constant.
Yet, it is instructive to view this package as the sequence of independent
operations it truly is [25, 26]. It is then trivial to see that the parallel addition
of sixteen constants 0x63 can be moved (unchanged) through the ShiftRows
operation. It can also be moved (unchanged) through the MixColumns operation.
We might therefore remove the addition of the constant from the encryption
process entirely and, instead, consider it a minor addition to the key schedule.
We can also view the sixteen parallel applications of the linear map L as part of
The Cryptanalysis of the AES - A Brief Survey 5

the di¬usion layer that follows. While making the di¬usion layer slightly more
complicated than that given in the standard description, this separation of the
components of the AES yields a more uni¬ed functional description.
The value of such rewriting has been questioned [12], but it does provide
some additional perspectives on the AES structure. But while there is some
interaction between this line of work and the aims of algebraic cryptanalysis
(see Section 5) these di¬erent perspectives on the AES have yet to yield any
practical cryptanalytic advance. Instead the most successful attacks on the AES
are of an entirely di¬erent nature.


4 Structural Attacks
The most e¬ective attacks on reduced-round variants of the AES are variants of
the Square attack which is due to Knudsen. Since this attack was used against
a predecessor [10] of the AES it was accounted for by the AES designers [11].
In this attack we take a set of 256 plaintexts where the ¬rst byte takes all
possible values. The other 15 bytes of the input can take any value but the
same value in a given byte position must be used across all 256 texts. We will
describe a set of texts that have this property as an integral. Imagine one begins
an AES-round with such an integral. In the following we shall denote the byte-
position containing a variable value with an “a” (for “all”). Consider the actions
of SubBytes, ShiftRows, and MixColumns.

a a a a
SubBytes ShiftRows MixColumns a
- - -
a
a

The AddRoundKey operation adds the same round key to each of the 256 texts
in the integral, therefore any integral before AddRoundKey will yield an integral
after. Consider a second round of transformation.
a a a aaaa
SubBytes ShiftRows a MixColumns a a a a
a a
- - -
a a a aaaa
a a a aaaa

It follows that after two rounds of encryption and for each byte position,
every possible value in a given byte position is taken once and only once in the
set of 256 texts. Now consider a third round.
a a a a SubBytes a a a a a a a a sss s
ShiftRows MixColumns s s s
a a a a - aaa a a a a a s
- -
a a a a aaa a a a a a sss s
a a a a aaa a a a a a sss s

Here s indicates that the sum of the texts in a particular byte can be deter-
mined (and in this case is equal to zero). The interesting part is what happened
6 H. Dobbertin, L. Knudsen, and M. Robshaw

during the MixColumns operation. Before the operation, in each byte position
the 256 values were a permutation of the values 0, . . . , 255. MixColumns com-
bines four bytes to yield one byte in a linear way. This means that after the
application of MixColumns every byte position will be balanced, that is, if we
exclusive-or all 256 values in any single byte position we will get zero as a result.
Note how this property, after three rounds of AES encryption does not depend
on the details of the S-box nor on the value of the secret key.
Such three-round structures can be used to attack the AES reduced to six
rounds (where the ¬rst round consists of AddRoundKey and the last round is
without MixColumns). The structure is used over rounds two to four. Then by
guessing four key bytes in the ¬rst round, four key bytes in the ¬nal application
of AddRoundKey and one key byte in the second-last application of AddRoundKey,
in total nine key bytes, one can compute a candidate value for the sum of the
texts in one byte position after four rounds of encryption. For a structure of 256
plaintexts of the form above, this sum is known to be zero. In fact, there will
be values of the nine key bytes that will return zero as the value of the sum
by chance. So to eliminate false alarms, the attack needs to be repeated a few
times to uniquely determine the correct key bytes. Once the nine key bytes have
been found, we ¬nd the remaining twelve key bytes of the ¬nal application of
AddRoundKey, after which the user-selected key can be derived. Taking advantage
of some advanced observations, there is a more e¬ective extension of this attack.
This can be used to ¬nd the secret key with 6 · 232 chosen plaintexts in a time
equivalent to 244 encryptions and 232 words of memory [15, 22]. There have also
been some further extensions to the basic Square attack, but these require an
explosive increase in the running time [15, 22].
Another kind of structural attack that has been described against the AES
is sometimes referred to as a collision or bottleneck attack. These attacks re-
quire around 232 plaintexts and exploit a three-round structure [17, 24]. These
approaches can be used to attack AES reduced to seven rounds but the running
time is almost the same as an exhaustive search for the key.


5 Algebraic Attacks
We saw in Section 3.1 that the S-box was carefully constructed around inversion
in GF(28 ). As a consequence, if we appeal to our earlier notation (1), then we
have the implicit equation A’1 (S(x))x = 1 for x = 0. Thus there are eight
quadratic equations that relate the bits of S(x) and x. Of these eight equations
seven holds always, while the eighth holds only when x = 0, that is, in 255 of 256
cases. In addition, another 32 quadratic equations can be derived since xy = 1
implies that

x2 y = x, xy 2 = y, x4 y = x3 , and that xy 4 = y 3 .

Each of these equations leads to eight quadratic equations on the bit level and
all of these always hold. The resulting 39 quadratic equations turn out to be a
The Cryptanalysis of the AES - A Brief Survey 7

base for the vector space, over GF(2), of all quadratic equations relating the
input and output bits of the AES S-box.
In every round of the AES, a parallel block of several instances of the S-
box is applied. But everything else that happens in the encryption/decryption
procedure outside the S-boxes is GF(28 )-linear. These observations motivate a
tempting idea. Suppose a plaintext block P and the corresponding ciphertext
block C (or a collection of such pairs) were known. Could we recover the encryp-
tion key K by establishing, and solving, a binary quadratic equation system?
Establishing such a quadratic equation system is easy. The bits of the ex-
panded round keys, which we consider unknowns, are added bitwise (in byte
blocks) to each S-box input. We introduce new variables for the input and out-
put bits of each occurring S-box, and relate them by the quadratic equations
mentioned above. The disadvantage is that this leads to a huge number of bi-
nary variables.
Everything in the AES encryption/decryption algorithm can be described
equally over GF(2) or GF(28 ) with two exceptions. The ¬rst exception is inver-
sion over GF(28 ); this makes it hard to work over GF(2). However, the inversion
operation would be much easier if we could work over GF(28 ). But at this point,
the second exception comes into play. The GF(2)-linear mapping L, used to
modify 1/x in the S-box, appears to prevent an algebraic attack with quadratic
equations over GF(28 ). Indeed, it was the intention of the AES designers to de-
stroy the GF(28 )-structure by taking an a¬ne modi¬cation of 1/x. However, it
was observed [27] that the GF(2)-linear mappings

L : GF(2n ) ’’ GF(2n )

are precisely those, which can be written as polynomials in the form
n
L(x) = ±i x2 ,
i<n

with uniquely determined ±i ∈ GF(2n ) (i < n). Thus the GF(2)-a¬ne map A
i
can be represented as A(x) = i<8 ai x2 + c with coe¬cients in GF(28 ). This
then allows AES encryption to be represented as a sparse system of quadratic
equations over GF(28 ) and there are strong reasons for expecting such a system
to be easier to solve than the corresponding system over GF(2) [27].
There is much discussion and speculation about whether such algebraic at-
tacks might ever be relevant. While some very positive views have been ex-
pressed [9], most researchers are more cautious. Without doubt, the need to ¬nd
powerful elimination techniques for multi-variate equation systems is a signif-
icant topic in cryptography, though not only in the context of block ciphers.
Some well known basic ingredients such as

“ linearization (substitution of monomials by single new variables) and
“ Buchberger™s algorithm (computations of Gr¨bner bases),
o
8 H. Dobbertin, L. Knudsen, and M. Robshaw

have lead to algorithms such as XL (eXtended Linearization), XSL (eXtended
Sparse Linearization), and also the algorithms F4 and F5 due to Faug`re. Various
e
web-links on this topic are available [9]. Unfortunately the complexity of these
algorithms is closely related to very di¬cult problems in algebraic geometry and
commutative algebra, and heuristics are very risky. A recent result leading to a
re-evaluation of the XL algorithm exempli¬es this [14].
The threat posed by algebraic attacks on the AES is di¬cult to quantify. As
things stand, there is little belief that the XSL algorithm”which was explic-
itly formulated to work with the AES equation systems”will work as orginally
hoped. That said, there is no intrinsic reason why new variants of XL or XLS
might not work at some stage in the future.
Instead, the AES system of equations over either GF(2) or GF(28 ) is cur-
rently “best” solved [6] using Gr¨bner basis techniques such as Buchberger™s
o
algorithm or F4 . However there are many complications and there remains much
to understand. Furthermore, recent experimental work [6] has shown that basic
implementations of these algorithms are limited, and memory limitations thwart
attempts to cryptanalyse even the most basic variants of the AES. However all
is not lost for the cryptanalyst.
One frustrating aspect of the experimental work in [6] is that simple changes
to the way the equation systems are presented can have an unpredictable ef-
fect on the solution time. Furthermore, equal-sized equation systems arising
from two very di¬erent AES-variants can take very di¬erent amounts of time
to solve. However, if equal-sized equation systems can take di¬erent times to
solve, then the solving algorithm would seem to be taking advantage of hidden
structure in one of the cases. Thus it might be hoped that additional research
will lead to more e¬cient, potentially AES-speci¬c, solution methods in the
future.
There is currently no solid estimation for the e¬ort of an algebraic attack
against the AES. To break AES in practice remains completely elusive. How-
ever for those interested in a challenge, one example in the Mystery Twister
2005 [2] cryptographic challenge is dedicated to an attack on a small scale vari-
ant of the AES [6] with 64-bit keys.


6 Conclusions
The AES is a de facto world standard with an intended lifespan of 30 years and,
as the successor to DES, has much to live up to. Yet, apart from the currently
speculative threat of algebraic attacks, there are few results since standardisation
that would lead anyone to seriously question the practical security of the AES.
Hopefully, by the time of some future AES5 conference, the true extent of block
cipher algebraic cryptanalysis will be much clearer, but at the time of writing
the AES has reached its ¬fth birthday in very good shape.
The Cryptanalysis of the AES - A Brief Survey 9

References
1. AES web site of ECRYPT:http://www.iaik.tu-graz.ac.at/research/krypto/
AES/
2. Mystery Twister web site: http://www.mystery-twister.com
3. E. Barkan and E. Biham, In how many ways can you write Rijndael?, Proceedings
of Asiacrypt 2002, Lecture Notes on Computer Science, vol. 2501, Springer-Verlag,
Berlin “ New York, 2002.
4. E. Biham and A. Shamir. Di¬erential Cryptanalysis of the Data Encryption Stan-
dard. Springer Verlag, 1993.
5. A. Biryukov, The boomerang attack on 5 and 6-round reduced AES, in these
proceedings, pp. 13“17.
6. C. Cid, S. Murphy and M. Robshaw, Small Scale Variants of the AES,
Proceedings of Fast Software Encryption 2005, Lecture Notes on Com-
puter Science, vol. Springer-Verlag, Berlin “ New York, to appear; see
http://www.isg.rhul.ac.uk/∼ccid/publications.htm
7. J.H. Cheon, M. Kim, K. Kim, J.-Y. Lee, and S. Kang, Improved impossible di¬er-
ential cryptanalysis of Rijndaeland Crypton, In 3rd International Conference on
Information Security and Cryptology (ICISC 2001), volume 2288 of Lecture Notes
in Computer Science 2288, Springer-Verlag, Berlin “ New York, 2001, pp. 39“49.
8. K. Chun, S. Kim, S. Lee, S. Sung, and S. Yoon, Di¬erential and linear cryptanalysis
for 2-round SPNs, Information Processing Letters 87, 2003, pp. 277“282.
9. N. Courtois: Is AES a secure cipher? http://www.cryptosystem.net/aes/
10. J. Daemen, L. Knudsen, and V. Rijmen, The block cipher Square, In Fast Soft-
ware Encryption, 4th International Workshop, FSE™97, Haifa, Israel, January 1997,
E. Biham(ed.), Lecture Notes in Computer Science, vol. 1267, Springer-Verlag,
Berlin “ New York, 1997, pp. 149“165.
11. J. Daemen and V. Rijmen, AES Proposal: Rijndael. Version 2.0, available via
http://www.crsc.nist.gov.
12. J. Daemen and V. Rijmen, Answers to “New Observations on Rijndael”. Archived
via http://www.crsc.nist.gov.
13. J. Daemen and V. Rijmen, The Design of Rijndael. AES - The Advanced Encryp-
tion Standard, Springer-Verlag, Berlin “ New York, 2002.
14. C. Diem, The XL-algorithm and a conjecture from commutative Algebra, Asiacrypt
2004, December 2004, Korea, Lecture Notes in Computer Science, to appear.
15. N. Ferguson, J. Kelsey, B. Schneier, M. Stay, D. Wagner, and D. Whiting, Improved
cryptanalysis of Rijndael, Fast Software Encryption, 7th International Workshop,
FSE 2000, B. Schneier (ed.), New York, April 2000, Lecture Notes in Computer
Science, vol. 1978, Springer-Verlag, Berlin “ New York, 2001, pp. 213“230.
16. N. Ferguson, R. Shroeppel, and D. Whiting, A simple algebraic representa-
tion of the AES, Selected Areas in Cryptography, SAC 2001, S. Vaudenay and
A.M. Youssef (editors), Lecture Notes in Computer Science, vol. 2259, Springer-
Verlag, Berlin “ New York, 2001, pp. 103“111.
17. H. Gilbert and M. Minier., A collision attack on 7 rounds of Rijndael, 3rd Advanced
Encryption Standard Candidate Conference, National Institute of Standards and
Technology, April 2000, pp. 230“241.
18. S. Hong, S. Lee, J. Lim, J. Sung, and D. Cheon, Provable security against di¬er-
ential and linear cryptanalysis for the spn structure, Fast Software Encryption,
7th International Workshop, FSE 2000, B. Schneier (ed.), New York, April 2000,
Lecture Notes in Computer Science, vol. 1978, Springer-Verlag, Berlin “ New York,
2001, pp. 273“283.
10 H. Dobbertin, L. Knudsen, and M. Robshaw

19. L. Keliher, Re¬ned analysis of bounds related to linear and di¬erential cryptanalysis
for the AES these proceedings, pp. 45“60.
20. L. Keliher, H. Meijer, and S. Tavares, New method for upper bounding the max-
imum average linear hull probability for SPNs Advances in Cryptology - EURO-
CRYPT™01, Birgit P¬tzmann(ed.), Lecture Notes in Computer Science, vol. 2045,
Springer-Verlag, Berlin “ New York, 2001, pp. 420“436.
21. L. Keliher, H. Meijer, and S. Tavares, Improving the upper bound on the maximum
average linear hull probability for Rijndael, In Selected Areas in Cryptography,
8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August
16-17, 2001, S. Vaudenay and A. M. Youssef (ed.), Lecture Notes in Computer
Science, vol. 2259, Springer-Verlag, Berlin “ New York, 2001, pp. 112“128.
22. S. Lucks, Attacking seven rounds of Rijndael under 192-bit keys and 256-bit keys,
Proceedings of the 3rd Advanced Encryption Standard Candidate Conference, Na-
tional Institute of Standards and Technology, April 2000, pp. 215“229.
23. M. Matsui, The First Experimental Cryptanalysis of the Data Encryption Stan-
dard Advances in Cryptology - CRYPTO™94, Yvo Desmedt (ed.), Lecture Notes in
Computer Science, vol. 839, Springer-Verlag, Berlin “ New York, 1994, pp. 26“39.
24. M. Minier, A three rounds property of the AES, these proceedings, pp. 18“29.
25. S. Murphy and M. Robshaw, New Observations on Rijndael. August 7, 2000.
Archived via http://www.crsc.nist.gov.
26. S. Murphy and M. Robshaw, Further Comments on the Structure of Rijndael.
August 17, 2000. Archived via http://www.crsc.nist.gov.
27. S. Murphy and M. Robshaw, Essential algebraic structure within the AES, Ad-
vances in Cryptology “ CRYPTO 2002, Lecture Notes in Computer Science, vol.
2442, Springer-Verlag, Berlin “ New York, 2002, pp. 1-16.
28. National Institute of Standards and Technology: Advanced encryption standard,
FIPS 46-3, US Department of Commerce, Washington D.C., October 1999.
29. National Institute of Standards and Technology: Advanced encryption standard,
FIPS 197, US Department of Commerce, Washington D.C., November 2001.
30. S. Park, S.H. Sung, S. Chee, E.-J. Yoon, and J. Lim, On the security of Rijndael-like
structures against di¬erential and linear cryptanalysis, Advances in Cryptology -
ASIACRYPT 2002, Y. Zheng (ed.), Lecture Notes in Computer Science, vol. 2501,
Springer-Verlag, Berlin “ New York, 2002, pp. 176“191.
31. S. Park, S.H. Sung, S. Lee, and J. Lim, Improving the upper bound on the maximum
di¬erential and the maximum linear hull probability for SPN structures and AES,
Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Sweden,
February 2003, T. Johansson (ed.), Lecture Notes in Computer Science, vol. 2887,
Springer-Verlag, Berlin “ New York, 2003, pp. 247“260.
32. R.C.W. Phan, Classes of impossible di¬erentials of the advanced encryption stan-
dard, Electronics Letters 38(11), 2002, pp. 508“510.
33. R.C.W. Phan, Impossible di¬erential cryptanalysis of 7-round Advanced Encryp-
tion Standard, Information Processing Letters 91, 2004, pp. 33“38.
34. R.C.W. Phan and M.U. Siddiqi, Generalised impossible di¬erentials of the Ad-
vanced Encryption Standard, Electronics Letters 37(14), 2001, pp. 896“898.
35. H. Raddum, More Dual Rijndaels, these proceedings, pp. 144“150.
The Boomerang Attack on 5 and 6-Round
Reduced AES

Alex Biryukov

Katholieke Universiteit Leuven, Dept. ESAT/SCD-COSIC,
Kasteelpark Arenberg 10,
B“3001 Heverlee, Belgium
http://www.esat.kuleuven.ac.be/∼abiryuko/



Abstract. In this note we study security of 128-bit key 10-round AES
against the boomerang attack. We show attacks on AES reduced to 5
and 6 rounds, much faster than the exhaustive key search and twice
faster than the “Square” attack of the AES designers. The attacks are
structural and apply to other SPN ciphers with incomplete di¬usion.



1 Introduction
In this paper we study security of 128-bit key AES [4] against the boomerang at-
tack [7]. The boomerang attack was developed in 1999 after the AES competition
was already running. This attack sometimes allows to break more rounds than
the conventional di¬erential or linear attacks, especially for the ciphers with few
but carefully designed rounds (for example, see an attack on SAFER++ [2]).
In this paper we show attacks on AES reduced to 5 and 6 rounds. Six round
attack has complexity of 271 data and steps of analysis (measured in 6-round
encryptions). The attack is twice faster than the “Square” attack of the designers
of the AES in terms of time complexity which is a dominant factor, but has
much higher data complexity. The boomerang attack on AES is less e¬cient
than the partial sum attack [5]. See Table 1 for comparison of our attacks with
the previous results on a 128-bit key AES.



2 Boomerang Attack on SPNs with Incomplete Di¬usion
Boomerang attack is a chosen plaintext-adaptive chosen ciphertext attack. It is
an extension of di¬erential cryptanalysis and works on quartets of data (P, P ),

This work was supported in part by the Concerted Research Action (GOA) Me¬sto-
2000/06 of the Flemish Government and in part by the European Commission
through the IST Programme under Contract IST-2002-507932 ECRYPT. The in-
formation in this document re¬‚ects only the author™s views, is provided as is and no
guarantee or warranty is given that the information is ¬t for any particular purpose.
The user thereof uses the information at its sole risk and liability.

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 11“15, 2005.
c Springer-Verlag Berlin Heidelberg 2005
12 A. Biryukov

Table 1. Comparison of our results with previous attacks on AES

Rounds Dataa Typeb Workloadc Memorya
Attack Key size
211 240 211
Square attack [4] 128 5 of 10 CP
232 272 232
Square attack [4] 128 6 of 10 CP
232 2128 280
Collision attack [6] 128 7 of 10 CP
234.6 244 232
Partial sum [5] 128 6 of 10 CP
7 of 10 2128 “2119 2120 264
Partial sum [5] 128 CP
29.5 31
240
Imposs. di¬. [1] 128 5 of 10 2 CP 2
291.5 2122 2?
Imposs. di¬. [3] 128 6 of 10 CP
239 239 233
Our Boomerang attack 128 5 of 10 CP/ACC
271 271 233
Our Boomerang attack 128 6 of 10 CP/ACC
a
Expressed in the number of blocks.
b
CP “ Chosen Plaintext, ACC “ Adaptive Chosen Ciphertext.
c
Expressed in equivalent number of encryptions.



(Q, Q ). The attack works when encryption E() can be split into E = E1 —¦ E0 ,
where E0 is weak in encryption direction and E1 is weak in decryption direction.
We refer the reader to [7] for further details.
In this section we present a generic method of breaking ¬ve and six round
substitution-permutation networks (SPNs) using a boomerang distinguisher.
The attacks that we will show will be structural in the sense that they will not
use speci¬c properties of S-boxes or of the mixing layer, but will use only the
fact that di¬usion is incomplete (which is the case for many ciphers, including
the AES).
We will describe this attack on an example of Rijndael-like cipher with layers
of 16, 8x8-bit S-boxes, and Rijndael-like di¬usion involving ShiftRows and Mix-
Columns (though exact constants in the MixColumns matrix will be irrelevant
to the attack).
The ¬ve round attack will be as follows:

1. Prepare a pool of plaintexts {Pi }, i = 0, . . . 232 ’ 1 which have all possible
values in four bytes (which will appear in the same column before the Mix-
Columns) and arbitrary constant in the other bytes. Encrypt the pool and
obtain a pool of 232 ciphertexts {Ci }.
2. Construct a pool of modi¬ed ciphertexts: Di = Ci • ∇, where ∇ is a ¬xed
non-zero di¬erence with only one active S-box (for example, a non-zero dif-
ference in the ¬rst byte and zero di¬erence in 15 other bytes).
3. Decrypt the pool {Di } to obtain a pool {Qi } of 232 new plaintexts.
4. Sort the pool {Qi } by the bytes corresponding to eight inactive S-boxes.
Pick only those pairs Qi , Qj which have zero di¬erence in these 8 bytes. If
none found go to step 1.
5. For each of the quartets Pi , Pj , Qi , Qj that pass step 4, guess the 32-bit
key value that enters the four S-boxes corresponding to non-constant bytes.
Using the guessed key value partially encrypt one round and check that
The Boomerang Attack on 5 and 6-Round Reduced AES 13

00
11 11
00 11
00 11
00 ’22 00
11
11
00 00
11
00
11 000
111
000
111
111 111
000 000 0000
1111
11
00 00
11 11
00 11
00 00
11
00
11 11
00
11
00 000
111
000
111
000 000
111 111 0000
1111
P=2
11
00 00
11 00
11 00
11 00
11
00
11 11
00
11
00 000
111
000
111
000 000
111 111 1111
0000
00000
11111 1111
0000
11111
00000 0000
1111
00000
11111 1111
0000
00000
11111 1111
0000
P=1
00000
11111 0000
1111
00000
11111 0000
1111
00000
11111 1111
0000
11111
00000 1111
0000
11111
00000 1111
0000
00000
11111 1111
0000
11
00 00000
11111 00
11 00
11 0000
1111
00
11 11111
00000 11
00 00
11 0000
1111
00
11 00000
11111 11
00 00
11 1111
0000
00000
11111 1111
0000
11111
00000 0000 ’13.5
1111
11111
00000 1111
0000
11111
00000 0000
1111
P=2
00000
11111 0000
1111
11111
00000 1111
0000
P=1
11111
00000 1111
0000
00000
11111 1111
0000
00000
11111 1111
0000
11111
00000 1111
0000
00
11 00
11 11
00 00
11 00
11 11
00 000
111 111
000 1111
0000
00000
11111
11
00 11
00 00
11 11
00 00
11 11
00 000
111 000
111 1111
0000
11111
00000
11
00 00
11 00
11 00
11 00
11 11
00 000
111 000
111 1111
0000
11111
00000 0000
1111
00000
11111 1111
0000
11111
00000 1111
0000
00000
11111 1111
0000
P=1
11111
00000 1111
0000
11111
00000 0000
1111
00000
11111 1111
0000
11111
00000 0000
1111
11111
00000 1111
0000
11111
00000 0000 ’32
1111
11 11 11 11 11 11 11 11
00 00 00 00 00 00 00 00
11 11 11 11 11 11 11 11
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00
11 11 11 11 11 11 11 11111
00000 00 00 00 00 00 000 000
11 11 11 11 11 111 111
00
11
11 11 11 11 111 111
00 00 00 00 000 000
11
00 111 111 111
000 000 000
111 111
000 000
111 111
000 000
11 11 11 11 11 11 11 11
00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00
11 11 11 11 11 11 11 11 11111
00000 00 00 00 00 00 000 000
11 11 11 11 11 111 111
00 00 00 00 000 000
11 11 11 11 111 111
000 000 000
111 111 111 P=2
11 11 11 11 11 11 11 11
00 00 00 00 00 00 00 00
11
00 00000
11111 11 11 11 11
00 00 00 00
11 11 11
00 00 00000 000 000
111 111 111
11111
00000 0000
1111
00000
11111 0000
1111
00000
11111 0000
1111
00000
11111 0000
1111
00000
11111 0000
1111
00000
11111 1111
0000
00000
11111 0000
1111
P=1 P=1
11111
00000 0000
1111
11111
00000 1111
0000
11111
00000 0000
1111
11
00 11111
00000 00
11 0000
1111
00
11 11111
00000 11
00 1111
0000
00
11 00000
11111 11
00 0000
1111


Fig. 1. Schematic description of a boomerang quartet for Rijndael reduced to ¬ve
rounds

resulting di¬erence is in a single active S-box, which is a 22-bit ¬ltering
condition for each pair (Pi , Pj ) and (Qi , Qj ). This gives a 44-bit condition
in total for both sides of the boomerang in the case of common 4-tuples
of active S-boxes. However with probability half we will have no common
4-tuples, i.e. all the twelve active S-boxes (4 from the (Pi , Pj ) pair and 8
from the (Qi , Qj ) pair) non-overlapping. We will then pick key-candidates
that are suggested at least twice.

See Figure 1 for a schematic description of the boomerang distinguisher used in
this 5-round attack. The rectangles in the ¬gure denote the layers of S-boxes,
and the gray squares indicate the active S-boxes. Arrows represent the cost of
pattern propagation in terms of probability.


Complexity of the 5-Round Attack. Analysis of the complexity of the at-
tack described above is as follows: Each pool of 232 texts contains 263 pairs with
di¬erence in the four relevant bytes. From these pairs 263 /222 = 241 will have a
single active S-box after one round1 . After the second round we will have four
active S-boxes. After the 3rd round all bytes will be active. From the bottom up
direction we will have one round crossed with probability one, with a truncated
di¬erential that starts with one active S-box and ends with four active S-boxes.
At this point we need that after the next S-box layer the di¬erence in these four
active S-boxes would be the same. This happens with probability 2’32 . Then
we can switch to the last face of the boomerang, where the e¬ect of the mixing
of the 3rd round can then be undone with probability one and we will get four
active S-boxes after the S-box layer of the 3rd round. We will have to pay 2’13.5

The chance of going from 4 active S-boxes to one is 4 · 28 /232 = 2’22 , since we do
1

not care about the location of the single active S-box.
14 A. Biryukov

in probability for the four active S-box di¬erence to turn into two active S-box
di¬erence after this S-box layer and the MixColumns which is just above it. From
that point we let our truncated di¬erential run freely with probability 1. As a
result we will obtain a new pair of plaintexts with some di¬erence in eight bytes
and zero di¬erence in the other eight bytes. This is our 64 ’ log(6)-bit ¬ltering
condition for the good boomerang quartets (the ’ log(6) appears since we do
not ¬x the places of the two active S-boxes).
We pick about 26 pools in which we will have 241 · 26 · 2’13.5 · 2’32 ≈ 3 good
boomerangs returning back. The average amount of false quartets which satisfy
our initial ¬ltering condition is 263 · 26 · 2’64 · 6 = 192.
In the simplest case when the boomerang returns in the same four bytes as
it was sent we perform a guess of the 32-bit key and check it against two sides of
the boomerang Pi , Pj and Qi , Qj whether in both cases it leads to a single active
S-box after one round. This gives a 44-bit ¬ltration condition which leaves only
the correct key guess with probability 1 ’ 2’12 . However with probability 1/2 it
may happen that for the two boomerang pairs active 4-tuples of the output pair
(Qi , Qj ) will be di¬erent from those of the input pair (Pi , Pj ). In this case we
independently guess 32-bits of the key corresponding to the input four bytes for
each pair and leave only those keys that lead to a single active S-box after the
¬rst round. We expect at least two good boomerang quartets in our pools and
thus the correct key would be counted at least twice. Note that we have about 100
noisy pairs (those with non-overlapping 4-tuples) each of which suggests about
4 · 28 candidates for the 32-bit key. That means that we may have a few wrong
keys suggested due to the birthday collisions together with the correct key sug-
gested by the good boomerangs. The same analysis can be performed in parallel
on another 4-tuple to produce few candidates for another 32-bit part of the key.
Knowing a few candidates for at least half of the ¬rst subkey we can repeat the at-
tack with much less data and smaller complexity to achieve the full key-recovery.
Total complexity of this 5-round attack is 238 chosen plaintext/adaptive cho-
sen ciphertext queries and 238 time steps which mainly would be spent on en-
crypting and sorting the data. The memory required by the attack is 232 blocks
or 236 bytes.

Extension to 6-Rounds of AES. The attack described above can be extended
by one round at the bottom at the cost of guessing 32-bits of the key of the 6th
round. We double the number of pools from 26 to 27 to get 4-6 good quartets for
better ¬ltration. We expect that at least 2-3 good quartets will have overlapping
4-tuples between the P ™s and the Q™s which provides 2’12 ¬ltration power. Thus
we will get about 232 · 100 · 2’12 ≈ 227 candidates for 64-bit partial key: 32-bits
at the top and 32-bits at the bottom. The correct key will be suggested at least
twice, and the wrong keys would likely be suggested only once, since we are
below the birthday bound for a 64-bit event. Thus we expect that all the wrong
pairs will be ¬ltered out at the key-recovery step. Finally, complexity of this 6
round attack will be 239 chosen plaintexts, 271 adaptively chosen ciphertexts,
the same amount of time steps spent mainly encrypting the texts and 237 bytes
of memory.
The Boomerang Attack on 5 and 6-Round Reduced AES 15

It seems likely that this attack may be converted to break 7-rounds of the
192-bit key AES.



3 Conclusions
We have shown boomerang attacks on 5 and 6 round AES much faster than
exhaustive search. We notice that AES has many truncated di¬erentials with
probability one spanning up to three rounds, however they are quite expensive in
terms of probability when trying to extend them at either end of the boomerang
distinguisher. The attacks presented in this paper are twice more e¬cient than
the “Square” attack but are less e¬cient than the partial sum attack. This may
mean that AES has su¬cient security margin against the boomerang attacks.
The attacks presented in this paper are structural attacks (i.e. they do not use
speci¬c properties of the underlying cipher) applicable to arbitrary 5-6 round
SPNs with incomplete di¬usion. It is an open problem whether the middle-
round gaining trick, for example as used in a recent attack on Safer++ [2] would
be applicable to the AES.



References
[1] E. Biham and N. Keller, “Cryptanalysis of reduced variants of Rijn-
dael,” in O¬cial public comment for Round 2 of the Advanced Encryp-
tion Standard development e¬ort, 2000. Available at http://csrc.nist.gov/
encryption/aes/round2/conf3/papers/35-ebiham.pdf.
[2] A. Biryukov, C. D. Canni´re, and G. Dellkrantz, “Cryptanalysis of SAFER++,”
e
in Proceedings of Crypto™03 (D. Boneh, ed.), Lecture Notes in Computer Sci-
ence, Springer-Verlag, 2003. NES/DOC/KUL/WP5/028. Full version available at
http://eprint.iacr.org/2003/109/.
[3] J. H. Cheon, M. Kim, K. Kim, J.-Y. Lee, and S. Kang, “Improved impossible
di¬erential cryptanalysis of Rijndael and Crypton,” in Proceedings of ICISC™01
(K. Kim, ed.), no. 2288 in Lecture Notes in Computer Science, pp. 39“49, Springer-
Verlag, 2001.
[4] J. Daemen and V. Rijmen, The Design of Rijndael: AES ” The Advanced En-
cryption Standard . Springer-Verlag, 2002.
[5] N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, and D. Whiting,
“Improved cryptanalysis of Rijndael,” in Fast Software Encryption, FSE 2000
(B. Schneier, ed.), vol. 1978 of Lecture Notes in Computer Science, pp. 213“230,
Springer-Verlag, 2001.
[6] H. Gilbert and M. Minier, “A collision attack on seven rounds of Rijndael,” in Pro-
ceedings of the Third AES Candidate Conference, pp. 230“241, National Institute
of Standards and Technology, Apr. 2000.
[7] D. Wagner, “The boomerang attack,” in Fast Software Encryption, FSE™99 (L. R.
Knudsen, ed.), vol. 1636 of Lecture Notes in Computer Science, pp. 156“170,
Springer-Verlag, 1999.
A Three Rounds Property of the AES

Marine Minier

Universit´ Paris 8 - INRIA,
e
Projet CODES,
Domaine de Voluceau-Rocquencourt,
B.P. 105, 78 153 Le Chesnay Cedex - France
marine.minier@inria.fr



Abstract. Rijndael is the new Advanced Encryption Standard designed
by V. Rijmen and J. Daemen and chosen as AES by the NIST in October
2000. Surprisingly, the number of cryptanalyses against this algorithm is
very low in depict of many e¬orts furnished to break it.
This paper presents a stronger property than the one used in the Bot-
tleneck Cryptanalysis [GM00]. Unfortunately, this property could not be
used to mount a more e¬cient cryptanalysis than the Bottleneck Attack
because it is not possible to improve the complexity of the four rounds
distinguisher used in this attack. So, the complexity of the Bottleneck
Attack (recalled in this paper) is always 2144 AES executions using 232
plaintexts.



1 Introduction
In the initial article describing Rijndael [DR98], V. Rijmen and J. Daemen wrote :
“For the di¬erent block lengths of Rijndael, no extensions to 7 rounds [of a known
attack] faster than an exhaustive key search have been found”. Of course, since
1998, some attacks reached this aim. In the case of key length equal to 192 or
256 bits, Ferguson et al., in [FKS+ 00], presented an improvement of the Square
Attack [DR98] permitting to cryptanalyse an eight-rounds version of Rijndael
with a complexity equal to 2204 executions and 2128 ’ 2119 plaintexts. S. Lucks
presented in [Luc01] an other improvement of the Square Attack using a par-
ticular weakness of the key schedule against a seven-rounds version of Rijndael
where 2194 executions are required for a number of chosen plaintexts equal to
232 . H. Gilbert and M. Minier in [GM00] also presented an attack against a
seven-rounds version of Rijndael (known under the name of “Bottleneck At-
tack”) using a stronger property on three inner rounds than the one used in the
Square Attack in order to mount an attack against a seven-rounds version of
Rijndael requiring 2144 cipher executions with 232 chosen plaintexts. In the case
of a 128 bits key lenght, for a seven-rounds version of Rijndael, only two attacks
are known. The ¬rst is due to Ferguson et al. in [FKS+ 00] and requires 2120
cipher executions for a number of plaintexts equal to 2128 ’ 2119 . The second
one, due to H. Gilbert and M. Minier in [GM00], is a marginal speed up of the
128-bits key search requiring 232 chosen plaintexts.

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 16“26, 2005.
c Springer-Verlag Berlin Heidelberg 2005
A Three Rounds Property of the AES 17

During the two last years, some new results was published concerning essen-
tially the algebraic structure of the AES S-box. Those results use a potential
weakness of the AES : there is only one non-linear operation in the AES round
function, the inversion in the Galois Field GF (28 ). So, it is possible to derive
this inversion application into quadratic equations that are true with probability
one. In [CP02], N. Courtois and J. Pieprzyk presents the quadratic equations
given by the AES S-box on GF (2). The authors use those quadratic equations
to express all input/output bytes of each round and generate a huge system to
solve. They apply the XL and the XSL algorithms to obtain the solutions of the
system generated. An other article presented at Crypto™02 by S. Murphy and
M. Robshaw [MR02] also describe the algebraic structure of the AES S-box and
the quadratic equations of this one but on the ¬eld GF (256).
The aim of this paper is to present a ”new property” on three inner AES
rounds stronger than the one used in the Bottleneck Attack described in [GM00].
This ”new property” is very similar to the bottleneck property but as now does
not permit to improve any attack due to the same number of dependent bytes
implied in the four rounds distinguisher. This property is, however, stronger
because the number of deduced collisions is bigger.
This paper is organized as follow: Section 2 provides a brief outline of the
AES. Section 3 describes the 3-rounds property and the 4-rounds distinguisher
used in the Bottleneck Attack. Section 4 presents the ”new property”. Section 5
describes, one more time, the bottleneck attack on seven rounds of the AES for
a 128 bits block and a 192 or 256 bits key. Section 6 concludes this paper.


2 A Brief Outline of the AES
The AES is a symmetric block cipher using a parallel and byte-oriented structure.
The key length and the block length are variable and are equal to 128, 192 or
256 bits. The current block is represented by a matrix of bytes. We focus from
now on a 128-bits block represented by a 4 — 4 matrix of bytes :

b0,0 b0,1 b0,2 b0,3
b b1,1 b1,2 b1,3
B = 1,0
b2,0 b2,1 b2,2 b2,3
b3,0 b3,1 b3,2 b3,3

The number of rounds nr is also variable : 10, 12 or 14, depending on the
block length and on the key length. The key schedule derives nr + 1 128-bits
round keys k0 to knr from the master key k of variable length.
The round function, repeated nr ’ 1 times, is composed of four basic trans-
formations, all linear except the ¬rst one :

“ SubBytes : a bytewise transformation that applies on each byte of the current
block an 8-bits to 8-bits non linear S-box (that we call S) composed by the
inversion in the Galois Field GF (256) and by an a¬ne transformation.
18 M. Minier

“ ShiftRows: a linear mapping that rotates on the left all the rows of the
current matrix (0 for the ¬rst row, 1 for the second, 2 for the third and 3 for
the fourth)
“ MixColumn: another linear mapping represented by a 4 — 4 matrix chosen
for its good properties of di¬usion (see [DR02]). Each column of the input
matrix is multiplied by the MixColumns matrix in the Galois Field GF (256)
that provides the corresponding column of the output matrix. We denote by
ai,j for i and j from 0 to 3, the coe¬cients of the MixColumns matrix.
“ AddRoundKey : a simple x-or operation between the input matrix and the
subkey of the current round denoted by ki .
Those nr ’ 1 rounds are surrounded at the top by an initial key addition
with the subkey k0 and at the bottom by a ¬nal transformation composed by a
call to a round function where the MixColumns operation is omitted.


3 The Three-Rounds Property and the Four-Rounds
Distinguisher
We now describe the three inner rounds property used in [GM00] and the four
inner rounds distinguisher deduced.

3.1 The Three-Rounds Property
We note Y, Z, R and S the di¬erent intermediate input/output states of three
consecutive inner rounds as noticed in ¬gure 1.
We focus from now on an input block Y with its three left columns ¬xed.
The most at right column, marked on ¬gure 1, is composed by one active byte
y which takes all possible values between 0 and 255 and by a triplet c equal to
(c0 , c1 , c2 ) of constant bytes which will represent a parameter. More formally, we
note Y0,3 = y, Y1,3 = c0 , Y2,3 = c1 and Y3,3 = c2 .
In the same way, we use the following notations for some particular bytes
marked on ¬gure 1. So, we denote Z0,3 = z0 , Z1,3 = z1 , Z2,3 = z2 , Z3,3 = z3 ,
R0,3 = r0 , R1,0 = r1 , R2,1 = r2 , R3,2 = r3 and S0,3 = s.
So, let us analyze how the Z, R and S particular bytes z0 to z3 , r0 to r3 and
s can be seen as c-dependent and key-dependent functions of the y input byte.
“ After the ¬rst round, the y ’ z0 [y] one to one function is independent from
c

the value of the c 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 values
entirely determined by four key-dependent bytes. More formally, there exists
4 key-dependent constants k1,i,0 for i = 0..3 such that

zi = ai,0 · S(y) + k1,i,0 , i = 0..3

where S represents the AES S-box.
A Three Rounds Property of the AES 19

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. 1. The Three Inner Rounds Property


“ After the second round, each of the four bytes ri [y], i = 0..3 is a one to one
function of the corresponding zi [y] byte entirely determined by one single
unknown byte that is entirely determined by c and the key. The quartet of
bytes (r0 , r1 , r2 , r3 ) of R marked on ¬gure 1 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 1 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.

. 1
( 7)



>>