Aes1 2016

Chapter 3
The Mathematical Background

of the Advanced Encryption Standard
3.1 Introduction
In 2001 Rijndael became the official new encryption standard named Advanced
Encryption Standard (AES). It is the successor of the Data Encryption Standard
(DES) and won the competition, started by the National Institute for Standards
and Technology (NIST) in 1997, which we will briefly explain in Sect. 3.2. In this
competition Rijndael, which was proposed by Joan Daemen and Vincent Rijmen
[6], prevailed over the other proposals such as Mars by IBM [3], RC6 by RSA Labs
[19], Serpent by Ross Anderson et al. [1] and Twofish by Counterpane Inc. [20]. The
goal of this section is to give comprehensive explanations about the design criteria
of Rijndael and their specific realization.1
One of the AES requirements was that the submitted ciphers should be block
ciphers, which are used for computer security such as online banking, smart cards,
computer communication, etc. This means that input and output of the ciphers should
be one-dimensional array of bits.
In Sect. 3.3 we will show that there exists a bijection from the set of all one-
dimensional array of bits of length n to the set GF(2)[x]|n of all polynomials with
coefficients in GF(2) and degree less than n. Each of these polynomials and therewith
each one-dimensional array of bits of length n represents an element of the finite field
GF(2n ). In this section we will define the addition and multiplication of the finite field
GF(28 ) and the finite ring GF(232 ) and show how byte-addition, byte-multiplication,
4-byte-column-addition and 4-byte-column-multiplication are realized in Rijndael.
We will show that byte- and 4-byte-column-addition equal the bitwise XOR operation,
which can be efficiently evaluated. Further on, we show that byte-multiplication,
which equals the polynomial multiplication followed by the reduction via the modulo
1 Rudolf Ahlswede was invited with his group to the “Seminar Rijndael” in June 2001 in Paderborn.
There he noticed the very interesting mathematics of the new code. Therefore he decided to section
about it. His student Christian Heup wrote his dipolma thesis about this topic.
© Springer International Publishing Switzerland 2016 155

A. Ahlswede et al. (eds.), Hiding Data – Selected Topics,
Foundations in Signal Processing, Communications
and Networking 12, DOI 10.1007/978-3-319-31515-7_3
156 3 The Mathematical Background of the Advanced Encryption Standard
operation of a so-called reduction polynomial, can be efficiently computed by the

xtime operation, if at least one operand is ‘small’.
In the following Sect. 3.4 we give some basic definitions of several boolean func-
tions, which map a boolean vector onto another boolean vector. Since a boolean vector
of length n equals an one-dimensional array of bits of length n, these functions can
be used to describe the block cipher Rijndael. After that, this section finishes with
the definitions of several types of block ciphers, such as the iterated block cipher,
which consists of the repeated application of one and the same round function and the
key-iterated block cipher, where every application of the round function is followed
by an addition of a particular round key, which is derived from the given cipherkey.
Section 3.5 concentrates on the design of Rijndael, which arose from the crypt-
analysis of the DES. There were two approaches to analyze DES, the differential
attack developed by Biham and Shamir [2] and the linear attack developed by
Matsui [13]. To attack a block cipher via the differential respectively linear attack an
enemy has to find trails over all but a few rounds of the cipher with a high difference
propagation probability respectively with a high correlation. We will define the dif-
ferential and linear weight of differential and linear trails as the negative logarithm
of their difference propagation probability and their correlation. To be secure against
both attacks was the main security requirement for the AES candidates. In order to
achieve this goal Rijndael was designed according to the Wide Trail Strategy, which
was developed by Joan Daemen in his doctoral dissertation [5] in 1995 and offers
design criteria for block ciphers, so that there exist no low-weighted differential or
linear trails. The Wide Trail Strategy suggests that the round function should be
decomposed into two different layers, a non-linear substitution layer γ, which oper-
ates on only a limited number of bits of the intermediate results, called bundles, with
high minimum differential and linear weights in relation to the bundle size, and a
linear diffusion layer λ, which increases minimum differential and linear weights
round by round. With this γλ round structure we are able to eliminate any trails of
given differential or linear weights by increasing the number rounds of the cipher.
After that, in Sect. 3.6, we give the exact specifications of the individual steps of
Rijndael. Firstly, we show how the plaintext block is mapped on the state, which
represents the intermediate results of Rijndael. Then we specify the non-linear layer
SubBytes, which consists of the inverse mapping in GF(28 ) followed by an affine
mapping to avoid interpolation attacks [11], and the linear layer, which consists of
ShiftRows and MixColumns, where ShiftRows shifts the individual bytes of each row
of the state over its columns and MixColumns multiplies each column of the state
by a fixed polynomial. In the next sections, we show that the round keys are added
to the state by the simple bitwise XOR operation and derive the round keys from the
cipherkey via the Key Schedule. Finally, we present the whole encryption and decryp-
tion as they are implemented in Rijndael, provide some facts about its complexity
and show how the requirements of the Wide Trail Strategy are applied to the Rijndael
cipher in order to make it secure against differential and linear cryptanalysis.
Section 3.7 treats an cryptanalytic attack, the saturation attack. This attack is
a chosen-plaintext attack over up to six rounds of Rijndael, which means that it
exploits its specific structure by encrypting properly chosen plaintexts in order to
3.1 Introduction 157
derive the unknown cipherkey. The set of chosen plaintexts are the so-called -sets,
which consists of 28 plaintexts in which all the 28 bytes at the same position of these
plaintexts sum up to zero. The property of Rijndael, which is exploited by this attack,
is that the steps SubBytes, ShiftRows and AddRoundKey do not destroy a -set and,
if the -sets are properly chosen, the MixColumns step maintains a -set two times.
This means that all the bytes at the same positions of the state sum up to zero until
the input of the third MixColumns step and since MixColumns is linear this property
is still true to its output state and therefore remains until the input of the fourth
MixColumns step. To obtain all bytes of one round key we then guess its value and
verify its correctness by summing up all bytes at the same position of the input state
of the fourth MixColumns step. If we obtain zero the guess was correct with some
probability, and if we do not obtain zero our guess was wrong. If we have found one
whole round key with this method, we are able to obtain the cipherkey by going the
Key Schedule algorithm the other way round.
3.2 The AES Selection Process
The Data Encryption Standard (DES) describes the data encryption algorithm (DEA),
which is an improvement of the algorithm Lucifer developed by IBM in the early
1970s. This standard is up to now the most widely spread encryption algorithm in the
world. But since the development of the differential attack [2] and the linear attack
[13], it is no longer considered to be secure enough for security-critical applications.
For example the U.S. government is no longer allowed to use it. To gain a higher
security level, triple-DES was invented, which consists of the threefold application
of DES, but whose disadvantage is its efficiency.
In 1997 the National Institute for Standards and Technology (NIST) announced
the start of a competition, whose goal was to find an encryption algorithm to become
the Advanced Encryption Standard (AES).
The requirements to the submissions were that the algorithm should be a sym-
metric block cipher with 128-bit blocks and 128-, 192- and 256-bit keys, in contrast
to DES, which uses 56-bit keys and to 3-DES, which uses 112-bit keys. Further on,
the algorithm should offer at least as much security as 3-DES, but should be much
more efficient and finally the algorithm should be available royalty-free world-wide,
which includes that the security-testing would be realized by the world-wide cryptol-
ogy community and be therefore much more reliable. Another innovation was that the
submissions were international and not only reserved to American cryptographers.
In August 1998 the first AES conference was held and fifteen submissions were
accepted, where the first ones were submitted by companies and the last ones by
researchers:
CAST-256 by Entrust (CA)

Crypton by Future Systems (KR)
E2 by NTT (JP)
Frog by TecApro (CR)
Magenta by Deutsche Telekom (DE)
Mars by IBM (USA)
RC6 by RSA (USA)
SAFER+ by Cylink (USA)
Twofish by Counterpane Inc. (USA)
DEAL by Outerbridge, Knudsen (USA-DK)
DFC by ENS-CNRS (FR)
HPC by Schroeppel (USA)
LOKI97 by Brown (AU)
Rijndael by Daemen, Rijmen (BE)
Serpent by Anderson, Biham, Knudsen(UK-IL-DK)
At the second conference, which took place in Rome in 1999, the five finalists were
selected:
• Mars (IBM)
• RC6 (RSA)
• Rijndael (Daemen, Rijmen)
• Serpent (Anderson, Biham, Knudsen)
• Twofish (Counterpane Inc.)
The other submissions withdrew because of security or efficiency problems.
The final AES conference was held in 2000 in New York.
All finalists offered adequate security, but Rijndael was selected because of its
efficiency and its flexibility, which makes it usable on all kind of processors.
3.3 Finite Fields
In this section we will introduce the theory of finite fields, especially the finite field
GF(28 ). We will represent the elements of GF(28 ) by polynomials of degree less
than 8 and show how byte-addition and byte-multiplication are defined in Rijndael.
We start with the two basic definitions of a finite field and the characteristic of a
finite field.
Definition 43 Let F be a set. A triple < F, ⊕, > is called a finite field of order
m, denoted by GF(m), if:
• < F, ⊕ > is an Abelian group, with 0 as the neutral element,
• < F\{0}, > is an Abelian group, with 1 as the neutral element,
• Distributivity holds: a (b ⊕ c) = a b ⊕ a c ∀ a, b, c ∈ F,
• |F| = m < ∞.
3.3 Finite Fields 159
Definition 44 The characteristic of a finite field of order m, denoted by char

(GF(m)), is defined by:
char(GF(m)) := minl∈N {l| 1 ⊕ ·

· · ⊕ 1 = 0}.
l times
Now we come to some well known results, for example see [12], from the theory of
finite fields, which we will need in the remaining section.
Theorem 57 A finite field exists and has order m, if and only if m is a prime power,
e.g. m = pk , with p ∈ Pand k ∈ N+ , where P is the set of all primes.
Theorem 58 All finite fields of the same order are isomorphic, they differ only in
the way of representing the elements.
Theorem 59 The characteristic of the finite field GF(pk ) is p.
From Theorems 57 and 58 it follows that for all p ∈ P and for all k ∈ N exists a
unique finite field with pk elements.
3.3.1 Polynomials Over a Field
From Theorem 58 it follows that besides the definition of addition and multiplication,
we have to determine the representation of a finite field.
In Rijndael the polynomial representation is used, which means that every element
of GF(pk ) is represented by a polynomial of degree k − 1 and coefficients in GF(p).
This is done, because the definitions for addition and multiplication are quite intuitive
with the polynomial representation.
Definition 45 A polynomial over a field F is an expression of the following form:
a(x) := an−1 x n−1 + · · · + a1 x + a0 , with ai ∈ F.
Definition 46 Let F be a field. F[x] is the set of all polynomials over F.
Definition 47 Let F be a field. F[x]|d is the set of all polynomials over F with degree
less than d.
3.3.2 The Field < F[x]|d , ⊕, >
In Rijndael we are only interested in the case F = GF(2k ). Since the construction of
both addition and multiplication does not depend on the structure of the underlying
field, we will do this in general for any field F.
In this section we will define the addition ⊕ and the multiplication in order to
give < F[x]|d , ⊕, > a field structure. To do this we have to choose a irreducible
reduction polynomial in order to make the multiplication closed.
Definition 48 Let F be a field and a(x), b(x) ∈ F[x]|d , then addition

c(x) := a(x) ⊕ b(x) is defined by:
ci = ai + bi ∀ i ∈ {0, . . . , d − 1},
where + is the addition in the field F.
Proposition 15 < F[x]|d , ⊕ > is an Abelian group.
Proof The associativity and commutativity follow directly from the field structure
of F. Now let z(x) ∈ F[x]|d be the polynomial with all its coefficients equal to
the neutral element for addition in the field F. It follows that z(x) is the neutral
element for addition in < F[x]|d , ⊕ > and it is denoted by 0. For a given polynomial
a(x) ∈ F[x]|d , the polynomial b(x) ∈ F[x]|d with bi = −ai , where −ai is the additive
inverse of ai in F, is the additive inverse of a(x) in < F[x]|d , ⊕ >. Finally, the above
defined addition is closed, which means a(x) ⊕ b(x) ∈ F[x]|d , because, on the one
hand, the addition in F is closed and from this it follows that all the coefficients
ai + bi are also in F. And on the other hand, deg(a(x) ⊕ b(x)) ≤ max{deg(a(x)),
deg(b(x))} < d.
As we can see this definition is equal to the known polynomial addition for any
polynomial over a field F. From now on we will denote both the above defined
addition and the normal polynomial addition with ⊕.
The definition for the multiplication is a bit more complicated, because we have
to do a so-called reduction in order to make the multiplication closed.
It is known that the polynomial multiplication ⊗ is associative, commutative,
distributive together with ⊕ and it has a neutral element e(x), denoted by 1, with
e0 = 1f and ei = 0f , for all i ≥ 1, where 1f is the neutral element for multiplication
and 0f is the neutral element for addition in the underlying field F. The problem is
that the multiplication of polynomials is not closed over F[x]|d , because deg(a(x) ⊗
b(x)) = deg(a(x)) + deg(b(x)), which could certainly be bigger than d − 1.
To solve this problem we select a reduction polynomial.
Definition 49 Let F be a field and d ∈ N.

A polynomial m(x) ∈ F[x], with deg(m(x)) = d and md = 1f , is called a reduction
polynomial in F[x]|d .
Definition 50 Let a(x), m(x) ∈ F[x].

r(x) is called the residue of a(x) modulo m(x),
written a(x) = r(x) (mod m(x)), if and only if ∃q(x), r(x) ∈ F[x], with a(x) =
q(x) ⊗ m(x) ⊕ r(x) and deg(r(x)) < deg(m(x)).
Claim q(x) and r(x) from the above definition are unique.
Proof Suppose there are q(x), r(x), q (x) and r (x), with:
(q(x) ⊗ m(x)) ⊕ r(x) = a(x) = (q (x) ⊗ m(x)) ⊕ r (x)
and deg(r(x)) < deg(m(x)), deg(r (x)) < deg(m(x))
⇒ (q(x) ⊕ (−q (x)))m(x) = r (x) ⊕ (−r(x))
⇒ q(x) = q (x) ⇒ r(x) = r (x),
because deg(m(x)) > max{deg(r(x)), deg(r (x))} ≥ deg(r (x) ⊕ (−r(x)))
Definition 51 Let F be a field and a(x), b(x) ∈ F[x]|d , then the multiplication is
defined by:
a(x) b(x) := a(x) ⊗ b(x) (mod m(x)),
where m(x) is a reduction polynomial in F[x]|d .
Together with the above definitions for the reduction polynomial and the residue
modulo m(x), it follows that the multiplication is closed over F[x]|d .
But it is still a Ring, because not every element of F[x]|d needs to have a mul-
tiplicative inverse. The reason for this is that until now the only restrictions to the
reduction polynomial are that its degree must equal d and md = 1f . So if we choose
the reduction polynomial m(x) = m1 (x) ⊗ m2 (x), with d > deg(m1 (x)) > 0 and
d > deg(m2 (x)) > 0, then any polynomial of the form a(x) = a1 (x) ⊗ m1 (x) or
b(x) = b1 (x) ⊗ m2 (x) has no multiplicative inverse. Because if we assume the oppo-
site that, for example for a(x) = a1 (x) ⊗ m1 (x) there exists a multiplicative inverse,
denoted by a−1 (x), it would hold that:
∃q(x) ∈ F[x] with: a(x) ⊗ a−1 (x) = (q(x) ⊗ m(x)) ⊕ 1
⇔ −(q(x) ⊗ m(x)) ⊕ (a(x) ⊗ a−1 (x)) = 1
⇔ (c1 (x) ⊗ m1 (x)) ⊕ (c2 (x) ⊗ m1 (x)) = 1,
where c1 (x) = −q(x) ⊗ m2 (x), c2 (x) = a1 (x) ⊗ a−1 (x)
⇔ m1 (x) ⊗ (c1 (x) ⊕ c2 (x)) = 1
And this is a contradiction. Because if c1 (x) ⊕ c2 (x) = 0, then
deg(m1 (x) ⊗ (c1 (x) ⊕ c2 (x))) > 0 and deg(1) = 0 and if c1 (x) ⊕ c2 (x) = 0,
it would follow that 0 = 1.
The same holds for any polynomial of the form b(x) = b1 (x) ⊗ m2 (x).
In order to obtain a field structure we have to choose a special kind of reduction
polynomial, which does not have the property that it can be decomposed into two
polynomials with degree bigger than zero. These polynomials are called irreducible.
Definition 52 Let F be a field. A polynomial c(x) ∈ F[x] is called irreducible, if

and only if there exist no two polynomials a(x), b(x) ∈ F[x], with c(x) = a(x)⊗b(x)
and deg(a(x)) > 0 and deg(b(x)) > 0.
Lemma 18 If m(x) is an irreducible reduction polynomial in F[x]|d , then gcd(a(x),

m(x)) = 1, for all a(x) ∈ F[x]|d .
Proof a(x) = 1: gcd(a(x), m(x)) = gcd(1, m(x)) = 1.

a(x) = 1: The only possible divisor of m(x) with degree less than d has degree
0. Since md = 1f , it follows that the only possible divisors of m(x) are 1 and m(x)
itself. Since deg(m(x)) = d > deg(a(x)), it follows that gcd(a(x), m(x)) = 1.
Proposition 16 If we choose the reduction polynomial to be irreducible it follows

