<<

. 7
( 7)





Here every K is some expanded key byte, each Ci is a known constant and each
— is a known exponent or subscript, but these values depend on the summation
variables that enclose the symbol.
A fully expanded version of (19) has 225 terms. It is currently unknown what
a practical algorithm to solve this type of equations would look like.

6.4 XL and XSL Methods
XL and XSL are new methods to solve nonlinear algebraic equations [5, 15]. The
e¬ectiveness and e¬ciency of these methods remain a topic of debate. It seems
plausible that the complexity of the methods is in¬‚uenced by the description that
is chosen. For instance, the authors of [10] claim that using their representation,
the complexity of the XSL method decreases signi¬cantly. More details about
the methods can be found elsewhere in these proceedings.



7 Conclusions and Perspective on the Future
Compared with other symmetric ciphers, the design of Rijndael shows a remark-
able level of mathematical abstraction. The rich structure, and in particular the
Representations and Rijndael Descriptions 157

ease with which equivalent descriptions can be constructed, on the one hand has
caused worries with some people fearing for its long-term security. On the other
hand, the presence mathematical structure has certainly greatly facilitated the
development of e¬cient implementations on constrained environments and envi-
ronments where protection measures against side-channel attacks are required.
We expect that the continuation and generalization of this research will lead
to better insights in the security of Rijndael and even more e¬cient implemen-
tations. Furthermore, we expect that many results will be applicable to other
ciphers as well, leading to an increased understanding about the process of de-
signing secure symmetric primitives.



References
1. Mehdi-Laurant Akkar and Christophe Giraud, “An implementation of DES and
AES secure against some attacks,” CHES 2001, LNCS 2162, Springer-Verlag, 2001,
pp. 309“318.
2. Elad Barkan and Eli Biham, “In how many ways can you write Rijndael?”,
Advances in Cryptology ” Asiacrypt 2002, LNCS 2051, Springer-Verlag, 2002,
pp. 160“175.
3. Alex Biryukov, Christophe De Canni´re, An Braeken and Bart Preneel, “A tool-
e
box for cryptanalysis: linear and a¬ne equivalence algorithms,” Advances in
Cryptology ” Eurocrypt 2003, LNCS 2656, Springer-Verlag, 2003, pp. 33“50.
4. Johannes Bl¨mer, Guajardo Merchan and Volker Krummel, “Provably secure
o
masking of AES”, Selected Areas in Cryptography - SAC™04, LNCS, Springer-
Verlag, to appear.
5. Nicolas T. Courtois and Josef Pieprzyk, “Cryptanalysis of block ciphers with
overde¬ned systems of equations,” Advances in Cryptology ” Asiacrypt ™02,
LNCS 2501, Springer-Verlag, 2003, pp. 267“287.
6. Marc Davio, Yvo Desmedt, Marc Foss´prez, Ren´ Govaerts, Jan Hulsbosch, Pa-
e e
trik Neutjens, Philippe Piret, Jean-Jacques Quisquater, Joos Vandewalle, and Pas-
cal Wouters, “Analytical characteristics of the DES,” Advances in Cryptology ”
Crypto ™83, Plenum Press, 1984, pp. 171“202.
7. Niels Ferguson, Richard Schroeppel, and Doug Whiting, “A simple algebraic rep-
resentation of Rijndael,” Selected Areas in Cryptography SAC01, LNCS 2259,
Springer-Verlag, 2001, pp. 103-111.
8. Joanne Fuller and William Millan, “On linear redundancy in S-boxes,” Fast Soft-
ware Encryption ™03, LNCS 2887, Springer-Verlag, 2003, pp. 74“86.
9. Jovan Dj. Golic and Christophe Tymen, “Multiplicative masking and power anal-
ysis of AES,” CHES 2002, LNCS 2535, Springer-Verlag, 2003, pp. 198“212.
10. Sean Murphy and Matthew J.B. Robshaw, “Essential algebraic structure within
the AES”, Advances in Cryptology ” Crypto 2002, LNCS 2442, Springer-Verlag,
2002, pp. 17“38.
11. Elisabeth Oswald, Stefan Mangard and Norbert Pramstaller, “Secure and e¬cient
masking of the AES: a mission impossible?,” Technical report IAIK-TR 2003/11/1,
available from http://eprint.iacr.org/2004/134.pdf.
12. Vincent Rijmen, “E¬cient implementation of the Rijndael S-box,” available from
http://www.esat.kuleuven.ac.be/∼rijmen/rijndael/sbox.pdf, 2000.
158 V. Rijmen and E. Oswald

