5. Simplicity of description.

In [Ny94] several methods are given to construct S-boxes that satisfy the first three criteria. For

invertible S-boxes operating on bytes, the maximum input/output correlation can be made as

low as 2’ and the maximum value in the EXOR table can be as low as 4 (corresponding to a

3

difference propagation probability of 2’ ).

6

We have decided to take from the candidate constructions in [Ny94] the S-box defined by the

mapping x ’ x’ in GF(2 ).

1 8

By definition, the selected mapping has a very simple algebraic expression. This enables

algebraic manipulations that can be used to mount attacks such as interpolation attacks

[JaKn97]. Therefore, the mapping is modified by composing it with an additional invertible

affine transformation. This affine transformation does not affect the properties with respect tot

the first three criteria, but if properly chosen, allows the S-box to satisfy the fourth criterion.

We have chosen an affine mapping that has a very simple description per se, but a

complicated algebraic expression if combined with the ˜inverse™ mapping. It can be seen as

modular polynomial multiplication followed by an addition:

b( x ) = ( x 7 + x 6 + x 2 + x ) + a ( x )( x 7 + x 6 + x 5 + x 4 + 1) mod x 8 + 1

The modulus has been chosen as the simplest modulus possible. The multiplication polynomial

has been chosen from the set of polynomials coprime to the modulus as the one with the

simplest description. The constant has been chosen in such a way that that the S-box has no

fixed points (S-box(a) = a) and no ™opposite fixed points' (S-box(a) = a ).

Note: other S-boxes can be found that satisfy the criteria above. In the case of suspicion of a

trapdoor being built into the cipher, the current S-box might be replaced by another one. The

cipher structure and number of rounds as defined even allow the use of an S-box that does

not optimise the differential and linear cryptanalysis properties (criteria 2 and 3). Even an S-

box that is “average” in this respect is likely to provide enough resistance against differential

and linear cryptanalysis.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

7.3 The MixColumn transformation

MixColumn has been chosen from the space of 4-byte to 4-byte linear transformations

according to the following criteria:

1. Invertibility;

2. Linearity in GF(2);

3. Relevant diffusion power;

4. Speed on 8-bit processors;

5. Symmetry;

6. Simplicity of description.

4

Criteria 2, 5 and 6 have lead us to the choice to polynomial multiplication modulo x +1. Criteria

1, 3 and 4 impose conditions on the coefficients. Criterion 4 imposes that the coefficients have

small values, in order of preference ˜00™, ™01™, ™02™, ™03™¦The value ˜00™ implies no processing

at all, for ˜01™ no multiplication needs to be executed, ˜02™ can be implemented using xtime

and ˜03™ can be implemented using xtime and an additional EXOR.

The criterion 3 induces a more complicated conditions on the coefficients.

7.3.1 Branch number

In our design strategy, the following property of the linear transformation of MixColumn is

essential. Let F be a linear transformation acting on byte vectors and let the byte weight of a

vector be the number of nonzero bytes (not to be confused with the usual significance of

Hamming weight, the number of nonzero bits). The byte weight of a vector is denoted by W( a).

The Branch Number of a linear transformation is a measure of its diffusion power:

Definition: The branch number of a linear transformation F is

mina≠0 (W(a) + W(F(a))) .

A non-zero byte is called an active byte. For MixColumn it can be seen that if a state is applied

with a single active byte, the output can have at most 4 active bytes, as MixColumn acts on the

columns independently. Hence, the upper bound for the branch number is 5. The coefficients

have been chosen in such a way that the upper bound is reached. If the branch number is 5, a

difference in 1 input (or output) byte propagates to all 4 output (or input) bytes, a 2-byte input

(or output) difference to at least 3 output (or input) bytes. Moreover, a linear relation between

input and output bits involves bits from at least 5 different bytes from input and output.

7.4 The ShiftRow offsets

The choice from all possible combinations has been made based on the following criteria:

1. The four offsets are different and C0 = 0;

2. Resistance against attacks using truncated differentials [Kn95];

3. Resistance against the Square attack [DaKnRi97];

4. Simplicity.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ lasoporP SEA

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

QHPHD' QDR-

QHPML5 WQHFQL9

For certain combinations, attacks using truncated differentials can tackle more rounds

(typically only one) than for other combinations. For certain combinations the Square attack

can tackle more rounds than others. From the combinations that are best with respect to

criteria 2 and 3, the simplest ones have been chosen.

7.5 The key expansion

The key expansion specifies the derivation of the Round Keys in terms of the Cipher Key. Its

function is to provide resistance against the following types of attack:

• Attacks in which part of the Cipher Key is known to the cryptanalyst;

• Attacks where the Cipher Key is known or can be chosen, e.g., if the cipher is used

as the compression function of a hash function[Kn95a];

• Related-key attacks [Bi93], [KeScWa96]. A necessary condition for resistance

against related-key attacks is that there should not be two different Cipher Keys that

have a large set of Round Keys in common.

The key expansion also plays an important role in the elimination of symmetry:

• Symmetry in the round transformation: the round transformation treats all bytes of a

state in very much the same way. This symmetry can be removed by having round

constants in the key schedule;

• Symmetry between the rounds: the round transformation is the same for all rounds.

This equality can be removed by having round-dependent round constants in the

key schedule.

The key expansion has been chosen according to the following criteria:

• It shall use an invertible transformation, i.e., knowledge of any Nk consecutive words

