<<

. 6
( 7)



>>

masked data. IACR Cryptology ePrint Archive (2003)
29. Wolkerstorfer, J.,: An ASIC implementation of the AES MixColumn operation, In
Proceedings Austrochip 2001 (2001)
30. Wolkerstorfer, J., Oswald, E., Lamberger, M.: An ASIC implementation of the AES
S-Boxes. Proc. Topic in Cryptography “ CT-RSA 2002. 2271 of Lecture Notes in
Computer Science 2271 (2002) 67-78
Complementation-Like and Cyclic Properties
of AES Round Functions

Tri Van Le 1 , R¨diger Sparr 2 , Ralph Wernsdorf 2 , and Yvo Desmedt 1
u
1
Dept. of Computer Science, Florida State University,
260 Love Building, Tallahassee, FL 32306-4530, USA
tll6935@garnet.acns.fsu.edu
desmedt@cs.fsu.edu
2
Rohde & Schwarz SIT GmbH,
Agastraße 3, D-12489 Berlin, Germany
{ruediger.sparr, ralph.wernsdorf}@sit.rohde-schwarz.com



Abstract. While it is known previously that the cycle lengths of indi-
vidual components of the AES round function are very small, we demon-
strate here that the cycle length of the S-box combined with the ShiftRow
and MixColumn transformation is at least 10205 . This result is obtained
by providing new invariances of the complete AES round function with-
out the key addition. Furthermore, we consider self-duality properties of
the AES round function and derive a property analogous to the com-
plementation property of the DES round function. These results con¬rm
the assessments given in other publications that the AES components
have several unexpected structural properties.

Keywords: Rijndael, AES, invariance, cyclic properties, self-duality.



1 Introduction
The cipher Rijndael was selected in 2000 as the Advanced Encryption Standard
(AES) and was designed to resist known attacks to block ciphers up to that time.
In particular, Rijndael is considered to be immune to di¬erential cryptanalysis
[2] and linear cryptanalysis [6], cf. [10]. On the other hand, in order to achieve
a good performance on di¬erent platforms, the components of Rijndael operate
completely on the Galois ¬eld GF (28 ). Some recent algebraic analyses of the
AES try to exploit the algebraic structure of the ¬nite ¬eld GF (28 ) which lead
to algebraic relations and simple algebraic representations (cf. [4], [8], and [15]).
The analysis of such mathematical properties can lead to new cryptanalytic
insights and approaches. In many cases this seems to be the only way to ¬nd
cryptographic weaknesses. Regularities of algorithm components, such as short
cycles, ”inner structures” or symmetries can yield starting points for attacks.
In this paper we present some new results on the algebraic properties of the
AES round function. The paper is organized as follows: In Section 2 we ¬rst
give a short description of the AES round function and ¬x some de¬nitions and

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 128“141, 2005.
c Springer-Verlag Berlin Heidelberg 2005
Complementation-Like and Cyclic Properties of AES Round Functions 129

notations with respect to invariances and permutation groups. In Section 3 we
summarize known results on the cyclic order of basic components of the AES
round function and provide some new results. In Section 4 we present a number of
new invariances of the AES round function with the all zero subkey. In addition,
we have found more invariances of some powers of this round function. From the
result proved in [13] that the set of AES round functions generates the alternating
group on {0, 1}128 , it follows that the existence of nontrivial invariances which
hold for all 2128 AES round subkeys can be excluded. In Section 5 we compute
di¬erent cycle lengths of the AES round function under the all zero subkey
exploiting the invariances found in Section 4. The cycle computations performed
in Section 5 show that the cyclic order of this round function has by far not the
small size as the cyclic orders of its components. In Section 6 we consider self-
duality properties of the AES round function and we derive a property analogous
to the complementation property of the DES round function.


2 Preliminaries
2.1 Description of the AES Round Function
We now give a short description of the AES round function. The AES is de¬ned
for 128-bit blocks and key sizes 128, 192, and 256 bits (cf. [9]). The bytes bi of
the state space of the AES are written in matrix form:
b1 b5 b9 b13
b2 b6 b10 b14
b3 b7 b11 b15
b4 b8 b12 b16
In the following we write the state of the AES as a byte vector of the form
(b1 , b2 , b3 , b4 , ..., b16 ) with meaning as a matrix of the form as indicated above. A
round of Rijndael proceeds in the following 4 consecutive operations on {0, 1}128
(cf. [9]):
To every byte of the state the S-Box is applied (ByteSub), the bytes of the
rows of the state matrix are shifted (ShiftRow ), every byte-column is mixed by
a linear transformation (MixColumn), and ¬nally, the state is XORed with the
128-bit subkey (AddRoundKey).
The S-box of Rijndael is composed as the inversion in the Galois ¬eld GF (28 )
modulo the irreducible polynomial x8 + x4 + x3 + x + 1, followed by an a¬ne
transformation (see [9] for details). The application of the inversion in GF (28 ),
resp. the a¬ne transformation described above to the 16 bytes of the state is
denoted by I and A, respectively.
In the ShiftRow operation, the bytes of row i of the state are rotated i places
to the left, where i = 0, 1, 2, 3.
In the MixColumn operation, each column of the state is considered as a
polynomial over GF (28 ) and multiplied modulo x4 + 1 with the polynomial
03 · x3 + 01 · x2 + 01 · x + 02.
130 T. Van Le et al.

The ShiftRow, MixColum, AddRoundKey operation is denoted by S, M , and
X, respectively.


2.2 De¬nitions and Notation
Let Y be a nonempty ¬nite set and let G be a permutation group on Y , i.e., a
subgroup of the group of bijective mappings of Y to itself. G is called transitive
if, for any pair of elements (y, y ) ∈ Y 2 , there is a permutation f ∈ G with
f (y) = y , otherwise G is said to be intransitive. The cyclic order of an element
f ∈ G is the cardinality of the cyclic subgroup generated by f or, in other
words, the least natural number n > 0 such that f n (y) = y for all y ∈ Y .
Further information on the theory of permutation groups can be found in [11]
or [14].
Let f : {0, 1}128 ’ {0, 1}128 denote an operation on the state space of Ri-
jndael. A property P ⊆ {0, 1}128 , P = …, is called an invariance of f , if P is
preserved by f , i.e., for every x ∈ P it follows that f (x) ∈ P .
In this paper we use the notation (f —¦ g)(x) = g(f (x)) for compositions of
functions f, g. The cardinality of a set Y is denoted by |Y |. Furthermore, we
write F2 for the Galois ¬eld with two elements.



Cyclic Order of Components of I —¦ A —¦ S —¦ M
3
In this section we summarize known results on the cyclic order of (compositions
of) basic components of the Rijndael round function and provide some new
results.
Clearly, the cyclic order of I, S, X, X = id, is 2, 4, 2, respectively. Song and
Seberry showed that the cyclic order of the MixColumn operation M is 4 (cf.
[12]). Because the cycle lengths for I —¦ A applied to bytes are 87, 81, 59, 27, 2,
the cyclic order of I —¦ A applied to the AES state space is the least common
multiple of 87, 81, 59, 27, 2 which is 277182 (cf. [12]). Then it follows that the
cyclic order of I —¦ A —¦ S is 554364 (cf. [12]) which is the least common multiple
of 277182 and 4. Murphy and Robshaw [7] showed that the order of A —¦ S —¦ M
is 16, where A (a)(u) = (u7 + u6 + u5 + u4 + 1)a(u) mod u8 + 1.

Proposition 1. The cyclic order of the a¬ne transformation A is 4.

Proof. According to [3], the a¬ne transformation A can be written as a mapping
of the ring F2 [u]/(u8 + 1)

A : a(u) ’ f (u)a(u) + g(u) mod u8 + 1,

where f (u) = u7 + u6 + u5 + u4 + 1, and g(u) = u7 + u6 + u2 + u. Then
we have f (u)2 = u6 + u4 + u2 mod u8 + 1 and f (u)4 = 1 mod u8 + 1. Since
f (u)3 + f (u)2 + f (u) = 1 mod u8 + 1, it follows that A4 (a)(u) = f (u)4 a(u) +
(f (u)3 + f (u)2 + f (u) + 1)g(u) = a(u) mod u8 + 1. 2
Complementation-Like and Cyclic Properties of AES Round Functions 131

The next two propositions summarize the results about the cyclic orders for
step-2 and step-3 compositions of basic components of the AES round function.
The cyclic orders of the mappings I —¦ A and I —¦ A —¦ S were stated by Song and
Seberry in [12].
Proposition 2. The cyclic order of I —¦ A, A —¦ S, S —¦ M , M —¦ X for X = id, is
277182, 4, 8, 8, respectively.
Proof. From the preceding proposition it follows that the cyclic order of A —¦ S
must be 4. Because the S —¦ M -mapping is F2 -linear, it can be represented by a
128 — 128-matrix over F2 , whose order is 8. It remains to prove the result for the
cyclic order of M —¦ X. We consider M as an element in the ring Mat128 (F2 ) of
128 — 128-matrices over F2 . Let E denote the unit element of Mat128 (F2 ). Then
we have (M —¦X)8 (y) = M 8 y +(M +E)7 x, where y denotes an 128-bit vector over
F2 and x denotes the 128-bit key added by X. Since (M + E)4 = M 4 + E 4 = 0,
it follows that (M —¦ X)8 (y) = y for all 128-bit vectors y over F2 . Because there
exist cycles for M —¦ X of length 8, the cyclic order of M —¦ X is 8. 2

Similar arguments yield the following results for the cyclic order of the map-
pings A —¦ S —¦ M , S —¦ M —¦ X, and A —¦ S —¦ M —¦ X, with X = id, stated in Proposition
3 and 4.
Proposition 3. The cyclic order of I —¦ A —¦ S, A —¦ S —¦ M , S —¦ M —¦ X for X = id,
is 554364, ¤ 32, 16, respectively. 2
Proposition 4. The cyclic order of A —¦ S —¦ M —¦ X for X = id is ¤ 32. 2