13. Atri Rudra, Pradeep K. Dubey, Charanjit S. Jutla, Vijay Kumar, Josyula R. Rao,
and Pankaj Rohatgi, “E¬cient Rijndael encryption implementation with composite
¬eld arithmetic,” CHES 2001, LNCS 2162, Springer-Verlag, 2001, pp. 171“184.
14. Akashi Satoh, Sumio Morioka, Kohji Takano, and Seiji Munetoh, “A compact
Rijndael hardware architecture with S-box optimization,” Advances in Cryptology,
Asiacrypt 2001, LNCS 2248, Springer-Verlag, 2001, pp. 239“254.
15. Adi Shamir, Jacques Patarin, Nicolas Courtois and Alexander Klimov, “E¬cient
Algorithms for solving Overde¬ned Systems of Multivariate Polynomial Equa-
tions”, Advances in Cryptology ” Eurocrypt 2000, LNCS 1807, Springer-Verlag,
2000, pp. 392“407.
16. Johannes Wolkerstorfer, Elisabeth Oswald, and Mario Lamberger, “An ASIC
implementation of the AES S-boxes,” Topics in Cryptology ” CT-RSA 2002,
LNCS 2271, Springer-Verlag, 2002, pp. 67“78.
17. Shee-You Wu, Shih-Chuan Lu, and Chi Sung Laih, “Design of AES Based on Dual
Cipher and Composite Field,” Topics in Cryptology ” CT-RSA 2004, LNCS 2964,
Springer-Verlag, 2004, pp. 25“38
Linearity of the AES Key Schedule

Frederik Armknecht and Stefan Lucks

Theoretische Informatik,
Universit¨t Mannheim,
a
68131 Mannheim Germany
armknecht@th.informatik.uni-mannheim.de
lucks@th.informatik.uni-mannheim.de



Abstract. The AES key schedule can almost be described as collection
of 32 linear feedback shift registers LFSRs, working in parallel. This
implies that for related keys, i.e., pairs of unknown keys with known
di¬erences, one can in part predict the di¬erences of the individual round
keys. Such a property has been used (but not explained in detail) by
Ferguson et al. [3] for a related key attack on a 9-round variant of the
AES (with 256-bit keys). In the current paper, we study the propagation
of (known) key di¬erences in the key schedule for all three key sizes of
the AES.



1 Introduction
Recall the key schedule of the AES, e.g. for 128-bit keys. Denote the inital cipher
4
key (K0 , K1 , K2 , K3 ) ∈ {0, 1}32 . This is the ¬rst round key, as well. The next
round key is (K4 , K5 , K6 , K7 ), the next one is (K8 , K9 , K10 , K11 ), . . . The 32-bit
values Ki are generated by the following key schedule algorithm:

If (i mod 4) = 0
then Ki := Ki’4 • f (Ki’1 ) • const(i)
else Ki := Ki’4 • Ki’1 ,

where f : {0, 1}32 ’ {0, 1}32 is a nonlinear function and const(i) are some
round-dependent constants. The nonlinear function f allows reasonably e¬cient
implementations, and thus the key schedule itself is highly e¬cient. The key
schedules for 192-bit and 256-bit keys are de¬ned similarly.
˜˜˜˜
Consider two unknown cipher keys (K0 , K1 , K2 , K3 ) and (K0 , K1 , K2 , K3 )
˜
with known di¬erences δi = Ki • Ki , i = 0, 1, 2, 3. The key schedule allows us
to describe linear realationships of the form
43
˜
ci · (Ki • Ki ) = δ, ci ∈ {0, 1}
i=0


Supported by grant 620307 of the DFG (German Research Foundation).

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 159“169, 2005.
c Springer-Verlag Berlin Heidelberg 2005
160 F. Armknecht and S. Lucks

