ńņš. 6 |

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

HĖ

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 |