of the Expanded Key shall allow to regenerate the whole table;

• Speed on a wide range of processors;

• Usage of round constants to eliminate symmetries;

• Diffusion of Cipher Key differences into the Round Keys;

• Knowledge of a part of the Cipher Key or Round Key bits shall not allow to calculate

many other Round Key bits.

• Enough non-linearity to prohibit the full determination of Round Key differences from

Cipher Key differences only;

• Simplicity of description.

In order to be efficient on 8-bit processors, a light-weight, byte oriented expansion scheme has

been adopted. The application of SubByte ensures the non-linearity of the scheme, without

adding much space requirements on an 8-bit processor.

7.6 Number of rounds

We have determined the number of rounds by looking at the maximum number of rounds for

which shortcut attacks have been found and added a considerable security margin. (A shortcut

attack is an attack more efficient than exhaustive key search.)

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

For Rijndael with a block length and key length of 128 bits, no shortcut attacks have been

found for reduced versions with more than 6 rounds. We added 4 rounds as a security margin.

This is a conservative approach, because:

• Two rounds of Rijndael provide “full diffusion” in the following sense: every state bit

depends on all state bits two rounds ago, or, a change in one state bit is likely to

affect half of the state bits after two rounds. Adding 4 rounds can be seen as

adding a “full diffusion” step at the beginning and at the end of the cipher. The high

diffusion of a Rijndael round is thanks to its uniform structure that operates on all

state bits. For so-called Feistel ciphers, a round only operates on half of the state

bits and full diffusion can at best be obtained after 3 rounds and in practice it

typically takes 4 rounds or more.

• Generally, linear cryptanalysis, differential cryptanalysis and truncated differential

attacks exploit a propagation trail through n rounds in order to attack n+1 or n+2

rounds. This is also the case for the Square attack that uses a 4-round propagation

structure to attack 6 rounds. In this respect, adding 4 rounds actually doubles the

number of rounds through which a propagation trail has to be found.

For Rijndael versions with a longer Key, the number of rounds is raised by one for every

additional 32 bits in the Cipher Key, for the following reasons:

• One of the main objectives is the absence of shortcut attacks, i.e., attacks that are

more efficient than exhaustive key search. As with the key length the workload of

exhaustive key search grows, shortcut attacks can afford to be less efficient for

longer keys.

• Known-key (partially) and related-key attacks exploit the knowledge of cipher key

bits or ability to apply different cipher keys. If the cipher key grows, the range of

possibilities available to the cryptanalyst increases.

As no threatening known-key or related-key attacks have been found for Rijndael, even for 6

rounds, this is a conservative margin.

For Rijndael versions with a higher block length, the number of rounds is raised by one for

every additional 32 bits in the block length, for the following reasons:

• For a block length above 128 bits, it takes 3 rounds to realise full diffusion, i.e., the

diffusion power of a round, relative to the block length, diminishes with the block

length.

• The larger block length causes the range of possible patterns that can be applied at

the input/output of a sequence of rounds to increase. This added flexibility may allow

to extend attacks by one or more rounds.

We have found that extensions of attacks by a single round are even hard to realise for the

maximum block length of 256 bits. Therefore, this is a conservative margin.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

8. Strength against known attacks

8.1 Symmetry properties and weak keys of the DES type

Despite the large amount of symmetry, care has been taken to eliminate symmetry in the

behaviour of the cipher. This is obtained by the round constants that are different for each

round. The fact that the cipher and its inverse use different components practically eliminates

the possibility for weak and semi-weak keys, as existing for DES. The non-linearity of the key

expansion practically eliminates the possibility of equivalent keys.

8.2 Differential and linear cryptanalysis

Differential cryptanalysis was first described by Eli Biham and Adi Shamir [BiSh91]. Linear

cryptanalysis was first described by Mitsuru Matsui [Ma94].

Chapter 5 of [Da95] gives a detailed treatment of difference propagation and correlation. To

better describe the anatomy of the basic mechanisms of linear cryptanalysis (LC) and of

differential cryptanalysis (DC), new formalisms and terminology were introduced. With the aid

of these it was, among other things, shown how input-output correlations over multiple rounds

are composed. We will use the formalisms of [Da95] in the description of DC and LC. To

provide the necessary background, Chapter 5 of [Da95] has been included in Annex.

8.2.1 Differential cryptanalysis

DC attacks are possible if there are predictable difference propagations over all but a few

(typically 2 or 3) rounds that have a prop ratio (the relative amount of all input pairs that for the

1-n

given input difference give rise to the output difference) significantly larger than 2 if n is the

block length. A difference propagation is composed of differential trails, where its prop ratio is

the sum of the prop ratios of all differential trails that have the specified initial and final

difference patterns. To be resistant against DC, it is therefore a necessary condition that there

1-n

are no differential trails with a predicted prop ratio higher than 2 .

For Rijndael, we prove that there are no 4-round differential trails with a predicted prop ratio

“150 “300

above 2 (and no 8-round trails with a predicted prop ratio above 2 ). For all block lengths

of Rijndael, this is sufficient. For the significance of these predicted prop ratios, we refer to

Chapter 5 of [Da95]. The proof is given in Section 8.2.3.

In [LaMaMu91] it has been proposed to perform differential cryptanalysis with another notion of

difference. This is especially applicable to ciphers where the key addition is not a simple EXOR

operation. Although in Rijndael the keys are applied using EXORs, it was investigated whether