with known δ. In principle, such relationships could be used to mount related-key
attacks against the AES “ and in fact, one such related-key attack for the AES
variant with 256-bit keys has been previously published [3].
The current paper investigates the existence of such linear relationships in
the AES key schedule(s). It turns out that for none of the de¬ned key sizes, any
such relationship exists which covers the entire key-schedule (i.e., which involves
values from the ¬rst round key and values from the last round key, but no values
from round keys in between).

2 De¬nitions and Motivation
There exist three di¬erent versions of the AES:
Nk Key size 32 · Nk Number of rounds Nr
4 128 bit 10
6 192 bit 12
8 256 bit 14

Before encryption, the secret key K of size 32 · Nk is expanded to a key K of
size 128 · (Nr + 1). Following the description given in [2] we divide the expanded
key K into 4 · (Nr + 1) parts K0 , . . . , K4Nr +3 ∈ {0, 1}32 . In the following, we will
treat the Ki as vectors of the vector space 32 and denote by • the corresponding
2
addition of two vectors. The ¬rst Nk vectors are exactly the secret key K and
1

the rest is de¬ned by the key schedule.
To increase the resistance against related-key attacks the key schedule was
designed such that the descriptions of the columns Ki , i ≥ Nk , are linearly inde-
˜
pendent of K. In fact, given two unknown keys K and K with known di¬erence
˜ ˜ ˜
K • K = (K0 • K0 , . . . , KN ’1 • KN ’1 ) =: (δ0 , . . . , δN ’1 ) =: δ
k k k

˜
it should be infeasible to say anything about the di¬erences Ki • Ki for i ≥ Nk .
Surprisingly, it is possible to ¬nd (many) linear combinations of the following
kind:
4Nr +3
ci · Ki = 0, ci ∈ (1)
2
i=0
This implies that the following equation is true
Nk ’1 Nk ’1 4Nr +3
˜ ˜
ci · δi = ci · (Ki • Ki ) = ci · (Ki • Ki )
i=0 i=0 i=Nk

For example the following equation holds for the 128-bit variant:
˜ ˜
K4 • K 4 • K 5 • K 5 = δ 1
In the following section, we develop the general theory and provide a basis
of all valid linear combinations of K0 , . . . , K4Nr +3 for all three AES variants.

1
In fact, this is simply the componentwise XOR of the 32 bits of the two vectors.
Linearity of the AES Key Schedule 161

3 Linearity of the AES Key Schedule
In the following we examine the key schedules of the three AES variants with
128-bit, 192-bit resp. 256-bit key lengths. We will see that in all cases many
equations of the type (1) exist.

3.1 AES with 128 Bit Key Length
Let K = (K0 , K1 , K2 , K3 ) ∈ {0, 1}128 be the secret key with Ki ∈ {0, 1}32 . Then
the expanded key K = (K0 , . . . , K43 ) is de¬ned by the following key schedule:
Ki := Ki ,0 ¤ i < 4
Ki := Ki’4 • fi (Ki’1 ) , 4 ¤ i ¤ 43, i mod 4 = 0
Ki := Ki’4 • Ki’1 , 4 ¤ i ¤ 43, i mod 4 = 0
fi (x) is the permutation f (x) • const(i) mentionend in section 1; but we
will see that the exact de¬nition of fi does not matter for our observations. To
motivate the theory, we have a look at the de¬nition of K4 , . . . , K11 :
K4 = K0 • f4 (K3 )
K5 = K1 • K4 = K0 • K1 • f4 (K3 )
K6 = K2 • K5 = K0 • K1 • K2 • f4 (K3 )
K7 = K3 • K6 = K0 • K1 • K2 • K3 • f4 (K3 )
K8 = K4 • f8 (K7 ) = K0 • f4 (K3 ) • f8 (K7 )
K9 = K8 • K5 = K1 • f8 (K7 )
K10 = K9 • K6 = K0 • K2 • f4 (K3 ) • f8 (K7 )
K11 = K10 • K7 = K1 • K3 • f8 (K7 )