Invariances of I —¦ A —¦ S —¦ M
4
In this section we list various invariances of the mapping I —¦ A —¦ S —¦ M and its
powers. The following three propositions can easily be veri¬ed.
Proposition 5. The following sets Inv1 , ..., Inv6 are invariances of the mapping
I —¦ A —¦ S —¦ M.
Inv1 = {(x, x, x, ..., x)|x ∈ GF (28 )},
Inv2 = {(x, y, x, y, x, y, ..., x, y)|x, y ∈ GF (28 )},
Inv3 = {(w, x, y, z, w, x, y, z, w, x, y, z, w, x, y, z)|w, x, y, z ∈ GF (28 )},
Inv4 = {(w, x, w, x, y, z, y, z, w, x, w, x, y, z, y, z)|w, x, y, z ∈ GF (28 )},
Inv5 = {(w, x, y, z, y, z, w, x, w, x, y, z, y, z, w, x)|w, x, y, z ∈ GF (28 )},
Inv6 = {(s, t, u, v, w, x, y, z, s, t, u, v, w, x, y, z)|s, t, u, v, w, x, y, z ∈ GF (28 )}. 2
Proposition 6. The following sets Inv7 , ..., Inv10 are invariances of the map-
ping (I —¦ A —¦ S —¦ M )2 .
Inv7 = {(x, x, x, x, y, y, y, y, x, x, x, x, y, y, y, y)|x, y ∈ GF (28 )},
Inv8 = {(x, y, x, y, y, x, y, x, x, y, x, y, y, x, y, x)|x, y ∈ GF (28 )},
Inv9 = {(s, t, s, t, u, v, u, v, w, x, w, x, y, z, y, z)|s, t, u, v, w, x, y, z ∈ GF (28 )},
Inv10 = {(s, t, u, v, w, x, y, z, u, v, s, t, y, z, w, x)|s, t, u, v, w, x, y, z ∈ GF (28 )}. 2
132 T. Van Le et al.


Proposition 7. The following sets Inv11 , ..., Inv14 are invariances of the map-
ping (I —¦ A —¦ S —¦ M )4 .
Inv11 = {(w, w, w, w, x, x, x, x, y, y, y, y, z, z, z, z)|w, x, y, z ∈ GF (28 )},
Inv12 = {(w, x, y, z, x, y, z, w, y, z, w, x, z, w, x, y)|w, x, y, z ∈ GF (28 )},
Inv13 = {(w, x, w, x, y, z, y, z, x, w, x, w, z, y, z, y)|w, x, y, z ∈ GF (28 )},
Inv14 = {(w, x, y, z, z, w, x, y, y, z, w, x, x, y, z, w)|w, x, y, z ∈ GF (28 )}. 2

Note that the invariances of (I —¦ A —¦ S —¦ M )2 resp. (I —¦ A —¦ S —¦ M )4 listed in
Propositions 6 and 7 are not invariances of I —¦ A —¦ S —¦ M .
Proposition 8. There exist no invariances P of I —¦ A —¦ S —¦ M —¦ X such that
P = {0, 1}128 which hold for all 2128 round subkeys.
Proof. The existence of a nontrivial invariance of I —¦ A —¦ S —¦ M —¦ X that holds for
all 2128 round subkeys would imply that the permutation group generated by all
2128 round functions is intransitive. But this contradicts the fact from [13] that
this group is the alternating group on {0, 1}128 . 2
Remark 1. The same argument shows that for any natural number n > 0 there
are no nontrivial invariances P of (I —¦ A —¦ S —¦ M —¦ X)n which hold for all 2128·n
combinations of n round subkeys. 2
Nevertheless, for special sets of round functions we obtain the following in-
variances.
Remark 2. (a) For all i ∈ {1, 2, ..., 6} we have: If the round subkey is an element
of Invi , then Invi is an invariance of I —¦ A —¦ S —¦ M —¦ X.
(b) For i ∈ {7, 8, ..., 14} similar properties can be derived by a suitable choice of
2
the round keys over 2 and 4 rounds respectively.

This means that for round subkeys and input blocks with one of the structures
given above, the round function of AES has some strong regularities. From the
size of the invariance Inv6 , we obtain the following result.
Corollary 1. There exists a set of AES round functions R with |R| = 264 such
that the permutation group generated by R is intransitive. 2

One cannot expect that these invariances can be extended to the complete
AES because the AES key scheduling is designed to avoid regularities.



On the Cyclic Order of I —¦ A —¦ S —¦ M
5
Because the mappings I, A, S, M and their concatenations I —¦ A, A —¦ S, S —¦ M ,
I —¦ A —¦ S, and A —¦ S —¦ M all have relatively small cyclic orders, it is important to
check whether this causes small cyclic orders of the AES round functions.
Complementation-Like and Cyclic Properties of AES Round Functions 133

Table 1. Cycle Lengths for Invariances Inv1 , ..., Inv5
Invariance: Cycle lengths:
Inv1 87, 81, 59, 27, 2
Inv2 \ Inv1 39488, 16934, 7582, 548, 36, 24, 21, 15, 8, 2
Inv3 \ Inv2 1088297796, 637481159, 129021490, 64376666,
11782972, 13548, 10756, 5640, 3560, 1902, 136,
90, 47, 40, 12, 4
Inv4 \ Inv2 1219717400, 599556416, 315637164, 4307366,
2990738, 2153683, 1958224, 1606154, 1495369,
975150,803077, 564988, 487575, 86038, 82750,
67324, 21758, 13024, 10902, 5451, 5354, 3340,
2677, 2356, 988, 856, 108, 48, 22, 20, 18, 12,
11, 9, 8, 4
Inv5 \ Inv2 1052651234, 737292504, 417828286, 193225414,
96612707, 87601912, 11068518, 9460050, 6486298,
5534259, 4730025, 3243149, 394266, 197133, 42454,
16932, 3166, 3078, 2366, 1583, 1539, 1183, 1160,
1062, 912, 496, 38, 18, 9, 6, 2


The round function I —¦ A —¦ S —¦ M with the all zero round subkey is intuitively
one of the ¬rst candidates for which a small cyclic order seems to be possible.
The results of Section 4 can be exploited to ¬nd out a lower bound for the cyclic
order of this round function. Consider the invariance sets of the permutation
I —¦ A —¦ S —¦ M given in Section 4. Since a cycle starting from a point of an
invariance set can only contain points of this set, the cycle length is limited by
the size of the invariance set. Because we have |Invi | ¤ 232 for i = 1, ..., 5, it is
possible to compute such cycles on a PC. Table 1 lists all cycle lengths according
to the invariances Inv1 , ..., Inv5 . Note that the cycles from the invariance Inv3
are related to those provided in the Appendix of [12]. The Appendix provides a
complete listing of the cycles for Inv1 , ..., Inv5 .
The least common multiple of the computed cycle lengths for the invariances
Inv1 , ..., Inv5 of Table 1 is equal to

15480 20902 25688 03988 20263 80165 33732 81646 22636
91465 18521 79549 12467 08119 71956 75745 56484 49918
71194 74949 82013 75604 65431 85505 89291 91969 54985
57959 09774 73220 08631 61663 54665 95490 84924 52493
78665 19158 83139 45332 15200 0,

which is a number of 206 decimals. Since the least common multiple of the cycle
lengths for Inv1 , ..., Inv5 is a divisor of the cyclic order of I —¦ A —¦ S —¦ M , we obtain
the following result.
Proposition 9. The cyclic order of I —¦ A —¦ S —¦ M is greater than 10205 . 2

Starting from other points in other invariance sets still other cycles can be
found. This way the lower bound can be further increased essentially.
134 T. Van Le et al.

It follows that the cyclic order of I —¦ A —¦ S —¦ M has by far not the small size
as the cyclic orders of its components, but for points from invariance sets short
cycles may occur. Furthermore, the cyclic order of I —¦ A —¦ S —¦ M is much greater
than the number 2128 of AES blocks.


6 Self-duality of the AES Round Function
According to [1], two block ciphers E and E are called dual to each other if
there are invertible transformations f , g, and h such that

f (Ek (x)) = Eg(k) (h(x))

holds for all keys k and plaintexts x. Any cipher is trivially dual to itself, but
sometimes there are nontrivial invertible transformations for a cipher onto itself
such that the equation above holds for all k and x, as is the case for the DES (cf.
[5], p. 248). In [1] the question is considered whether the AES block encryption
has self-duality properties, i.e.:

Do nontrivial invertible transformations f , g, h exist such that for the AES
block encryption for all plaintext blocks x and all keys k the equation f (AESk (x))
= AESg(k) (h(x)) holds ?

In this section we show that this question has a positive answer according to
the AES round function.
For any natural number n > 0, let Sn denote the symmetric group of degree
n, i.e., the permutation group on the set {1, ..., n}. Now we set π0 := (1 6 11 16),
π1 := (5 10 15 4), π2 := (9 14 3 8), and π3 := (13 2 7 12), and de¬ne G as
the semidirect product of the group generated by π0 , π1 , π2 , π3 and S4 , where
S4 operates arbitrarily on the four vectors v0 := (1, 6, 11, 16), v1 := (5, 10, 15, 4),
v2 := (9, 14, 3, 8), and v3 := (13, 2, 7, 12). Then we obtain the following result.


Proposition 10. There exists a permutation group G of order |G| = 6144 such
that for any byte-permutation π ∈ G, there exists a byte-permutation π such
that ∀x ∈ {0, 1}128 : π —¦ I —¦ A —¦ S —¦ M (x) = I —¦ A —¦ S —¦ M —¦ π (x). 2