attacks could be mounted using another notion of difference. We have found no attack

strategies better than using EXOR as the difference.

8.2.2 Linear cryptanalysis

LC attacks are possible if there are predictable input-output correlations over all but a few

(typically 2 or 3) rounds significantly larger than 2 n/2. An input-output correlation is composed of

linear trails, where its correlation is the sum of the correlation coefficients of all linear trails that

have the specified initial and final selection patterns. The correlation coefficients of the linear

trails are signed and their sign depends on the value of the Round Keys. To be resistant

against LC, it is a necessary condition that there are no linear trails with a correlation

n/2

coefficient higher than 2 .

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ lasoporP SEA

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

QHPHD' QDR-

QHPML5 WQHFQL9

“75

For Rijndael, we prove that there are no 4-round linear trails with a correlation above 2 (and

“150

no 8-round trails with a correlation above 2 ). For all block lengths of Rijndael, this is

sufficient. The proof is given in Section 8.2.4.

8.2.3 Weight of differential and linear trails

In [Da95], it is shown that:

• The prop ratio of a differential trail can be approximated by the product of the prop

ratios of its active S-boxes.

• The correlation of a linear trail can be approximated by the product of input-output

correlations of its active S-boxes.

The wide trail strategy can be summarised as follows:

• Choose an S-box where the maximum prop ratio and the maximum input-output

“6

correlation are as small as possible. For the Rijndael S-box this is respectively 2

“3

and 2 .

• Construct the diffusion layer in such a way that there are no multiple-round trails with

few active S-boxes.

We prove that the minimum number of active S-boxes in any 4-round differential or linear trail

“150

is 25. This gives a maximum prop ratio of 2 for any 4-round differential trail and a maximum

“75

of 2 for the correlation for any 4-round linear trail. This holds for all block lengths of Rijndael

and is independent of the value of the Round Keys.

Note: the nonlinearity of an S-box chosen randomly from the set of possible invertible 8-bit S-

“5 “4

boxes is expected to be less optimum. Typical values are 2 to 2 for the maximum prop ratio

“2

and 2 for the maximum input-output correlation.

8.2.4 Propagation of patterns

For DC, the active S-boxes in a round are determined by the nonzero bytes in the difference of

the states at the input of a round. Let the pattern that specifies the positions of the active S-

boxes be denoted by the term (difference) activity pattern and let the (difference) byte weight

be the number of active bytes in a pattern.

For LC, the active S-boxes in a round are determined by the nonzero bytes in the selection

vectors (see Annex ) at the input of a round. Let the pattern that specifies the positions of the

active S-boxes be denoted by the term (correlation) activity pattern and let the (correlation)

byte weight W(a) be the number of active bytes in a pattern a.

Moreover, let a column of an activity pattern with at least one active byte be denoted by active

column. Let the column weight, denoted by W C(a), be the number of active columns in a

pattern. The byte weight of a column j of a, denoted by W(a)|j, is the number of active bytes in

it.

The weight of a trail is the sum of the weights of its activity patterns at the input of each round.

Difference and correlation activity patterns can be seen as propagating through the

transformations of the different rounds of the block cipher to form linear and differential trails.

This is illustrated with an example in Figure 7.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ lasoporP SEA

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

QHPHD' QDR-

QHPML5 WQHFQL9

ByteSub

ShiftRow

MixColumn

AddRoundKey

Figure 7: Propagation of activity pattern (in grey) through a single round

The different transformations of Rijndael have the following effect on these patterns and

weights:

• ByteSub and AddRoundKey: activity patterns, byte and column weight are invariant.

• ShiftRow: byte weight is invariant as there is no inter-byte interaction.

• MixColumn: column weight is invariant as there is no inter-column interaction.

ByteSub and AddRoundKey do not play a role in the propagation of activity patterns and

therefore in this discussion the effect of a round is reduced to that of ShiftRow followed by

MixColumn. In the following, ByteSub and AddRoundKey will be ignored. MixColumn has a

branch number equal to 5, implying:

• For any active column of a pattern at its input (or, equivalently, at its output), the

sum of the byte weights at input and output for this column is lower bounded by 5.

ShiftRow has the following properties:

• The column weight of a pattern at its output is lower bounded by the maximum of the

byte weights of the columns of the pattern at its input.

• The column weight of a pattern at its input is lower bounded by the maximum of the

byte weights of the columns of the pattern at its output.

This is thanks to the property that MixColumn permutes the bytes of a column to all different

columns.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ lasoporP SEA

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

rehpiC kcolB leadnjiR ehT

QHPHD' QDR-

QHPML5 WQHFQL9

In our description, the activity pattern at the input of a round i is denoted by ai“1 and the activity

pattern after applying ShiftRow of round i is denoted by bi“1. The initial round is numbered 1

and the initial difference pattern is denoted by a0. Clearly, ai and bi are separated by ShiftRow

and have the same byte weight, bj“1 and aj are separated by MixColumn and have the same

column weight. The weight of an m-round trail is given by the sum of the weights of a0 to am“1 .

The propagation properties are illustrated in Figure 8. In this figure, active bytes are indicated

in dark grey, active columns in light grey.

ai

W C (a i ) ≥ m a x j W ( b i )| j

W (b i ) = W(a i )

W C (b i) ≥ m a x j W ( a i)| j

bi

For all active columns j:

W C (a i+1 ) = W C (b i )