We observe that each of the vectors K0 , . . . , K11 can be expressed by a linear
combination of K0 , K1 , K2 , K3 , f4 (K3 ), f8 (K7 ). This can be easily generalized:
each of the vectors K0 , . . . , K43 can be written as a linear combination of ele-
ments of the set
B := {K0 , K1 , K2 , K3 , f4 (K3 ), . . . , f40 (K39 )}.
=K

This complies with the following matrix-vector-product where M is a binary
matrix of size 44 — 14:
⎛ ⎞
K0
⎜ ⎟⎛
. ⎞
⎜ ⎟
.
. K0
⎜ ⎟
⎜ K3 ⎟ ⎜ . ⎟
M ·⎜ ⎟
⎜ f4 (K3 ) ⎟ = ⎝ . ⎠ (2)
.
⎜ ⎟
K43
⎜ ⎟
.
⎝ ⎠
.
.
f40 (K39 )
162 F. Armknecht and S. Lucks



K0 K1 K2 K3 f4 (K3 ) f40 (K39 )
...
K0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0
K4 1 0 0 0 1 0 0 0 0 0 0 0 0 0
1 1 0 0 1 0 0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 0 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0 0 0 0 0 0
K8 1 0 0 0 1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 1 0 0 0 0 0 0 0 0
1 0 1 0 1 1 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0 0 0
K12 1 0 0 0 1 1 1 0 0 0 0 0 0 0
1 1 0 0 1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 1 1 0 0 0 0 0 0 0
0 0 1 1 0 0 1 0 0 0 0 0 0 0
K16 1 0 0 0 1 1 1 1 0 0 0 0 0 0
0 1 0 0 0 1 0 1 0 0 0 0 0 0
0 0 1 0 0 0 1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 0 0 0
K20 1 0 0 0 1 1 1 1 1 0 0 0 0 0
1 1 0 0 1 0 1 0 1 0 0 0 0 0
1 1 1 0 1 0 0 1 1 0 0 0 0 0
1 1 1 1 1 0 0 0 1 0 0 0 0 0
K24 1 0 0 0 1 1 1 1 1 1 0 0 0 0
0 1 0 0 0 1 0 1 0 1 0 0 0 0
1 0 1 0 1 1 0 0 1 1 0 0 0 0
0 1 0 1 0 1 0 0 0 1 0 0 0 0
K28 1 0 0 0 1 1 1 1 1 1 1 0 0 0
1 1 0 0 1 0 1 0 1 0 1 0 0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 0
0 0 1 1 0 0 1 0 0 0 1 0 0 0
K32 1 0 0 0 1 1 1 1 1 1 1 1 0 0
0 1 0 0 0 1 0 1 0 1 0 1 0 0
0 0 1 0 0 0 1 1 0 0 1 1 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0
K36 1 0 0 0 1 1 1 1 1 1 1 1 1 0
1 1 0 0 1 0 1 0 1 0 1 0 1 0
1 1 1 0 1 0 0 1 1 0 0 1 1 0
1 1 1 1 1 0 0 0 1 0 0 0 1 0
K40 1 0 0 0 1 1 1 1 1 1 1 1 1 1
0 1 0 0 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 1 0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 0 0 1 0 0 0 1

Fig. 1. The linear expressions of K0 , . . . , K43 for the 128-bit variant
Linearity of the AES Key Schedule 163

Figure 1 in section 4 displays the linear expression for K0 , . . . , K43 .
As the rank of M is 14, one can construct 30 linearly independent vectors
C , . . . , C (30) ∈ 32 such that
(1)
2

t
C (i) · M = 0, i = 1, . . . , 30.

In fact, C (1) , . . . , C (30) is a basis of the nullspace of M t . Together with (2) this
(i) (i)
implies for C (i) = (c0 , . . . , c43 )t the following equation:
⎛ ⎞
K0 43
⎜.⎟
t
·⎝ . ⎠=
(i)
0= C cj · Kj .
(i)
.
K43 j=0