Although one cannot expect that this property can be extended to the com-
plete AES mapping, the property of Proposition 10 opens some new possibilities
for protection against side channel attacks. Furthermore, Proposition 10 is re-
lated to the results provided in Appendix A of [15] where the expressions of
the 128 bit-components of the AES round function have many similarities and
partially the same component expressions.
On the basis of Proposition 10 it is possible to derive self-duality properties
of the AES round function. If X is added, we obtain the following result.
Complementation-Like and Cyclic Properties of AES Round Functions 135

Corollary 2. There exists a permutation group G of order |G| = 6144 such
that for any byte-permutation π ∈ G, there exists a byte-permutation π such
that (π —¦ I —¦ A —¦ S —¦ M —¦ X(k))(x) = (I —¦ A —¦ S —¦ M —¦ X(π ’1 (k)) —¦ π )(x) holds
for all k ∈ {0, 1}128 and x ∈ {0, 1}128 . 2
If we consider in Corollary 2 the special case π = π , then we ¬nd the following
byte permutations (written as products of cycles, the bytes are enumerated as
described in Section 2.1).
P1 = (1 5 9 13)(2 6 10 14)(3 7 11 15)(4 8 12 16),
P2 = (1 9)(5 13)(2 10)(6 14)(3 11)(7 15)(4 12)(8 16),
P3 = (1 13 9 5)(2 14 10 6)(3 15 11 7)(4 16 12 8).
This means that the following automorphism equations hold for the AES round
function.
Proposition 11. For any byte permutation Pi , i = 1, 2, 3 de¬ned above, the
equation Pi ((I —¦ A —¦ S —¦ M —¦ X(k))(x)) = (I —¦ A —¦ S —¦ M —¦ X(Pi (k)))(Pi (x)) holds
for all k ∈ {0, 1}128 and x ∈ {0, 1}128 . 2
This way we have found a property analogous to the complementation prop-
erty of the DES round function (see for example p. 248 in [5]).


7 Conclusions
Novel invariances of the mapping I —¦ A —¦ S —¦ M were found. It follows that for big
sets of round subkeys there are regularities in the corresponding round functions.
On the other hand, the existence of nontrivial invariances which hold for all 2128
AES round subkeys is excluded.
Several cycle lengths for the complete AES round function with the all zero
subkey were computed. It turns out that the cyclic order of this round function is
much greater than the cyclic orders of its components. Nevertheless, for several
special round keys some short cycles exist.
The self-duality properties described in Section 6 con¬rm the assessments
given in other publications that the AES components have several unexpected
structural properties.
We conclude that the AES has many algebraic properties which have not been
found before in other block ciphers. In particular, the round function seems
to have more invariants than the round function of DES. The results are not
necessarily suitable to break AES. But in combination with other approaches
they may lead to new insights and analysis methods.


References
1. E. Barkan and E. Biham. In how many ways can you write Rijndael? In Advances
in Cryptology - ASIACRYPT 2002, Lecture Notes in Computer Science 2501, pp.
160-175, Springer-Verlag, 2002.
136 T. Van Le et al.

2. E. Biham and A. Shamir. Di¬erential cryptanalysis of DES-like cryptosystems. J.
Cryptology, Vol. 4, pp. 3-72, 1991.
3. J. Daemen and V. Rijmen. AES Proposal: Rijndael. Available via
http://csrc.nist.gov/CryptoToolkit/aes, September 3, 1999.
4. N. Ferguson, R. Schroeppel, and D. Whiting. A simple algebraic representation of
Rijndael. In Selected Areas in Cryptography, SAC 2001, Lecture Notes in Computer
Science 2259, pp. 103-111, Springer-Verlag, 2001.
5. A. G. Konheim. Cryptography: A Primer. John Wiley and Sons, 1981.
6. M. Matsui. Linear cryptanalysis method for DES cipher. In Advances in Cryp-
tology - EUROCRYPT™93, Lecture Notes in Computer Science 765, pp. 386-397,
Springer-Verlag, 1994.
7. S. Murphy and M. J. B. Robshaw. New observations on Rijndael. Available via
http://csrc.nist.gov/CryptoToolkit/aes, August 7, 2000.
8. S. Murphy and M. J. B. Robshaw. Essential algebraic structure within the AES.
In Advances in Cryptology - CRYPTO 2002, Lecture Notes in Computer Science
2442, pp. 1-16, Springer-Verlag, 2002.
9. National Institute of Standards and Technology (U.S.): Advanced Encryp-
tion Standard (AES), FIPS Publication 197, November 26, 2001. Available at
http://csrc.nist.gov/publications/fips/fips197/ fips-197.pdf.
10. S. Park, S. H. Sung, S. Lee, and J. Lim. Improving the upper bound on the max-
imum di¬erential and the maximum linear hull probability for SPN structures
and AES. In Fast Software Encryption, 10th International Workshop, FSE 2003,
Lecture Notes in Computer Science 2887, pp. 247-260, Springer-Verlag, 2003.
11. D. Robinson. A Course in the Theory of Groups. Graduate Texts in Mathematics,
Springer-Verlag, New York, 1982.
12. B. Song and J. Seberry. Further observations on the structure of the AES algorithm.
In Fast Software Encryption, 10th International Workshop, FSE 2003, Lecture
Notes in Computer Science 2887, pp. 223-234, Springer-Verlag, 2003.
13. R. Wernsdorf. The round functions of Rijndael generate the alternating group. In
Fast Software Encryption, 9th International Workshop, FSE 2002, Lecture Notes
in Computer Science 2365, pp. 143-148, Springer-Verlag, 2002.
14. H. Wielandt. Finite Permutation Groups. Academic Press, New York, 1964.
15. A. M. Youssef and S. E. Tavares. On some algebraic structures in the AES round
function, http://eprint.iacr.org/2002/144, September 20, 2002.
Complementation-Like and Cyclic Properties of AES Round Functions 137

Some Cycles of I —¦ A —¦ S —¦ M
A
The following tables provide a complete listing of the cycles for the invariances
Inv1 , ..., Inv5 .


Cycles of I —¦ A —¦ S —¦ M for Inv1
A.1
Starting point in INV1 : Cycle length:
(04x , 04x , 04x , 04x , 04x , 04x , 04x , 04x , ... )
1 87
(01x , 01x , 01x , 01x , 01x , 01x , 01x , 01x , ... )
2 81
(00x , 00x , 00x , 00x , 00x , 00x , 00x , 00x , ... )
3 59
(0bx , 0bx , 0bx , 0bx , 0bx , 0bx , 0bx , 0bx , ... )
4 27
(73x , 73x , 73x , 73x , 73x , 73x , 73x , 73x , ... )
5 2



Cycles of I —¦ A —¦ S —¦ M for Inv2 \ Inv1
A.2
Starting point in INV2 \ Inv1 : Cycle length:
(00x , 02x , 00x , 02x , 00x , 02x , 00x , 02x , ... )
1 39488
(00x , 01x , 00x , 01x , 00x , 01x , 00x , 01x , ... )
2 16934
(00x , 07x , 00x , 07x , 00x , 07x , 00x , 07x , ... )
3 7582
(00x , b8x , 00x , b8x , 00x , b8x , 00x , b8x , ... )
4 548
(00x , c6x , 00x , c6x , 00x , c6x , 00x , c6x , ... )
5 548
(03x , d6x , 03x , d6x , 03x , d6x , 03x , d6x , ... )
6 36
(07x , f1x , 07x , f1x , 07x , f1x , 07x , f1x , ... )
7 36
(03x , d5x , 03x , d5x , 03x , d5x , 03x , d5x , ... )
8 24
(05x , 0fx , 05x , 0fx , 05x , 0fx , 05x , 0fx , ... )
9 21
(0fx , 05x , 0fx , 05x , 0fx , 05x , 0fx , 05x , ... )
10 21
(06x , 86x , 06x , 86x , 06x , 86x , 06x , 86x , ... )
11 15
(0ex , 6ex , 0ex , 6ex , 0ex , 6ex , 0ex , 6ex , ... )
12 15
(2dx , 4ax , 2dx , 4ax , 2dx , 4ax , 2dx , 4ax , ... )
13 8
(5dx , a3x , 5dx , a3x , 5dx , a3x , 5dx , a3x , ... )
14 2
(86x , c0x , 86x , c0x , 86x , c0x , 86x , c0x , ... )
15 2



Cycles of I —¦ A —¦ S —¦ M for Inv3 \ Inv2
A.3
Starting point in Inv3 \ Inv2 : Cycle length:
(00x , 00x , 00x , 03x , 00x , 00x , 00x , 03x , ... )
1 1088297796
(00x , 00x , 00x , 02x , 00x , 00x , 00x , 02x , ... )
2 637481159
(00x , 00x , 00x , 04x , 00x , 00x , 00x , 04x , ... )
3 637481159
(00x , 00x , 00x , 06x , 00x , 00x , 00x , 06x , ... )
4 637481159
(00x , 00x , 00x , 08x , 00x , 00x , 00x , 08x , ... )
5 637481159
(00x , 00x , 00x , 01x , 00x , 00x , 00x , 01x , ... )
6 129021490
(00x , 00x , 00x , 07x , 00x , 00x , 00x , 07x , ... )
7 129021490
(00x , 00x , 00x , 09x , 00x , 00x , 00x , 09x , ... )
8 129021490
(00x , 00x , 00x , 10x , 00x , 00x , 00x , 10x , ... )
9 129021490
138 T. Van Le et al.