W (b i)| j + W (a i+ 1 )| j ≥ 5

a i+ 1

Figure 8: Propagation of patterns in a single round.

Theorem 1: The weight of a two-round trail with Q active columns at the input of the second

round is lower bounded by 5Q.

Proof: The fact that MixColumn has a Branch Number equal to 5 implies that sum of the byte

weights of each column in b0 and a1 is lower bounded by 5. If the column weight of a1 is Q, this

gives a lower bounded of 5Q for the sum of the byte weights of b0 and a1 . As a0 and b0 have

the same byte weight, the lower bounded is also valid for the sum of the weights a0 and a1 ,

proving the theorem.

QED

Theorem 1 is illustrated in Figure 9.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

a0

W (b 0 ) = W( a 0 )

b0

W (a 1 ) + W (b 0 ) ≥ 5 W C (a 1 )

a1

Figure 9: Illustration of Theorem 1 with Q = 2.

From this it follows that any two-round trail has at least 5 active S-boxes.

Lemma 1: in a two-round trail, the sum of the number of active columns at its input and the

number of active columns at its output is at least 5. In other words, the sum of the columns

weights of a0 and a2 is at least 5.

Proof: ShiftRow moves all bytes in a column of ai to different columns in bi and vice versa. It

follows that the column weight of ai is lower bounded the byte weights of the individual

columns of bi. Likewise the column weight of bi is lower bounded by the byte weights of the

individual columns of ai.

In a trail, at least one column of a1 (or equivalently b0 ) is active. Let this column be denoted by

“column g”. Because MixColumn has a branch number of 5, the sum of the byte weights of

column g in b0 and column g in a1 is lower bounded by 5. The column weight of a0 is lower

bounded by the byte weight of column g of b0. The column weight of b1 is lower bounded by

the byte weight of column g of a1. It follows that the sum of the column weights of a0 and b1 is

lower bounded by 5. As the column weight of a2 is equal to that of b1, the lemma is proven.

QED

Lemma 1 is illustrated in Figure 10.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

a0

W C (a 0 ) ≥ max j W ( b 0 )| j

b0

W (a 1 )| j + W( b 0 )| j ≥ 5

a1

W C (b 1 ) ≥ max j W ( a 1 )| j

b1

W C (a 2 ) = W C (b 1 )

a2

Figure 10: Illustration of Lemma 1 with one active column in a1.

Theorem 2: Any trail over four rounds has at least 25 active bytes.

Proof: By applying Theorem 1 on the first two rounds (1 and 2) and on the last two rounds (3

and 4), it follows that the byte weight of the trail is lower bounded by the sum of the column

weight of a1 and a3 multiplied by 5. By applying Lemma 1, the sum of the column weight ofa1

and a3 is lower bounded by 5. From this it follows that the byte weight of the four-round trail is

lower bounded by 25.

QED

Theorem 2 is illustrated in Figure 11.

a0

W (a 0 ) + W( a 1 ) ≥ 5 W C (a 1 )

a1

W C (a 1 ) + W C (a 3 ) ≥ 5 a2

W (a 2 ) + W( a 3 ) ≥ 5 W C (a 3 )

a3

Figure 11: Illustration of Theorem 2.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

8.3 Truncated differentials

The concept of truncated differentials was first published by Lars Knudsen [Kn95]. The

corresponding class of attacks exploit the fact that in some ciphers differential trails tend to

cluster [Da95] (see Annex ). Clustering takes place if for certain sets of input difference

patterns and output difference patterns, the number of differential trails is exceedingly large.

The expected probability that a differential trail stays within the boundaries of the cluster can

be computed independently of the prop ratios of the individual differential trails. Ciphers in

which all transformation operate on the state in well aligned blocks are prone to be susceptible

to this type of attack. Since this is the case for Rijndael, all transformations operating on bytes

rather than individual bits, we investigated its resistance against “truncated differentials”. For 6

rounds or more, no attacks faster than exhaustive key search have been found.

8.4 The Square attack

The “Square” attack is a dedicated attack on Square that exploits the byte-oriented structure of

Square cipher and was published in the paper presenting the Square cipher itself [DaKnRi97].

This attack is also valid for Rijndael, as Rijndael inherits many properties from Square. We

describe this attack in this section.

The attack is a chosen plaintext attack and is independent of the specific choices of ByteSub,

the multiplication polynomial of MixColumn and the key schedule. It is faster than an

exhaustive key search for Rijndael versions of up to 6 rounds. After describing the basic attack

on 4 rounds, we will show how it can be extended to 5 and 6 rounds. For 7 rounds or more, no

attacks faster than exhaustive key search have been found.

8.4.1 Preliminaries

Let a Λ -set be a set of 256 states that are all different in some of the state bytes (the active)

and all equal in the other state bytes (the passive) We have

± xi , j ≠ yi , j if (i , j ) active

∀x , y ∈ Λ: .

xi , j = yi , j else

Applying the transformations ByteSub or AddRoundKey on (the elements of) a Λ -set results

in a (generally different) Λ -set with the positions of the active bytes unchanged. Applying

ShiftRow results in a Λ -set in which the active bytes are transposed by ShiftRow. Applying

MixColumn to a Λ -set does not necessarily result in a Λ -set. However, since every output

byte of MixColumn is a linear combination (with invertible coefficients) of the four input bytes in

the same column, an input column with a single active byte gives rise to an output column with

all four bytes active.