This is exactly an equation as displayed in (1). A possible choice of C (1) , . . . , C (30)
is given in Figure 2 in section 4. We checked that no non-trivial linear relations
between the K0 , K1 , K2 , K3 (= K) and the key vectors K40 , K41 , K42 , K43 of the
last round exist.
43
Assume we try to ¬nd expressions i=0 ci · Ki = 0 with at least one non-zero
coe¬cient c40 , . . . , c43 and as many zero coe¬cients c39 , c38 , . . . as possible.2 One
such example is

K2 • K3 • K8 • K12 • K24 • K28 • K40 • K41 • K42 • K43 .

As one of the anonymous referees pointed out, this is optimal. It is straightfor-
ward to verify this using Figure 2.
Similarly, Figure 2 can be used to solve the open problem posed by Nicolas
43
Courtois [1] whether i=1 Ki is equal to zero. Figure 2 desribes a base for all
43
valid linear combinations of the Ki . As it turns out, i=1 Ki is not within its
linear span.


3.2 AES with 192 Bit Key Length
We denote again by K = (K0 , K1 , K2 , K3 , K4 , K5 ) ∈ {0, 1}192 the secret key with
Ki ∈ 32 . The key schedule is very similar to the 128 bit variant described in
2
3.1:

Ki := Ki ,0 ¤ i < 6
Ki := Ki’6 • fi (Ki’1 ) , 6 ¤ i ¤ 51, i mod 6 = 0
Ki := Ki’6 • Ki’1 , 6 ¤ i ¤ 51, i mod 6 = 0

Again, the exact de¬nition of fi is of no importance and is therefore omitted
here.

This means to express a linear relationship of the last round key (K40 , K41 , K42 , K43 )
2

by earlier round keys - the earlier, the better.
164 F. Armknecht and S. Lucks

K0 K3 K8 K16 K24 K32 K40
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0
0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0
0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1
0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


Fig. 2. 30 linearly independent non-trivial linear combinations of the vectors Ki for
the 128-bit variant

As in the 128-bit case, the de¬nition of the vectors K0 , . . . , K51 can be ex-
pressed by a system of linear equations:
⎛ ⎞
K0
⎜ ⎟⎛
. ⎞
⎜ ⎟
.
. K0
⎜ ⎟
⎜ K5 ⎟ ⎜ . ⎟
M ·⎜ ⎟
⎜ f6 (K5 ) ⎟ = ⎝ . ⎠ (3)
.
⎜ ⎟
K51
⎜ ⎟
.
⎝ ⎠
.
.
f48 (K47 )

Now, M is a binary matrix of size 52 — 14. An exact description of the linear
expressions of the vectors Ki can be found in Figure 3 in section 4.
The rank of M is 14 and hence the dimension of the nullspace of M t is 38.
A possible choice of the basis3 is displayed in Figure 4 in section 4. Again, no

I.e., a set of 38 linearly independent non-trivial linear relations of the Ki .
3
Linearity of the AES Key Schedule 165

