ńņš. 1 |

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

HĖ

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 |