Starting point in Inv3 \ Inv2 : Cycle length:
(00x , 00x , 00x , 16x , 00x , 00x , 00x , 16x , ... )
10 64376666
(00x , 00x , 01x , 42x , 00x , 00x , 01x , 42x , ... )
11 64376666
(00x , 00x , 00x , eax , 00x , 00x , 00x , eax , ... )
12 11782972
(00x , 02x , 3ax , f9x , 00x , 02x , 3ax , f9x , ... )
13 13548
(00x , 05x , fdx , e6x , 00x , 05x , fdx , e6x , ... )
14 13548
(00x , 10x , 04x , adx , 00x , 10x , 04x , adx , ... )
15 10756
(00x , 02x , 2dx , b0x , 00x , 02x , 2dx , b0x , ... )
16 5640
(00x , 15x , e1x , 86x , 00x , 15x , e1x , 86x , ... )
17 5640
(00x , 09x , 40x , 90x , 00x , 09x , 40x , 90x , ... )
18 3560
(00x , 00x , c2x , 2bx , 00x , 00x , c2x , 2bx , ... )
19 1902
(00x , 21x , e4x , f9x , 00x , 21x , e4x , f9x , ... )
20 1902
(01x , d2x , 66x , c5x , 01x , d2x , 66x , c5x , ... )
21 136
(03x , 04x , c1x , cax , 03x , 04x , c1x , cax , ... )
22 90
(02x , 33x , 8dx , 7fx , 02x , 33x , 8dx , 7fx , ... )
23 90
(01x , 12x , dcx , 34x , 01x , 12x , dcx , 34x , ... )
24 47
(01x , 8bx , 9dx , edx , 01x , 8bx , 9dx , edx , ... )
25 47
(02x , 4dx , b4x , b1x , 02x , 4dx , b4x , b1x , ... )
26 47
(03x , c9x , 75x , a2x , 03x , c9x , 75x , a2x , ... )
27 47
(0ax , ¬x , 4ax , dfx , 0ax , ¬x , 4ax , dfx , ...
28 ) 40
(03x , 27x , 26x , 6cx , 03x , 27x , 26x , 6cx , ... )
29 12
(01x , 82x , 8fx , c8x , 01x , 82x , 8fx , c8x , ... )
30 4
(27x , aax , 2fx , 56x , 27x , aax , 2fx , 56x , ... )
31 4
(7dx , adx , f5x , a3x , 7dx , adx , f5x , a3x , ... )
32 4



Cycles of I —¦ A —¦ S —¦ M for Inv4 \ Inv2
A.4
Starting point in Inv4 \ Inv2 : Cycle length:
(00x , 00x , 00x , 00x , 00x , 01x , 00x , 01x , ... )
1 1219717400
(00x , 00x , 00x , 00x , 00x , 0ax , 00x , 0ax , ... )
2 1219717400
(00x , 00x , 00x , 00x , 00x , 06x , 00x , 06x , ... )
3 599556416
(00x , 00x , 00x , 00x , 00x , 0ex , 00x , 0ex , ... )
4 599556416
(00x , 00x , 00x , 00x , 00x , 03x , 00x , 03x , ... )
5 315637164
(00x , 00x , 00x , 00x , 00x , 07x , 00x , 07x , ... )
6 315637164
(00x , 00x , 00x , 00x , 02x , 62x , 02x , 62x , ... )
7 4307366
(00x , 00x , 00x , 00x , 02x , 3cx , 02x , 3cx , ... )
8 2990738
(00x , 00x , 00x , 00x , 00x , 16x , 00x , 16x , ... )
9 2153683
(00x , 00x , 00x , 00x , 0dx , aex , 0dx , aex , ... )
10 2153683
(00x , 00x , 00x , 00x , 01x , 64x , 01x , 64x , ... )
11 1958224
(00x , 00x , 00x , 00x , 01x , 88x , 01x , 88x , ... )
12 1958224
(00x , 00x , 00x , 00x , 07x , 0fx , 07x , 0fx , ... )
13 1606154
(00x , 00x , 00x , 00x , 08x , 42x , 08x , 42x , ... )
14 1495369
(00x , 00x , 00x , 00x , 0ex , 98x , 0ex , 98x , ... )
15 1495369
(00x , 00x , 00x , 00x , 0dx , e8x , 0dx , e8x , ... )
16 975150
(00x , 00x , 00x , 00x , 01x , 14x , 01x , 14x , ... )
17 803077
(00x , 00x , 00x , 00x , 01x , adx , 01x , adx , ... )
18 803077
(00x , 00x , 00x , 00x , 05x , b0x , 05x , b0x , ... )
19 564988
Complementation-Like and Cyclic Properties of AES Round Functions 139

Starting point in Inv4 \ Inv2 : Cycle length:
(00x , 00x , 00x , 00x , 0bx , 2fx , 0bx , 2fx , ... )
20 487575
(00x , 00x , 00x , 00x , 21x , 9ax , 21x , 9ax , ... )
21 487575
(00x , 01x , 00x , 01x , 3cx , ecx , 3cx , ecx , ... )
22 86038
(00x , 01x , 00x , 01x , b9x , 14x , b9x , 14x , ... )
23 86038
(00x , 01x , 00x , 01x , cdx , a4x , cdx , a4x , ... )
24 86038
(00x , 02x , 00x , 02x , a9x , bbx , a9x , bbx , ... )
25 86038
(00x , 00x , 00x , 00x , 06x , 15x , 06x , 15x , ... )
26 82750
(00x , 00x , 00x , 00x , 15x , 06x , 15x , 06x , ... )
27 82750
(00x , 00x , 00x , 00x , 34x , 48x , 34x , 48x , ... )
28 82750
(00x , 01x , 00x , 01x , bcx , 72x , bcx , 72x , ... )
29 82750
(00x , 00x , 00x , 00x , 02x , 02x , 02x , 02x , ... )
30 67324
(00x , 00x , 00x , 00x , 05x , 05x , 05x , 05x , ... )
31 21758
(00x , 00x , 00x , 00x , 17x , 17x , 17x , 17x , ... )
32 21758
(00x , 00x , 00x , 00x , 03x , 03x , 03x , 03x , ... )
33 13024
(00x , 0ax , 00x , 0ax , 63x , 1ex , 63x , 1ex , ... )
34 10902
(00x , 0fx , 00x , 0fx , 79x , 89x , 79x , 89x , ... )
35 5451
(00x , 07x , 00x , 07x , aax , 22x , aax , 22x , ... )
36 5451
(00x , 0ex , 00x , 0ex , 4bx , 2ex , 4bx , 2ex , ... )
37 5354
(00x , 00x , 00x , 00x , 01x , 01x , 01x , 01x , ... )
38 3340
(00x , 05x , 00x , 05x , 7fx , 04x , 7fx , 04x , ... )
39 2677
(00x , 29x , 00x , 29x , 8ex , b1x , 8ex , b1x , ... )
40 2677
(00x , 00x , 00x , 00x , 91x , 91x , 91x , 91x , ... )
41 2356
(00x , 0bx , 00x , 0bx , 2ex , 35x , 2ex , 35x , ... )
42 988
(00x , 00x , 00x , 00x , 09x , 09x , 09x , 09x , ... )
43 856
(02x , bbx , 02x , bbx , bbx , 02x , bbx , 02x , ... )
44 108
(00x , 2bx , 00x , 2bx , 38x , bfx , 38x , bfx , ... )
45 48
(00x , 6ex , 00x , 6ex , c2x , 78x , c2x , 78x , ... )
46 48
(00x , bax , 00x , bax , 24x , b5x , 24x , b5x , ... )
47 48
(13x , 18x , 13x , 18x , 78x , 69x , 78x , 69x , ... )
48 48
(12x , 13x , 12x , 13x , cdx , d6x , cdx , d6x , ... )
49 22
(05x , f1x , 05x , f1x , 83x , e9x , 83x , e9x , ... )
50 20
(0dx , eax , 0dx , eax , 62x , d1x , 62x , d1x , ... )
51 20
(07x , 6cx , 07x , 6cx , 7bx , 4ax , 7bx , 4ax , ... )
52 18
(03x , b4x , 03x , b4x , b4x , 03x , b4x , 03x , ... )
53 12
(06x , 06x , 06x , 06x , 35x , 35x , 35x , 35x , ... )
54 12
(05x , cbx , 05x , cbx , 51x , cex , 51x , cex , ... )
55 11
(21x , 7ex , 21x , 7ex , 21x , ebx , 21x , ebx , ... )
56 11
(1ax , 27x , 1ax , 27x , 49x , fax , 49x , fax , ... )
57 9
(28x , 8dx , 28x , 8dx , 90x , eax , 90x , eax , ... )
58 9
(03x , 2dx , 03x , 2dx , 09x , 76x , 09x , 76x , ... )
59 8
(2cx , 26x , 2cx , 26x , 97x , 84x , 97x , 84x , ... )
60 8
(2cx , b1x , 2cx , b1x , b1x , 2cx , b1x , 2cx , ... )
61 8
(12x , 12x , 12x , 12x , f9x , f9x , f9x , f9x , ... )
62 4
(39x , 53x , 39x , 53x , eax , 4bx , eax , 4bx , ... )
63 4
(39x , 67x , 39x , 67x , 9fx , e4x , 9fx , e4x , ... )
64 4
140 T. Van Le et al.