K0 K5 f6 (K5 ) ... f48 (K47 )
K0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0
K4 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 0 0 0
1 1 0 0 0 0 1 0 0 0 0 0 0 0
K8 1 1 1 0 0 0 1 0 0 0 0 0 0 0
1 1 1 1 0 0 1 0 0 0 0 0 0 0
1 1 1 1 1 0 1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0 0 0 0 0 0 0
K12 1 0 0 0 0 0 1 1 0 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 0 0
1 0 1 0 0 0 1 1 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0 0 0 0 0
K16 1 0 1 0 1 0 1 1 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0 0 0 0 0 0
1 0 0 0 0 0 1 1 1 0 0 0 0 0
1 1 0 0 0 0 1 0 1 0 0 0 0 0
K20 0 1 1 0 0 0 0 1 1 0 0 0 0 0
0 0 1 1 0 0 0 0 1 0 0 0 0 0
1 0 0 1 1 0 1 1 1 0 0 0 0 0
1 1 0 0 1 1 1 0 1 0 0 0 0 0
K24 1 0 0 0 0 0 1 1 1 1 0 0 0 0
0 1 0 0 0 0 0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0 0 0
K28 1 0 0 0 1 0 1 1 1 1 0 0 0 0
0 1 0 0 0 1 0 1 0 1 0 0 0 0
1 0 0 0 0 0 1 1 1 1 1 0 0 0
1 1 0 0 0 0 1 0 1 0 1 0 0 0
K32 1 1 1 0 0 0 1 0 0 1 1 0 0 0
1 1 1 1 0 0 1 0 0 0 1 0 0 0
0 1 1 1 1 0 0 1 1 1 1 0 0 0
0 0 1 1 1 1 0 0 1 0 1 0 0 0
K36 1 0 0 0 0 0 1 1 1 1 1 1 0 0
0 1 0 0 0 0 0 1 0 1 0 1 0 0
1 0 1 0 0 0 1 1 0 0 1 1 0 0
0 1 0 1 0 0 0 1 0 0 0 1 0 0
K40 0 0 1 0 1 0 0 0 1 1 1 1 0 0
0 0 0 1 0 1 0 0 0 1 0 1 0 0
1 0 0 0 0 0 1 1 1 1 1 1 1 0
1 1 0 0 0 0 1 0 1 0 1 0 1 0
K44 0 1 1 0 0 0 0 1 1 0 0 1 1 0
0 0 1 1 0 0 0 0 1 0 0 0 1 0
0 0 0 1 1 0 0 0 0 1 1 1 1 0
0 0 0 0 1 1 0 0 0 0 1 0 1 0
K48 1 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 1 0 1 0 1 0 1
0 0 1 0 0 0 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 0 0 1 0 0 0 1



Fig. 3. The linear expressions of K0 , . . . , K51 for the 192-bit variant

non-trivial linear relations between the vectors K0 , K1 , K2 , K3 , K4 , K5 and the
key K48 , K49 , K50 , K51 of the last round exist.

3.3 AES with 256 Bit Key Length
Let K = (K0 , K1 , K2 , K3 , K4 , K5 , K6 , K7 ) ∈ {0, 1}256 with Ki ∈ {0, 1}32 be the
secret key. The description of the key schedule di¬ers from the both given before:
Ki := Ki ,i < 8
Ki := Ki’8 • fi (Ki’1 ) , i ≥ 8, i mod 8 = 0
Ki := Ki’8 • g(Ki’1 ) , i ≥ 8, i mod 8 = 4
Ki := Ki’8 • Ki’1 , i ≥ 8, i mod 8 ∈ {0, 4}
Again, fi and g are non-linear permutations whose exact de¬nitions do not
matter.
In fact the description of the key schedule can be simpli¬ed. Let fi := g for
i mod 8=4. Then the key schedule can be rewritten to
166 F. Armknecht and S. Lucks

K0 K5 K8 K16 K24 K32 K40 K48
0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1
0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0




Fig. 4. 38 linearly independent non-trivial linear combinations of the vectors Ki for
the 192-bit variant


Ki := Ki ,i < 8
Ki := Ki’8 • fi (Ki’1 ) , i ≥ 8, i mod 4 = 0
Ki := Ki’8 • Ki’1 , i ≥ 8, i mod 4 = 0
This is very similar to the key schedule used in the 128-bit case. Again,
each of the key vectors K0 , . . . , K59 can be expressed by a linear combination of
the vectors K0 , . . . , K7 , f8 (K7 ), . . . , f56 (K55 ). These can be found in Figure 5 in
section 4. The corresponding matrix-vector-product is
⎛ ⎞
K0
⎜ ⎟⎛
. ⎞
⎜ ⎟
.
. K0
⎜ ⎟
⎜ K7 ⎟ ⎜ . ⎟
M ·⎜ ⎟
⎜ f8 (K7 ) ⎟ = ⎝ . ⎠ (4)
.
⎜ ⎟
K59
⎜ ⎟
.
⎝ ⎠
.
.
f56 (K55 )

M has the size 60 — 21 and the rank 21. This implies that 39 linearly inde-
pendent non-trivial linear combinations of the vectors Ki can be found. One
possible choice is displayed in Figure 6 in section 4. As in both cases before, the
expressions of the vectors K0 , . . . , K7 , K56 , . . . , K59 are linearly independent.
Linearity of the AES Key Schedule 167