8.4.2 The basic attack

Consider a Λ -set in which only one byte is active. We will now trace the evolution of the

st

positions of the active bytes through 3 rounds. MixColumn of the 1 round converts the active

byte to a complete column of active bytes. The four active bytes of this column are spread over

nd nd

four distinct columns by ShiftRow of the 2 round. MixColumn of the 2 round subsequently

converts this to 4 columns of only active bytes. This stays a Λ -set until the input of MixColumn

rd

of the 3 round.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

Since the bytes of this (in fact, any) Λ -set, denoted by a, range over all possible values and

are therefore balanced over the Λ -set, we have

•(2a )

• bi , j = • 3ai +1, j • ai + 2 , j • ai + 3, j

i, j

b = MixColumn( a ),a ∈Λ a ∈Λ

= 2• a •a •a •a

•3 • •

i +1, j i +2, j i + 3, j

i, j

a ∈Λ a ∈Λ a ∈Λ a ∈Λ

= 0• 0• 0• 0 = 0

th

Hence, all bytes at the input of the 4 round are balanced. This balance is in general

destroyed by the subsequent application of ByteSub.

th

We assume the 4 round is a final round, i.e., it does not include a MixColumn operation.

th th

Every output byte of the 4 round depends on only one input byte of the 4 round. Let a be

th th

the output of the 4 round, b its output and k the Round Key of the 4 round. We have:

()

ai , j = Sbox bi ′ , j ′ • k i , j .

By assuming a value for ki , j , the value of bi ′ , j ′ for all elements of the Λ -set can be calculated

from the ciphertexts. If the values of this byte are not balanced over Λ , the assumed value for

the key byte was wrong. This is expected to eliminate all but approximately 1 key value. This

can be repeated for the other bytes of k.

8.4.3 Extension by an additional round at the end

If an additional round is added, we have to calculate the above value of bi ′ , j ′ from the output of

the 5th round instead of the 4th round. This can be done by additionally assuming a value for

th

a set of 4 bytes of the 5 Round Key. As in the case of the 4-round attack, wrong key

assumptions are eliminated by verifying that bi ′ , j ′ is not balanced.

In this 5-round attack 2 40 key values must be checked, and this must be repeated 4 times.

Since by checking a single Λ -set leaves only 1/256 of the wrong key assumptions as possible

candidates, the Cipher Key can be found with overwhelming probability with only 5 Λ -sets.

8.4.4 Extension by an additional round at the beginning

The basic idea is to choose a set of plaintexts that results in a Λ -set at the output of the 1

st

round with a single active S-box. This requires the assumption of values of four bytes of the

Round Key that is applied before the first round.

st

If the intermediate state after MixColumn of the 1 round has only a single active byte, this is

nd

also the case for the input of the 2 round. This imposes the following conditions on a column

of four input bytes of MixColumn of the second round: one particular linear combination of

these bytes must range over all 256 possible values (active) while 3 other particular linear

combinations must be constant for all 256 states. This imposes identical conditions on 4 bytes,

in different positions at the input of ShiftRow of the first round. If the corresponding bytes of

the first Round Key are known, these conditions can be converted to conditions on four

plaintext bytes.

32

Now we consider a set of 2 plaintexts, such that one column of bytes at the input of

MixColumn of the first round range over all possible values and all other bytes are constant.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

Now, an assumption is made for the value of the 4 bytes of the relevant bytes of the first

Round Key. From the set of 2 32 available plaintexts, a set of 256 plaintexts can be selected

that result in a Λ -set at the input of round 2. Now the 4-round attack can be performed. For

the given key assumption, the attack can be repeated for a several plaintext sets. If the byte

values of the last Round Key are not consistent, the initial assumption must have been wrong.

A correct assumption for the 32 bytes of the first Round Key will result in the swift and

consistent recuperation of the last Round Key.

8.4.5 Working factor and memory requirements for the attacks

Combining both extensions results in a 6 round attack. Although infeasible with current

technology, this attack is faster than exhaustive key search, and therefore relevant. The

working factor and memory requirements are summarised in Figure 12. For the different block

lengths of Rijndael no extensions to 7 rounds faster than exhaustive key search have been

found.

Attack # Plaintexts # Cipher Memory

executions

9 9

Basic (4 rounds) 2 2 small

11 40

Extension at end 2 2 small

32 40 32

Extension at beginning 2 2 2

32 72 32

Both Extensions 2 2 2

Figure 12: Complexity of the Square attack applied to Rijndael.

8.5 Interpolation attacks

In [JaKn97] Jakobsen and Knudsen introduced a new attack on block ciphers. In this attack,

the attacker constructs polynomials using cipher input/output pairs. This attack is feasible if the

components in the cipher have a compact algebraic expression and can be combined to give

expressions with manageable complexity. The basis of the attack is that if the constructed

polynomials (or rational expressions) have a small degree, only few cipher input/output pairs

are necessary to solve for the (key-dependent) coefficients of the polynomial. The complicated

8

expression of the S-box in GF(2 ), in combination with the effect of the diffusion layer prohibits

these types of attack for more than a few rounds. The expression for the S-box is given by:

127 191 223 239 247 251 253 254

63 + 8f x + b5 x + 01 x + f4 x + 25 x + f9 x + 09 x + 05 x

8.6 Weak keys as in IDEA

The weak keys discussed in this subsection are keys that result in a block cipher mapping with