Cycles of I —¦ A —¦ S —¦ M for Inv5 \ Inv2
A.5
Starting point in Inv5 \ Inv2 : Cycle length:
(00x , 00x , 00x , 03x , 00x , 03x , 00x , 00x , ... )
1 1052651234
(00x , 00x , 00x , 05x , 00x , 05x , 00x , 00x , ... )
2 1052651234
(00x , 00x , 00x , 04x , 00x , 04x , 00x , 00x , ... )
3 737292504
(00x , 00x , 00x , 01x , 00x , 01x , 00x , 00x , ... )
4 417828286
(00x , 00x , 00x , 02x , 00x , 02x , 00x , 00x , ... )
5 417828286
(00x , 00x , 00x , 2cx , 00x , 2cx , 00x , 00x , ... )
6 193225414
(00x , 00x , 00x , 18x , 00x , 18x , 00x , 00x , ... )
7 96612707
(00x , 00x , 00x , 47x , 00x , 47x , 00x , 00x , ... )
8 96612707
(00x , 00x , 00x , 0ex , 00x , 0ex , 00x , 00x , ... )
9 87601912
(00x , 00x , 00x , 66x , 00x , 66x , 00x , 00x , ... )
10 87601912
(00x , 00x , 00x , 49x , 00x , 49x , 00x , 00x , ... )
11 11068518
(00x , 00x , 03x , e9x , 03x , e9x , 00x , 00x , ... )
12 9460050
(00x , 00x , 04x , 45x , 04x , 45x , 00x , 00x , ... )
13 6486298
(00x , 00x , 00x , 43x , 00x , 43x , 00x , 00x , ... )
14 5534259
(00x , 00x , 0bx , 61x , 0bx , 61x , 00x , 00x , ... )
15 5534259
(00x , 00x , 00x , 27x , 00x , 27x , 00x , 00x , ... )
16 4730025
(00x , 00x , 01x , 2fx , 01x , 2fx , 00x , 00x , ... )
17 4730025
(00x , 00x , 05x , 23x , 05x , 23x , 00x , 00x , ... )
18 3243149
(00x , 00x , 06x , 49x , 06x , 49x , 00x , 00x , ... )
19 3243149
(00x , 00x , 40x , 54x , 40x , 54x , 00x , 00x , ... )
20 394266
(00x , 00x , 1ax , 8fx , 1ax , 8fx , 00x , 00x , ... )
21 197133
(00x , 00x , 22x , 91x , 22x , 91x , 00x , 00x , ... )
22 197133
(00x , 02x , 9ex , 6dx , 9ex , 6dx , 00x , 02x , ... )
23 42454
(00x , 06x , 7ax , f3x , 7ax , f3x , 00x , 06x , ... )
24 42454
(00x , 00x , b9x , 2dx , b9x , 2dx , 00x , 00x , ... )
25 16932
(00x , 02x , 00x , 45x , 00x , 45x , 00x , 02x , ... )
26 16932
(00x , 02x , cax , 65x , cax , 65x , 00x , 02x , ... )
27 16932
(00x , 09x , 9ex , e9x , 9ex , e9x , 00x , 09x , ... )
28 16932
(00x , 16x , efx , 51x , efx , 51x , 00x , 16x , ... )
29 3166
(00x , 02x , 54x , 1ax , 54x , 1ax , 00x , 02x , ... )
30 3078
(00x , 25x , c7x , 5ex , c7x , 5ex , 00x , 25x , ... )
31 2366
(00x , 02x , 9cx , e1x , 9cx , e1x , 00x , 02x , ... )
32 1583
(00x , 13x , 25x , 5ax , 25x , 5ax , 00x , 13x , ... )
33 1583
(00x , 12x , 23x , f1x , 23x , f1x , 00x , 12x , ... )
34 1539
(00x , 23x , 71x , aex , 71x , aex , 00x , 23x , ... )
35 1539
(00x , 16x , a2x , eax , a2x , eax , 00x , 16x , ... )
36 1183
(00x , 1dx , 56x , 47x , 56x , 47x , 00x , 1dx , ... )
37 1183
(00x , 84x , 4dx , b4x , 4dx , b4x , 00x , 84x , ... )
38 1160
(00x , 03x , 49x , 72x , 49x , 72x , 00x , 03x , ... )
39 1062
(00x , 09x , 9dx , 7ax , 9dx , 7ax , 00x , 09x , ... )
40 1062
(00x , 24x , f5x , 24x , f5x , 24x , 00x , 24x , ... )
41 1062
(00x , 5ax , 24x , 44x , 24x , 44x , 00x , 5ax , ... )
42 1062
(00x , 0fx , 39x , 9bx , 39x , 9bx , 00x , 0fx , ... )
43 912
Complementation-Like and Cyclic Properties of AES Round Functions 141

Starting point in Inv5 \ Inv2 : Cycle length:
(00x , 49x , cfx , ccx , cfx , ccx , 00x , 49x , ... )
44 496
(00x , f8x , 3fx , e6x , 3fx , e6x , 00x , f8x , ... )
45 496
(02x , 9bx , adx , 9ex , adx , 9ex , 02x , 9bx , ... )
46 38
(03x , 5bx , 16x , d9x , 16x , d9x , 03x , 5bx , ... )
47 38
(03x , 58x , 9cx , 44x , 9cx , 44x , 03x , 58x , ... )
48 18
(25x , dex , 99x , 86x , 99x , 86x , 25x , dex , ... )
49 9
(3bx , dcx , 96x , e9x , 96x , e9x , 3bx , dcx , ... )
50 9
(06x , 83x , 45x , d3x , 45x , d3x , 06x , 83x , ... )
51 6
(3ex , 99x , 88x , cex , 88x , cex , 3ex , 99x , ... )
52 6
(08x , 24x , f2x , 16x , f2x , 16x , 08x , 24x , ... )
53 2
(24x , f2x , 16x , 08x , 16x , 08x , 24x , f2x , ... )
54 2
(35x , ecx , c0x , a7x , c0x , a7x , 35x , ecx , ... )
55 2
(c0x , a7x , 35x , ecx , 35x , ecx , c0x , a7x , ... )
56 2
More Dual Rijndaels


avard Raddum

Dep. of Informatics, The University of Bergen, P.O.box 7800, 5020 Bergen, Norway


Abstract. It is well known that replacing the irreducible polynomial
used in the AES one can produce 240 dual ciphers. In this paper we
present 9120 other representations of GF (28 ), producing more ciphers
dual to the AES. We also show that if the matrix used in the S-box
of Rijndael is linear over a larger ¬eld than GF (2), this would have
implications for the XSL attack.



1 Introduction
The cipher Rijndael [1] has been selected by NIST as the AES. Most of the
operations in Rijndael are based on the ¬eld GF (28 ), and several researchers
have made comments on the algebraic structures found in the cipher [3, 4, 5].
At ASIACRYPT 2002 Barkan and Biham [5] showed that the ciphers produced
when changing the polynomial used in AES are duals of Rijndael. In this paper
we construct many more duals of the AES.
Also at ASIACRYPT 2002 Courtois and Pieprzyk [6] described a possible
attack on the AES, using a large system of equations. We will show that one of
the dual ciphers could produce a much smaller system, that should be easier to
solve. However, we have checked that the matrix used in the a¬ne transformation
in the S-box is not among those which would simplify the system of equations.
At EUROCRYPT 2003 Biryukov et al. [7] presented a tool for ¬nding a¬ne
equivalent S-boxes. This can be used to ¬nd 2040 pairs of a¬ne mappings that
can be inserted in the AES, without changing the permutation induced by the
cipher. By replacing the ¬eld polynomial in the AES with one of the 30 other
irreducible polynomials, one is likely to be able to produce as many as 61,200
di¬erent versions of the duals of the AES found in [5]. This class can probably
be extended using the duals presented here.
In Section 2 we give a brief description of Rijndael, and the de¬nition of a
dual cipher. In Section 3 we show how to construct 1170 di¬erent representations
of GF (28 ), each one resulting in 8 ciphers dual to the AES. In Section 4 we check
whether the system of equations in the XSL-attack can be simpli¬ed. Conclusions
are made in Section 5.


2 Description of Rijndael
We here give a brief description of Rijndael, omitting the key schedule. A more
detailed description can be found in [1].

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 142“147, 2005.
c Springer-Verlag Berlin Heidelberg 2005
More Dual Rijndaels 143

Rijndael is a 128-bit block cipher with key sizes of 128, 192 or 256 bits. The
cipher consists of a round function that is repeated 10, 12 or 14 times according
to the length of the key. The cipher block and the round keys are viewed as
4 — 4-matrices of bytes. In some operations these bytes are viewed as elements
of GF (28 ), as well as 8-bit strings. The irreducible polynomial over GF (2) used
to represent GF (28 ) is x8 + x4 + x3 + x + 1.
There are four operations in the round function of Rijndael. These are used
in the following order:

“ SubBytes
“ ShiftRows
“ MixColumns
“ AddRoundKey
SubBytes replaces each byte of the cipher block. Each byte is ¬rst replaced by its
inverse, when viewed as an element of GF (28 ) (0’1 = 0), and then passed through
an a¬ne transformation Ax + b as an 8-bit vector. The constants A and b are
⎞ ⎛⎞

10001111 1
⎜1 1 0 0 0 1 1 1⎟ ⎜1⎟
⎜ ⎟ ⎜⎟
⎜1 1 1 0 0 0 1 1⎟ ⎜0⎟
⎟ ⎜⎟

⎜1 1 1 1 0 0 0 1⎟ ⎜0⎟
⎟, b=⎜ ⎟
A=⎜ ⎜1 1 1 1 1 0 0 0⎟ ⎜0⎟
⎟ ⎜⎟

⎜0 1 1 1 1 1 0 0⎟ ⎜1⎟
⎟ ⎜⎟

⎝0 0 1 1 1 1 1 0⎠ ⎝1⎠
00011111 0

ShiftRows takes row i of the cipher block, containing four bytes, and shifts
it i positions to the left. The top row is row 0 and the bottom is row 3.
MixColumns views the cipher state as a 4 — 4-matrix over GF (28 ), and pre-
multiplies it with a constant 4 — 4-matrix with elements from GF (28 ).
AddRoundKey simply xors the cipher block with the key for the current
round.
An AddRoundKey is applied to the plaintext before the ¬rst round, and in
the last round MixColumns is removed.

2.1 Dual Ciphers
We give here the de¬nition of a dual cipher from [5].
De¬nition 2.1. Two ciphers E and E are called dual ciphers if there exists
invertible transformations f, g and h such that

∀P, K f (EK (P )) = Eg(K) (h(P )).

In the case for Rijndael in this paper we will have f = g = h. The transfor-
mation f will be an isomorphism of GF (28 ) applied on all 16 bytes in the cipher
block in parallel.
144 H. Raddum