K0 K7 f8 (K7 ) f56 (K55 )
K0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
K4 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
K8 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
K12 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0
K16 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
K20 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0
K24 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
K28 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0
K32 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
K36 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0
K40 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0
1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
K44 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0
0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0
0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0
K48 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0
0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0
1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0
0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0
K52 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0
K56 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1
0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1



Fig. 5. The linear expressions of K0 , . . . , K59 for the 256-bit variant


4 Exact Descriptions
In this section, we provide an exact description of
“ the expression of Ki as a linear combination of the vectors K0 , . . . , KNk ’1
and fj (Kj’1 )
“ a basis for all non-trivial linear combinations of the vectors K0 , . . . , K4Nr +3
for all three AES variants.
We demonstrate on an example how the tables have to be read. Figure 1 shows
how K0 , . . . , K43 (in the 128-bit case) can be expressed by a linear combination of
K0 , K1 , K2 , K3 , f4 (K3 ), . . . , f40 (K39 ). Assume for example that we are interested
168 F. Armknecht and S. Lucks

K0 K7 K8 K20 K32 K44 K56
0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0
0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0
0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1




Fig. 6. 39 linearly independent non-trivial linear combinations of the vectors Ki for
the 256-bit variant

in the expression of K19 . This can be found in the 20th row of the table (not
counting the ”indexing row” at the top). This row contains only two entries
unequal zero: one in the 4th column which corresponds to K3 and one in the 8th
column which corresponds to f16 (K15 ). This means that

K19 = K3 • f16 (K15 ).

Figure 2 displays 30 linearly independent non-trivial linear relations of K0 , . . . ,
K43 . For example, the last but four row shows that

K1 • K2 • K4 • K12 • K20 • K22 = 0.



5 Conclusion
The current paper gives a complete description of all linear relationships between
singular round key values Ki ∈ {0, 1}32 . More speci¬cally, for each key schedule
a matrix M is described such that each linear relationship of the form
4Nr +3
ci · Ki = 0, ci ∈ 2
i=0

corresponds to a vector in the nullspace of M t . Such relationships can in principle
be useful for related-key attacks against the AES.
Our observations are independent from the choice of the nonlinear function f
(in fact, we could even allow independent nonlinear functions for each of the fi ).
Linearity of the AES Key Schedule 169

If the AES key schedule would evaluate one nonlinear function fi for each
round key value Ki (i ≥ 4 for 128-bit keys ect.), the corresponding matrix M
would be a square matrix of full rank, and thus no useful linear relationships
could exist.
This would, however, decrease the performance of the AES key schedule
signi¬cantly, without solving an immediate problem: We could verify that no
exclusive relationship between the round key values from the ¬rst round and the
last round exists. Thus, there is no straightforward way to exploit of our ¬ndings
to mount a related key attack against the AES.


Acknowledgment
The author would like to thank Joe Cho, Nicolas Courtois, Erik Zenner, Matthias
Krause and the unknown referees for helpful comments and discussions.


References
1. Nicolas Courtois, Private Communication.
2. J. Daemen and V. Rijmen: The Design of Rijndael, 2002, Springer.
3. Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wag-
ner, and Doug Whiting. Improved Crypanalysis of Rijndael. Fast Software Encryp-
tion 2000, Springer Lecture Notes in Computer Science.
Author Index



Armknecht, Frederik 159 Oswald, Elisabeth 148
Biryukov, Alex 11
Pramstaller, Norbert 98
Cid, Carlos 58
Raddum, H˚ avard 142
Courtois, Nicolas T. 67, 170
Rijmen, Vincent 148
Desmedt, Yvo 128 Robshaw, Matt 1
Dobbertin, Hans 1
Dominikus, Sandra 98 Sparr, R¨diger
u 128
Giraud, Christophe 27
Toli, Ilia 84
Keliher, Liam 42 Trichina, Elena 113
Knudsen, Lars 1
Korkishko, Tymur 113 Van Le, Tri 128
Lee, Kyung Hee 113
Wernsdorf, Ralph 128
Lucks, Stefan 159
Wolkerstorfer, Johannes 98
Mangard, Stefan 98
Minier, Marine 16 Zanoni, Alberto 84

<<

. 7
( 7)