that < F[x]|d , ⊕, > is a field.
Proof Given two polynomials a(x), m(x) ∈ F[x] the Extended Euclidean Algorithm,
which is described in Sect. 3.8 determines uniquely b(x), c(x) ∈ F[x], with (a(x) ⊗
b(x)) ⊕ (m(x) ⊗ c(x)) = gcd(a(x), m(x)) and deg(b(x)) < deg(m(x)). In our case
a(x) ∈ F[x]|d and m(x) is an irreducible reduction polynomial in F[x]|d .
It follows from Lemma 18 that gcd(a(x), m(x)) = 1.
⇒ (a(x) ⊗ b(x)) ⊕ (m(x) ⊗ c(x)) = 1
⇒ a(x) ⊗ b(x) = 1 (mod m(x))
⇒ a(x) b(x) = 1.
And since deg(b(x)) < deg(m(x)) = d, it follows b(x) ∈ F[x]|d .
That means, by applying the Extended Euclidean Algorithm we can determine the
unique multiplicative inverse for any given element of F[x]|d .
We showed that for any given field F we can construct a field < F[x]|d , ⊕, >
with |F|d elements. It follows that if |F| < ∞, also | < F[x]|d , ⊕, > | = |F|d <
∞. This means that if F is a finite field, for example F = GF(pk ), p ∈ P, then
< GF(pk )[x]|d , ⊕, >, is the finite field GF(pkd ). On the other hand, by starting
with GF(p), where F = {0, . . . , p − 1}, ⊕ is the addition modulo p and is the
multiplication modulo p, we can obtain the elements of GF(pkd ) for all k, d ∈ N, by
constructing the polynomials over GF(p) with degree less than kd.
The only thing left to do, is defining ⊕d and d . From this it immediately fol-
lows that both GF(p)[x]|kd and GF(pk )[x]|d represent the elements of GF(pkd ). That
means, with appropriate definitions for ⊕, , ⊕d and d , it follows that:
< GF(pk )[x]|d , ⊕, > = GF(pkd ) = < GF(p)[x]|kd , ⊕d , ⊗d > .
3.3.3 Byte-Operations in Rijndael
In Rijndael we are only interested in the finite fields with characteristic 2, in particular
in GF(28 ) and GF(232 ). The reason for that is that Rijndael is an block-cipher which
operates, on the one hand, on one-dimensional arrays of bits of length 8, called bytes,
which represent the elements of GF(28 ), and on the other hand, it deals with one-
dimensional arrays of bytes of length 4, called 4-byte columns, which represent the
elements of GF(232 ).
As shown above, there are different ways to construct GF(2kd ). In the case of
bytes, GF(28 ) is constructed via < GF(2)[x]|8 , ⊕, > and in the case of 4-byte
columns, GF(232 ) is constructed via < GF(28 )[x]|4 , ⊕, >.
The Finite Field GF(28 )

In this subsection we will show how the addition and the multiplication work while
operating on bytes. We will see that the addition is, by its definition, nothing more
than the bitwise XOR-operation and that the multiplication can be done efficiently
by applying the xtime-operation.
The set of all possible bytes, denoted by B, has 28 elements. From Theorem 57
it follows that we can use this set to represent the elements of GF(28 ). Following
Sects. 3.3.1 and 3.3.2 we can also represent the elements of GF(28 ) by all possible
polynomials of degree less than 8 with coefficients in GF(2). By applying Theorem 58
it follows that there has to exist a bijection ϕ : B → GF(2)[x]|8 . Since every bit of
a byte is either 0 or 1, this bijection is quite natural and defined as follows.
Definition 53 For a given byte β = β7 β6 . . . β0 ∈ B, where the βi ’s are bits, ϕ(β)

is defined via:
ϕ(β) := b(x) ∈ GF(2)[x]|8 , with bi = βi .
From now on we will write β = β7 β6 . . . β0 ∼ b7 x 7 + b6 x 6 + · · · + b0 = b(x) or

“the byte β corresponds to the polynomial b(x)”, if ϕ(β) = b(x).
For example 10110101 ∼ x 7 +x 5 +x 4 +x 2 +1. In some cases it is more convenient
to write a byte not in the binary notation but in the hexadecimal notation. For example
the hexadecimal notation of 10110101 is “B5”. We will always use quotes, if we mean
the hexadecimal notation.
Byte-Addition ⊕
We will now give an example for the byte-addition in Rijndael and we will show that
it is in fact a very simple byte-level operation, which can be evaluated by computer-
hardware very fast.
“B5” ⊕ “6C”
= 10110101 ⊕ 01101100
∼ (x 7 + x 5 + x 4 + x 2 + 1) ⊕ (x 6 + x 5 + x 3 + x 2 )
= x 7 + x 6 + (1 + 1)x 5 + x 4 + x 3 + (1 + 1)x 2 + 1
= x7 + x6 + x4 + x3 + 1
∼ 11011001
= “D9”
As we can see, this is the same as the simple bitwise exclusive-or-operation, which
is the following for given bits β1 and β2 :

0, if β1 = β2
XOR(β1 , β2 ) :=
1, otherwise
From now on we will denote both the addition of bytes and XOR by ⊕.
Remark 30 Since the characteristic of GF(28 ) is 2, every element is its own additive
inverse.
Byte-Multiplication
In order to define the multiplication of GF(28 ) we have to choose an irreducible
reduction polynomial m(x) in GF(2)[x]|8 .
In Rijndael m(x) := x 8 + x 4 + x 3 + x + 1 ∼ 100011011 = “11B” is chosen to
be this reduction polynomial.
Example 8 “57” “83”

= 01010111 10000011
∼ (x 6 + x 4 + x 2 + x + 1) (x 7 + x + 1)
= (x 6 + x 4 + x 2 + x + 1) ⊗ (x 7 + x + 1) (mod m(x))
= (x 13 + x 11 + x 9 + x 8 + x 7 ) ⊕ (x 7 + x 5 + x 3 + x 2 + x) ⊕ (x 6 + x 4 + x 2 + x + 1)
(modm(x))
= (x 13 + x 11 + x 9 + x 8 + x 6 + x 5 + x 4 + x 3 + 1) (mod m(x))
= (x 7 + x 6 + 1) (mod (x 8 + x 4 + x 3 + x + 1)) ∼ 11000001 = “C1”
The disadvantage of multiplication compared to addition is the fact that there is no

obvious simple byte-operation, as there is the XOR-operation for addition. But any
monomial of a polynomial over GF(2) is either 0, 1 or it is a power of x. Since,
as we will show, the multiplication by x ∼ “02” can be done efficiently, also the
multiplication of any monomial can be done efficiently, by an iterated application of
the multiplication of x. In order to obtain the whole polynomial, we only have to do
an XOR of all the monomials.
Multiplication by x
Let b(x) ∈ GF(2)[x]|8 .
From the definition of the multiplication it follows that:
b(x) x = b(x) ⊗ x = b7 x 8 + b6 x 7 + · · · + b1 x 2 + b0 x (mod x 8 + x 4 + x 3 + x + 1).
If b7 = 0:
b(x) x = b6 x 7 + · · · b1 x 2 + b0 x
In this case the multiplication by x is a left-shift of the bits over one bit, where the
last bit of the result is filled up with the zero bit.
If b7 = 1:
b(x) x
= x 8 + b6 x 7 + · · · b1 x 2 + b0 x (mod x 8 + x 4 + x 3 + x + 1)
= (x 8 + b6 x 7 + · · · b1 x 2 + b0 x) ⊕ (x 8 + x 4 + x 3 + x + 1)
= b6 x 7 + b5 x 6 + b4 x 5 + (b3 ⊕ 1)x 4 + (b2 ⊕ 1)x 3 + b1 x 2 + (b0 ⊕ 1)x + 1
In this case the multiplication by x is a left-shift of the bits over one bit, followed by
a bitwise XOR with “1B”.
So in both cases the multiplication by x consists only of simple byte-operations,
a left-shift and an optional XOR. We will denote the multiplication of b(x) by x with
xtime(b).
We will show now, by the example of “57” “13”, how the multiplication of two
bytes is done via the multiplication of “02” ∼ x.
The first step is to obtain the product of “57” with all the monomials of “13”.
Since “13” ∼ x 4 + x + 1, it suffices to apply xtime four times to obtain “10” ∼ x 4 .
“57” = 01010111
“57” “02” = xtime(“57”)

= 10101110 = “AE”
“57” “04” = xtime(“AE”)

= 01011100 ⊕ 00011011
= 01000111 = “47”
“57” “08” = xtime(“47”)

= 10001110 = “8E”
“57” “10” = xtime(“8E”)

= 00011100 ⊕ 00011011
= 00000111 = “07”
The second step is then to add all the obtained monomials in order to get the final
result.
“57” “13” = “57” (“10” ⊕ “02” ⊕ “01”)
= “07” ⊕ “AE” ⊕ “57”
= 00000111
⊕ 10101110
⊕ 01010111
= 11111110 = “FE”.
We have seen that the byte-multiplication can be done efficiently if it is done by an
iterated application of xtime. The efficiency depends on the smaller operand, “13” in
the above example. The bigger this smaller operand is, the more often xtime has to
be applied and the byte-multiplication via xtime becomes less efficient.
In the subsection “The MixColums Step” of Sect. 3.6.3 we will see that in the only
case Rijndael uses byte-multiplication, one operand will always be small.
The Finite Ring < GF(28 )[x]|4 ,⊕,• >
In this subsection we will introduce addition and multiplication of 4-byte-columns.
A 4-byte column is a one-dimensional array of bytes. The set C of all possible
4-byte columns has (28 )4 = 232 elements and therefore can be used to represent the
elements of GF(232 ). But also GF(28 )[x]|4 represents the elements of GF(232 ), so a
bijection ψ : C → GF(28 )|4 has to exist. Since every byte represents an element of
GF(28 ), this bijection is defined as follows:
Definition 54 For a given 4-byte column γ = γ3 γ2 γ1 γ0 ∈ C, with γi ∈ B for
i ∈ {0, . . . , 3}, ψ(γ) is defined via:
ψ(γ) := c(x) ∈ GF(28 )|4 , with ci = γi .

4-Byte-Column-Addition ⊕
As shown before the addition of a 4-byte-column consists of the addition of the
coefficients in GF(28 ). Since this addition is only a bitwise XOR of the individual
bits, again the addition of a 4-byte-column equals a bitwise XOR, not only over the
bits of one byte, but over all the bits of the two 4-byte-columns. Therefore we will
denote the 4-byte-column-addition also with ⊕.
4-Byte-Column-Multiplication •
In order to get a closed multiplication we have to choose a reduction polynomial. For
the multiplication of 4-byte-columns l(x) := x 4 + 1 ∈ GF(28 )[x]|4 was chosen. In
GF(2k ) this polynomial satisfies the “Freshman’s Dream”, which means that x 4 +1 =
(x + 1)4 , and from this it follows that l(x) is not irreducible. This property holds for
a
every polynomial x 2 + 1 ∈ GF(2k )[x]|d , where k ∈ N and 2a < d.
a59, the characteristic of GF(2 ) is 2. Further on, it holds

k
Proof Following Theorem
a 2
that (x + 1)2 = 2i=0
a
x i , where all the binomial coefficients, except the first
i
and the last, are even and therefore every addend, except the first and last, each sums
up to zero.
This definition for the reduction polynomial gives < GF(28 )|4 , ⊕, • > not a field
structure but a ring structure, which means that not every element needs to have a
multiplicative inverse.
In particular an element a of < GF(28 )|4 , ⊕, • > has an inverse, if and only if its
corresponding polynomial a(x) is not of the form a1 (x) ⊗ (x + 1).
We have shown before, in Sect. 3.3.2 that if a(x) = a1 (x) ⊗ (x + 1), an inverse
element for a(x) does not exist and if a(x) is not of this form, it follows that
gcd(a(x), l(x)) = 1 and the Extended Euclidean Algorithm determines a unique
inverse element.
But this fact is not important for Rijndael, because in Rijndael the 4-byte-column-
multiplication is done by a fixed polynomial c(x), with gcd(c(x), l(x)) = 1 and so
the multiplication by a fixed polynomial will be invertible.
Multiplication by Fixed Polynomial
The reason for the choice of l(x) is that with this choice the multiplication with a
fixed polynomial can be written as a matrix multiplication by a circulant matrix and
therewith can be efficiently computed.
Let c(x) = c3 x 3 + c2 x 2 + c1 x + c0 ∈ GF(28 )[x]|4 be the fixed polynomial and
a(x) = a3 x 3 + a2 x 2 + a1 x + a0 ∈ GF(28 )[x]|4 be another polynomial. The coeffi-
cients of d (x) := c(x) ⊗ a(x) are:
d0 = c0 a0
d1 = c1 a0 ⊕ c0 a1
d2 = c2 a0 ⊕ c1 a1 ⊕ c0 a2
d3 = c3 a0 ⊕ c2 a1 ⊕ c1 a2 ⊕ c0 a3
d4 = c3 a1 ⊕ c2 a2 ⊕ c1 a3
d5 = c3 a2 ⊕ c2 a3
d6 = c3 a3
Now we come to the claim, which is the basis for the choice of l(x) = x 4 + 1.
Claim x j = x j mod 4 (mod (x 4 + 1)).
Proof Let j = 4q + r, with 0 ≤ r < 4.

xj = x 4q+r = x 4(q−1)+r (x 4 + 1) + x 4(q−1)+r
x 4(q−1)+r = x 4(q−2)+r (x 4 + 1) + x 4(q−2)+r
..
.
x 4+r = x r (x 4 + 1) + x r
q 4(q−i)+r
⇒ x 4q+r = i=1 x (x 4 + 1) + x r
⇒ x = x (mod (x + 1)), with r = j mod 4.
j r 4

With this we get the following coefficients for

d(x) := c(x) • a(x) = c(x) ⊗ a(x) (mod (x 4 + 1)):
d0 = c0 a0 ⊕ c3 a1 ⊕ c2 a2 ⊕ c1 a3
d1 = c1 a0 ⊕ c0 a1 ⊕ c3 a2 ⊕ c2 a3
d2 = c2 a0 ⊕ c1 a1 ⊕ c0 a2 ⊕ c3 a3
d3 = c3 a0 ⊕ c2 a1 ⊕ c1 a2 ⊕ c0 a3
So if we write this system of equations as a matrix-multiplication, we see that we
obtain a circulant matrix:
⎛ ⎞ ⎛ ⎞⎛ ⎞
d0 c0 c3 c2 c1 a0
⎜ d1 ⎟ ⎜ c1 c0 c3 c2 ⎟ ⎜ a1 ⎟
⎜ ⎟=⎜ ⎟ ⎜ ⎟.
⎝ d2 ⎠ ⎝ c2 c1 c0 c3 ⎠ ⎝ a2 ⎠
d3 c3 c2 c1 c0 a3
Since the 4-byte-column-multiplication equals, as shown, the iterated application of
the byte-multiplication and the byte-addition ⊕, it can be evaluated efficiently if
the coefficients of the fixed polynomial are small.
3.4 A Key-Iterated Block Cipher
In this section we will give some important definitions about boolean functions and
introduce the key-iterated block cipher.
3.4.1 Boolean Functions
Firstly, we give the definition of a boolean vector, which is, as we will see, the input
and the output of Rijndael.
Definition 55 A boolean vector b of length n is a vector, whose entries are bits:
b ∈ GF(2)n .
A boolean vector of length n is also called a one-dimensional array of bits of

length n.
Rijndael is a cipher, which operates on bytes. We have seen in the last section, that
any boolean vector of length n represents an element of the finite field GF(2n ). We
will now define a boolean function, which operates on the finite field GF(2n ).
Definition 56 A boolean function φ is a mapping, which maps a boolean vector to

another boolean vector:
φ : GF(2)n → GF(2)m .
Definition 57 A boolean transformation χ is a boolean function, which maps a

boolean vector to another boolean vector of the same length:
χ : GF(2)n → GF(2)n .
We say, it operates on an n-bit-state.

If the boolean transformation χ is invertible it is called a series boolean permu-
tation.
We come now to three special boolean functions. The bricklayer function, the trans-
position and the iterative boolean function. As we will see, Rijndael is an iterative
boolean permutation, which concatenates several boolean round functions. These
boolean round functions are again iterative boolean permutations, which consist of
three individual boolean permutations, namely a non-linear bricklayer permutation,
a transposition and a linear bricklayer permutation.
Definition 58 A bricklayer function is a boolean function that can be decomposed

into several boolean functions, operating independently on subsets of bits of the input
vector.
If these boolean functions are linear, they are called diffusion boxes, or D-boxes,
and if they are non-linear, they are called substitution boxes, or S-boxes.
Definition 59 A bricklayer transformation (permutation) is a bricklayer func-

tion, which can be decomposed into several boolean transformations (permutations).
Definition 60 A transposition is a boolean permutation, for which the binary output

vector has the same hamming weight like the input vector.
3.4 A Key-Iterated Block Cipher 169
Definition 61 An iterative boolean function ψ : GF(2)n0 → GF(2)nk is the

concatenation of k ∈ N boolean functions ψi : GF(2)ni → GF(2)ni+1 , for
i ∈ {0, . . . , k − 1}:
ψ := ψk−1 ◦ · · · ◦ ψ0 .
Definition 62 An iterative boolean transformation (permutation) is the concate-

nation of boolean transformations (permutations).
3.4.2 A Key-Iterated Block Cipher
The input of Rijndael consists of the plaintext and the cipherkey, the output is the
encrypted plaintext, called the ciphertext.
Rijndael is a symmetric cipher, which means that the same cipherkey is used for
both encryption and decryption.
A block cipher is a cipher, where the plaintext is a one-dimensional array of bits
of an arbitrary length, which is divided into several blocks, which are again one-
dimensional array of bits, but all of the same given length NB . All of these blocks are
encrypted separately and in the same way, which means with the same algorithm and
the same cipherkey. After the encryption of the blocks, the derived ciphertext-blocks,
which are still of the same length NB , are stuck together in order to obtain the whole
ciphertext.
From now on, we will speak of only one block to be the input of a block cipher
and therefore the output is also only one ciphertext block. Of course, every ciphertext
block has to be uniquely decryptable into the same plaintext block from which it was
encrypted in order to make a cipher work. In other words, the encryption has to be
invertible. Since the plaintext block is a one-dimensional array of bits of length NB ,
it follows that a block cipher is a boolean permutation which operates on an NB -bit
state.
An iterated block cipher consists of several rounds and in every round a round
transformation is applied to the block. Each round transformation does not change
the length of its input vector and since the whole cipher has to be invertible, every
single round transformation has to be invertible, too.
Similar to the whole cipher, the round transformations are also boolean permuta-
tions, which operate on NB -bit states. The individual round transformations depend
on individual roundkeys, which are derived form the cipherkey. So if we denote the
ith round transformation with ρi , the ith roundkey with κi , the whole block cipher
with B and the number of rounds with Nr , an iterated block cipher can be written as
follows:
B = ρNr [κNr ] ◦ ρNr −1 [κNr −1 ] ◦ · · · ◦ ρ1 [κ1 ].
In a key-alternating block cipher each key-depended round transformation can be
decomposed into a key-independent round transformation ρi and an addition of the
roundkey, which is denoted by σ[κi ], and an additional key-addition of the 0th
roundkey, which is applied before the first round transformation ρ1 . With this notation
a key-iterated block cipher can be written in the following form:
B = σ[κNr ] ◦ ρNr ◦ σ[κNr −1 ] ◦ ρNr −1 ◦ · · · ◦ σ[κ1 ] ◦ ρ1 ◦ σ[κ0 ].
A key-iterated block cipher is a key-alternating block cipher, where all rounds, except
perhaps the first or the last, use the same round transformation ρ:
B = σ[κNr ] ◦ ρ ◦ σ[κNr −1 ] ◦ ρ ◦ · · · ◦ σ[κ1 ] ◦ ρ ◦ σ[κ0 ].
3.5 The Wide Trail Strategy
In this section we will introduce the Wide Trail Strategy, which was developed by
Joan Daemen in his doctoral dissertation [5]. The first section introduces linear trails.
In a linear attack of a key-iterated block cipher a attacker needs to find linear trails
over all but a few rounds with a high correlation. In the second section we come to
differential trails, which are needed in differential cryptanalysis. In the third section
the properties of linear and differential trails, derived in the first both sections, are
used to design a key-iterated block cipher, which is secure against both attacks.
3.5.1 Linear Trails
Correlation
In this first subsection we will explain what is meant by a correlation between two
binary boolean functions.
Definition 63 A parity is a binary boolean function p : GF(2)n → GF(2), with:

p(a) = aj , where Jp ⊂ {0, . . . , n − 1}.
j∈Jp
Definition 64 The selection pattern u of a parity p is a boolean vector, with:

1, if i ∈ Jp
ui =
0, if i∈/ Jp
It follows that p(a) = uT a := u0 a0 ⊕ · · · ⊕ un−1 an−1 .

From now on we will write “uT _”, if we speak of a parity p.
Definition 65 The correlation C(f , g) between two binary boolean functions

f : GF(2)n → GF(2) and g : GF(2)n → GF(2) is defined as:
3.5 The Wide Trail Strategy 171
C( f , g) := 2 · Prob( f = g) − 1,
where Prob(f = g) := 1
2n
· #{i ∈ {0, . . . , 2n − 1}|f (ai ) = g(ai ), ai ∈ GF(2)n }
It follows that C(f , g) ∈ [−1, 1].

Two binary boolean functions f , g are said to be correlated, if C(f , g) = 0.
We will now show that any binary boolean function can be written in terms of its
input parities and the correlation between itself and these input parities. To do this
we have to show that any binary boolean functions can be understood as an element
n
of the vector space < R2 , +, . >.
Definition 66 The real-valued counterpart fˆ : GF(2)n → R of a binary boolean

function f is defined as:
fˆ (ai ) := (−1)f (ai ) , ∀ ai ∈ GF(2)n and i ∈ {0, . . . , 2n − 1}.
The real-valued counterpart fˆ of a binary boolean function f can be seen as an element

of the vector space < R2 , +, . >, where fˆ is represented and defined by the vector
n
⎛ ⎞
fˆ (a0 )
⎜ .. ⎟
⎝ . ⎠ (aj ∈ GF(2)n , j ∈ {0, . . . , 2n − 1}).
fˆ (a2n −1 )
fˆ (aj ) is then the jth component of this vector.
We denote the above vector by fˆ and since fˆ determines f uniquely, we will say
that the vector fˆ represents the binary boolean function f .
n
From the definitions of the inner product and the norm in < R2 , +, . > follow
directly the definitions of the inner product and the norm of two binary boolean
functions.
Definition 67 The inner product of two binary boolean functions f and g is defined
as:
2
n
−1
ˆ
< f , g >:=< f , ĝ >= fˆ (ai )ĝ(ai ).
i=0
Definition 68 The norm of a binary boolean function f is defined as:

||f || := ||fˆ || = < fˆ , fˆ >.
It follows that: ||fˆ || = 2 2 , since fˆ (ai )fˆ (ai ) = 1, for all i ∈ {0, . . . , 2n − 1}.
n
Proposition 17 For two binary boolean function f, g, it holds that:
< fˆ , ĝ >
C(f , g) = .
||fˆ || · ||ĝ||
Proof
−1
2n
<fˆ ,ĝ>
= 2−n fˆ (ai )ĝ(ai )
||fˆ ||·||ĝ|| i=0
= 2−n ( 1− 1)
f (ai )=g(ai ) f (ai )=g(ai )
= 2−n (#{i ∈ {0, . . . , 2n − 1}|f (ai ) = g(ai ), ai ∈ GF(2)n }

−(2n − #{i ∈ {0, . . . , 2n − 1}|f (ai ) = g(ai ), ai ∈ GF(2)n })
= 2−n (2 · #{i ∈ {0, . . . , 2n − 1}|f (ai ) = g(ai ), ai ∈ GF(2)n } − 2n )
= 2 · Prob(f = g) − 1
= C(f , g)
In other words, the correlation between two binary boolean functions is the angle
n
between their representing vectors in < R2 , +, . >.
Proposition 18 The representing vectors of the parities form an orthogonal basis

n
in < R2 , +, . >.
Proof For any two parities uT _ and v T _ it holds that:

2
n
−1
< (−1)u _ , (−1)v _ > = (−1)u ai (−1)v ai
T T T T
i=0
2
n
−1 T
ai ⊕v T ai
= (−1)u
i=0
2
n
−1
(−1)(u⊕v)
T
= ai
i=0
Since we sum up over all ai ’s, the sum contains exactly 2n−1 1’s and 2n−1 (−1)’s, if
u ⊕ v = 0, and therefore sums up to 0.
And if u ⊕ v = 0, every addend equals 1 and we obtain 2n .
We have shown that all the 2n parities are pairwise orthogonal and therefore form
n
an orthogonal basis in < R2 , +, . >.
This means that the representing vector fˆ of every binary boolean function f can be
written as the linear combination of the parity vectors:

fˆ =
T
λu (−1)u _
.
u
The next proposition shows that the coefficients λu equal the correlation C(f , uT _ )
between the binary boolean function f and the parity uT _ , which means that a binary
boolean function f can be completely determined by the correlations between itself
and its input parities uT _ .
Proposition 19 For all i ∈ {0, . . . , 2n − 1}, it holds that:

fˆ (ai ) =
T
C(f , uT _ )(−1)u ai .
u
Proof
2
n
−1
= 2−n fˆ (aj )(−1)u aj ) (−1)u ai
T T T
C(f , uT _ )(−1)u ai
(
u u j=0
2
n
−1
= 2−n fˆ (aj )(−1)u aj (−1)u ai
T T
u j=0
2
n
−1
= 2−n fˆ (aj )(−1)u (aj ⊕ai )
T
u j=0

= 2−n (fˆ (ai ) + fˆ (aj )(−1)u (aj ⊕ai ) )
T
u j=i

= fˆ (ai ) + 2−n fˆ (aj )(−1)u (aj ⊕ai )
T
u j=i

= fˆ (ai ) + 2−n fˆ (aj )(−1)u (aj ⊕ai )
T
j=i u

=0
= fˆ (ai )
As a special case it holds for an output parity w T f of an binary boolean function and
for every ai that:
T
w T f (ai ) = C(w T f , uT _ )(−1)u ai .
u
Definition 69 For a given binary boolean function f we define, according to

[10, 18], the spectrum F(u) of f by:
F(u) := C(f , uT _ ).
Correlation Matrices
Up to now we have only considered binary boolean functions.
We come now to the more general case of boolean transformations, which can be
represented by their correlation matrix.
Reminding of Definition 57 a boolean transformation χ is a boolean function,
operating on a n-bit state:
χ : GF(2)n → GF(2)n .
A boolean transformation can be decomposed into n binary boolean functions:
χi : GF(2)n → GF(2), for i ∈ {0, . . . , n − 1}.
These binary boolean functions χi can be represented by the vector

⎛ ⎞
χ̂i (a0 )
⎜ .. ⎟
χ̂i = ⎝ . ⎠
χ̂i (a2 −1 )
n
and it holds that:

T
χ̂i (aj ) = C(χi , uT _ )(−1)u aj .
u
Let Xi (u) = C(χi , uT _ ) be the spectrum of χi .

By applying Lemma 19 we will obtain that the spectrum Wχ of the output parity
w T χ of χ is:

Wχ (u) = C(w T χ, uT _ ) = Xi (u).
ui =1
Definition 70 The 2n × 2n correlation matrix C χ of a boolean function χ is defined

via its input parities uT _ and its output parities w T χ in the following way:
C χ = (Cw,u
χ
), with
χ
Cw,u := C(w T χ, uT _ ).
It can be proved in the same way like in the proof of Proposition 19 that it holds for
every ai :

(−1)w χ(ai ) = χ
T T
Cw,u (−1)u ai .
u
Hence, each row of the correlation matrix expresses an output parity of a boolean
transformation with respect to its input parities.
χ χ
Definition 71 The linear weight wl (w, u) of a correlation Cw,u between an output
parity w χ and an input parity u _ of a boolean transformation χ is defined via:
T T
χ χ
wl (w, u) := −log2 (Cw,u ).
We will now consider two special cases of boolean transformations, iterative boolean
transformations and bricklayer transformations, which we will need in the remaining
section.
Proposition 20 Let π = π1 ◦ π0 : GF(2)n → GF(2)n be an iterative boolean

transformation, with πi : GF(2)n → GF(2)n . Further on, let C πi be the 2n × 2n
correlation matrix of πi . Then it holds for the 2n × 2n correlation matrix C π of π that:
C π = C π1 × C π0 .
Proof We have for all ai :

(−1)w π(ai ) π1
(−1)v π0 (ai )
T T
= Cw,v
v
π1
π0 T
= Cw,v Cv,u (−1)u ai
v u
π1 π0 T
= Cw,v Cv,u (−1)u ai .
u v
From this follows:

C π = C π1 × C π0 .
From this proposition follows for π = π1 ◦ π0 that the correlation between an output
parity w T π and an input parity uT _ of π is given by:

C(w T π, uT _ ) = C(w T π1 , v T _ )C(v T π0 , uT _ ). (3.5.1)
v
By an iterated application of Proposition 20 we obtain the following fact for boolean

transformations consisting of more than two boolean transformations.
Proposition 21 For k ∈ N let π = πk−1 ◦ · · · ◦ π0 : GF(2)n → GF(2)n be an

iterative boolean transformation, with πi : GF(2)n → GF(2)n .
Further on, let C πi be the 2n × 2n correlation matrix of πi .
Then it holds for the 2n × 2n correlation matrix C π of π that:
C π = C πk−1 × · · · × C π0 .
A bricklayer transformation h can be decomposed into k ∈ {2, . . . , n} boolean trans-

formations hi , for i ∈ {0, . . . , k − 1}, which operate independently on different bits
of the n-bit state. We will only consider bricklayer transformations, whose boolean
transformations hi operate on the same number nh of independent bits, but the results
can be applied to all bricklayer transformations.
We have n = knh and denote the ith nh bits of an n-bit state a by a(i) .
With this notation we have:
b = h(a) ⇔ b(i) = hi (a(i) ), with i ∈ {0, . . . , k − 1}.
We can write the hi ’s in the following form:

j
hi = (hi0 , . . . , hin−1 ), with hi = 0, if j ∈
/ {inh , . . . , (i + 1)nh − 1}.
It follows that:

k−1
h= hi .
i=0
We will show that the correlation of a bricklayer transformation can be derived

from correlations of its underlying boolean transformations. To do this we have to
revert to binary boolean functions. As we have seen a bricklayer transformation can
be written as a XOR of its underlying boolean transformations. This yields to the
following lemma.
Lemma 19 For two binary boolean functions f and g, with spectra F(u) and G(v),
let h := f ⊕ g. Then it holds for the spectrum H(w) of h:

H(w) = F(u) ⊗ G(v) := F(v ⊕ w)G(v).
v
Proof Firstly, we show that the real-valued counterpart of the XOR ⊕ of two binary
boolean functions is the product of the individual real-valued counterparts.
⊕ g = (−1)f ⊕g = (−1)f (−1)g = fˆ · ĝ.

f
Now it holds for every ai that:

fˆ (ai )ĝ(ai ) = G(v)(−1)v
T T
F(u)(−1)u ai ai
u v

F(u)G(v)(−1)(u⊕v)
T
= ai
u v

F(v ⊕ w)G(v) (−1)w
T
= ai
w v
From Proposition 19 and Definition 69 it follows that:

H(w) = F(v ⊕ w)G(v).
v
As mentioned on p. 28, from this lemma follows that the spectrum Wχ of the output
parity w T χ of χ is:

Wχ (u) = C(w T χ, uT _ ) = Xi (u).
ui =1
The individual boolean transformations of a bricklayer transformation operate inde-

pendently on subsets of the input vector. This fact simplifies the above lemma. For
this we preliminarily define the support space of a binary boolean function.
Definition 72 Let f be a binary boolean function and F(u) its spectrum.

The subspace of GF(2)n generated by the selection patterns u, with F(u) = 0, is
called the support space Vf of f.
The following property holds for the support space of the XOR of two binary boolean
functions.
Lemma 20 Let f and g be two binary boolean functions with support spaces Vf and
Vg and let h = f ⊕ g.
Then it holds for the support space Vh of h:
Vh = Vf ⊕g ⊆ Vf ⊕ Vg .
Proof Let w ∈ Vf ⊕g , then it follows by Definition 72 and Lemma 19 that:

H(w) = F(v ⊕ w)G(v) = 0.
v
Further on, it holds that:

0 = F(v ⊕ w)G(v) = F(v ⊕ w)G(v)
v v∈Vg

= F(v ⊕ w)G(v)
v∈Vg ∧(v⊕w)∈Vf
From this it follows that there exist v ∈ Vg and u = v ⊕ w ∈ Vf , with w = u ⊕ v

and this yields to:
w ∈ Vf ⊕ Vg .
The independence of the individual boolean transformations can be translated into

terms of the support space.
Definition 73 Two binary boolean functions f and g are called disjoint, if it holds
for their support spaces Vf and Vg :
Vf ∩ Vg = {0}.
We are now able to simplify Lemma 19.
Lemma 21 Let f and g be two disjoint binary boolean functions with spectra F(u)
and G(v) and let h = f ⊕ g.
Then there exist unique u ∈ Vf and v ∈ Vg , with w = u ⊕ v ∈ Vh and it holds for
the spectrum H(w) of h:
H(w) = F(u)G(v), where w = u ⊕ v.
Proof Lemma 20 states that each w ∈ Vh can be written as the XOR of u ∈ Vf and
v ∈ Vg . Suppose there exist u, u ∈ Vf and v, v ∈ Vg and it holds that:
u⊕v =w =u ⊕v ⇔u⊕u =v⊕v
Since u ⊕ u ∈ Vf , v ⊕ v ∈ Vg and Vf ∩ Vg = {0}, it follows:
u⊕u =v⊕v =0⇒u=u ∧v =v.
For the spectrum of h it holds:

H(w) = F(u)G(v).
v∈Vg ∧u∈Vf
Since, as shown above, u ∈ Vf and v ∈ Vg are unique, it follows:
H(w) = F(u)G(v), with w = u ⊕ v.
With this lemma we are able to show how the correlation matrix of a bricklayer
transformation can be derived from the correlation matrices of its underlying boolean
transformations.
Proposition 22 Let h be a bricklayer transformation consisting of k ∈ {2, . . . , n}

boolean transformations hi , for i ∈ {0, . . . , k − 1}. Further on, let Cwhi(i) ,u(i) be the
correlation between the output parities w(i) T hi and the input parities u(i) T _ of hi ,
where w(i) , u(i) ∈ GF(2)nh . It holds for the correlation Cw,uh
between the output
parities w h and the input parities u _ of h:
T T

k−1
k−1
Cw,u
h
= Cwhi(i) ,u(i) ⇔ wlh (w, u) = wlhi (w(i) , u(i) ),
i=0 i=0
where w = (w(0) , . . . , w(k−1) ) and u = (u(0) , . . . , u(k−1) ).

Proof Like we have done above with the individual hi ’s, we write the individual
w(i) ’s in the following form:
j
w(i) = (w(i)
0
, . . . , w(i)
n−1
), with w(i) = 0, if j ∈
/ {inh , . . . , (i + 1)nh − 1}.
If we do the same with the individual u(i) ’s, we obtain:

k−1
k−1
w= w(i) and u = u(i) .
i=0 i=0
From this follows:

k−1
wT h = w(i) T hi .
i=0
Now we denote the spectrum of wT h by Wh (u) and the spectra of w(i) T hi by Whi (u(i) ).
Further on, we denote the support spaces of w(i) T hi by Vi .
From the structure of hi and w(i) it follows that:
Vi ∩ Vj = {0}, for all i = j and i, j ∈ {0, . . . , k − 1}.
We are now in the situation of Lemma 21 and an iterated application of this lemma
yields to:

k−1
Wh (u) = Whi (u(i) ).
i=0
Since, by definition, Wh (u) = Cw,u

h
and Whi (u(i) ) = Cwhi(i) ,u(i) , this proves the proposi-
tion.
Linear Trails
We will now define a linear trail and the weight of a linear trail and finish this
subsection with the Theorem of Linear Trail Composition.
Let ρ be an iterative boolean transformation, operating on a n-bit state:
ρ = ρr−1 ◦ · · · ◦ ρ0 .
It follows by Proposition 21 for the correlation matrix C ρ of ρ:
C ρ := C ρr−1 × · · · × C ρ0 ,
where C ρi is the correlation matrix of the boolean transformation ρi .
Definition 74 A linear trail Uρ over an iterative boolean transformation ρ with r

rounds consists of a sequence of (r + 1) selection patterns u(i) :
Uρ = u(0) , . . . , u(r) ,
for which each of the r steps (u(i) , u(i+1) ) (i ∈ {0, . . . , r − 1}) has a correlation given
by:
ρ T T
Cu(i+1)
i
, u(i)
= C(u(i+1) ρi , u(i) _ ) = 0.
Definition 75 The correlation contribution Cp of a linear trail Uρ is defined via:

r−1
ρ
Cp (Uρ ) := Cu(i+1)
i
, u(i)
.
i=0
Definition 76 The weight wl (Uρ ) of a linear trail Uρ is defined by:
wl (Uρ ) := −log2 (Cp (Uρ )).
It follows that the weight of a linear trail is the sum of the linear weights of the
correlations of its steps:

r−1
ρ
wl (Uρ ) = wl i (u(i+1) , u(i) ). (3.5.2)
i=0
Definition 77 Let ρ = ρr−1 ◦ · · · ◦ ρ0 be an iterative boolean transformation with r

rounds. The set containing all linear trails Uρ , with u(0) = u and u(r) = w is denoted
by:
Uw,u .
From Definitions 74 and 75 and the iterated application of (3.5.1) follows:

ρ
Theorem 60 (Theorem of linear trail composition, [5]) The correlation Cw,u between
an output parity w ρ and an input parity u _ of an iterative boolean transformation
T T
ρ with r rounds is given by:

ρ
Cw,u = C(w T ρ, uT _ ) = Cp (Uρ ).
Uρ ∈Uw,u
3.5.2 Differential Trails
Differential Propagation Probability

Consider a boolean transformation χ, operating on a n-bit state, and two n-bit vectors
ai and aj , with ai ⊕ aj = a .
Let bi = χ(ai ), bj = χ(aj ) and b = bi ⊕ bj .

We say that the difference pattern a propagates to the difference pattern b through
χ with a particular probability, which is called the difference propagation probability
and defined as follows.
Definition 78 Given two difference patterns a and b , the difference propagation

probability Probχ (a , b ) of χ is defined via:
2
n
−1
χ −n
Prob (a , b ) := 2 δ(b ⊕ χ(ai ⊕ a ) ⊕ χ(ai )),
i=0

1, if x = 0
where δ(x) := is the Kronecker delta function.
0, if x = 0
χ
Definition 79 The differential weight wd (a , b ) of a difference propagation (a , b )
through χ is defined via:
χ
wd (a , b ) := −log2 (Probχ (a , b )).
Proposition 23 For given difference patterns a and b it holds that:
Probχ (a , b ) = 21−n k, for k ∈ {0, . . . , 2n−1 }.
Proof Suppose we have found an i ∈ {0, . . . , 2n − 1}, with:
b = χ(ai ⊕ a ) ⊕ χ(ai ).
Then we have for j ∈ {0, . . . , 2n − 1}, j = i and aj = ai ⊕ a :
χ(aj ⊕ a ) ⊕ χ(aj ) = χ(ai ) ⊕ χ(ai ⊕ a ) = b .
For given difference patterns a and b , Probχ (a , b ) is the fraction of the set of all
n-bit vectors, for which a propagates to b .
We denote the set of all ai ’s, for which b = χ(ai ⊕ a ) ⊕ χ(ai ) by:
M := {ai ∈ GF(2)n | b = χ(ai ⊕ a ) ⊕ χ(ai )}
and obtain:
#M = 2n Probχ (a , b ) = 2k, for k ∈ {0, . . . , 2n−1 }.
If k = 0, we say that a and b are incompatible and from now on we will only
consider the case k = 0.
We will now consider a special case of boolean transformations, the bricklayer

transformations. A bricklayer transformation h consists of k ∈ {2, . . . , n} boolean
transformations hi , operating on individual bits of the n-bit state a. Let the boolean
transformation hi operate on ni bits, with n0 + · · · + nk−1 = n, and without loss
of generality we assume that h0 operates on the bits from position 0 to position
n0 − 1, denoted by a(0) , and for i ∈ {1, . . . ,
k − 1} we assume that hi operates on
(i)
the bits from position i−1 j=0 nj to position i
j=0 nj − 1, denoted by a . Hence,
a = (a(0) , . . . , a(k−1) ).
With the above notation we can prove the following proposition.
Proposition 24 Let h be a bricklayer transformation consisting of k ∈ {2, . . . , n}

boolean transformations hi , for i ∈ {0, . . . , k − 1}. Further on, let Probhi (a(i) , b(i) )
be the probability that a(i) propagates to b(i) through hi .
Then it holds for the difference propagation probability of h:

k−1
k−1
Probh (a , b ) = Probhi (a(i) , b(i) ) ⇔ wdh (a , b ) = wdhi (a(i) , b(i) ).
i=0 i=0
Proof Let:
M := {aj ∈ GF(2)n | b = h(aj ⊕ a ) ⊕ h(aj )}
and for all i ∈ {0, . . . , k − 1}, let:
Mi := {aj(i) ∈ GF(2)ni | b(i) = h(aj(i) ⊕ a(i) ) ⊕ h(aj(i) )}.
Since M = M0 × · · · × Mk−1 , it follows:

k−1
#M = #Mi .
i=0
We obtain:

k−1
k−1
Probh (a , b ) = 2−n #M = 2−n #Mi = 2−ni #Mi
i=0 i=0

k−1
= Probhi (a(i) , b(i) )
i=0
Differential Trails
Let ρ = ρr−1 ◦ · · · ◦ ρ0 be an iterative boolean transformation with r rounds. We will
now define a differential trail and the weight of a differential trail.
Definition 80 A differential trail Qρ over an iterative boolean transformation ρ

with r rounds consists of a sequence of (r + 1) difference patterns qi :
Qρ := (q0 , . . . , qr ),
for which each of the r steps (qi , qi+1 ), for i ∈ {0, . . . , r − 1}, has a differential
weight given by:
ρ
wdi (qi , qi+1 ).
Definition 81 The weight wd (Qρ ) of a differential trail Qρ is defined via:

r−1
ρ
wd (Qρ ) := wdi (qi , qi+1 ).
i=0
With this definitions we are ready to define the difference propagation probability of
an iterative boolean transformation over r rounds.
Definition 82 Let ρ = ρr−1 ◦ · · · ◦ ρ0 be an iterative boolean transformation with

r rounds. The set containing all differential trails Qρ , with q0 = a and qr = b is
denoted by:
Qa ,b .
Definition 83 The difference propagation probability Probρ (a , b ) of an iterative

boolean transformation ρ over r rounds is defined as:

Probρ (a , b ) := 2−wd (Qρ ) .
Qρ ∈Qa ,b
3.5.3 The Wide Trail Strategy
In linear cryptanalysis the attacker needs to know a correlation over all but a few
rounds with a high amplitude and in differential cryptanalysis he needs to know an
input difference, which propagates to an output difference with a high probability.
The approach of the Wide Trail Strategy is to design a key-iterated block cipher,
which combines security and efficiency. By security we mean that there do not exist
any low weighted linear or differential trails.
The γλ Round Structure
Each round transformation ρ consists of two layers γ and λ, where γ is a non-linear
bricklayer permutation and λ is a linear permutation, which provides a high diffusion:
ρ = λ ◦ γ.
This structure is called a γλ round transformation.

The Construction of γ
The first layer γ is a non-linear bricklayer permutation, which means that it consists
of nγ invertible S-boxes Sγi , operating independently on different bits of the state.
The first construction step is that all the Sγi ’s operate on the same number m of
bits. This restricts the block length n to be nγ · m.
Definition 84 Let a ∈ GF(2)n be an n-bit state.

The ith bundle a(i) of a is defined via:
a(i) := (aim , . . . , a(i+1)m−1 ), for i ∈ {0, . . . , nγ − 1}.
This partition of the n-bit state according to γ, is called the bundle partition of γ.
The second construction step is that Sγi operates on the ith bundle a(i) :
b(i) = Sγi (a(i) ).
From Proposition 22 follows that the linear weight of a correlation between an output
and an input parity of γ is the sum of the linear weights of the correlations between the
particular output and input parities of Sγi . And from Proposition 24 follows that the
differential weight of an difference propagation of two difference patterns through γ
is the sum of the differential weights of the difference propagations of the particular
difference patterns through Sγi .
Definition 85 Let u = (u(0) , . . . , u(nγ −1) ) be a selection pattern, according to the

bundle partition of γ. A bundle u(i) of u is called active, if:
u(i) = 0.
Definition 86 Let q = (q(0) , . . . , q(nγ −1) ) be a difference pattern, according to the

bundle partition of γ. A bundle q(i) of q is called active, if:
q(i) = 0.
Definition 87 If we consider a linear trail Uρ over an iterated block cipher ρ, we call

a bundle a(i) of the input state a of a particular round active, if u(i) is active, where
u is the input selection pattern of this round.
If we consider a differential trail Qρ over an iterated block cipher ρ, we call a
bundle a(i) of the input state a of a particular round active, if q(i) is active, where q
is the input difference pattern of this round.
Definition 88 The bundle weight wb (u) of a selection pattern u is the number of

active bundles in u.
Definition 89 The bundle weight wb (q) of a difference pattern q is the number

of active bundles in q.
Definition 90 The bundle weight wb (a) of a state a is the number of active bundles
in a.
Let us consider a linear trail. From the above definitions follows that:
wb (u) = wb (a),
if u is the input selection pattern and a is the input state of the same round.
The same holds for differential trails:
wb (q) = wb (a),
if q is the input difference pattern and a is the input state of the same round.
If the input selection pattern u(i) is zero it follows that the output selection w(i)
is zero, because otherwise:
2
m
−1
−m
(−1)w(i) Sγi (aj ) = 0
T
T
C(w(i) Sγi , 0) =2
j=0
and from Proposition 22 follows that in this case C(wT γ, uT _ ) = 0, which is a

contradiction to the definition of linear trails.
We obtain:
2
m
−1
C(0, 0) = 2−m 1=1
j=0
and hence:
Sγ
wl i (0, 0) = 0. (3.5.3)
Similarly, if the input difference pattern a(i) is zero it follows that b(i) is zero and
therewith:
2
m
−1
−m
Prob (0, 0) = 2
Sγi
δ(Sγi (aj ) ⊕ Sγi (aj )) = 1
j=0
and hence:
Sγ
wd i (0, 0) = 0. (3.5.4)
Definition 91 The bundle weight wb (Uρ ) of a linear trail Uρ is the sum of the
bundle weights of the input states of the individual rounds.
Definition 92 The bundle weight wb (Qρ ) of a differential trail Qρ is the sum of

the bundle weights of the input states of the individual rounds.
Let us assume that the round transformation ρ consist only of the non-linear bricklayer
permutation γ and consider a linear (differential) trail Uρ = (u(0) , . . . , u(r) ) (Qρ =
(q0 , . . . , qr )) over r rounds.
Applying Eq. (3.5.2), Proposition 22 and Eq. (3.5.3) we obtain:
γ −1

r−1
ρ

r−1 n
Sγ(i+1) (i)
wl (Uρ ) = wl i (u(i+1) , (i)
u )= wl j (u(j) , u(j) )
i=0 i=0 j=0
Sγ(i+1) (i)
≥ wb (Uρ ) · min wl j (u(j) , u(j) ) (3.5.5)
i∈{0,...,r−1},j∈{0,...,nγ −1}
Analogous we obtain by Eq. (3.5.4), Definition 81 and Proposition 24:

Sγ
wd (Qρ ) ≥ wb (Qρ ) · min wd j (q(j) i , q(j) i+1 ). (3.5.6)
i∈{0,...,r−1},j∈{0,...,nγ −1}
From this follows the third construction step, which is to find a S-box Sγ with good
non-linearity properties and use this on all nγ bundles a(i) .
S (i+1) (i)
By good non-linearity properties we mean that the minimum of wl γ (u(j) , u(j) )
S
and wdγ (q(j) i , q(j) i+1 ) should be high.
In [16] Kaisa Nyberg gave several examples for S-boxes with good non-linearity
properties.
With this construction step Eqs. (3.5.5) and (3.5.6) become:
S
wl (Uρ ) ≥ wb (Uρ ) · min wl γ (u(j)
i+1
, u(j)
i
) (3.5.7)
i∈{0,...,r−1},j∈{0,...,nγ −1}
and:
S
wd (Qρ ) ≥ wb (Qρ ) · min wdγ (q(j) i , q(j) i+1 ). (3.5.8)
i∈{0,...,r−1},j∈{0,...,nγ −1}
Equations (3.5.7) and (3.5.8) provide two possibilities to increase the lower bounds
of linear and differential trails. The first is, to construct a S-box with a high minimum
linear and differential weight, but both minimum weights are upper bounded by the
number of bits on which the S-box operates. This would mean we have to increase
the bundle size m. This has a high implementation cost and hence this disagrees with
the efficiency approach of the Wide Trail Strategy. The second possibility is to extend
the round transformation ρ by the linear diffusion step λ, which increases the bundle
weight of linear and differential trails.
Branch Numbers
All the discussions in this subsection are done with respect to the bundle partition
given by γ.
λ is a linear boolean permutation λ : GF(2)n → GF(2)n , with λ(a) = Ma, where
M is a binary n × n matrix.
For an output selection pattern w we have:
w T λ(a) = w T Ma = (MT w)T a.
It follows for the elements of the correlation matrix C λ of λ:

2
n
−1 2
n
−1
λ −n
(−1)(M w)T ai
= 2−n (−1)((M w)⊕u)T ai
T T T
Cw, u =2 (−1)u ai
i=0 i=0
= δ((MT w) ⊕ u).
Definition 93 The linear branch number Bl (ϕ) of a boolean permutation ϕ is

defined by:
Bl (ϕ) := min
ϕ
{wb (u) + wb (w)}.
w,u,Cw,u =0
If the boolean permutation is linear and denoted by λ, the branch number is defined
via:
Bl (λ) := min{wb (u) + wb (MT u)}.
u=0
Definition 94 The differential branch number Bd (ϕ) of a boolean permutation ϕ

is defined by:
Bd (ϕ) := min {wb (a ⊕ b) + wb (ϕ(a) ⊕ ϕ(b))}.

a,b=a
If the boolean permutation is linear and denoted by λ, the branch number is defined
via:
Bd (λ) := min{wb (a ) + wb (Ma )}.
a =0
The remaining discussions of this subsection are valid both for linear and differential
branch numbers so that we denote both Bl and Bd by B and speak of a pattern, instead
of a selection or difference pattern.
Since the output pattern corresponding to an input pattern with a single non-zero
bundle has at least one and at most nγ non-zero bundle(s), it holds for the branch
number B(λ) of a linear permutation:
2 ≤ B(λ) ≤ nγ + 1. (3.5.9)
We have derived the following properties:

• from the symmetry of the Definitions 93 and 94 follows:
B(ϕ) = B(ϕ−1 ).
• a pattern is not affected by a key addition and hence its bundle weight is not affected
• a bricklayer permutation operates independently on individual bundles and there-
fore cannot turn an active bundle into a non-active bundle and vice versa. Hence,
it does not affect the bundle weight
• if ρ is a γλ round transformation it follows:
B(ρ) = B(λ).
Let us consider a key-iterated block cipher over two rounds with a γλ round trans-
formation ρ. The bundle weight of a two-round trail is the number of active bundles
at the input of the first and at the input of the second round. The state of the input
of of the second round is the XOR of the output of the first round and a round key.
With the above properties we obtain the following theorem.
Theorem 61 (Two-Round Propagation Theorem, [5]) For a key-iterated block

cipher over two rounds with a γλ round structure, it follows for any two-round
trail Tγλ :
wb (Tγλ ) ≥ B(λ).
The Construction of λ
According to Theorem 61, one possibility to obtain high lower bounds on the bundle
weight of multiple round trails would be to construct the linear diffusion layer λ as a
linear boolean permutation with a high branch number. Similar to large S-boxes this
has a high implementation cost and hence contradicts to the efficiency approach of
the Wide Trail Strategy.
Instead, the Wide Trail Strategy suggests the construction of a key-iterated block
cipher, whose linear diffusion layer λ consists of a sequence of two steps:
• θ: a linear bricklayer permutation, which offers a high local diffusion. The D-boxes
of θ operate independently on columns, which consists of bundles with respect to
the bundle partition of γ.
• π: a transposition, which provides a high dispersion. Dispersion means that bun-
dles, which are in the same column are moved to different columns.
The Construction of θ
The diffusion step θ is a linear bricklayer permutation, which consists of nθ D-boxes
Dθj operating independently on different bundles with respect to the bundle partition
of γ.
The first construction step of θ is that each of the D-boxes operates on the same
number nξ of bundles. This restricts the number nγ of bundles to be nθ · nξ and hence
the block size n to be nθ · nξ · m.
Definition 95 Let c ∈ GF(2)n which has been partitioned into bundles c(i) , for
i ∈ {0, . . . , nγ − 1}, with respect to the bundle partition of γ.
The jth column c(j) is defined by:
c(j) := (c(jnξ ) , . . . , c((j+1)nξ −1) ), for j ∈ {0, . . . , nθ − 1}.
Similar to the construction of γ, the second construction step is that the D-box Dθj
operates on column c(j) . Since the D-boxes are linear, they can be written as a nξ × nξ
matrix Dθ(j) :
d (j) = Dθj (c(j) ) = Dθ(j) c(j) . (3.5.10)
The measure for diffusion is the branch number B(θ). Since the output state of θ
corresponding to the input state with one active bundle in one column active has at
least one and at most nξ active bundles, it follows:
2 ≤ B(θ) ≤ nξ + 1. (3.5.11)
The third construction step is then to find a D-box with the maximum branch number
nξ + 1 and once it is found this one is used on every column.
We can now define the diffusion step θ.
Definition 96 The linear bricklayer permutation θ : GF(2)mnξ → GF(2)mnξ is
defined by:
d = θ(c) :⇔ d (j) = Dθ c(j) , for all j ∈ {0, . . . , nθ − 1},
where Dθ is a nξ × nξ , with entries in GF(2)m .

The inverse permutation θ−1 is defined via:
−1
c = θ−1 (d) :⇔ c(j) = Dθ d (j) , for all j ∈ {0, . . . , nθ − 1},
−1 −1
where Dθ is a nξ × nξ , with entries in GF(2)m and Dθ × Dθ = Inξ .
Since nξ = nθ−1 · nγ , the implementation cost of a linear diffusion step with branch
number nξ + 1 is much lower than the cost of one with branch number nγ + 1.
We can now adopt Theorem 61 and obtain the following proposition:
Proposition 25 For a key-iterated block cipher over two rounds, in which the first
round transformation has a γθ structure, it holds for any two-round trail Tγθ :
wb (Tγθ ) ≥ NB(θ),
where N is the number of active columns at the input of the second round.
Proof We can apply Theorem 61 to each column separately. Each active column at
the input of the second round imposes that the same column was active at the input
of the first round and hence there are at least B(θ) active bundles in that column in
both input states together.
The Construction of π
We will now define the transposition π and introduce the diffusion optimality, which
means that π offers the highest possible dispersion.
Definition 97 The bundle transposition π : GF(2)n → GF(2)n is defined as:
b = π(a) :⇔ b(i) = a(p(i)) ,
where p(i) is a permutation of the bundle partition of γ. The inverse bundle trans-
position π −1 is defined by:
a = π(b) :⇔ a(i) = b(p−1 (i)) .
Since θ and π together provide an inter-column action it is no longer sufficient to

concentrate only on the branch number but also on the column branch number. To
do so, we, firstly, define the column weight of a pattern.
Definition 98 A column c(j) is called active if at least one of its bundles c(jnξ ) ,
. . . , c((j+1)nξ −1) is active.
Definition 99 The column weight wc (a) of a (selection or difference) pattern a

is the number of active columns in the pattern a.
Definition 100 The column branch number B c () of a linear boolean permutation
is defined as:
B c () := min{wc (a) + wc ((a))}.

a=0
We will show now that if π is properly chosen the column branch number of π ◦ θ ◦ π
equals the branch number of θ.
Definition 101 The bundle transposition π is called diffusion optimal, if and only
if all bundles, which were in the same column of the input state of π are in different
columns of its output state.
From Definition 97 follows that if π is diffusion optimal, π −1 also is diffusion optimal.

Further on, Definition 98 imposes that the number nθ of columns has to be at least
as big as the number nξ of bundles in each column. This restricts the block size n in
the following way:
nθ ≥ nξ ⇒ n = nθ · nξ · m ≥ nξ2 · m. (3.5.12)
Proposition 26 If the bundle transposition π is diffusion optimal and the diffusion

step θ has a maximum branch number B(θ), it holds for := π ◦ θ ◦ π:
B c () = B(θ).
Proof Let a denote the input state of , d denote its output state and b and c its
intermediate states, with:
b = π(a), c = θ(b) = θ(π(a)) and d = π(c) = π(θ(π(a))) = (a).
Firstly, we assume that wb (a) = 1 and hence wc (a) = 1.

From this follows that there exists exactly one active column b(j) in b, with:
wb (b(j) ) = 1.
The property that θ has a maximum branch number B(θ) induces that there exists
exactly one column c(j) in c, with:
wb (c(j) ) = B(θ) − 1.
Since π is diffusion optimal, all the B(θ) − 1 active bundles in c(j) are mapped to
different columns of d and this yields to:
wc (d) = B(θ) − 1.
It follows that wc (a) + wc (d) = B(θ) and hence:
B c () ≤ B(θ).
Secondly, we will show that B c () ≥ B(θ), for all 0 = a ∈ GF(2)n .

For all a = 0 holds wc (a) ≥ 1 and hence wc (b) ≥ 1.
For any active column b(j) in b it follows that c(j) is active, too, and:
wb (b(j) ) + wb (c(j) ) = B(θ).
If b(j) and hence c(j) would be the single active columns in b and c it would follow
by the diffusion optimality of π and π −1 that:
wc (d) = wb (c(j) ) and wc (a) = wb (b(j) ).
But if the number of active columns in b and c is greater than 1 it could occur that:
wc (d) > wb (c(j) ) and wc (a) > wb (b(j) ).
Altogether, we have:
(j)
wc (a) + wc (d) ≥ wb (b(j) ) + wb = B(θ).
Now we are able to prove the final statement of the Wide Trail Strategy.
Theorem 62 For a key-iterated block cipher B with a γπθ round transformation,

diffusion optimal π and where θ has a maximum branch number B(θ), it holds for
any four-round trail Tγπθ :
wb (Tγπθ ) ≥ B(θ)2 .
Proof Consider four rounds of a key-iterated block cipher with a γπθ round trans-
formation:
B4 := σ[κ4 ]◦(θ◦π◦γ)◦σ[κ3 ]◦(θ◦π◦γ)◦σ[κ2 ]◦(θ◦π◦γ)◦σ[κ1 ]◦(θ◦π◦γ)◦σ[κ0 ],
where σ[κi ] is the round key addition of round key κi .

Since the non-linear bricklayer permutation γ and the key addition σ have no
impact on the bundle weight of the trail, we write:
B4 = (θ ◦ π) ◦ (θ ◦ π) ◦ (θ ◦ π) ◦ (θ ◦ π)
= θ ◦ π ◦ θ ◦ (π ◦ θ ◦ π) ◦ θ ◦ π.
We denote the input state of B4 by a and according to that:
a := π(a), b := θ(a ), b := π(b), c := θ(b ), c := π(c) and d := θ(c ).
We have to show that:
wb (a) + wb (b) + wb (c) + wb (d) ≥ B(θ)2 .
Since π does not change the number of active bundles and θ does not change the
number of active columns, it holds inter alia:
(i) wb (a ) = wb (a)
(ii) wb (c ) = wb (c)
(iii) wc (d) = wc (c )
Since c = π(θ(π(b))), it follows from (3.5.12) and (iii):
wc (d) + wc (b) ≥ B(θ). (3.5.13)
Further on, by applying (3.5.12) and (i), we obtain:
wb (a) + wb (b) ≥ wc (b) · B(θ)
and from (3.5.12) and (ii):
wb (c) + wb (d) ≥ wc (d) · B(θ)

Together we have:
wb (a) + wb (b) + wb (c) + wb (d) ≥ (wc (b) + wc (d)) · B(θ)
and hence with (3.5.13):
wb (a) + wb (b) + wb (c) + wb (d) ≥ B(θ)2
With this final theorem Eqs. (3.5.7) and (3.5.8) become:

S
wl (Uρ ) ≥ B(θ)2 · min wl γ (u(j)
i+1
, u(j)
i
) (3.5.14)
i∈{0,...,r−1},j∈{0,...,nγ −1}
and:
S
wd (Qρ ) ≥ B(θ)2 · min wdγ (q(j) i , q(j) i+1 ). (3.5.15)
i∈{0,...,r−1},j∈{0,...,nγ −1}
To construct a key-iterated block cipher, which resists linear and differentials attacks,
we have to give it a γπθ round transformation, where Sγ operates on only a small
number of bits with a high minimum linear and differential weight, π is diffusion
optimal and θ has the maximum possible branch number. It follows from Theorem 62
that Eqs. (3.5.14) and (3.5.15) hold for any four-round trail. To obtain a given security
level we only have to increase the number of rounds, which will increase the bundle
weight of any trails over all but a few rounds of the cipher.
3.6 The Specifications of Rijndael
In this section we will explain exact specifications of Rijndael and show how the
individual steps of the round transformations work.
Rijndael is a key-iterated block cipher. It was developed to work for different
values of the block length NB and the cipherkey length NC . Both are either 128,
192 or 256 bits. The number of rounds Nr depends on NB and NC and is defined as
follows:
⎧
⎨ 10, if max{NB , NC } = 128
Nr := 12, if max{NB , NC } = 192
⎩
14, if max{NB , NC } = 256
The design of Rijndael was derived from the Wide Trail Strategy and therefore it
has a linear and a non-linear layer. The non-linear layer consists of one step, the
SubBytes step, and the linear layer consists of two steps, the ShiftRows step and the
MixColumns step. Each round transformation is followed by a Key Addition with the
particular roundkey which is derived from the cipherkey via the Key Schedule.
The last section of this section covers the decryption, which has the nice added
feature that it can be done in mainly the same way as the encryption.
3.6.1 The Input, the Output, and the State
As explained in Sect. 3.4 the inputs of Rijndael are the plaintext block, which is an
one-dimensional array of bits of length NB and the cipherkey, a one-dimensional
array of bits of length NC . The plaintext block is also a one-dimensional array of
bytes of length 18 NB , which is denoted by p0 p1 . . . p 18 NB −1 . Similarly the output, which
is the ciphertext block, is a one-dimensional array of bytes of length 81 NB , denoted
by c0 c1 . . . c 18 NB −1 .
All steps of Rijndael, this means the round transformations and all their individual
steps and the roundkey addition, operate on the intermediate results, called the states.
Each state can be seen as a two-dimensional array of bytes with four rows and
Nb := 32 1
NB columns. Figure 3.1 shows the state for NB = 128.
The very first step of Rijndael is the mapping of the plaintext block p0 . . . p 18 NB −1
to the state. This is done via the following equation:
aij = pi+4j , for 0 ≤ i < 4 and 0 ≤ j < Nb .
This means that the state is ‘filled up’ column by column from the upper left to the
lower right with the individual bytes of the plaintext block.
After the last step of the encryption the final state is mapped on the ciphertext
block via:
ci = ai mod 4, 4i , for i ∈ {0, . . . , 4Nb − 1}.
So the state is ‘released’ into the ciphertext block again column by column from the
upper left to the lower right.
Fig. 3.1 The state for

NB = 128 a0,0 a0,1 a0,2 a0,3
a1,0 a1,1 a1,2 a1,3
a2,0 a2,1 a2,2 a2,3
a3,0 a3,1 a3,2 a3,3

3.6 The Specifications of Rijndael 195
3.6.2 The Non-linear Layer
The SubBytes Step

The SubBytes step is a bricklayer permutation, so it can be decomposed into several
boolean permutations, which operate independently on subsets of the state. Since
it is a non-linear permutation, these boolean permutations are called S-boxes. For
simplicity all the S-boxes are, in fact, one and the same boolean permutation, so we
have only one S-box, which is denoted by SRD . The subsets on which this S-box
operates, are the individual bytes aij of the state, which is visualized in Fig. 3.2.
Design Criteria
There are three design criteria, which were considered in the development of the
SubBytes step. The first is, of course, that it should offer a high shape non-linearity, the
second is that it should be algebraic complex and the third criterion is the simplicity,
which means that it should be easy to describe and have an efficient computability.
In his work [16], Kaisa Nyberg gave the following four criteria, which a substi-
tution step, like the S-box, should satisfy:
• high non-linearity
• resistance against linear cryptanalysis
• resistance against differential cryptanalysis
• efficient construction and computability
He also gave several alternatives of functions, which satisfy the above criteria. For
Rijndael the following of these alternatives was chosen:
g : GF(28 ) → GF(28 )
g(a) = a−1 ,
In this equation a−1 is the multiplicative inverse of a in GF(28 ), with m(x) = x 8 +

x 4 + x 3 + x + 1 as the irreducible reduction polynomial.
SRD
a0,0 a0,1 a0,2 a0,3 b0,0 b0,1 b0,2 b0,3
a1,0 a1,1 a1,2 a1,3 b1,0 b1,1 b1,2 b1,3
a2,0 a2,1 a2,2 a2,3 b2,0 b2,1 b2,2 b2,3
a3,0 a3,1 a3,2 a3,3 b3,0 b3,1 b3,2 b3,3
Fig. 3.2 The subsets on which the S-box operates

The disadvantages of this choice for the S-box are, on the one hand, the fact that
g(“00”) = “00” and on the other hand, this function has a very simple algebraic
expression, since a−1 = a254 in GF(28 ). This fact would offer vulnerability against
the interpolation attack [11], which was developed by Thomas Jakobsen and Lars
R. Knudsen.
To get rid of these two disadvantages we combine the non-linear permutation g
with the affine permutation f , which is defined as follows:
f : GF(28 ) → GF(28 )
f (a) = b
¨

⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞
b0 1 0 0 0 1 1 1 1 a0 1
⎜ b1 ⎟ ⎜ 1 1 0 0 0 1 1 1⎟ ⎜ a1 ⎟ ⎜ 1 ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜ b2 ⎟ ⎜ 1 1 1 0 0 0 1 1⎟ ⎜ ⎟ ⎜ ⎟
⎜ ⎟ ⎜ ⎟ ⎜ a2 ⎟ ⎜ 0 ⎟
⎜ b3 ⎟ ⎜ 1 1 1 1 0 0 0 1⎟⎜ ⎟ ⎟ ⎜ ⎟
⎜ ⎟=⎜ ⎜ a3 ⎟ ⊕ ⎜ 0 ⎟
⎜ b4 ⎟ ⎜ 1 ⎟
1 1 1 1 0 0 0 ⎟ ⎜ a4 ⎟⎜ ⎜ ⎟
⎜ ⎟ ⎜ ⎟ ⎜0⎟
⎜ b5 ⎟ ⎜ 0 ⎟ ⎜
1 1 1 1 1 0 0 ⎟ ⎜ a5 ⎟ ⎜ ⎟ ⎟
⎜ ⎟ ⎜ ⎜1⎟
⎝ b6 ⎠ ⎝ 0 0 1 1 1 1 1 0 ⎠ ⎝ a6 ⎠ ⎝ 1⎠
b7 0 0 0 1 1 1 1 1 a7 0
Since f is an affine permutation, it does not effect the non-linearity of g. Moreover

f was chosen in such a way that SRD has no fixed points (SRD (a) ⊕ a = “00”) or
opposite fixed points (SRD (a) ⊕ a = “FF”). This was only done as a precautionary
measure, since, up to now, there are no attacks known which exploit the existence of
(opposite) fixed points.
By applying the Lagrange interpolation technique we obtain the following expres-
sion for SRD :
SRD (a) = “05” a254 ⊕ “09” a253 ⊕ “F9” a251 ⊕ “25” a247
⊕ “F4” a239 ⊕ “01” a223 ⊕ “B5” a191 ⊕ “8F” a127 ⊕ “63”.
Together with the linear layer, consisting of ShiftRows and MixColumns, this expres-
sion offers sufficient security against the interpolation attack.
There is one other fact about the affine permutation f . As we see, the matrix
which defines f is a circulant (8 × 8)-matrix. So if we go the other way round as in
the subsection “The Finite Ring < GF(28 )[x]|4 , ⊕, • >” of Sect. 3.3.3, where we
showed that the multiplication by a fixed polynomial in < GF(28 )|4 , ⊕, • > can
be written as a circulant (4 × 4)-matrix, then we can show that f can be seen as
a multiplication by a fixed polynomial c(x), with m (x) = x 8 + 1 as the reducible
reduction polynomial, followed by an addition with d(x) = x 6 + x 5 + x + 1. Since in
this case, the first row of the matrix would be (c0 c7 c6 c5 c4 c3 c2 c1 ), this
fixed polynomial has to be c(x) = x 4 + x 3 + x 2 + x + 1.
Altogether f can be written as:
f (a) = ((x 4 +x 3 +x 2 +x +1)⊗(a7 x 7 +· · ·+a0 ))⊕(x 6 +x 5 +x +1) (mod x 8 +1).
If we denote the multiplication modulo m (x) of two polynomials, which are elements
of GF(2)[x]|8 , by , it follows that the triple
< GF[2][x]|8 , ⊕, > forms a Ring.
Definition 102 The SubBytes step is a bricklayer permutation, which consists of

the 18 NB -fold application of the S-box SRD : GF(28 ) → GF(28 ), operating on the
individual bytes α of the input state, which is defined by:
SRD (α) := f (g(α)),
where g(α) α = 1 and

f (β) = ((x 4 + x 3 + x 2 + x + 1) b(x)) ⊕ (x 6 + x 5 + x + 1), where β ∼ b(x).
InvSubBytes
The inverse operation of SubBytes is called InvSubBytes and is obtained by the
application of the inverse permutation of f , called f −1 , followed by g, because g is
the inverse operation and therewith self-inverse.
For f −1 , it must hold that f −1 (f (a)) = a(x) ∼ a ∈ B, for all a ∈ B, where B is
the set of all bytes. Additionally, it should be of the same form like f , which means
that for suitable choices for the constant polynomials c (x) and d (x): f −1 (b) =
(c (x) b(x)) ⊕ d (x).
Together the following must hold for all a(x) ∼ a ∈ B:
f −1 (f (a)) = a(x)
⇔ (c (x) ((c(x) a(x)) ⊕ d(x))) ⊕ d (x) = a(x)
⇔ (c (x) c(x) a(x)) ⊕ (c (x) d(x)) ⊕ d (x) = a(x)
⇔ c (x) = c−1 (x) (mod x 8 + 1) ∧ d (x) = c−1 (x) d(x).
Since c(x) is coprime to x 8 + 1, c−1 (x) exists and therewith c (x) and d (x) are well-
defined. By applying the Extended Euclidean Algorithm we can determine c−1 (x) =
x 6 + x 3 + x and it follows that:
f −1 (b) = ((x 6 + x 3 + x) b(x)) ⊕ (x 2 + 1). Again f −1 (b) = a can be written as a
multiplication by a circulant (8 × 8)-matrix followed by an addition with d ∼ d (x):
⎛ ⎞ ⎛ ⎞⎛ ⎞ ⎛ ⎞
a0 0 0 1 0 0 1 0 1 b0 1
⎜ a1 ⎟ ⎜ 1 0 0 1 0 0 1 0 ⎟ ⎜ b1 ⎟ ⎜ 0 ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜ a2 ⎟ ⎜ 0 1 0 0 1 0 0 1 ⎟ ⎜ b2 ⎟ ⎜ 1 ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜ a3 ⎟ ⎜ 1 0 1 0 0 1 0 0 ⎟ ⎜ b3 ⎟ ⎜ 0 ⎟
⎜ ⎟=⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜ a4 ⎟ ⎜ 0 1 0 1 0 0 1 0 ⎟ ⎜ b4 ⎟ ⊕ ⎜ 0 ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟
⎜ a5 ⎟ ⎜ 0 0 1 0 1 0 0 1 ⎟ ⎜ b5 ⎟ ⎜ 0 ⎟
⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟
⎝ a6 ⎠ ⎝ 1 0 0 1 0 1 0 0 ⎠ ⎝ b6 ⎠ ⎝ 0 ⎠
a7 0 1 0 0 1 0 1 0 b7 0
Definition 103 The InvSubBytes step is a bricklayer permutation, which consists

−1
of the 18 NB -fold application of the S-box SRD : GF(28 ) → GF(28 ), operating on the
individual bytes β of the input state, which is defined by:
−1
SRD (β) := g(f −1 (β)),
where g(α) α = 1 and

f −1 (β) = ((x 6 + x 3 + x) b(x)) ⊕ (x 2 + 1), where β ∼ b(x).
3.6.3 The Linear Layer
The ShiftRows Step

The ShiftRows step is a byte transposition. It consists only of a cyclically left-shift
of the bytes of each row, where the bytes in row i are shifted over Ci bytes. The only
thing remaining is the choice of the four constants C0 , . . . , C3 .
Design Criteria
The two design criteria for the ShiftRows step are:
• simplicity
• diffusion optimality
The simplicity criterion means nothing more than that one of the Ci ’s equals zero.
In Rijndael C0 is zero.
The ShiftRows step is diffusion optimal, if all bytes, which were in the same
column of the input state, are mapped into different columns of the output state.
To achieve this criterion, all the Ci ’s have to be different modulo Nb . The Ci ’s are
obtained from the following table:
NB C0 C1 C2 C3
128 0 1 2 3
192 0 1 2 3
256 0 1 3 4
Definition 104 Let aij be the byte in row i and column j of the input state sinput and
bij the byte in row i and column j of the output state soutput of ShiftRows SR.
SR is then defined by:
SR(sinput ) = soutput ,
with bij := ai,(j+Ci ) mod Nb and the Ci s are obtained from the above tabular.
Figure 3.3 shows the ShiftRows step for NB = 128.

Fig. 3.3 The ShiftRows step for NB = 128
InvShiftRows
The inverse of ShiftRows, which is denoted by InvShiftRows, is, of course, the byte
transposition, which cyclically shifts the bytes of row i over Ci bytes to the right.
Definition 105 Let bij be the byte in row i and column j of the input state tinput and
aij the byte in row i and column j of the output state toutput of InvShiftRows SR−1 .
SR−1 is then defined by:
SR−1 (tinput ) = toutput ,

with aij := bi,(j−Ci ) mod Nb , with the same Ci s like before.
The MixColumns Step

The MixColumns step is a bricklayer permutation. It can be decomposed into several
linear boolean permutations which are called D-boxes according to Definition 58. In
fact, like for the SubBytes step, in MixColumns there is only one D-box, denoted by
DRD , operating independently on each of the Nb 4-byte columns of the state. This
D-box consists of the multiplication by a fixed polynomial c(x) ∈ GF(28 )[x]|4 , with
l(x) = x 4 + 1 as the reducible reduction polynomial.
Figure 3.4 shows the application of the D-box for NB = 128.
Design Criteria
In order to define DRD we have to choose the fixed polynomial c(x). Of course, c(x)
has to coprime to l(x) = x 4 + 1 = (x + 1)4 , which leads to the criterion that the
decomposition of c(x) must not include the factor x + 1.
Further on, it should have an efficient computability.
Let c(x) = c3 x 3 + c2 x 2 + c1 x + c0 ∈ GF(28 )[x]|4 be the fixed polynomial
and a(x) = a3 x 3 + a2 x 2 + a1 x + a0 ∈ GF(28 )[x]|4 be a 4-byte column of the
input state of MixColumns. As we have seen in subsection “The Finite Ring <
GF(28 )[x]|4 , ⊕, • >” of Sect. 3.3.3 the multiplication of c(x) and a(x) modulo l(x)
can be written as a matrix multiplication. This means that the coefficients ci , ai ∈
DRD
a0,0 a0,1 a0,2 a0,3 b0,0 b0,1 b0,2 b0,3
a1,0 a1,1 a1,2 a1,3 b1,0 b1,1 b1,2 b1,3
a2,0 a2,1 a2,2 a2,3 b2,0 b2,1 b2,2 b2,3
a3,0 a3,1 a3,2 a3,3 b3,0 b3,1 b3,2 b3,3
Fig. 3.4 The application of the D-box for NB = 128
GF(28 ) are multiplied by the application of the multiplication, which was defined in
subsection “The Finite Field GF(28 )” of Sect. 3.3.3.
In the same subsection it was shown that this multiplication can be done efficiently
by the application of xtime, if the coefficients of c(x) are ‘small’.
From this it follows that the criterion of efficient computability can be translated
into the requirement that the coefficients of c(x) are ‘small’.
Since also the inverse operation of MixColumns should be efficiently computable,
the criterion has to be extended in such a way that also the coefficients of the fixed
polynomial d(x) ∈ GF(28 )[x]|4 , by which a 4-byte-column in InvMixColumns is
multiplied, have to be ‘small’.
In Rijndael a coefficient of the fixed polynomials c(x), d(x) ∈ GF(28 )[x]|4 is said
to be ‘small’ if it is less than “10”.
The last design criterion is that the coefficients of c(x) are chosen in such a way
that the branch number of MixColumns is 5 which is the maximum branch number.
Definition 106 The MixColumns step is a bricklayer permutation, which consists

of the Nb -fold application of the D-box DRD , operating independently on the indi-
vidual 4-byte-columns α of the input state, which is defined by:
DRD (α) := c(x) • a(x),

where ψ(α) = a(x) and c(x) := “03” x 3 + x 2 + x + “02”.
Following subsection “The Finite Ring < GF(28 )[x]|4 , ⊕, • >” of Sect. 3.3.3,
b(x) = b3 x 3 +b2 x 2 +b1 x +b0 = (“03” x 3 +x 2 +x + “02”)•(a3 x 3 +a2 x 2 +a1 x +a0 )
can be written as the multiplication by the following circulant matrix:
⎛ ⎞ ⎛ ⎞⎛ ⎞
b0 02 03 01 01 a0
⎜ b1 ⎟ ⎜ 01 02 03 01 ⎟ ⎜ a1 ⎟
⎜ ⎟=⎜ ⎟⎜ ⎟.
⎝ b2 ⎠ ⎝ 01 01 02 03 ⎠ ⎝ a2 ⎠
b3 03 01 01 01 a3
There is one other interesting way of rewriting MixColumns, denoted by MC. Let aij
denote the byte in row i and column j of the input state and bij denote the byte in row
i and column j of the output state.
It follows: bij = MC(aij ) := “02” aij ⊕ “03” ai+1,j ⊕ ai+2,j ⊕ ai+3,j , where
the (i + k)’s are taken modulo 4, for k ∈ {1, 2, 3}.
InvMixColumns
−1
InvMixColumns is also a bricklayer permutation, consisting of one D-box DRD , oper-
−1
ating on each of the Nb 4-byte-columns of the input state. Again DRD is the multipli-
cation by a fixed polynomial d(x) ∈ GF(28 )[x]|4 modulo l(x) = x 4 + 1.
It must hold that:
c(x) • d(x) = 1.
By applying the Extended Euclidean Algorithm we obtain:
d(x) = “0B” x 3 + “0D” x 2 + “09” x + “0E”.
Definition 107 The InvMixColumns step is a bricklayer permutation which con-

−1
sists of the Nb -fold application of the D-box DRD , operating independently on the
individual 4-byte-columns β of the input state, which is defined by:
−1
DRD (β) := d(x) • b(x),
where ψ(β) = b(x) and d(x) := “0B” x 3 + “0D” x 2 + “09” x + “0E”.
Again, a(x) = d(x) • b(x) can be written as the multiplication by the following
circulant matrix: ⎛ ⎞ ⎛ ⎞⎛ ⎞
a0 0E 0B 0D 09 b0
⎜ a1 ⎟ ⎜ 09 0E 0B 0D ⎟ ⎜ b1 ⎟
⎜ ⎟=⎜ ⎟⎜ ⎟
⎝ a2 ⎠ ⎝ 0D 09 0E 0B ⎠ ⎝ b2 ⎠ .
a3 0B 0D 09 0E b3
And InvMixColumns, denoted by MC −1 , can be written as:

aij = MC −1 (bij ) := “0E” bij ⊕ “0B” bi+1,j ⊕ “0D” bi+2,j ⊕ “09” bi+3,j , where
the bij ’s are the individual bytes of the input state and the aij ’s are the individual bytes
of the output state of InvMixColumns.
3.6.4 The AddRoundKey Step
We have seen in Sect. 3.4 that Rijndael is a key-iterated block cipher.

Up to now we have defined how the plaintext block is mapped on the state and
back on the ciphertext block and how the individual steps of the round transformation
operate on the state. So the only things left to do, are to define the AddRoundKey
step and how the individual RoundKeys are derived from the cipherkey.
Let us suppose we have generated all the required RoundKeys rki . Since there
is an additional AddRoundKey step before the first round, we will need (Nr + 1)
different RoundKeys, all of the length NB .
Definition 108 The AddRoundKey step of round i, with i ∈ {0, 1, . . . , Nr }, is a

bitwise XOR of its input state and the ith RoundKey rki .
Since the XOR operation on bits is self-inverse, it follows that the AddRoundKey
step is also self-inverse so that the AddRoundKey step is used in both encryption and
decryption.
3.6.5 The Key Schedule
The Key Schedule consists of two different parts. The first part is the Key Expansion,
where the cipherkey is expanded into the ExpandedKey and the second part is the
RoundKey Selection, where the ExpandedKey is decomposed into the individual
RoundKeys rki . Since we need (Nr + 1) RoundKeys, all of length NB , the length of
the ExpandedKey has to be NB (Nr + 1) bits.
The Key Expansion
The Key Expansion is a boolean function, consisting of several rounds
NKE := N1k Nb (Nr + 1), where Nk := 32 1
NC , with the cipherkey as its input and
the ExpandedKey, consisting of all the RoundKeys, as its output. Of course, this
is a security-critical part of Rijndael so that the Key Expansion was based on the
following design criteria:
• non-linearity
• diffusion
• no symmetry in the rounds
The non-linearity criterion is obtained by the application of a S-box, which is in
fact the same S-box SRD like in the SubBytes step. In order to offer diffusion, a shift
over the columns is applied and finally different constants for each round are used
to delete the symmetry of each round.
The ExpandedKey is a two-dimensional array of four rows and Nb (Nr + 1)
columns. The first round of the KeyExpansion is different than the other rounds,
since there only the cipherkey is used to fill up the first columns of the ExpandedKey
and in the other rounds the already filled up columns are used to fill up the remaining
columns.
We will visualize how the KeyExpansion works for NC = 128.
In the first round the cipherkey is mapped into the first Nk = 4 columns of the
ExpandedKey. This is done in the same way like the plaintext block is mapped into
the state. Let z = z0 z1 . . . z 18 NC −1 be the cipherkey, where the zi ’s are bytes and kij be
the byte in row i and column j of the ExpandedKey (Fig. 3.5).
Fig. 3.5 The first round

k0,0 k1,0 k2,0 k3,0
k0,1 k1,1 k2,1 k3,1

•••
k0,2 k1,2 k2,2 k3,2
k0,3 k1,3 k2,3 k3,3
K0 K1 K2 K3
Then:
kij = zi+4j , for 0 ≤ i < 4 and 0 ≤ j < Nk
The second to the last round all have the same structure and can be divided into
two different cases (Figs. 3.6 and 3.7).
If j = 0 mod Nk , then the jth column Kj is the XOR of the previous column Kj−1
and column Kj−Nk , written: Kj = Kj−Nk ⊕ Kj−1 .
And if j = 0 mod Nk , then the jth column Kj is a XOR of column Kj−Nk and the
previous column Kj−1 , after function F was applied to Kj−1 . This is written in the
following form: Kj = Kj−Nk ⊕ F(Kj−1 ).
The function F is the iterated application of the following parts.
Firstly, each byte of Kj−1 is transformed via SRD , then Kj−1 is shifted over one
byte to the top and, lastly, the round constant RC(m) := x m−1 , for m ∈ {2, . . . , NKE },
is added via the bitwise XOR-operation.
Fig. 3.6 First case of the

other rounds
K0 K1 K2 K3 K4 K5 K6 K7 •••
Fig. 3.7 Second case of the

other rounds
K0 K1 K2 K3 K4 K5 K6 K7 •••
F
Altogether we have:

j
kij = ki,j−Nk ⊕ SRD (ki+1,j−1 ) ⊕ RC ,
Nk
where kij is the ith byte of column j.

The RoundKey Selection
Finally the RoundKey rkj , for j ∈ {0, . . . , Nr }, of the jth round is given by the columns
KNb ·j , . . . , KNb ·(j+1)−1 .
Figure 3.8 visualizes the RoundKey selection for NC = 192 and NB = 128.
3.6.6 Encryption
This encryption is written in pseudo-code, which means that both input and output
are arguments of the individual functions.
For example Rijndael(plaintext, cipherkey, ciphertext) means that the argu-
ments of the whole cipher are the plaintext, the cipherkey and the ciphertext,
where ciphertext is an empty argument and obtains its value during the execution
of the function Rijndael. For some functions like AddRoundKey, Round, FinalRound
and the individual steps of each round there is no particular output given. The out-
put of these functions is always the state.
For given NB , NC and Nr the encryption is done in the following way:
Rijndael(plaintext, cipherkey, ciphertext)

{
PlainToState(plaintext, state);
KeySchedule(cipherkey, roundkeys[i]);
AddRoundKey(state, roundkeys[0]);
for (i = 1, i < Nr , i++) {
Nk = 6
K0 K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 K12 • • •
rk0 rk1 rk2 •••
Nb = 4
Fig. 3.8 The RoundKey selection for NC = 192 and NB = 128

Round(state, roundkeys[i]);}
FinalRound(state, roundkeys[Nr ]);
StateToCipher(state, ciphertext);
}
with:
KeySchedule(cipherkey, roundkeys[i])
{
KeyExpansion(cipherkey, expkey);
RoundKeySelection(expkey, roundkeys[i]);
}
Round(state, roundkeys[i])
{
SubBytes(state);
ShiftRows(state);
MixColumns(state);
AddRoundKey(state, roundkeys[i]);
}
FinalRound(state, roundkeys[Nr ])
{
SubBytes(state);
ShiftRows(state);
AddRoundKey(state, roundkeys[Nr ]);
}
The variables of the Rijndael cipher and its individual functions are:
• plaintext, ciphertext:
one-dimensional arrays of bytes of length 18 NB
• cipherkey:
one-dimensional array of bytes of length 18 NC
• state:
1
two-dimensional array of bytes with 4 rows and 32 NB columns
• expkey:
one-dimensional array of bytes of length 18 (Nr + 1)NB
• roundkeys[i]:
one-dimensional array of round keys of length Nr + 1, where roundkeys[i] is the
ith round key
3.6.7 Decryption
There are two ways in which the decryption can be done. The first is the straight-
forward decryption, where the decryption is done by applying the operations exactly
the other way round.
Table 3.1 shows this for a three-round Rijndael.
The other way is called the equivalent decryption, where the decryption is done
in mainly the same way as the encryption. This can be done because of the following
properties of the individual steps of Rijndael.
Since InvSubBytes operates on each byte of the state independently and
InvShiftRows is a shift of the rows of the state and has no effect on the values of
the individual bytes, these two steps can be interchanged.
In order to interchange InvMixColumns and AddRoundKey we have to take advan-
tage of the linear structure of InvMixColumns.
From the linearity of InvMixColumns it follows that:
InvMixColumns(a ⊕ rki ) = InvMixColumns(a) ⊕ InvMixColumns(rki )
It follows that if the RoundKey rkj is changed into InvMixCoulmns(rkj ) then InvMix-
Columns and AddRoundKey can be interchanged, too.
Table 3.2 shows the equivalent decryption for a three-round Rijndael.
The advantage of the equivalent decryption is that it can be done by the same
algorithm as the encryption, where only the kes schedule has to be adapted. This is
especially important if the cipher is constructed in hardware, since we are able to
encrypt and decrypt with the same hardware.
Table 3.1 The straight-forward decryption for a three-round Rijndael

Encryption Decryption
AddRoundKey(rk0 ) AddRoundKey(rk3 )
SubBytes InvShiftRows
ShiftRows InvSubBytes
MixColumns
SubBytes InvMixColumns
ShiftRows InvShiftRows
MixColumns InvSubBytes
SubBytes InvMixColumns
InvSubBytes
Table 3.2 The equivalent decryption for a three-round Rijndael

Encryption Decryption
SubBytes InvSubBytes
MixColumns InvMixColumns
AddRoundKey(rk1 ) AddRoundKey(InvMixColumns(rk2 ))
MixColumns InvMixColumns
AddRoundKey(rk2 ) AddRoundKey(InvMixColumns(rk1 ))
3.6.8 Complexity
First we will calculate the complexity of the individual steps of Rijndael. The measure
of the complexity is how often the S-box SRD and the XOR-operation on bytes are
applied.
SubBytes:
In the SubBytes step the S-box SRD is applied to each of the 18 NB = 4Nb bytes of the
state so that its complexity is:
4Nb SRD ’s.
ShiftRows:
The ShiftRows step consists only of a shift on byte-level and therefore does not
contribute to the complexity of the cipher.
MixColumns:
If we denote one column of the input state of the MixColumns step with (a0 , a1 , a2 , a3 )
and the corresponding column of the output state with (b0 , b1 , b2 , b3 ), the Mix-
Columns step MC can be written as follows:
bi = MC(ai ) = “02” ai ⊕ “03” ai+1 ⊕ ai+2 ⊕ ai+3

= xtime(ai ) ⊕ xtime(ai+1 ) ⊕ ai+1 ⊕ ai+2 ⊕ ai+3
It follows that each application of the D-box of the MixColumns step consists of
four applications of the XOR-operations on bytes and two applications of xtime.
In subsection “The Finite Field GF(28 )” of Sect. 3.3.3 we have seen that the xtime
operation consists either only of a left-shift of bits or of a left-shift of bits followed
by one XOR-operation on bytes. Since the shift operation does not contribute to the
complexity, we assume that the xtime operation equals one XOR-operation on bytes.
The D-box is applied to each of the Nb columns so that the whole MixColumns
step has a complexity of:
6Nb XORs.
AddRoundKey:
The AddRoundKey step is the NB -fold application of the bitwise XOR of the state and
the particular RoundKey, which corresponds to the ( 18 NB = 4Nb )-fold application of
the XOR-operation on bytes and therefore its complexity is:
4Nb XORs.
Table 3.3 shows the complexity of each of the individual steps of Rijndael.
We can now calculate the complexity of the whole Rijndael cipher.
As shown in Sect. 3.6.6 Rijndael consists of the KeyExpansion, the
initial AddRoundKey step, the Round and the FinalRound.
KeyExpansion:
In subsection “The Key Expansion” of Sect. 3.6.5 we have seen that the KeyExpansion
consists of
NKE rounds, where NKE = N1k Nb (Nr + 1) and Nk = 32 1
NC .
In the first round no calculation is done, since there only the cipherkey is mapped
into the first Nk columns and in the following rounds each column Kj of the Expand-
edKey is derived from the previous columns.
If j = 0 (mod Nk ), Kj = Kj−Nk ⊕ Kj−1 , which corresponds to four XOR-
operations on bytes.
If j = 0 (mod Nk ), Kj = Kj−Nk ⊕ F(Kj−1 ).
The map F consists of four applications of the S-box SRD , one shift and four
XOR-operations on bytes, from which it follows that in this case four applications
of SRD and eight XOR-operations on bytes are done.
It follows that each round, besides the first, consists of four applications of SRD
and 4(Nk + 1) XOR-operations on bytes and therewith the complexity of the whole
KeyExpansion is:
4( N1k Nb (Nr + 1) − 1) SRD ’s

and 4(Nk + 1)( N1k Nb (Nr + 1) − 1) XORs.
Table 3.3 Complexity of the Step SRD XOR

individual steps of Rijndael
SubBytes 4Nb –
ShiftRows – –
MixColumns – 6Nb
AddRoundKey – 4Nb
initial AddRoundKey step:

As seen above the initial AddRoundKey step has a complexity of:
4Nb XORs.
Round:
Each Round consists of all the previously calculated steps so that its complexity is:
4Nb SRD ’s and 10Nb XORs.
FinalRound:
In the FinalRound the MixColumns step is omitted, which leads to a complexity of:
4Nb SRD ’s and 4Nb XORs.
The complexity for the Rijndael cipher with block length NB = 32Nb bits and
cipherkey length NC = 32Nk bits over Nr rounds is:
4( N1k Nb (Nr + 1) − 1) + 4Nb Nr SRD ’s

and 4(Nk + 1)( N1k Nb (Nr + 1) − 1) + 10Nb (Nr − 1) + 8Nb XORs.
3.6.9 Security
Rijndael has been designed according to the Wide Trail Strategy with the following
properties for:
• the bundle size m:
m=8
• the column size nθ :
nθ = 4
• the non-linear bricklayer permutation γ:
γ = SubBytes, whose S-box SRD has been selected from [16] so that its minimum
linear weight is at least 3 and its minimum differential weight is at least 6.
• the byte transposition π:
π = ShiftRows, which is diffusion optimal.
• the linear bricklayer permutation θ:
θ = MixColumns, where coefficients of the fixed polynomial c(x) has been chosen
in such a way that the branch number of MixColumns is 5, the maximum possible
branch number
From Eqs. (3.5.14) and (3.5.15) follows that the minimum weight for any linear trail
over four rounds is at least 75 and the minimum weight for any differential trail is
at least 150. Hence any eight round linear (differential) trail has a weight of at least
150 (300).
The authors of [6] “consider this sufficient to resist differential and linear attacks”.
3.7 Cryptanalysis
In this section we introduce the saturation attack. The saturation attack is an attack
by the authors of Rijndael themselves, which exploits the specific structure of the
round transformation, to launch an attack of up to six rounds of Rijndael.
3.7.1 The Saturation Attack
This attack is based on the Square attack, developed by Lars Knudsen, which was
designed to attack the block cipher Square [7]. The block cipher Square by Joan
Daemen, Lars Knudsen and Vincent Rijmen is a precursor of Rijndael. Its round
structure is very similar to the round structure of Rijndael so that this attack was
improved by Joan Daemen and Vincent Rijmen to allow attacks on a round reduced
Rijndael of up to six rounds.
-Sets
The saturation attack is a chosen-plaintext attack, which means that we try to derive
the unknown cipherkey by encrypting several properly chosen plaintexts and exploit-
ing the particular structure of the attacked cipher. In this attack the set of chosen
plaintexts is called a -set and defined as follows.
Definition 109 A -set is a set of 28 states (or intermediate results) with the fol-
lowing properties.
Let x, y ∈ be two states of the -set and let I := {0, . . . , 3} × {0, . . . , Nb − 1}
be the index space of the individual bytes in the states within the -set.
For (i, j) ∈ I, xij , yij denote the byte in row i and column j of x, y ∈ .
It holds:

∃I1 , I2 , with I = I1 I2 , I1 I2 = ∅ and
−∀ (i, j) ∈ I1 ⇒ xij = yij ∀ x, y ∈
−∀ (i, j) ∈ I2 ⇒ xij = yij ∀ x, y ∈
Definition 110 In a -set the bytes at position (i1 , j1 ) ∈ I1 are called active bytes
and the bytes at position (i2 , j2 ) ∈ I2 are called passive bytes.
Definition 111 L = {0, . . . , 28 − 1} denotes the index space of the individual states
in a -set.
The reason for the choice of the plaintexts is given by the following proposition.
3.7 Cryptanalysis 211

Proposition 27 xijl = 0 ∀ (i, j) ∈ I.
l∈L
Proof Let (i, j) ∈ I1 , then all the bytes at position (i, j) of the individual states are
pairwise different. Since the -set contains 28 states, all the possible 28 values for
the bytes are obtained and therefore sum up to zero.
Let (i, j) ∈ I2 , then all the bytes at position (i, j) of the individual states are equal.
Since every byte is self-inverse under ⊕ and the -set contains 28 states, the bytes
sum up to zero.
Definition 112 A -maintaining boolean transformation is a boolean transforma-

tion which maps all the 28 states of a -set into states which form again a -set.
In the saturation attack we exploit the fact that, if we choose the -sets properly,
all the individual steps of Rijndael are -maintaining. This fact is proved by the
following two propositions.
Proposition 28 The SubBytes, the ShiftRows and the AddRoundKey steps are -
maintaining.
Proof The SubBytes step does not change the position of the bytes of a state and it
consists of one S-box which operates independently on the individual bytes of each
state and is a bijection in GF(28 ). There are 28 states in a -set. If (i, j) ∈ I1 , after the
application of the S-box to the bytes xij the resulting bytes at this position are again
pairwise different. If (i, j) ∈ I2 , the resulting bytes are again all equal. It follows that
the output states of the SubBytes step form a -set.
The AddRoundKey step consists of the bitwise XOR of the states with a round-
key of length NB . If we decompose this roundkey into its 18 NB bytes rkl , for
l ∈ {0, . . . , 18 NB − 1}, this step equals the bitwise XOR of each byte of the state
and each byte of the roundkey. It follows that if (i, j) ∈ I1 the resulting bytes are
pairwise different and if (i, j) ∈ I2 the resulting bytes are all equal again. Hence, the
output states of the AddRoundKey step form a -set.
Since the ShiftRows step does not change the value of the individual bytes, but
only changes their positions, the application of ShiftRows to the states of a -set
results in states, which again form a -set.
In general the MixColumns step
bij = MC(aij ) = “02” aij ⊕ “03” ai+1,j ⊕ ai+2,j ⊕ ai+3,j
is not -maintaining. Suppose the first two bytes a0j , a1j of column j of the input
state of MixColumns are active and the last two bytes a2j , a3j of column j are passive.
Now we look to three different input states al1 , al2 , al3 of the -set with the above
property, where l1 , l2 , l3 ∈ L, and assume that:
l2
a0j = (“02”)−1 “03” a1j
l1
l2
and a1j = (“03”)−1 “02” a0j
l1 l1
a1j .
lk
Applying MixColumns would result in the following output bytes b0j :
l1 l2 l1 l1
b0j = b0j = “02” a0j ⊕ “03” a1j ⊕c
l3 l3 l3
and b0j = “02” a0j ⊕ “03” a1j ⊕ c,
lk lk
where c = a2j ⊕ a3j .
l3 l1 l2
Since b0j = b0j = b0j , the resulting set of states do not form a -set.
Proposition 29 If the input states of the MixColumns step have at most one active
byte in each column, then the MixColumns step is -maintaining.
Proof Since the MixColumns step consists of one D-box operating independently
on each of the columns of the input state, the condition of the proposition equals the
condition that at most one byte of the input of the D-box is active.
If no byte is active, of course, the bytes of the resulting column are all passive and
the states form again a -set.
If one byte is active, without loss of generality we assume that this is the first byte
a0j of the column, we obtain the following equality for all l ∈ L:
bijl = di a0j
l
⊕ c,
where:
⎧
⎨ “02”, if i mod 4 = 0
di = “01”, if i mod 4 = 1, 2
⎩
“03”, if i mod 4 = 3
and:
c = di+1 a1j
l
⊕ di+2 a2j
l
⊕ di+3 a3j
l
.
l
Since the a0j ’s are pairwise different, so are the bijl ’s and the resulting states form
again a -set.
Basic Four-Round Attack

This attack is a chosen-plaintext attack and we will examine it for
NB = NC = 128. We choose 28 plaintexts so that the input states of the first round
form a -set with only one active byte.
Since the AddRoundKey (ARK), the SubBytes (SB) and the ShiftRows (SR) steps
are -maintaining, the input states of the first MixColumns (MC) step form a -set
with one active byte. From Proposition 29 it follows that the output states of the
first MC step form a -set, where all the four bytes of one column are active. This
property remains until the output of the second SR step. The second SR step spreads
the active bytes over all the columns so that the input states of the second MC step
have one active byte per column. The output states of the second MC step form again
a -set with only active bytes and this remains until the input of the third MC step.
After the application of the third MC step the states do not usually form a -set, but
we obtain the following property.
Proposition 30 The bytes on each position (i, j) ∈ I of the input states of the fourth
round sum up to zero.
Proof We denote the input states of the third MC step by al , the output states by bl ,
for l ∈ L, and the individual bytes of each of them by aijl and bijl , where i ∈ {0, . . . , 3}
and j ∈ {0, . . . , Nb − 1}.
From Propositions 27, 28 and 29 it follows that all the bytes of the output states
of the third MC step sum up to zero:
l
bij = MC(aijl )
l∈L l∈L

= (“02” aijl ⊕ “03” ai+1,j
l
⊕ ai+2,j
l
⊕ ai+3,j
l
)
l∈L

= “02” aijl ⊕ “03” l
ai+1,j ⊕ l
ai+2,j ⊕ l
ai+3,j
l∈L l∈L l∈L l∈L
=0⊕0⊕0⊕0=0
(3) (3) (3)
Since ARK(bijl , rki+4j ) = bijl ⊕ rki+4j , where rki+4j is the (i + 4j)th byte of the third
roundkey, and since from this it follows that:
(3) (3) l (3)
ARK(bijl , rki+4j ) = (bijl ⊕ rki+4j )= bij ⊕ rki+4j = 0 ⊕ 0 = 0,
l∈L l∈L l∈L l∈L
this property holds until the input of the fourth round.
Now let cij , for all (i, j) ∈ I, denote the bytes of the input c of the fourth round, let
dij , for all (i, j) ∈ I, denote the bytes of the output of the fourth round, which is the
ciphertext, and let kij , for all (i, j) ∈ I, denote the bytes of the fourth roundkey. Then
the following equality holds for all (i, j) ∈ I:
dij = SRD (ci,j+Ci ) ⊕ kij .
It follows that each byte cij of the input state c of the fourth round can be expressed
in terms of the bytes di,j−Ci of the known ciphertext d and the bytes ki,j−Ci of the last
roundkey k:
−1
cij = SRD (di,j−Ci ⊕ ki,j−Ci ) ∀ (i, j) ∈ I.
Following Proposition 30, it must hold that:

cijl = 0 ∀ (i, j) ∈ I. (3.7.1)
l∈L
The individual bytes di,j−Ci of the ciphertext d are known, which means that one can
now guess a value for each byte ki,j−Ci of the last roundkey k and check whether the
following equality holds:

−1 l
(SRD (di,j−Ci ⊕ ki,j−Ci )) = 0. (3.7.2)
l∈L
One of the 28 possible values for each byte of the last roundkey is the right value and
l
therefore the above equality will hold. If we assume that the 28 values di,j−C i
, l ∈ L,
of each byte of the ciphertext d are uniformly distributed, it follows that for each of
the 28 − 1 wrong values the 28 values cijl , l ∈ L, are uniformly distributed, since both
−1
the S-box SRD and the XOR operation ⊕ are bijective.
From this property it follows generally that:

1
Prob cijl =x = , ∀ x ∈ GF(28 )
28
l∈L
and in particular for x = 0.

It follows that the expected number of remaining values for each byte of the last
roundkey is 1 + 255256
≈ 2, one is the right value and one is a wrong value.
If we now do the same calculation for a second -set, again approximatly two
values will remain for each byte of the last roundkey, again the right value and one
wrong value. Since the probablility that the two wrong remaining values are equal is
1
255
, we have found the right value with a probablility of 254 255
. The last roundkey has
1
8
N b = 16 bytes and therefore we have determined the last roundkey uniquely with a
probablility of ( 254
255
) 16
, if we repeat the above calculation for the remaining 15 bytes
of the last roundkey.
Retrieval of the Cipherkey
In Sect. 3.6.5 we have seen that each byte kij(m) , ∀ (i, j) ∈ I, of the mth roundkey k (m) ,
where m ∈ {1, . . . , 4}, can be derived from the cipherkey k (0) with the following
equation:
⎧ (m−1) (m)
⎨ kij ⊕ ki,j−1 , if j = 1, 2, 3
kij(m) = .
⎩ (m−1) (m−1)
ki,0 ⊕ SRD (ki+1,3 ) ⊕ RC(m − 1), if j = 0
From this it follows that we can determine each byte kij(m) , ∀ (i, j) ∈ I, of the mth
roundkey k (m) , where m ∈ {0, . . . , 3}, uniquely from the last roundkey k (4) via the
following equation:
⎧ (m+1) (m+1)
⎨ kij ⊕ ki,j−1 , if j = 1, 2, 3
kij(m) = .
⎩ (m+1) (m)
ki,0 ⊕ SRD (ki+1,3 ) ⊕ RC(m), if j = 0
Attack Complexity
In this basic attack we need two -sets, which corresponds to 29 known plaintexts.
Checking Eq. (3.7.2) for each possible value of each byte of the last roundkey
−1
requires 16 × 28 × 28 = 220 applications of the S-box SRD and the same number
of XORs ⊕. Following Sect. 3.6.8, the complexity of a four round cipher execution
where both the block length and the cipherkey length are 128 bits is:
80 = 26 + 24 ≈ 26 applications of SRD
and 232 = 27 + 26 + 25 + 23 + 2 ≈ 27 XORs ⊕.
It follows that the attack complexity corresponds roughly to the number of 214 4-
round cipher executions.
Extension at the End
In this extension we add a fifth round at the end. We denote the bytes of the output state
e of the fifth round, which is the ciphertext, by eij , (i, j) ∈ I. Following Sect. 3.6.7
we can interchange the InvMixColumns and the AddRoundKey step if we adopt the
roundkey accordingly.
In order to calculate Eq. (3.7.1) we have to use the following expression for cij :
−1 −1 (5)
ci,j+Ci = SRD ((“0E” (SRD (ei,j−Ci ⊕ ki,j−Ci
)
−1 (5)
⊕(“0B” (SRD (ei+1,j−Ci ⊕ ki+1,j−Ci+1
)
(3.7.3)
−1 (5)
⊕(“0D” (SRD (ei+2,j−Ci ⊕ ki+2,j−C i+2
)
(5)
−1
⊕(“09” (SRD (ei+3,j−Ci ⊕ ki+3,j−Ci+3
) ⊕ kij∗(4) ),
where kij∗(4) = MC −1 (kij(4) ).

It follows that we have in addition to the one byte kij∗(4) of the fourth roundkey the
(5)
four additional bytes ki+q,j−C i+q
, for q ∈ {0, . . . , 3}, of the fifth roundkey k (5) to be
guessed, in order to check whether Eq. (3.7.1) holds or not.
This means that we have (28 )5 = 240 combinations of 28 values of the five bytes.
If we guess the right combination Eq. (3.7.1) will hold and again if we assume that
the bytes eij of the ciphertext e are unifromly distributed then Eq. (3.7.1) will hold
1
for every wrong combination with probability 256 . It follows that the amount of the
2 −1
40
(2 − 1) wrong combinations is reduced to 28 after the checking of (3.7.1) with
40
the first -set so that the amount of the remaining possible combinations is 1+ 2 2−1
40
8 .
If we repeat the whole calculation with another different -set the amount of the
remaining wrong combinations will be 2 216−1 . Again the right combination will sum
40
up to zero so that the amount of the remaining possible combinations is 1 + 2 216−1 .

40
In general the amount of the remaining possible combinations after the calculation
of Eq. (3.7.1) with k different -sets is 1 + 2 28k−1 .
40
After the calculation of (3.7.1) with five -sets we will obtain two remaining
possible combinations so that the calculation with the sixth -set will determine the
right combination with probability 254 255
.
We have to repeat the whole attack four times in order to obtain all of the sixteen
bytes of the last roundkey.
Attack Complexity
This extension needs six different -sets which corresponds to 6 · 28 chosen plain-
texts.
The calculation of (3.7.3) requires four multiplications .
As shown in subsection “The Finite Field GF(28 )” of Sect. 3.3.3 the multiplication
can be done efficiently via the application of xtime. The multiplication by “0E”, “0B”
and “0D” requires three applications of xtime and two XORs ⊕ and the multiplication
by “09” requires three applications of xtime and one XOR ⊕.
If we follow Sect. 3.6.8 and simplify the xtime operation to equal one XOR oper-
ation we obtain that the calculation of (3.7.3) requires five applications of the S-box
−1
SRD and 27 XORs ⊕.
We have to check (3.7.1) 28 times for every of the 240 possible combinations. And
we have to do this six times for every needed -set.
After that we have uniquely determined four of the sixteen bytes of the last round-
key so that we have to repeat the whole calculation three more times.
This leads to a complexity of:
4×6×240 ×28 ×5 ≈ 254 S −1 RD ’s

and 4 × 6 × 240 × 28 × 27 ≈ 258 XORs.
Since the complexity of a five-round cipher equals:
100 = 26 + 25 + 22 ≈ 26 S −1 RD ’s
and 272 = 28 + 24 ≈ 28 XORs,
the complexity of this attack corresponds roughly to 249 five-round cipher executions.
Extension at the Beginning

Consider a set of 232 chosen plaintexts so that the input states of the first MixColumns
step contain one column C which ranges over all 232 possible values and three
columns which are constant.
Since the MixColumn step and the AddRoundKey step do not change the positions
of the bytes, this property remains until the input of the second round.
Now we consider the 232 plaintexts as a set of 224 -sets where each -set has
one active byte in column C and the other bytes are passive.
We cannot separate the plaintext and calculate (3.7.1) for each of the 224 -sets
independently. But since (3.7.1) must hold for every -set, it still must hold if we
calculate it for all of the 232 plaintexts.
It follows that we can determine the last roundkey uniquely with 225 different
-sets.
Attack Complexity
This extension needs 225 -sets which corresponds to 233 chosen plaintexts.
To find one byte of the last roundkey we have to calculate (3.7.1) for each possible
value of this byte and for each of the 225 -sets and this must be repeated sixteen
times to obtain all bytes of the last roundkey. This leads to a complexity of:
−1
16 × 28 × 225 × 28 = 245 SRD ’s
and 16 × 28 × 225 × 28 = 245 XORs
which corresponds roughly to 238 five-round cipher executions.

Six-Round Attack
If we apply both extensions we need 5 × 225 ≈ 227 -sets which corresponds to 235
chosen plaintexts.
To obtain a 4-byte column of the last roundkey we have to calculate (3.7.1) over
equation (3.7.3) for each possible value of the five key bytes and for each of the 225
-sets and this must be repeated four times to get all bytes of the last roundkey. This
leads to a complexity of:
−1
4 × 240 × 225 × 28 × 5 ≈ 277 SRD ’s
4 × 2 × 2 × 2 × 27 ≈ 2 XORs.
40 25 8 79
Since the complexity of a six-round cipher equals:

−1
120 = 26 + 25 + 24 + 23 ≈ 26 SRD ’s
and 328 = 2 + 2 + 2 ≈ 2 XORs,
8 6 3 8
the complexity of this attack corresponds roughly to 271 six-round cipher executions.
3.7.2 Further Cryptanaylsis
There are many actual approaches to cryptanalize Rijndael and we will now give
a short view on three of these. All three approaches take advantage of the specific
structure of Rijndael but do not yield to an actual attack to cryptanalize it.
In [8] Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay,
David Wagner and Doug Whiting introduce the partial sum technique, which can be
used to lower the attack requirements of the six-round saturation attack to 246 cipher
executions and to launch an attack over seven and eight rounds of Rijndael. The
seven-round attack requires 2128 − 2119 chosen plaintexts and 2120 cipher executions.
The eight-round attack requires the same amount of chosen plaintexts and 2204 cipher
executions. Of course, these attacks are faster than the exhaustive key search attack,
which requires 2NC cipher executions, but the number of cipher executions is still to
great to be feasible.
In [9] Niels Ferguson, Richard Schroeppel and Doug Whiting show that the full
fourteen-round Rijndael cipher, with NC = 256, can be expressed as a single alge-
braic formula, which consists of 270 terms. This is an interesting result but the authors
are not aware of any technique to exploit this fact and launch an attack.
In [17] Josef Pieprzyk and Nicolas T. Courtois introduce the XSL attack, which can
applied on all block ciphers with a XSL round structure. The round transformation of
a XSL block cipher consists of a XOR with the roundkey (X), a non-linear substitution
layer (S) and a linear diffusion layer (L). As we have seen, Rijndael fulfills this
requirement. Firstly, the authors of [17] show that the cryptanalysis of Rijndael
can be reduced to the problem of solving multivariate quadratic equations, called
MQ-equations. In general this problem is NP-hard but its workload decreases if the
number of equations exceeds the number of variables, see [21]. The authors show,
that this can be achieved but T.T. Moh [15] and Dan Coppersmith [4] state that this
fact cannot be used to launch an actual attack on Rijndael.
3.8 The Extended Euclidean Algorithm
We will now define the Extended Euclidean Algorithm in mainly same way as it
is done in [14]. We will show that given two polynomials m(x), a(x) ∈ F[x] the
Extended Euclidean Algorithm determines uniquely b(x), c(x) ∈ F[x], with (m(x)⊗
c(x)) ⊕ (a(x) ⊗ b(x)) = gcd(m(x), a(x)).
In Sect. 3.3.2 we have shown that a(x) b(x) = 1.
In the last section we will show that deg(b(x)) < deg(m(x)) = d.
Hence, b(x) is the multiplicative inverse of a(x) under field multiplication ,
defined in Sect. 3.3.2.
3.8 The Extended Euclidean Algorithm 219
3.8.1 The Euclidean Algorithm
We will start with the definition of the Euclidean domain.
Definition 113 Let D be a set.

An integral domain is a triple (D, +, ·) with the following properties:
• (D, +, ·) is a Ring with 0 as the additive neutral element and 1 as the multiplicative
neutral element
• If ab = ac and a = 0, then b = c, for all a, b, c ∈ D
Definition 114 Let S be an ordered set.

An Euclidean domain E is an integral domain (D, +, ·) together with a function
g : D → S, with the following properties:
• g(a) ≤ g(ab), if b = 0
• ∀ a, b ∈ D\{0}, there exist unique q, r ∈ D, such that a = qb+r, with g(r) < g(b)
Remark 31 (F[x], +, ⊗) together with g : F[x] → N is an Euclidean domain, where

F[x] is the set of polynomials over a field F, + is the polynomial addition, ⊗ is the
polynomial multiplication and g(f (x)) := deg(f (x)).
The following proposition is the inductive basis for the Euclidean Algorithm for
polynomials.
Proposition 31 For any elements m(x), a(x), q(x) ∈ F[x], it holds that:
gcd(m(x), a(x)) = gcd(a(x), m(x) − q(x) ⊗ a(x)).
Proof Let D[x] ⊂ F[x] denote the set of common divisors of m(x) and a(x) and let
D [x] ⊂ F[x] denote the set of common divisors of a(x) and (m(x) − q(x) ⊗ a(x)).
If d(x) ∈ D[x]
⇒ d(x)|(m(x) − q(x) ⊗ a(x)) ⇒ d(x) ∈ D [x].
If d(x) ∈ D [x]
⇒ d|(m(x) = (m(x) − q(x) ⊗ a(x)) + q(x) ⊗ a(x)) ⇒ d(x) ∈ D[x].
It follows that D[x] = D [x] and from this follows the proposition.
The input of the Euclidean Algorithm are two polynomials m(x), a(x) ∈ F[x], with
deg(m(x)) ≥ deg(a(x)), and its output is gcd(m(x), a(x)) ∈ F[x], which is 1 if m(x)
is irreducible.
For a given input m(x), a(x) ∈ F[x], it follows from Definition 114 that there exist
unique q1 (x), r1 (x) ∈ F[x], with:
m(x) = q1 (x) ⊗ a(x) + r1 (x) and deg(r1 (x)) < deg(a(x)).

And from Proposition 31 it follows that:
gcd(m(x), a(x)) = gcd(a(x), r1 (x)).
Again there exist unique q2 (x), r2 (x) ∈ F[x] with:
a(x) = q2 (x) ⊗ r1 (x) + r2 (x) and deg(r2 (x)) < deg(r1 (x)),
and it follows that:
gcd(m(x), a(x)) = gcd(a(x), r1 (x)) = gcd(r1 (x), r2 (x)).
Since the sequence (deg(rk (x)))k is strictly decreasing and deg(rk (x)) ∈ N, it follows
that after a finite number n ∈ N of steps deg(rn (x)) = 0.
A polynomial of degree zero divides any other polynomial.
If rn (x) = 0, it follows that
gcd(m(x), a(x)) = · · · = gcd(rn−1 (x), rn (x)) = rn (x)
and if rn (x) = 0, it follows that
gcd(m(x), a(x)) = · · · = gcd(rn−2 (x), rn−1 (x)) = rn−1 (x).
The Euclidean Algorithm for Polynomials

• input: m(x), a(x) ∈ F[x]
• set: r−1 (x) := m(x), r0 (x) := a(x) and k := 1
• while rk (x) = 0 do:
– rk (x) := rk−2 (x) − qk (x) ⊗ rk−1 (x)
– increase k by 1
• output: rk−1 (x) = gcd(m(x), a(x)) ∈ F[x]
3.8.2 The Extended Euclidean Algorithm
The extended version of the Euclidean Algorithm has the same input as the Euclidean
Algorithm, two polynomials m(x), a(x) ∈ F[x], but in addition to gcd(m(x), a(x)) ∈
F[x], the output also includes two polynomials b(x), c(x) ∈ F[x] with m(x) ⊗ c(x) +
a(x) ⊗ b(x) = gcd(m(x), a(x)).
In the previous section we have seen that if we define r−1 (x) := m(x) and r0 (x) :=
a(x), there exist unique sequences (qk (x))k , (rk (x))k ,
for k ∈ {1, 2, . . . , n}, with:
rk−2 = qk (x) ⊗ rk−1 (x) + rk (x) and deg(rk (x)) < deg(rk−1 (x)).
Definition 115 Let ck (x) ∈ F[x].

The sequence (ck (x))k is defined via:
⎧
⎨ 1, if k = −1
ck (x) := 0, if k = 0
⎩
ck−2 (x) − qk (x) ⊗ ck−1 (x), if k ≥ 1.
Definition 116 Let bk (x) ∈ F[x].

The sequence (bk (x))k is defined via:
⎧
⎨ 0, if k = −1
bk (x) := 1, if k = 0
⎩
bk−2 (x) − qk (x) ⊗ bk−1 (x), if k ≥ 1.
With these definitions we are able to prove the following proposition, which proves
the correctness of the Extended Euclidean Algorithm.
Proposition 32 The following property holds for all k ∈ {−1, 0, 1, 2, . . . , n}:
rk (x) = ck (x) ⊗ m(x) + bk (x) ⊗ a(x)
Proof For k = −1, we have:
r−1 (x) = m(x), c−1 (x) = 1 and b−1 (x) = 0 ⇒ m(x) = 1 ⊗ m(x) + 0 ⊗ a(x).
For k = 0, we have:
r0 (x) = a(x), c0 (x) = 0 and b0 (x) = 1 ⇒ a(x) = 0 ⊗ m(x) + 1 ⊗ a(x).
If we now assume that the proposition is proved for k − 2 and k − 1, we have the
following equations:
rk−2 (x) = ck−2 (x) ⊗ m(x) + bk−2 (x) ⊗ a(x) (3.8.1)

rk−1 (x) = ck−1 (x) ⊗ m(x) + bk−1 (x) ⊗ a(x) (3.8.2)
rk (x) = rk−2 (x) − qk (x) ⊗ rk−1 (x) (3.8.3)
If we insert the Eqs. (3.8.1) and (3.8.2) in Eq. (3.8.3), we obtain:
rk (x) = ck (x) ⊗ m(x) + bk (x) ⊗ a(x).
The Extended Euclidean Algorithm for Polynomials

• input: a(x), b(x) ∈ F[x]
• set:
– r−1 (x) := m(x), r0 (x) := a(x)

– c−1 (x) := 1, s0 (x) := 0
– b−1 (x) := 0, t0 (x) := 1
– k := 1
• while rk (x) = 0 do:

– rk (x) := rk−2 (x) − qk (x) ⊗ rk−1 (x)
– ck (x) := ck−2 (x) − qk (x) ⊗ ck−1 (x)
– bk (x) := bk−2 (x) − qk (x) ⊗ bk−1 (x)
– increase k by 1
• output: rk−1 (x), sk−1 (x), tk−1 (x) ∈ F[x], where:
– ck−1 (x) = c(x)
– bk−1 (x) = b(x)
– rk−1 (x) = gcd(m(x), a(x)) = c(x) ⊗ m(x) + b(x) ⊗ a(x)
3.8.3 Results
For all the results in this section we assume that deg(m(x)) > deg(a(x)) > 0.
Lemma 22 For all k ∈ {1, 2, . . . , n} it holds that:
deg(qk (x)) = deg(rk−2 (x)) − deg(rk−1 (x)) > 0.
Proof From Definition 114 and the construction of the Euclidean Algorithm it fol-
lows for all k ∈ {1, 2, . . . , n} that:
deg(rk−2 (x)) > deg(rk−1 (x)) > deg(rk (x)) ≥ 0
and:
deg(rk−2 (x)) = deg(qk (x) ⊗ rk−1 (x) + rk (x))
= deg(qk (x) ⊗ rk−1 (x))
= deg(qk (x)) + deg(rk−1 (x)).
It follows that:
deg(qk (x)) = deg(rk−2 (x)) − deg(rk−1 (x)) > 0.
Lemma 23 For all k ∈ {0, 1, . . . , n} it holds that:
deg(bk (x)) ≥ deg(bk−1 (x)).

Proof For k = 0 it follows that:
deg(b0 (x)) = deg(1) = 0 = deg(0) = deg(b−1 (x))
For k = 1 it follows that:
deg(b1 (x)) ≥ 0 = deg(1) = deg(b0 (x))
We now assume that the lemma is proved for k − 2 and k − 1.

It follows from Definition 116 that we have the following equality:
deg(bk (x)) = deg(bk−2 (x) − qk (x) ⊗ bk−1 (x))
Since deg(bk−1 (x)) ≥ deg(bk−2 (x)) and deg(qk (x)) > 0 (Lemma 22), it follows that:

= deg(qk (x) ⊗ bk−1 (x))
= deg(qk (x)) + deg(bk−1 (x))
> deg(bk−1 (x)).
Proposition 33 For all k ∈ {1, 2, . . . , n} it holds that:
deg(bk (x)) < deg(m(x))
Proof We will show that deg(bk (x)) = deg(m(x)) − deg(rk−1 (x)).

Since deg(rk−1 (x)) > deg(rk (x)) ≥ 0, for all k ∈ {1, 2, . . . , n}, this yields to
deg(bk (x)) < deg(m(x)).
For k = 1 it follows from b1 (x) = −q1 (x) that:
deg(b1 (x)) = deg(q1 (x)) = deg(m(x)) − deg(a(x)) = deg(m(x)) − deg(r0 (x)).
We now assume that the proposition is proved for k − 1.

= deg(qk (x) ⊗ bk−1 (x))
= deg(qk (x)) + deg(bk−1 (x))
= deg(qk (x)) + deg(m(x)) − deg(rk−2 (x))
= deg(rk−2 (x)) − deg(rk−1 (x)) + deg(m(x)) − deg(rk−2 (x))
= deg(m(x)) − deg(rk−1 (x)).
References
1. R. Anderson, E. Biham, L. Knudsen, Serpent: a proposal for the advanced encryption standard,
in 1st AES Conference (1999)
2. E. Biham, A. Shamir, Differential Cryptanalysis of the Data Encryption Standard (Springer,
New York, 1993)
3. C. Burwick, D. Coppersmith, E. D’Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas,
L. O’Connor, M. Peyravian, D. Safford, N. Zunic, MARS a candidate cipher for AES, in 1st
AES Conference (1999)
4. D. Coppersmith, Re: impact of Courtois and Pieprzyk results, Entry at the AES discussion
forum (2002). http://aes.nist.gov/aes/
5. J. Daemen, Cipher and hash function design strategies based on linear and differential crypt-
analysis, Doctoral dissertation K.U. Leuven (1995)
6. J. Daemen, V. Rijmen, AES proposal: Rijndael, in 1st AES Conference (1999)
7. J. Daemen, L. Knudsen, V. Rijmen, The Block Cipher SQUARE, Fast Software Encryption’97
(Springer, New York, 1997)
8. N. Ferguson, J. Kelsey, S. Lucks, B. Schneier, M. Stay, D. Wagner, D. Whiting, Improved
Cryptanalysis of Rijndael, Fast Software Encryption 2000 (Springer, New York, 2001), pp.
213–231
9. N. Ferguson, R. Schroeppel, D. Whiting, A Simple Algebraic Representation of Rijndael, Lec-
ture Notes in Computer Science (Springer, New York, 2001)
10. S.W. Golomb, Shift Register Sequences (Holden-Day Inc., San Francisco, 1967)
11. T. Jakobsen, L.R. Knudsen, The Interpolation Attack on Block Ciphers, Fast Software Encryp-
tion’97 (Springer, New York, 1997), pp. 28–40
12. R. Lidl, H. Niederreiter, Introduction to Finite Fields and Their Applications (Cambridge
University Press, Cambridge, 1986)
13. M. Matsui, Linear cryptanalysis method for DES cipher, Advances in Cryptology, Proceedings
of Eurocrypt’93 (Springer, New York, 1994), pp. 386–397
14. R.J. McEliece, Finite Fields for Computer Scientists and Engineers (Kluwer Academic Pub-
lishers, Boston, 1987), pp. 3–9
15. T.T. Moh, On the Courtois-Pieprzyk’s attack on Rijndael (2002). http://www.usdsi.com/aes.
html
16. K. Nyberg, Differentially uniform mappings for cryptography, Advances in Cryptology, Pro-
ceedings of Eurocrypt’93 (Springer, New York, 1994), pp. 55–64
17. J. Pieprzyk, N.T. Courtois, Cryptanalysis of block ciphers with overdefined systems of equa-
tions, Advances in Cryptology - ASIACRYPT 2002, vol. 2501, Lecture Notes in Computer
Science (Springer, New York, 2002), pp. 267–287
18. B. Preneel, Analysis and design of cryptographic hash functions, Doctoral dissertation K.U.
Leuven (1993)
19. R.L. Rivest, M.J.B. Robshaw, R. Sidney, Y.L. Yin, The RC6 block cipher, 1st AES Conference
(1999)
20. B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson, Twofish: a 128-bit block
cipher, 1st AES Conference (1999)
21. A. Shamir, A. Kipnis, Cryptanalysis of the HFE public key cryptosystem, in Proceedings of
Crypto’99 (Springer, New York, 1999)

Aes1 2016

Uploaded by

Copyright:

Available Formats

Aes1 2016

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Aes1 2016

Uploaded by

Copyright:

Available Formats

Chapter 3

The Mathematical Background

© Springer International Publishing Switzerland 2016 155

operation of a so-called reduction polynomial, can be efficiently computed by the

3.2 The AES Selection Process

CAST-256 by Entrust (CA)

3.3 Finite Fields

Definition 44 The characteristic of a finite field of order m, denoted by char

char(GF(m)) := minl∈N {l| 1 ⊕ ·

Theorem 59 The characteristic of the finite field GF(pk ) is p.

3.3.1 Polynomials Over a Field

Definition 45 A polynomial over a field F is an expression of the following form:

a(x) := an−1 x n−1 + · · · + a1 x + a0 , with ai ∈ F.

Definition 46 Let F be a field. F[x] is the set of all polynomials over F.

3.3.2 The Field < F[x]|d , ⊕, >

Definition 48 Let F be a field and a(x), b(x) ∈ F[x]|d , then addition

where + is the addition in the field F.

Proposition 15 < F[x]|d , ⊕ > is an Abelian group.

Definition 49 Let F be a field and d ∈ N.

Definition 50 Let a(x), m(x) ∈ F[x].

a(x) b(x) := a(x) ⊗ b(x) (mod m(x)),

where m(x) is a reduction polynomial in F[x]|d .

Definition 52 Let F be a field. A polynomial c(x) ∈ F[x] is called irreducible, if

Lemma 18 If m(x) is an irreducible reduction polynomial in F[x]|d , then gcd(a(x),

Proof a(x) = 1: gcd(a(x), m(x)) = gcd(1, m(x)) = 1.

Proposition 16 If we choose the reduction polynomial to be irreducible it follows

< GF(pk )[x]|d , ⊕, > = GF(pkd ) = < GF(p)[x]|kd , ⊕d , ⊗d > .

3.3.3 Byte-Operations in Rijndael

The Finite Field GF(28 )

Definition 53 For a given byte β = β7 β6 . . . β0 ∈ B, where the βi ’s are bits, ϕ(β)

ϕ(β) := b(x) ∈ GF(2)[x]|8 , with bi = βi .

From now on we will write β = β7 β6 . . . β0 ∼ b7 x 7 + b6 x 6 + · · · + b0 = b(x) or

Example 8 “57” “83”

The disadvantage of multiplication compared to addition is the fact that there is no

“57” “02” = xtime(“57”)

“57” “04” = xtime(“AE”)

“57” “08” = xtime(“47”)

“57” “10” = xtime(“8E”)

ψ(γ) := c(x) ∈ GF(28 )|4 , with ci = γi .

 a59, the characteristic of GF(2 ) is 2. Further on, it holds

Claim x j = x j mod 4 (mod (x 4 + 1)).

Proof Let j = 4q + r, with 0 ≤ r < 4.

With this we get the following coefficients for

3.4 A Key-Iterated Block Cipher

3.4.1 Boolean Functions

Definition 55 A boolean vector b of length n is a vector, whose entries are bits:

A boolean vector of length n is also called a one-dimensional array of bits of

Definition 56 A boolean function φ is a mapping, which maps a boolean vector to

Definition 57 A boolean transformation χ is a boolean function, which maps a

We say, it operates on an n-bit-state.

Definition 58 A bricklayer function is a boolean function that can be decomposed

Definition 59 A bricklayer transformation (permutation) is a bricklayer func-

Definition 60 A transposition is a boolean permutation, for which the binary output

Definition 61 An iterative boolean function ψ : GF(2)n0 → GF(2)nk is the

Definition 62 An iterative boolean transformation (permutation) is the concate-

3.4.2 A Key-Iterated Block Cipher

B = σ[κNr ] ◦ ρNr ◦ σ[κNr −1 ] ◦ ρNr −1 ◦ · · · ◦ σ[κ1 ] ◦ ρ1 ◦ σ[κ0 ].

B = σ[κNr ] ◦ ρ ◦ σ[κNr −1 ] ◦ ρ ◦ · · · ◦ σ[κ1 ] ◦ ρ ◦ σ[κ0 ].

3.5 The Wide Trail Strategy

a59, the characteristic of GF(2 ) is 2. Further on, it holds

Vi ∩ Vj = {0}, for all i = j and i, j ∈ {0, . . . , k − 1}.