Di¬erent Representations of GF (28 )
3
The designers of Rijndael chose the irreducible polynomial r(x) = x8 + x4 + x3 +
x + 1 to construct GF (28 ). In the following let ± be a root of r(x). Elements of
GF (2)[±] (all sums and products of elements from GF (2) ∪ {±}) may be written
as polynomials in ± over GF (2), with degree at most 7. The elements of GF (28 )
are sometimes regarded as 8-bit vectors, with the natural mapping
c7 ±7 + . . . + c1 ± + c0 ←’ (c7 , . . . , c1 , c0 ).
When an element of GF (28 ) is written as a column vector c0 is at the top and
c7 is at the bottom.

Dual Ciphers by Replacing r(x)
3.1
There are 30 irreducible polynomials of degree 8 over GF (2). As pointed out in
[5], we may de¬ne β to be a root of any one of these polynomials, and construct
GF (28 ) = GF (2)[β]. The isomorphism φ between GF (2)[±] and GF (2)[β] is
established when we ¬nd a root of r(x) in GF (2)[β], and let this root be the
image of ±.
This isomorphism is a linear mapping. Let Mφ be the 8—8-matrix over GF (2)
whose column i is φ(±i ), where column 0 is the leftmost column and column 7
is the rightmost column. Then φ(a) can be computed as φ(a) = Mφ · a, where
a ∈ GF (2)[±] is written as a column vector.
Denote encryption of plaintext P under key K using Rijndael by EK (P ). Let the
cipher we get by replacing all constants in GF (28 ) in Rijndael by their image under
’1
φ, and replacing A with Mφ AMφ be called E . Then we have the duality [5]:
φ(EK (P )) = Eφ(K) (φ(P )),
where we understand φ to be applied to each of the GF (28 )-elements in the blocks
P, K and EK (P ).
Since there are 8 di¬erent roots of r(x) in GF (28 ), we get 8 di¬erent iso-
morphisms between GF (2)[±] and each representation of GF (28 ). With 30 ir-
reducible polynomials of degree 8 over GF (2) we therefore get a total of 240
di¬erent matrices Mφ .

Other Representations of GF (28 )
3.2
There are other ways of constructing GF (28 ) than by using an irreducible poly-
nomial of degree 8 over GF (2). This is shown by the following example.
First we create GF (22 ) = GF (2)[β] with β 2 + β + 1 = 0. Then we can make
GF (28 ) with t(x) = x4 + βx3 + x + (β + 1), an irreducible polynomial of degree
4 over GF (2)[β]. De¬ning γ to be a root of t(x), the elements of GF (28 ) can be
written as polynomials in γ of degree at most 3 with coe¬cients from GF (2)[β].
Writing elements of GF (22 ) as polynomials in β of degree at most 1 over GF (2),
we get a natural mapping between 8-bit strings and elements of GF (2)[β, γ]:
(c7 β + c6 )γ 3 + (c5 β + c4 )γ 2 + . . . + (c1 β + c0 ) ←’ (c7 , . . . , c0 ). (1)
More Dual Rijndaels 145

With this mapping the isomorphism φ : GF (2)[±] ’’ GF (2)[β, γ] can now be
realized as a matrix-multiplication in the same way as in the single extension
case. We ¬nd a root of r(x) in GF (2)[β, γ] and let this element be φ(±). Then
Mφ = [1, φ(±), φ(±2 ), . . . , φ(±7 )].


All Possible Representations of GF (28 ) Using Irreducible
3.3
Polynomials
Here we will show that there are 1170 di¬erent representations of GF (28 ) using
roots from irreducible polynomials. We have the following inclusions of sub¬elds
of GF (28 ):
GF (2) ‚ GF (22 ) ‚ GF (24 ) ‚ GF (28 ).

This induces four di¬erent chains of ¬elds starting with GF (2) and ending in
n
GF (28 ), these chains are listed below. The number above an arrow in GF (2i ) ’’
GF (2di ) means there are n irreducible polynomials of degree d over GF (2i ).
30
“ GF (2) ’’ GF (28 ): 30 representations.
1 60
“ GF (2) ’’ GF (22 ) ’’ GF (28 ): 60 representations.
3 120
“ GF (2) ’’ GF (24 ) ’’ GF (28 ): 360 representations.
1 6 120
“ GF (2) ’’ GF (22 ) ’’ GF (24 ) ’’ GF (28 ): 720 representations.

Adding the numbers together we get 1170 representations of GF (28 ).
The mapping between 8-bit strings and ¬eld elements for the last two chains
can be done as follows.
GF (2) ’’ GF (24 ) ’’ GF (28 ): Let β be a root of an irreducible polynomial
of degree 4 over GF (2), and let γ be a root of an irreducible polynomial of degree
2 over GF (2)[β]. The conversion is then

(c7 β 3 + . . . + c4 )γ + (c3 β 3 + . . . + c0 ) ←’ (c7 , . . . , c0 ).

GF (2) ’’ GF (22 ) ’’ GF (24 ) ’’ GF (28 ): Let β be a root of x2 + x + 1,
γ a root of an irreducible polynomial of degree 2 over GF (2)[β], and δ a root of
an irreducible polynomial of degree 2 over GF (2)[β, γ]. The mapping becomes

((c7 β + c6 )γ + (c5 β + c4 ))δ + ((c3 β + c2 )γ + (c1 β + c0 )) ←’ (c7 , . . . , c0 ).

For each representation there are 8 choices for the element φ(±). In total we
then get 8 · 1170 = 9360 matrices Mφ yielding isomorphisms, and so 9360 duals
of the AES. We have generated all these matrices, and checked that they are all
di¬erent (However, it can be shown that there are 60 pairs of matrices {M, M }
such that the ¬rst 4 columns of M and M are equal).
It should be noted that the idea of constructing GF (28 ) using two ¬eld ex-
tensions and applying it to Rijndael is not new. It has been done in [8], for the
purpose of making an e¬cient hardware implementation of inversion in GF (28 ).
146 H. Raddum

4 Implications for the XSL-Attack
The XSL attack is described in [6]. The basis of the attack is the fact that the
non-linear part of the S-box in Rijndael is inversion in the ¬eld GF (28 ). If X is
the input to the inversion and Y is the output, we have the relation XY = 1
(except for X = 0). By writing X as x7 ±7 + . . . + x0 and Y as y7 ±7 + . . . + y0 ,
the expression
(x7 ±7 + . . . + x0 )(y7 ±7 + . . . + y0 ) = 0 · ±7 + . . . + 0 · ± + 1
will give us 8 quadratic equations in the variables x0 , . . . , x7 , y0 , . . . , y7 .

4.1 Brief Summary of the XSL Attack
At some point in each round, we give variable names to the bits of the cipher
block. Since all the operations in Rijndael except the ¬eld inversion are linear
over GF (2), the input and output of the inversion are linear expressions in
these variables. By using the relation of the ¬eld inversion described above, we
can create an equation system in the key bits and the intermediate ciphertext
bits using one known plaintext/ciphertext pair. All of these equations will be
quadratic, and for the 128-bit key case the system should de¬ne the key uniquely.
The rest of the attack is to try to solve this equation system by creating
new equations using multiplication with monomials, and in the end using re-
linearization. If the XSL attack works, it is important that it is faster than
exhaustive search. One crucial point for the complexity of solving the system is
the number of variables it contains, and for the re-linearization, the number of
monomials.

Matrix in S-Box GF (22 )-Linear?
4.2
Let us assume for a little while that the matrix used in the S-box of Rijndael is
linear over GF (22 ). The other linear operations are linear over GF (28 ), and in
particular over GF (22 ). This means that Rijndael can be described completely
in terms of GF (22 ), it will never be necessary to go down to bit level in any
of the operations. Since all the linear operations of Rijndael are GF (22 )-linear,
we can make an equation system like the one used in the XSL-attack, but now
with variables and coe¬cients from GF (22 ). Since two and two bits are melted
together to form one variable, we will only get half as many variables as in the
original system, and only about one fourth of the number of quadratic monomi-
als. Since the number of monomials is signi¬cantly smaller in the system over
GF (22 ), and since we only have half as many variables, it should be easier to
reach the point where re-linearization can be applied.
The number of invertible 8—8-matrices over GF (2) is about 262.2 , and of these
only about 231.5 are linear over GF (22 ). This means a random invertible GF (2)-
matrix have a probability of less than 2’30 of being GF (22 )-linear. A check has
indeed veri¬ed that the matrix used in the S-box of Rijndael is not GF (22 )-linear,
and so the system can not be simpli¬ed this way. To our knowledge this is the
¬rst time it has been checked whether this matrix is linear over a larger ¬eld.
More Dual Rijndaels 147

5 Conclusions
In this paper we have increased the list of ciphers dual to Rijndael from 240 to
9360. If this will have any impact on the security of Rijndael remains to be seen.
Many properties of Rijndael, such as di¬erential and linear probabilities, carry
over to any of the duals, but other things can change. The designers of Rijndael
stated in [2] that the constant b in the a¬ne transformation of the S-box was
chosen so the S-box would have no ¬xed points. However, some of the duals have
an S-box with four ¬xed points.
The idea of describing one of the duals of Rijndael completely in terms of
GF (22 ) did not pay o¬ this time, but we hope it could serve as an inspiration
to do more algebraic analysis of the AES.