detectable weaknesses. The best known case of weak keys are those of IDEA [Da95].

Typically, this weakness occurs for ciphers in which the non-linear operations depends on the

actual key value. This is not the case for Rijndael, where keys are applied using the EXOR and

all non-linearity is in the fixed S-box. In Rijndael, there is no restriction on key selection.

/

99/90/30 :etaD ,2 noisrev tnemucoD 54 83 :egaP

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

8.7 Related-key attacks

In [Bi96], Eli Biham introduced a related-key attack. Later it was demonstrated by John Kelsey,

Bruce Schneier and David Wagner that several ciphers have related-key weaknesses In

[KeScWa96].

In related-key attacks, the cryptanalyst can do cipher operations using different (unknown or

partly unknown) keys with a chosen relation. The key schedule of Rijndael, with its high

diffusion and non-linearity, makes it very improbable that this type of attack can be successful

for Rijndael.

9. Expected strength

Rijndael is expected, for all key and block lengths defined, to behave as good as can be

expected from a block cipher with the given block and key lengths. What we mean by this is

explained in Section 10.

This implies among other things, the following. The most efficient key-recovery attack for

Rijndael is exhaustive key search. Obtaining information from given plaintext-ciphertext pairs

about other plaintext-ciphertext pairs cannot be done more efficiently than by determining the

key by exhaustive key search. The expected effort of exhaustive key search depends on the

length of the Cipher Key and is:

• for a 16-byte key, 2

127

applications of Rijndael;

• for a 24-byte key, 2

191

applications of Rijndael;

• for a 32-byte key, 2

255

applications of Rijndael.

The rationale for this is that a considerable safety margin is taken with respect to all known

attacks. We do however realise that it is impossible to make non-speculative statements on

things unknown.

10. Security goals

In this section, we present the goals we have set for the security of Rijndael. A cryptanalytic

attack will be considered successful by the designers if it demonstrates that a security goal

described herein does not hold.

10.1 Definitions of security concepts

In order to formulate our goals, some security-related concepts need to be defined.

10.1.1 The set of possible ciphers for a given block length and key length

v

A block cipher of block length v has V = 2 possible inputs. If the key length is u it defines a set

u v v

of U = 2 permutations over {0,1} . The number of possible permutations over {0,1} is V!.

Hence the number of all possible block ciphers of dimensions u and v is

u

(V !) U .

(( 2 v ) !) ( 2 )

or equivalently

For practical values of the dimensions (e.g., v and u above 40), the subset of block ciphers

with exploitable weaknesses form a negligible minority in this set.

/

99/90/30 :etaD ,2 noisrev tnemucoD 54 93 :egaP

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

10.1.2 K-Security

Definition: A block cipher is K-secure if all possible attack strategies for it have the same

expected work factor and storage requirements as for the majority of possible block ciphers

with the same dimensions. This must be the case for all possible modes of access for the

adversary (known/chosen/adaptively chosen plaintext/ciphertext, known/chosen/adaptively

chosen key relations...) and for any a priori key distribution.

K-security is a very strong notion of security. It can easily be seen that if one of the following

weaknesses apply to a cipher, it cannot be called K-secure:

• Existence of key-recovering attacks faster than exhaustive search;

• Certain symmetry properties in the mapping (e.g., complementation property);

• Occurrence of non-negligible classes of weak keys (as in IDEA);

• related-key attacks.

K-security is essentially a relative measure. It is quite possible to build a K-secure block cipher

with a 5-bit block and key length. The lack of security offered by such a scheme is due to its

small dimensions, not to the fact that the scheme fails to meet the requirements imposed by

these dimensions. Clearly, the longer the key, the higher the security requirements.

10.1.3 Hermetic block ciphers

It is possible to imagine ciphers that have certain weaknesses and still are K-secure. An

example of such a weakness would be a block cipher with a block length larger than the key

length and a single weak key, for which the cipher mapping is linear. The detection of the

usage of the key would take at least a few encryptions, while checking whether the key is used

would only take a single encryption.

If this cipher would be used for encipherment, this single weak key would pose no problem.

However, used as a component in a larger scheme, for instance as the compression function

of a hash function, this property could introduce a way to efficiently generate collisions.

For these reasons we introduce yet another security concept, denoted by the term hermetic.

Definition: A block cipher is hermetic if it does not have weaknesses that are not present for

the majority of block ciphers with the same block and key length.

Informally, a block cipher is hermetic if its internal structure cannot be exploited in any

application.

10.2 Goal

For all key and block lengths defined, the security goals are that the Rijndael cipher is :

• K-secure;

• Hermetic.

If Rijndael lives up to its goals, the strength against any known or unknown attacks is as good

as can be expected from a block cipher with the given dimensions.

/

HWD' QRLVUHY WQHPXFR' HJD3

:srohtuA ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

nemeaD naoJ

nemjiR tnecniV

11. Advantages and limitations

11.1 Advantages

Implementation aspects:

• Rijndael can be implemented to run at speeds unusually fast for a block cipher on a

Pentium (Pro). There is a trade-off between table size/performance.

• Rijndael can be implemented on a Smart Card in a small amount of code, using a

small amount of RAM and taking a small number of cycles. There is some

ROM/performance trade-off.

• The round transformation is parallel by design, an important advantage in future

processors and dedicated hardware.

• As the cipher does not make use of arithmetic operations, it has no bias towards big-

or little endian processor architectures.

Simplicity of Design:

• The cipher is fully “self-supporting”. It does not make use of another cryptographic

component, S-boxes “lent” from well-reputed ciphers, bits obtained from Rand

tables, digits of π or any other such jokes.

• The cipher does not base its security or part of it on obscure and not well

understood interactions between arithmetic operations.

• The tight cipher design does not leave enough room to hide a trapdoor.

Variable block length:

• The block lengths of 192 and 256 bits allow the construction of a collision-resistant

iterated hash function using Rijndael as the compression function. The block length

of 128 bits is not considered sufficient for this purpose nowadays.

Extensions:

• The design allows the specification of variants with the block length and key length

both ranging from 128 to 256 bits in steps of 32 bits.

• Although the number of rounds of Rijndael is fixed in the specification, it can be

modified as a parameter in case of security problems.

11.2 Limitations

The limitations of the cipher have to do with its inverse:

• The inverse cipher is less suited to be implemented on a smart card than the cipher

itself: it takes more code and cycles. (Still, compared with other ciphers, even the

inverse is very fast)

• In software, the cipher and its inverse make use of different code and/or tables.

• In hardware, the inverse cipher can only partially re-use the circuitry that implements

the cipher.

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

12. Extensions

12.1 Other block and Cipher Key lengths

The key schedule supports any key length that is a multiple of 4 bytes. The only parameter

that needs to be defined for other key lengths than 128, 192 or 256 is the number of rounds in

the cipher.

The cipher structure lends itself for any block length that is a multiple of 4 bytes, with a

minimum of 16 bytes. The key addition and the ByteSub and MixColumn transformations are

independent from the block length. The only transformation that depends on the block length is

ShiftRow. For every block length, a specific array C1, C2, C3 must be defined.

We define an extension of Rijndael that also supports block and key lengths between 128 and

256 bits with increments of 32 bits. The number of rounds is given by:

Nr = max(Nk, Nb) + 6.

This interpolates the rule for the number of rounds to the alternative block and key lengths.

The additional values of C1, C2 and C3 are specified in Table 8.

C1 C2 C3

Nb

5 1 2 3

7 1 2 4

Table 8: Shift offsets in Shiftrow for the alternative block lengths

The choice of these shift offsets is based on the criteria discussed in Section 7.4.

12.2 Another primitive based on the same round transformation

The Rijndael Round transformation has been designed to provide high multiple-round diffusion

and guaranteed distributed nonlinearity. These are exactly the requirements for the state

updating transformation in a stream/hash module such as Panama [DaCl98]. By fitting the

round transformation (for Nb=8) in a Panama-like scheme, a stream/hash module can be built

that can hash and do stream encryption about 4 times as fast as Rijndael and perform as a

very powerful pseudorandom number generator satisfying all requirements cited in

[KeScWaHa98].

13. Other functionality

In this section we mention some functions that can be performed with the Rijndael block

cipher, other than encryption.

13.1 MAC

Rijndael can be used as a MAC algorithm by using it as the Block cipher in a CBC-MAC

algorithm. [ISO9797]

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

13.2 Hash function

Rijndael can be used as an iterated hash function by using it as the round function. Here is

one possible implementation. It is advised to use a block and key length both equal to 256 bits.

The chaining variable goes into the “input” and the message block goes into the “Cipher Key”.

The new value of the chaining variable is given by the old value EXORed with the cipher

output.

13.3 Synchronous stream cipher

Rijndael can be used as a synchronous stream cipher by applying the OFB mode or the

Filtered Counter Mode. In the latter mode, the key stream sequence is created by encrypting

some type of counter using a secret key [Da95].

13.4 Pseudorandom number generator

In [KeScWaHa98] a set of guidelines are given for designing a Pseudorandom Number

Generator (PRNG). There are many ways in which Rijndael could be used to form a PRNG

that satisfies these guidelines. We give an example in which Rijndael with a block length of

256 and a cipher key length of 256 is used.

There are three operations:

Reset:

• The Cipher Key and “state” are reset to 0.

Seeding (and reseeding):

• “seed bits” are collected taking care that their total has some minimum entropy.

They are padded with zeroes until the resulting string has a length that is a multiple

of 256 bits.

• A new Cipher Key is computed by encrypting with Rijndael a block of seed bits using

the current Cipher Key. This is applied recursively until the seed blocks are

exhausted.

• The state is updated by applying Rijndael using the new Cipher Key.

Pseudorandom Number generation:

• The state is updated by applying Rijndael using the Cipher Key. The first 128 bits of

the state are output as a “pseudorandom number”. This step may be repeated many

times.

13.5 Self-synchronising stream cipher

Rijndael can be used as a self-synchronising stream cipher by applying the CFB mode of

operation.

/

HWD' QRLVUHY WQHPXFR' HJD3

:srohtuA ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

nemeaD naoJ

nemjiR tnecniV

14. Suitability for ATM, HDTV, B-ISDN, voice and satellite

It was requested to give comments on the suitability of Rijndael to be used for ATM, HDTV, B-

ISDN, Voice and Satellite. As a matter of fact, the only thing that is relevant here, is the

processor on which the cipher is implemented. As Rijndael can be implemented efficiently in

software on a wide range of processors, makes use of a limited set of instructions and has

sufficient parallelism to fully exploit modern pipelined multi-ALU processors, it is well suited for

all mentioned applications.

For applications that require rates higher than 1 Gigabits/second, Rijndael can be implemented

in dedicated hardware.

15. Acknowledgements

In the first place we would like to thank Antoon Bosselaers, Craig Clapp, Paulo Barreto and

Brian Gladman for their efficient ANSI-C implementations and the Cryptix team, including

Paulo Barreto, for their Java implementation.

We also thank Lars Knudsen, Bart Preneel, Johan Borst and Bart Van Rompay for their

cryptanalysis of preliminary versions of the cipher.

We thank Brian Gladman and Gilles Van Assche and for proof-reading this version of the

documentation and providing many suggestions for improvement. Moreover, we thank all

people that have brought errors and inconsistencies in the first version of this document to our

attention.

We would also like to thank all other people that did efforts to efficiently implement Rijndael

and all people that have expressed their enthusiasm for the Rijndael design.

Finally we would like to thank the people of the NIST AES team for making it all possible.

16. References

[Bi93] E. Biham, "New types of cryptanalytic attacks using related keys," Advances in

Cryptology, Proceedings Eurocrypt'93, LNCS 765, T. Helleseth, Ed., Springer-Verlag, 1993,

pp. 398-409.

[BiSh91] E. Biham and A. Shamir, "Differential cryptanalysis of DES-like cryptosystems,"

Journal of Cryptology, Vol. 4, No. 1, 1991, pp. 3-72.

[Da95] J. Daemen, "Cipher and hash function design strategies based on linear and differential

cryptanalysis," Doctoral Dissertation, March 1995, K.U.Leuven.

[DaKnRi97] J. Daemen, L.R. Knudsen and V. Rijmen, "The block cipher Square," Fast

Software Encryption, LNCS 1267, E. Biham, Ed., Springer-Verlag, 1997, pp. 149-165. Also

available as http://www.esat.kuleuven.ac.be/rijmen/square/fse.ps.gz.

[DaKnRi96] J. Daemen, L.R. Knudsen and V. Rijmen, " Linear frameworks for block ciphers,"

to appear in Design, Codes and Cryptography.

[DaCl98] J. Daemen and C. Clapp, “Fast hashing and stream Encryption with PANAMA,” Fast

Software Encryption, LNCS 1372, S. Vaudenay, Ed., Springer-Verlag, 1998, pp. 60-74.

[ISO9797] ISO/IEC 9797, "Information technology - security techniques - data integrity

mechanism using a cryptographic check function employing a block cipher algorithm",

International Organization for Standardization, Geneva, 1994 (second edition).

/

HWD' QRLVUHY WQHPXFR' HJD3

VURKWX$ ODVRSRU3 6($

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

UHKSL& NFRO% OHDGQML5 HK7

QHPHD' QDR-

QHPML5 WQHFQL9

[JaKn97] T. Jakobsen and L.R. Knudsen, "The interpolation attack on block ciphers," Fast

Software Encryption, LNCS 1267, E. Biham, Ed., Springer-Verlag, 1997, pp. 28-40.

[KeScWa96] J. Kelsey, B. Schneier and D. Wagner, "Key-schedule cryptanalysis of IDEA,

GDES, GOST, SAFER, and Triple-DES," Advances in Cryptology, Proceedings Crypto '96,

LNCS 1109, N. Koblitz, Ed., Springer-Verlag, 1996, pp. 237-252.

[KeScWaHa98] J. Kelsey, B. Schneier, D. Wagner and Chris Hall, "Cryptanalytic attacks on

pseudorandom number generators," Fast Software Encryption, LNCS 1372, S. Vaudenay, Ed.,

Springer-Verlag, 1998, pp. 168-188.

[Kn95] L.R. Knudsen, "Truncated and higher order differentials," Fast Software Encryption,

LNCS 1008, B. Preneel, Ed., Springer-Verlag, 1995, pp. 196-211.

[Kn95a] L.R. Knudsen, "A key-schedule weakness in SAFER-K64," Advances in Cryptology,

Proceedings Crypto'95, LNCS 963, D. Coppersmith, Ed., Springer-Verlag, 1995, pp. 274-286.

[LaMaMu91] X. Lai, J.L. Massey and S. Murphy, "Markov ciphers and differential

cryptanalysis," Advances in Cryptology, Proceedings Eurocrypt'91, LNCS 547, D.W. Davies,

Ed., Springer-Verlag, 1991, pp. 17-38.

[LiNi86] R. Lidl and H. Niederreiter, Introduction to finite fields and their applications,

Cambridge University Press, 1986.

[Ma94] M. Matsui, "Linear cryptanalysis method for DES cipher," Advances in Cryptology,

Proceedings Eurocrypt'93, LNCS 765, T. Helleseth, Ed., Springer-Verlag, 1994, pp. 386-397.

[Ny94] K. Nyberg, "Differentially uniform mappings for cryptography," Advances in Cryptology,

Proceedings Eurocrypt'93, LNCS 765, T. Helleseth, Ed., Springer-Verlag, 1994, pp. 55-64.

[Ri97] V. Rijmen, "Cryptanalysis and design of iterated block ciphers," Doctoral Dissertation,

October 1997, K.U.Leuven.

17. List of Annexes

In Annex, we have included Chapter 5 of [Da95]: “Correlation and Propagation” as this lays the

fundaments for the Wide Trail Strategy.

Note: In the Annex, the EXOR is denoted by + instead of •.

/

99/90/30 :etaD ,2 noisrev tnemucoD 54 54 :egaP