References
1. FIPS PUB 197. Advanced Encryption Standard (AES), National Institute of Stan-
dards and Technology, U.S. Department of Commerce, November 2001.
http://cscr.nist.gov/publications/¬ps/¬ps197/¬ps-197.pdf
2. J. Daemen, V. Rijmen. AES Submission document on Rijndael, Version 2, Septem-
ber 1999.
http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf
3. N. Ferguson, R. Schroeppel, D. Whiting. A Simple Algebraic Representation of
Rijndael. Selected Areas in Cryptography 2001, LNCS 2259, pp. 103-111, 2001.
4. S. Murphy, M. Robshaw. Essential Algebraic Structure within the AES. CRYPTO
2002, LNCS 2442, pp. 1-16, 2002
5. E. Barkan, E. Biham. In How Many Ways Can You Write Rijndael?. ASIACRYPT
2002, LNCS 2501, pp. 160-175, 2002.
6. N. Courtois, J. Pieprzyk. Cryptanalysis of Block Ciphers with Overde¬ned Systems
of Equations. ASIACRYPT 2002, LNCS 2501, pp. 267-287, 2002.
7. A. Biryukov, C. De Canni`re, A. Braeken, B. Preneel. A Toolbox for Cryptanalysis:
e
Linear and A¬ne Equivalence Algorithms. EUROCRYPT 2003, LNCS 2656, pp.
33-50, 2003.
8. J. Wolkerstorfer, E. Oswald, M. Lamberger. An ASIC Implementation of the AES
SBoxes. CT-RSA 2002, LNCS 2271, pp. 67-78, 2002
Representations and Rijndael Descriptions

Vincent Rijmen and Elisabeth Oswald

IAIK, Graz University of Technology,
In¬eldgasse 16a, A-8010 Graz, Austria
{vincent.rijmen, elisabeth.oswald}@iaik.tugraz.at




Abstract. We discuss di¬erent descriptions of Rijndael and its compo-
nents and how to ¬nd them. The fact that it is easy to ¬nd equivalent
descriptions for the Rijndael transformations, has been used for two dif-
ferent goals. Firstly, to design implementations on a variety of platforms,
both e¬cient and resistant against side channel analysis. Secondly, to an-
alyze the security of the cipher We discuss these aspects, give examples,
and present our views.



1 Introduction
In this paper, we give an overview of recent developments in the study of Rijn-
dael security and e¬cient Rijndael implementations. Central to many of these
developments is the technique of changing representations, and therefore we take
this as the central theme of our treatment here.
When we look at what has been published about Rijndael in the last couple
of years, we see that most authors restrict in their studies the possible changes
of representation to the set of polynomial bases in a ¬nite ¬eld, e.g. selection
of a di¬erent base element or the selection of a di¬erent reduction polynomial.
However, ¬nite ¬elds have a much richer structure, e.g. they can also be described
as vector spaces over the ground ¬eld. It is our belief that exploration of the
vector space representation can bring us to new insights in both security and
e¬cient implementation of the Rijndael.
We start this paper by setting the framework to study di¬erent represen-
tations and the resulting equivalent descriptions for Rijndael. Afterwards, we
present the overview of recent results and place them in our framework.


2 Change of Representation: An Old Mathematical
Technique
It is well-known that the choice of representation in¬‚uences the complexity of
most problems related to algebra. One example with application in cryptography

This research was supported ¬nancially by the A-SIT, Austria.

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 148“158, 2005.
c Springer-Verlag Berlin Heidelberg 2005
Representations and Rijndael Descriptions 149

is given by elliptic curves. An arbitrary elliptic curve has a de¬ning equation of
the following form:
Ay 2 + Byx + Cy = Dx3 + Ex2 + F x + G. (1)
By choosing another representation, the de¬ning equation can be transformed
into the following form:
y 2 = x3 + ax + b . (2)

For all de¬ning equations of the form (1), there is an equation of the form (2)
de¬ning an elliptic curve with the same mathematical properties, although both
curves contain di¬erent points (x, y).
A second example is the gate complexity of a circuit that implements the
squaring operation in a ¬nite ¬eld with characteristic two. If the elements of the
¬eld are represented by their coordinates with respect to a normal basis, then
the squaring operation corresponds to a simple rotation of the coordinates. In
other representations, the squaring operation corresponds to a more complicated
linear transformation of the coordinates.
The problem we address in this paper, is exactly the opposite problem. When
given a Boolean transformation with ¬xed ˜points™ (x, S(x)), we want to ¬nd a
simple algebraic description for this Boolean transformation.


3 Boolean Transformations and Algebras
In order to improve understanding of the issues related to equivalent descriptions,
it is important to clearly de¬ne the terminology. We make a distinction between
two mathematical concepts that are often used as synonyms. These concepts are
an abstract element of an algebra on the one hand, and the representation of the
element on the other hand. We start with a de¬nition for an algebra.
An algebra consists of one or more sets of elements and one or more operations
between the elements. We will consider here algebras that contain only one set
of elements, denoted by A. Furthermore, we will assume that the cardinality of
A equals 2n for some integer value n.
An m-ary operation b maps an input consisting of m elements of A to an
output, which is also in A.
b : Am ’ A : (x1 , x2 , . . . , xm ) ’ b(x1 , x2 , . . . , xm ) = y (3)
A 1-ary operation is also called an (algebraic) function.
A Boolean vector is a one-dimensional array of bits. By Boolean transfor-
mation, we mean a function S that maps a Boolean vector to another Boolean
vector. For sake of simplicity, we will assume that the input and output vectors
have equal size.
S : Z2 ’ Z2 : x ’ y = S(x)
n n
(4)
A representation ρ maps the elements of A to n-bit Boolean vectors.
ρ : A ’ Z2 : x ’ ρ(x) = x
n
(5)
150 V. Rijmen and E. Oswald

The inverse map of a representation is called a labeling map. A representation,
or labeling, de¬nes a map from the algebraic functions to the Boolean transfor-
mations:
R(b) = Sb ” ∀x ∈ A : ρ(b(x)) = Sb (ρ(x)) . (6)


labeling

Algebra elements - Boolean vectors
representation


Operations Boolean transformations
description

Fig. 1. Terminology w.r.t. algebra elements and Boolean vectors



3.1 Finding Descriptions
Finding an algebraic description for a Boolean transformation S can be done in
three steps.
Initialization: Decide on an algebra to be used.
Labeling: De¬ne a labeling map from the Boolean vectors to elements of the
algebra.
Describing: Compute the description of the Boolean transformation S.
Before describing the steps in some more detail, we brie¬‚y return to the previ-
ous example. Suppose we have a Boolean transformation S that implements a
rotation of the bits: S(x) = x ≪ 1. Suppose further that we have chosen to use
the ¬nite ¬eld GF (2n ) as the algebra to work in. Since S is linear over this ¬eld,
it can always be described with a linear polynomial l(x):
n’1
i
l(x) = ai x2 , (7)
i=0

where the ai are some constants. If the Boolean vectors x are considered as the
representation of the coordinates of the elements x with respect to a normal
basis, then the polynomial describing S can be as simple as l(x) = x2 .

Selecting an Algebra. For the values of n that are of practical importance,
2n
the number of algebras that can be de¬ned, is very large: (2n )2 di¬erent bi-
nary operations can be de¬ned. However, the requirement to obtain a ˜simple™
description in practice limits the number of interesting algebras. The most natu-
ral choices are perhaps the vector space (GF(2))n or the ¬eld GF(2n ). However,
other algebras can be used as well, e.g. the algebra < Z2n +1 \{0}, — > as used
in IDEA.
Representations and Rijndael Descriptions 151

Selecting a Labeling. Once an algebra has been selected, the elements of the
algebra have to be assigned to the Boolean vectors. We call this the labeling of
the Boolean vectors. Let the labeling map be denoted by m:

m : (Z2 )n ’ A. (8)

The number of labeling maps equals (2n !). Note that this is more general than
a change of basis in a ¬nite ¬eld.

Computing the Representation. Once the algebra and the labeling map are
de¬ned, the input-output tuples of the transformation S can be translated into
tuples of the algebra:

(x, S(x)) ’ (a, b) = (m(x), m(S(x))). (9)

The functional description of S in the new representation can be derived from
the input-output tuples, using for instance the Lagrange interpolation formula,
if it can be applied in the algebra selected.


4 Rijndael Descriptions
Equivalent descriptions can be investigated for any block cipher. Indeed, al-
ready in the 1980™s, several results appeared about equivalent descriptions for
the DES [6]. Afterwards, the topic seems to have died out in the ¬eld of sym-
metric cryptography. The selection of Rijndael to become the AES has triggered
new research in this direction.

4.1 Number of Equivalent Descriptions
The design of Rijndael was made in the ¬eld GF(256). All design criteria were
made and the selection of components was done with this ¬eld in mind. In order
to be able to de¬ne the input-output behavior uniquely, one speci¬c representa-
tion of the ¬eld elements had to be chosen. The choice was made to use a binary
polynomial basis, with irreducible polynomial p(t) = t8 + t4 + t3 + t + 1.
In [2], it was observed that 240 equivalent ciphers (i.e. alternative descrip-
tions) can be generated by choosing one of the 30 irreducible binary polynomials
of degree 8 and by choosing one of the 8 roots of this polynomial as generator.
However, there are many more alternative representations possible. The ¬eld
GF(256) is isomorphic to the ¬eld (GF (2))8 , which is also an 8-dimensional
vector space. In this vector space, there are
7
(28 ’ 2i ) ≈ 262 (10)
i=0

di¬erent bases. Each base leads to a di¬erent labeling of bytes and hence a di¬er-
ent description of Rijndael. In [3], 2040 bases with a special property are derived.
152 V. Rijmen and E. Oswald

The authors combine these 2040 bases with the 30 irreducible polynomials in or-
der to de¬ne 61200 equivalent cipher descriptions.
Equivalent descriptions can also be constructed by de¬ning an arbitrary bi-
jective labeling map m. There are 256! di¬erent such labeling maps and at least
as many di¬erent descriptions. Finally, observe that labeling maps don™t have
to be bijective. Also injective maps can be used (cf. infra), and hence there are
in¬nitely many labeling maps.

4.2 Useful Representations
The vast majority of the 256! equivalent descriptions of Rijndael will not result in
any new insights. Indeed, only the 262 descriptions that are constructed following
a change of basis in the vector space (GF (2))8 , have the property that ˜addition™
corresponds to binary exclusive-or. In all other descriptions, the speci¬cation of
addition will require the use of tables without any apparent structure.
The transformations MixColumns and AddRoundKey can be described by
very simple operations when the default representation is used. This is a second
reason to look for new representations ˜close™ to the default representation.


5 Descriptions Assisting Implementations
Alternative descriptions facilitating implementations are used mostly on con-
strained platforms: hardware and small processors. In environments with little
constraints, the default description of Rijndael seems to be as good as any other
one.
The addition of side-channel attack countermeasures usually decreases the
performance and/or increases the cost of an implementation. Hence, the tech-
niques developed to improve the performance of ordinary implementations in
constrained environments, are usually also of use in side-channel attack resisting
hardware.

5.1 Hardware E¬cient Descriptions
As explained before, the use of alternative ¬nite ¬eld representations in order
to reduce the gate count of a circuit is a well-established technique. Several
alternative representations have been proposed in the cryptographic literature,
mainly in order to improve the implementation of the SubBytes transformation.
The ¬rst type of alternative representation is to label bytes as polynomials
of degree smaller than 2, with coe¬cients in GF(16):
m : Z2 ’ GF (16)[t]/(t2 + At + B) : x ’ m(x) = at + b,
8
(11)
with a = m1 (x), b = m2 (x). The maps m1 , m2 have to satisfy some conditions
and the coe¬cients A, B are chosen such that the polynomial t2 + At + B is irre-
ducible. Then, the transformation SubBytes can be described by one nonlinear
formula of the form
Representations and Rijndael Descriptions 153

(at + b)’1 = (b2 B + baA + a2 )’1 (bt + a + bA), (12)
combined with linear and a¬ne operations, which depend on the choice for A, B
and the details of the maps m1 (x), m2 (x). Descriptions of this type have been
proposed in [12, 13, 14, 16].
The alternative representations mainly improve the gate complexity of the
SubBytes step, while the complexity of the other steps remains the same, or
deteriorates slightly. This results in di¬erent approaches. In the ¬rst approach,
the SubBytes is implemented in the representation that is best for that step, and
the other steps are implemented using another representation. This approach
necessitates changes of representation in between steps [14, 16].
In the second approach, frequent changes of representation are avoided by
adopting a ˜compromise™ representation, which improves the complexity of Sub-
Bytes, and doesn™t increase the complexity of other steps too much [13].
In the third approach, an alternativ representation, which is best for the
SubBytes step, is combined with an equivalent AES [17].

5.2 Representations Assisting SCA Countermeasures
Side-channel attacks are used to extract secret key material from real systems. It
has been observed that computing hardware and software often leak information
about secret keys used in cryptographic algorithms. This leakage comes from
variations in execution time, power consumption, radiation, etc.
Many proposals for hardware designs that resist side-channel attacks, are
based on masking techniques: the sensitive values are never manipulated directly,
but only in blinded, or masked, form. The mask is a random value, which needs to
be processed separately. Such a masking scheme can also be described as a secret
sharing scheme, where the masked and the masked value are two shares. Hence,
a masking scheme by itself can already be seen as an expanding alternative
representation.
For linear operations, it is well-known what masking schemes to use and how
to implement them. For the non-linear operation of Rijndael, there are several
proposals.

5.3 Additive Split
In order to implement a linear operation L(x), the input x is represented by a
tuple (p, q) with p + q = x. We call this the additive split of sensitive variables.
In order to compute the tuple corresponding to L(x), the linear operation is
performed separately on each share. Indeed, we have that if x = p + q, then
L(x) = L(p) + L(q), and hence L(x) is represented by (L(p), L(q)).
The addition of two sensitive variables can also be protected using the addi-
tive split. The result can be computed in a secure way by simply adding the co-
ordinates of the corresponding tuples: if x is represented by (p, q) and y by (r, s),
then x + y can be represented by (v, w) = (p + r, q + s) or (v, w) = (p + s, q + r).
In both representations, v and w are completely uncorrelated to the values of x
and y.
154 V. Rijmen and E. Oswald

The SubBytes step in the Rijndael round transformation consists of an a¬ne
operation and the multiplicative inverse map, or, more accurately, the power
function map x254 . Protecting non-linear maps by means of an additive split is
not a straightforward process.
In order to implement this map, two functions f, g are required, such that
x = f (p) + g(q) (where x = p + q). In order to have security against ¬rst-
254

order side-channel attacks, the implementation of maps f (p) and g(q) should
not produce intermediate results which correlate with p + q. It remains an open
problem whether such maps can be de¬ned.
As an alternative solution, other types of split have been proposed in the
literature and we describe them in Section 5.4. In Section 5.5, we describe a re-
cently developed method. By using a special representation of the ¬eld elements,
it becomes possible to protect also the power function by means of an additive
split.

5.4 Multiplicative Split
A multiplicative split was proposed in [1]. A byte x is mapped to (p, q) with
x = pq 254 . It can be seen that the tuple corresponding to x254 can be computed
as (p254 , q 254 ) = (q, p). Hence this representation would allow to implement the
power function with a simple swap of registers. Alas, it seems from [1] that the
requirement to change the representation from additive split to multiplicative
split and vice versa, makes it necessary to compute the power functions of the
two shares explicitly.
A more important disadvantage is the so-called zero multiplication problem,
which refers to the fact that a multiplicative split fails to hide the zero value:

x = 0 ” (p = 0 or q = 0). (13)

One approach to ¬x this problem is to introduce a second injective map, that
maps the elements of GF(256) to a larger ring containing zero divisors [9].

5.5 Additive Split in Tower Fields
This technique has been described in [11]. It builds on the techniques explained
in [16]. During all operations, the variables are protected by means of an additive
split. In [4], an alternative method was developed, based on the same principles.
In the tower ¬eld representation, bytes are labeled as polynomials of degree
smaller than 2. The two coe¬cients of the polynomials are elements of GF(16).
For some of the computations, these coe¬cients in turn are labeled as polyno-
mials of degree 2, with coe¬cients in GF(4).

m : Z2 ’ GF (16)[t]/(t2 + At + B) : x ’ m(x) = at + b,
8
(14)
m : GF (16) ’ GF (4)[u]/(u2 + Cu + D) : y ’ m (y) = cu + d, (15)

with a = m1 (x), b = m2 (x), c = m1 (y), d = m2 (y). The maps m1 , m2 , m1 , m2
have to satisfy some conditions and the coe¬cients A, B, C, D are chosen such
Representations and Rijndael Descriptions 155

that the polynomials t2 + At + B and u2 + Cu + D are irreducible over GF(16),
respectively GF(4), and lead to e¬cient arithmetic. Note that the labeling maps
are all linear and hence they can be protected as explained in Section 5.3. The
multiplicative inverse map can be described in two steps, which are explained
below.

Step 1: GF(16). Firstly, (12) is used to describe the map using only the fol-
lowing operations: addition, multiplication and taking the multiplicative inverse.
All these operations are in GF(16). The implementation of the multiplicative in-
verse is done in Step 2. The additions in GF(16) are protected as explained in
Section 5.3.
The multiplication of two sensitive variables a and b, that are represented
by (p, q) and (r, s), is implemented by multiplying the coordinates p and r, and
adding so-called correction terms ci . The correction terms are de¬ned in such
a way that they can be computed without producing intermediate results that
correlate to a, b, ab, a + b, a2 , b2 , or any other value that could leak information
about the sensitive variables to the attacker. The result is a representation of
the following form:
(v, w) = (pq + ci , q). (16)
i

Step 2: GF(4). The second step is similar to the ¬rst step, but operating on
smaller ¬elds. A formula very similar to (12) describes how the multiplicative
inverse in GF(16) can be computed using operation in GF(4) only.
Addition and multiplication in GF(4) are implemented and protected as de-
scribed for Step 1. For the implementation of the multiplicative inverse, the
following fact is used.
For all x ∈ GF(4), it holds that x’1 = x2 , hence taking the multiplicative
inverse is a linear operation, that can be protected by means of an additive split,
as described in Section 5.3.


6 Representations Assisting Cryptanalysis
Several alternative descriptions have been derived, showing that more elegant,
more structured and more simple sets of equations de¬ning Rijndael can be
constructed. Although several of them seem a promising start for an attack, no
breakthrough has been demonstrated yet.

6.1 BES
Murphy and Robshaw [10] de¬ne the block cipher BES, which operates on data
blocks of 128 bytes instead of bits. According to Murphy and Robshaw, the
algebraic structure of BES is even more elegant and simple than that of Rijndael.
Furthermore, Rijndael can be embedded into BES. There is a map φ such that:

Rijndael(x) = φ’1 (BES (φ(x))) . (17)
156 V. Rijmen and E. Oswald

The map φ can also be seen as an injective labeling of the inputs of Rijndael.
Murphy and Robshaw proceed with some observations on the properties of
BES. However, these properties of BES do not apply to Rijndael.

6.2 Redundant S-Boxes
Any 8 — 8-bit S-box can be considered as a composition of 8 Boolean functions
sharing the same 8 input bits. J. Fuller and W. Millan observed that the S-box
of Rijndael can be described using one Boolean function only [8]. The 8 Boolean
functions can be described as
fi (x1 , . . . , x8 ) = f (gi (x1 , . . . , x8 )) + ci , i = 1, . . . , 8, (18)
where the function f is the only nonlinear function, the gi are a¬ne functions
and the ci are constants.

6.3 Continued Fractions
Ferguson, Schroeppel and Whiting [7] derive a closed formula for Rijndael that
can be seen as a generalization of continued fractions. Any byte of the interme-
diate result after 5 rounds can be expressed as follows.
C1
x=K+ (19)
C2
K— + C3
K— + C4

K+ C5
K— + K + p—

<<

. 6
( 7)



>>