<<

. 4
( 7)



>>

that matters, but their degree in the xi (their degree in the yi can be large,
provided that the total size of the equations is not too big and that there is
some method to generate these equations from the description of the cipher).
Our recommandation, for ciphers that aim at 2128 security is that there should be
no G that can be e¬ciently written (for example using up to 2128 of memory)
with degree d ¤ 16. (We do not exactly require that they do not exist, and for
some high d there may exist large relations with, for example 2100 monomials,
that are not a problem as long as there is no e¬cient algorithm to recover/write
and otherwise use them). For higher security levels, for example military-level
requirements of type 2256 , we recommend a cautious d ≥ 32. For speci¬c ciphers
these numbers may be lower but then they require a careful study if they will
not be broken by fast algebraic attacks [12, 1, 27].
It is certainly possible to obtain components that satisfy these criteria by
using su¬ciently large random S-boxes (the exact size will depend a lot of the
exact construction). Otherwise, proposing constructive methods to obtain com-
ponents that will (if possible provably) satisfy these criteria is an important open
problem. For Boolean functions, this problem can be rephrased as constructing
“good” Boolean function that in addition to classical non-linearity criteria re-
spond also to the new criterion of “algebraic immunity”. It also remains an open
problem, see [37].



5 Block Ciphers and Algebraic Relations
This paper is about a simple idea of studying algebraic relations on di¬erent
components. In this paper we will not try to summarise all the results but
the outcome of this approach on stream ciphers and multivariate public key
schemes was quite devastating, see among others [1, 2, 6, 9, 10, 11, 12, 14, 15, 16,
17, 18, 22, 23, 27, 31, 33, 37, 40, 41, 42, 43]. Several classes of schemes were shown
to be substantially less secure than expected, and sometimes badly broken. But
General Principles of Algebraic Attacks and New Design Criteria 75

the real question that many people are asking is, does this type of attacks matter
also for block ciphers ?
At present many cryptologists still believe that they don™t matter (at all).
Yet, from one point of view there is no doubt that it does ! For example with
the polynomial approximation attack of [30], Jakobsen was the ¬rst to claim
that to obtain secure ciphers “[...] it is not enough that round functions have
high Boolean complexity. [...]” . He proposes already to avoid functions that
have simple algebraic properties in the design of block ciphers (but his warning
was never taken seriously). Regarding the AES S-box, in [8] and in [13] in these
proceedings, Courtois shows that it is possible to construct, by several very
di¬erent methods, many block ciphers based on the inverse in GF (2n ) that
satisfy all the known design criteria on block ciphers, yet remain very very weak.
These schemes are insecure, because the Inverse-based Rijndael-type S-boxes,
though very complex when regarded as a function, can be characterised in several
ways by algebraic relations, cf. [13, 15, 38]. Here we are concerned with attacks
being forms of generalised linear cryptanalysis, see [26, 32, 8, 13]. Though these
attacks techniques clearly do evolve into general attacks that can be applied
potentially to any block cipher, the insecure ciphers constructed in [13] remain
very special contrived ciphers.
On the contrary, for ciphers such as DES and AES, that use relatively small S-
boxes and a lot of di¬usion that connects the outputs of one S-box to many other
S-boxes in the next rounds, (wide trail strategy of AES designers [19, 20]), we
expect that the things should be very di¬erent. In [13, 8], heuristic arguments are
given to the e¬ect that, the impact of generalised linear cryptanalysis on such
ciphers (e.g. AES) is expected to be low, as long as they resist well to linear
cryptanalysis. Therefore, it seems so far that the algebraic relations may do not
really matter so much for AES and similar ciphers.


6 Global Algebraic Attacks on Block Ciphers
We see that, ¬nding attacks on ciphers such as AES, remains an ambitious
task, even given the existence of algebraic relations on the S-boxes. Unfortu-
nately, there is yet another attack strategy, published in 2002 by Courtois and
Pieprzyk, that is designed to render the “wide trail strategy” useless. It can be
called a direct/global algebraic attack strategy, or exact algebraic approach.
At the origin, it also uses the existence of algebraic relations for the individual
components of the cipher. We do not however try to connect the speci¬c mono-
mials that appear in one equation to another equation, which may be very hard,
but just write the equations for the whole cipher, to obtain a global system of
equations that uniquely characterizes the key to be found. Then we see if it is
possible (in theory and/or in practice) to solve such a system of equations.
This type of approach, if proven to work e¬ciently in practice, is not less
than a major revolution in the ¬eld of block cipher cryptanalysis. This is be-
cause, except few very weak ciphers, all the general attacks known up till now
for block ciphers are attacks that combine “approximations”, that are some
76 N.T. Courtois

properties (linear, di¬erential, higher-order di¬erential, polynomial approxima-
tion etc..) true with some probability that except for some very weak ciphers is
di¬erent from 1. This “combine approximations” paradigm has three important
consequences. First of all, the complexity of the attacks must grow exponentially
with the number of rounds. Secondly, the number of plaintexts needed in an at-
tacks also grows in the same way (and may be the main limitation in practice).
Finally, ciphers with good di¬usion (wide trail strategy) force the attacker to
use several approximations in parallel in the same round, and the e¬ciency of
the attacks further decreases.
The “exact algebraic” approach that exploits equations that are true with
probability 1 that exist locally (for example for each S-box) has the potential
to remove simultaneously the three aforementioned obstacles. The complexity is
not longer condemned to grow exponentially with the number of rounds. The
number of required plaintexts may be quite small (e.g. 1). And the wide trail
strategy should have no impact whatsoever on the complexity of the attack.


6.1 How Secure Are Today™s Block Ciphers ?
Some people dismiss the idea of an algebraic attack on AES, as being too simple
and too naive to be true. Our impression is that, it is rather the current thinking
about the security of block ciphers that is very naive.
We get the impression that, if we mix su¬ciently many rounds of any con-
struction, it will be secure. In practice however, the ciphers are meant to be
rather fast, have a limited number of rounds, but yet the security claims made
on them are extremely ambitious. During the AES contest many authors pro-
posed ciphers claimed to be indistinguishable from a random permutation within
less than 2256 computations. This is a huge number. With the Moore™s law, such
keys should remain secure against brute force until around 2200. This gives us
200 years to invent new mathematics, new algorithms, and new attacks that will
break the cipher faster than the exhaustive search before it is outdated. Who
can make security predictions for such a long period of time, knowing that so
many security claims are disproved every year ? Moreover, 2256 is close to the
number of atoms in the universe, therefore it also possible that the computers
will never actually have such a computing power. This means that we are left
with in¬nite time to ¬nd better attacks. We believe therefore that betting that a
cipher cannot be distinguished from a random cipher faster than by brute force,
may be an in¬nitely risky bet for 256-bit ciphers. Our guess is rather that all the
block ciphers with 256-bit keys that were submitted to AES, will some day be
broken faster than by exhaustive search, simply because our current knowledge
about the real security of block ciphers is yet very low.


6.2 Who Invented Algebraic Attacks on Block Ciphers ?
According to a visionary recommandation of Shannon from his 1949 paper [44],
breaking a good cipher should require: “as much work as solving a system of
simultaneous equations in a large number of unknowns of a complex type”. There
General Principles of Algebraic Attacks and New Design Criteria 77

are many ways of interpreting this statement. For example we may think about
multivariate quadratic equations with Boolean variables, the large number of
unknowns may mean a large number of monomials, unknowns of a complex type
may mean monomials of high degree (or that combine variables that come from
remote location inside a cipher).
From another point of view, it is a trivial folklore attack that anyone can
think of. Indeed, it is easy to see that, for any practical cryptographic system
that relies on computational (not information-theoretic) security, we can write
a system of Boolean equations such that solving it allows to ¬nd the key. Then,
solving a general system of Boolean equations is an NP-hard problem, and solv-
ing non-linear systems of large size is expected to be hopeless. However, it turns
out that, what makes such problems hard is not so much the number of vari-
ables or monomials, but the balance between the number of equations and the
number of monomials that appear in these equations. From this, we expect that,
systems that are overde¬ned, sparse, or both, should be much easier to solve
than general systems of similar size. As far as we know, before 1998-2000, the
scienti¬c community were not aware of this fact, and easily believed that large
systems of equations are necessarily hard to solve. When the XL attack was ¬rst
introduced by Courtois, Klimov, Patarin and Shamir [43], as a development of
earlier ideas of Shamir and Kipnis [42], things started to change. In particular,
specialists of elimination methods such as Gr¨bner bases that have been stud-
o
ied for many years now, see for example [45, 22, 23], started to realise the full
potential of these and other algebraic techniques to solve problems that arise
in cryptography. It turns out that the cryptographic instances of multivariate
systems of equations have several interesting properties that may and do help to
solve them e¬ciently. Among these properties we will quote the fact that they
are over very small ¬nite ¬elds, they usually have a unique solution, they do not
have solutions in extensions ¬elds or at in¬nity, and again, they are frequently
over-determined, and sparse (with several possible notions of sparsity).
At present the area of algebraic attacks is full of open problems that should
be solved with time. A lot remains to be done in discovering cryptanalytic appli-
cations of already existing algebraic methods of solving systems of polynomial
equations. Similarly, speci¬c systems of equations that arise in cryptography
should allow (and already do) to better understand why certain very general al-
gebraic algorithms (such as Buchberger or F5 algorithms) for solving equations
work well in some cases, and do fail in some other cases. Finally, new meth-
ods of solving algebraic equations should and will be invented, motivated by
cryptographic attacks.

6.3 The Structure of Algebraic Attacks
Global algebraic attacks on block cipher following Courtois and Pieprzyk (pre-
viously imagined also by Shannon, Patarin and probably few others) contains
the following three stages, that can and should be studied separately.
1. Write an appropriate initial system. Write a system of equations that,
given one or several known plaintexts, uniquely characterizes the key. This
78 N.T. Courtois

system should be as over-determined (also called overde¬ned) and as sparse
as possible. This can be measured by the initial ratio Rini /Tini between the
number of equations Rini in the system and the total number of monomials
Tini that appear in it. It can be for example 1/4 or 1/3. It is not clear what
is the optimal setting for algebraic attacks: we may try simply to achieve
a lowest Rini /Tini possible, however for some systems with a higher initial
ratio, but a lower global size, or some speci¬c additional properties, the
overall complexity of an algebraic attack may be lower.
2. Expand it. The second step is an expansion step. The goal is, starting from
the original Rini equations with Tini monomials, to produce (for example by
multiplying the equations by some well chosen polynomials) another (much
bigger) set of R equations with T monomials. The goal is to have the new
ratio R/T close (or bigger than) 1. If R > T it means that the set of equations
is redundant, and we should think of a better method of generating them
(to avoid redundancies) and also of a better method of counting how many
equations we have, that are not trivial linear combinations of other equations,
and therefore serve no purpose.
Here the main criterion of “success” is not so much the ¬nal ratio R/T
(that simply must be somewhat close to 1, e.g. 0.9) but the size T . However
it remains possible that some attacks with a worse (larger) T and better
(bigger) R/T do in fact work better (cf. next step).
3. Final in place elimination. The ¬nal step should be an “in place” elimi-
nation method that given an “almost saturated system” with R/T close to 1,
¬nds a solution. On proposed method to achieve this is by generating a com-
pletely saturated system (the T™ method proposed by Courtois in [15, 14].
It can also be achieved by computing a Gr¨bner basis of the expanded sys-
o
tem, and probably by other means. The (heuristic) requirement is that the
memory required in this third step should not exceed T , otherwise maybe
we need to improve rather the second (expansion) step.


6.4 Applicability of Algebraic Attacks
There are reasons why, overde¬ned and/or sparse systems are bound to appear
frequently in cryptography. In most settings, there is no cryptographic solutions
with unconditional security, and we have to rely on computational security. A
relatively short (128 bits or less) key will be usually used many times, to produce
much more information: many known plaintexts, many signatures, etc. In public
key cryptography, a proof of security would allow to be certain that each utiliza-
tion of the cryptographic scheme, does not leak useful information. Secret key
schemes do not have such proofs of security, and the more we use it, the more the
problem become overde¬ned (if we do not introduce additional variables). It is
also in secret key cryptography, that the problems may become really massively
overde¬ned, if we think about the amounts of data that can be encrypted with a
single key, on a satellite link. Another problem is a consequence of the fact that
many ciphers are designed to be implemented in hardware with a very low gate
General Principles of Algebraic Attacks and New Design Criteria 79

count. This allows to design an algebraic attack with relatively small umber of
variables and a very small number of monomials (very sparse).
These are theoretical considerations. The present experience of algebraic at-
tacks is that, their complexity should grow “nearly polynomially” in the number
of rounds and in the block size, with however a really huge constant called “ that
does depend only on the S-box. (This for all known versions of the XSL attack,
and for both resulting de¬nitions of “ , see [15]). For a random S-box (and also
for many other S-boxes that have no special properties such as algebraic rela-
tions) this constant “ can be shown to be double-exponential in s, the size of the
S-box in bits. In [15], it appears that already 4-bit S-boxes, should be su¬cient
for 2128 security and probably beyond. For the Rijndael S-boxes, it is possible
to see that “ grows only simply exponentially in s. Then it seems that even
for s = 8 algebraic attacks faster than 2128 may exist, see [15, 38], but we are
clearly on the frontier of applicability of algebraic attacks. Thus, it seems that
in fact algebraic attacks are only possible for some very special ciphers. Apart
from Serpent and Rijndael, we are not aware of a single other block cipher for
which even a current (probably too optimistic) estimations of the complexity of
algebraic attacks would give less than the exhaustive search.

6.5 Is AES Broken ?
It is important to say: we really do not know. It is possible that, one of the XSL
attacks works exactly as predicted, or a simple combination of already known
attacks already breaks AES. Our favorite candidate in this respect would be to
combine the Murphy-Robshaw idea of using equations over GF (256) from [38],
with one of the XSL expansion attacks from [15], and replace the ¬nal T method
by a (presumably better) advanced Gr¨bner bases algorithm such as Faug`re™s
o e
F5 [23]. This might simply break AES. But it is also possible that it fails quite
miserably for some fundamental reason that is not yet understood. Then, a slight
modi¬cation of the attack could still remove the theoretical obstacle and give an
attack that might again work in practice. Studying algebraic attacks on block
ciphers in all due details is outside the scope of this paper, and remains largely
to be done. Both theoretical and experimental results will probably be needed
to get the full picture.

6.6 How to Avoid Algebraic Attacks on Block Ciphers
At any rate, we advocate to take the algebraic attacks on block ciphers very
seriously and to design block ciphers that do avoid such attacks. The resulting
security criterion is, still more or less the same. The S-boxes of a block cipher
should avoid the existence of “simple” algebraic relations of type:

G (x0 , . . . , xs’1 ; y0 , . . . , ys’1 ) = 0 (—)

The exact de¬nition of “simple” that would prevent all algebraic attacks
on block ciphers is not obvious to give. We need to avoid equations that, for
some representation, and some system of equations, give a low value of “ . For
80 N.T. Courtois

example following [15], we should avoid systems that are too overde¬ned or/and
too sparse.
This should not be very hard to achieve. We believe that using random S-
boxes on 8 bits should be about su¬cient to achieve 128-bit security (though not
for sure). We recommend in fact to construct bigger S-boxes that have no alge-
braic relations starting from random bijective 8-bit S-boxes. For higher security
requirements such as military applications, we advocate to make mandatory a
requirement that the cipher should use at several places inside the encryption,
a random S-box of at least 16 bits.


7 The Future of AES
In our opinion, AES should still be recommended as the best choice of encryption
algorithm for applications that do not require long-term security. We believe
however that NIST should set an expiration date for AES, that could be 2010.
It could be extended it later, according to the developments in cryptanalysis, but
we believe that in 2010 it will be much wiser to replace AES by a better cipher,
being not vulnerable to algebraic attacks, generalised linear cryptanalysis with
multiple approximations, and other attacks that will probably be invented by
2010. The replacement should be done even if it turns out that known algebraic
attacks on block ciphers do not work, and all other attacks that exploit algebraic
relations (e.g. generalised linear cryptanalysis) do not break AES either.
In addition, we believe that a cipher such as AES can only be really credible
as the world™s standard all-purpose cryptographic high security lock, if there is a
series of AES challenges. They could range from 100 to 1 million dollars, and be
o¬ered for solving various important open problems that in a di¬erent manner
do compromise the security of AES, up to a total break that is done or doable in
practice. This would allow to monitor the progress in the security of AES and to
ascertain a serious status of this scheme compared to so many other schemes that
are broken every year. For people that do not have expertise in cryptography,
and cannot tell between real or fake security experts, such challenges, are the
only way of knowing that the AES is indeed not yet broken, and some people take
its security seriously enough to o¬er 1 million dollar to whoever demonstrate it
can be broken in practice.



8 Conclusion
Algebraic attacks exploit the existence of multivariate relations on the appropri-
ate cryptographic component. They do allow to break many multivariate public
key schemes and stream ciphers. For block ciphers, their e¬ectiveness is far from
being clear. Yet, it is very sensible to avoid the existence of such algebraic re-
lations for non-linear components of block ciphers. This not only because of
algebraic attacks, but also because of generalised linear attacks: examples of
contrived ciphers are known that are not secure with relation to these.
General Principles of Algebraic Attacks and New Design Criteria 81

Thus, we propose (if possible) to simply avoid multivariate and algebraic
relations in all types of cipher components. This extends the current paradigm
of avoiding “bad” Boolean functions, or/and “bad” vectorial functions (S-boxes).
One method to achieve this would be to construct appropriate cryptographic
components with guaranteed “algebraic immunity”. A much simpler method, is
to use su¬ciently large random S-boxes. This should prevent all known attacks
on block ciphers: linear/di¬erential cryptanalysis with generalisations, all kinds
of generalised linear attacks as described in [13], and also any kind of exact
algebraic attacks such as XSL [15].



References
1. Frederik Armknecht: Improving Fast Algebraic Attacks, to appear in FSE 2004,
LNCS, Springer.
2. Frederik Armknecht, Matthias Krause: Algebraic Atacks on Combiners with Mem-
ory, Crypto 2003, LNCS 2729, pp. 162-176, Springer.
3. Kazuaro Aoki and Serge Vaudenay: On the Use of GF-Inversion as a Cryptographic
Primitive. SAC 2003, LNCS 3006, pp. 234-247, Springer 2004.
4. Ross Anderson, Eli Biham and Lars Knudsen: Serpent: A Proposal for the Ad-
vanced Encryption Standard.
5. Anne Canteaut, Marion Videau: Degree of composition of highly nonlinear func-
tions and applications to higher order di¬erential cryptanalysis, Eurocrypt 2002,
LNCS 2332, Springer.
6. Joo Yeon Cho and Josef Pieprzyk; Algebraic Attacks on SOBER-t32 and SOBER-
128, will appear in FSE 2004, LNCS, Springer.
7. Don Coppersmith, Shmuel Winograd: Matrix multiplication via arithmetic pro-
gressions, J. Symbolic Computation (1990), 9, pp. 251-280.
8. Nicolas Courtois: Feistel Schemes and Bi-Linear Cryptanalysis, To be presented at
Crypto 2004, Santa Barbara, California, 15-19 August 2004.
9. Nicolas Courtois: The security of Hidden Field Equations (HFE); Cryptographers™
Track Rsa Conference 2001, LNCS 2020, Springer, pp. 266-281.
10. Nicolas Courtois: Algebraic Attacks on Combiners with Memory and Several Out-
puts, Available on http://eprint.iacr.org/2003/125/. 23 June 2003.
11. Nicolas Courtois: La s´curit´ des primitives cryptographiques bas´es sur
e e e
les probl`mes alg´briques multivariables MQ, IP, MinRank, et HFE,
e e
PhD thesis, Paris 6 University, September 2001, in French. Available at
http://www.minrank.org/phd.pdf.
12. Nicolas Courtois: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback,
Crypto 2003, LNCS 2729, pp: 177-194, Springer.
13. Nicolas Courtois: The Inverse S-box, Non-linear Polynomial Relations and Crypt-
analysis of Block Ciphers, in AES 4 Conference, Bonn May 10-12 2004, LNCS,
Springer.
14. Nicolas Courtois and Jacques Patarin, About the XL Algorithm over GF (2), Cryp-
tographers™ Track RSA 2003, LNCS 2612, pages 141-157, Springer 2003.
15. Nicolas Courtois and Josef Pieprzyk, Cryptanalysis of Block Ciphers with
Overde¬ned Systems of Equations, Asiacrypt 2002, LNCS 2501, pp.267-287,
Springer, a preprint with a di¬erent version of the attack is available at
http://eprint.iacr.org/2002/044/.
82 N.T. Courtois

16. Nicolas Courtois: Higher Order Correlation Attacks, XL algorithm and Cryptanal-
ysis of Toyocrypt, ICISC 2002, LNCS 2587, pp. 182-199, Springer.
17. Nicolas Courtois and Willi Meier: Algebraic Attacks on Stream Ciphers with Linear
Feedback, Eurocrypt 2003, Warsaw, Poland, LNCS 2656, pp. 345-359, Springer. An
extended version is available at http://www.minrank.org/toyolili.pdf
18. Nicolas Courtois, Magnus Daum and Patrick Felke: On the Security of HFE, HFEv-
and Quartz, PKC 2003, LNCS 2567, Springer, pp. 337-350. The extended version
can be found at http://eprint.iacr.org/2002/138/.
19. Joan Daemen, Vincent Rijmen: AES proposal: Rijndael,
http://csrc.nist.gov/encryption/aes/rijndael/Rijndael.pdf
20. Joan Daemen, Vincent Rijmen: The Design of Rijndael. AES - The Advanced
Encryption Standard, Springer-Verlag, Berlin 2002. ISBN 3-540-42580-2.
21. Joan Daemen, Vincent Rijmen, Bart Preneel, Anton Bosselaers, Erik De Win: The
Cipher SHARK, FSE 1996, Springer.
22. Jean-Charles Faug`re: A new e¬cient algorithm for computing Gr¨bner bases
e o
(F4 ), Journal of Pure and Applied Algebra 139 (1999) pp. 61-88. See
www.elsevier.com/locate/jpaa
23. Jean-Charles Faug`re: A new e¬cient algorithm for computing Gr¨bner bases with-
e o
out reduction to zero (F5), Workshop on Applications of Commutative Algebra,
Catania, Italy, 3-6 April 2002, ACM Press.
24. Niels Ferguson, Richard Schroeppel and Doug Whiting: A simple algebraic repre-
sentation of Rijndael, SAC 2001, page 103, LNCS 2259, Springer.
25. Jovan Dj. Golic: On the Security of Nonlinear Filter Generators, FSE™96, LNCS
1039, Springer, pp. 173-188.
26. C. Harpes, G. Kramer, and J. Massey: A Generalization of Linear Cryptanaly-
sis and the Applicability of Matsui™s Piling-up Lemma, Eurocrypt™95, LNCS 921,
Springer, pp. 24-38. http://www.isi.ee.ethz.ch/ harpes/GLClong.ps
27. Philip Hawkes, Gregory Rose: Rewriting Variables: the Complexity of Fast
Algebraic Attacks on Stream Ciphers, by Philip Hawkes and Gregory G.
Rose. In crypto 2004, to appear in LNCS, Springer, 2004. Available from
eprint.iacr.org/2004/081/.
28. Thomas Jakobsen and Lars Knudsen: Attacks on Block Ciphers of Low Algebraic
Degree, Journal of Cryptology 14(3): 197-210 (2001).
29. Thomas Jakobsen: Higher-Order Cryptanalysis of Block Ciphers. Ph.D. thesis,
Dept. of Math., Technical University of Denmark, 1999.
30. Thomas Jakobsen: Cryptanalysis of Block Ciphers with Probabilistic Non-Linear
Relations of Low Degree, Crypto 98, LNCS 1462, Springer, pp. 212-222, 1998.
31. Antoine Joux, Jean-Charles Faug`re: Algebraic Cryptanalysis of Hidden Field
e
Equation (HFE) Cryptosystems Using Gr¨bner Bases, Crypto 2003, LNCS 2729,
o
pp. 44-60, Springer, 2003.
32. Lars R. Knudsen, Matthew J. B. Robshaw: Non-Linear Characteristics in Linear
Cryptoanalysis. Eurocrypt™96, LNCS 1070, Springer, pp. 224-236, 1996.
33. Dong Hoon Lee, Jaeheon Kim, Jin Hong, Jae Woo Han and Dukjae Moon: Alge-
braic Attacks on Summation Generators, on eprint.iacr.org/2003/229/ and to
appear in FSE 2004, LNCS, Springer.
34. R. Lidl, H. Niederreiter: Finite Fields, Encyclopedia of Mathematics and its appli-
cations, Volume 20, Cambridge University Press.
35. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied
Cryptography; CRC Press, 1996.
General Principles of Algebraic Attacks and New Design Criteria 83

36. Tsutomu Matsumoto, Hideki Imai: Public Quadratic Polynomial-tuples for e¬cient
signature-veri¬cation and message-encryption, Eurocrypt™88, Springer 1998, pp.
419-453.
37. Will Meier, Enes Pasalic and Claude Carlet: Algebraic Attacks and Decomposition
of Boolean Functions, Eurocrypt 2004, pp. 474-491, LNCS 3027, Springer, 2004.
38. S. Murphy, M. Robshaw: Essential Algebraic Structure within the AES, Crypto
2002, Springer.
39. Kaisa Nyberg: Di¬erentially Uniform Mappings for Cryptography, Eurocrypt™93,
LNCS 765, Springer, pp. 55-64.
40. Jacques Patarin: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of
Eurocrypt™88; Crypto™95, Springer, LNCS 963, pp. 248-261, 1995.
41. Jacques Patarin: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials
(IP): two new families of Asymm. Algorithms, Eurocrypt™96, Springer, pp. 33-48.
42. Adi Shamir, Aviad Kipnis: Cryptanalysis of the HFE Public Key Cryptosystem;
In Advances in Cryptology, Proceedings of Crypto™99, Springer, LNCS. The paper
can be found at http://www.hfe.info.
43. Adi Shamir, Jacques Patarin, Nicolas Courtois, Alexander Klimov, E¬cient Al-
gorithms for solving Overde¬ned Systems of Multivariate Polynomial Equations,
Eurocrypt™2000, LNCS 1807, Springer, pp. 392-407.
44. Claude Elwood Shannon: Communication theory of secrecy systems, Bell System
Technical Journal 28 (1949), see in patricular page 704.
45. Wang, D. Elimination Methods, Texts and Monographs in Symbolic Computation,
Springer, 2001. XIII, ISBN 3-211-83241-6.
An Algebraic Interpretation of AES’128

Ilia Toli and Alberto Zanoni


Dipartimento di Matematica Leonida Tonelli,
Universit` di Pisa,
a
Via Buonarroti 2, 56127 Pisa, Italy
{toli, zanoni}@posso.dm.unipi.it



Abstract. We analyze an algebraic representation of AES’128 as an
embedding in BES, due to Murphy and Robshaw. We present two sys-
tems of equations S and K concerning encryption and key generation
processes. After some simple but rather cumbersome substitutions, we
should obtain two new systems C1 and C2 . C1 has 16 very dense equa-
tions of degree up to 255 in each of its 16 variables. With a single pair
(p, c), with p a cleartext and c its encryption, its roots give all possible
keys that should encrypt p to c. C2 may be de¬ned using 11 or more pairs
(p, c), and has 16 times as many equations in 176 variables. K and most
of S is invariant for all key choices.



1 Introduction
The well famous symmetric-key 64-bit cryptosystem DES [10] was broken in
1998 by means of a special purpose computer called DES Cracker. This computer
contained 1536 chips, could search 88 billion keys/sec, and costed 250.000 $. It
won RSA Laboratories DES Challenge II-2 by successfully ¬nding a DES key
in 56 hours in July 1998. In January 1999, RSA Laboratories DES Challenge
III was solved by the DES Cracker working in conjunction with a worldwide
network of 100.000 computers known as distributed.net. This cooperative
e¬ort found a DES key in 1335 minutes, testing over 245 billion keys/sec.
Other than exhaustive key search, the two most important attacks to DES are
di¬erential cryptanalysis and linear cryptanalysis. An actual implementation of
the latter was carried out in 1994 by its inventor, Matsui. It is a known-plaintext
attack using 243 plaintext-ciphertext pairs, all of which are encrypted using the
same, unknown, key. It took 40 days to generate them, and it took 10 days to
actually ¬nd the key.
This cryptanalysis did not have any practical impact on the security of DES,
however, due to the extremely huge number of plaintext-ciphertext pairs that
are required to mount the attack. It is unlikely in practice that an adversary will
be able to accumulate such a huge number of plaintext-ciphertext pairs that are
all encrypted using the same key.
On January 2, 1997, NIST began the process of choosing a replacement for
DES. The replacement should be called AES (Advanced Encryption Standard).

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 84“97, 2005.
c Springer-Verlag Berlin Heidelberg 2005
An Algebraic Interpretation of AES’128 85

After a 3-years-long evaluation, Rijndael [3, 4] was chosen to be the AES
among 15 eligible candidates upon 21 submissions. It was published as FIPS 197
[5] on November 26, 2001.
Rijndael is a block cipher, that encrypts blocks of 128, 192, and 256 bits
using symmetric keys of 128, 192, and 256 bits. It was designed with a particular
attention to bit-level attacks, such as linear and di¬erential cryptanalysis. What
makes it particularly resistant to such attacks is the tension between operations
in the two ¬elds F = GF (28 ) and GF (2). Since its proposal, several new bit-
level attacks, such as impossible di¬erential and truncated di¬erential have been
proposed. Most of them break with some e¬ciency reduced versions of Rijndael.
For a general version of it, they are not much better than exhaustive key search.
In practice they are mostly academic arguments rather than real world threats
to the security of AES. The interested reader can ¬nd an account and some
references about these cryptological tools in [9].
Actually, only the blocklength 128 of Rijndael was approved to become AES.
Another, new, cryptological tool is the algebraic representation of the cipher
[8], [6], [2]. In this case, an eavesdropper tries to write the whole set of operations
and parameters of the cipher by means of a system of polynomial equations,
which he/she next tries to solve. In general, the related systems are enormous.
Solving them by means of general purpose techniques, such as Gr¨bner bases [1]
o
is considered the wrong way to face the problem. However, they sometimes bear
a lot of intrinsic structure, that probably facilitates the task. A little research
is done in the topic. Specially AES seems to have been designed regardless to
algebraic cryptanalysis tools.
In this paper we focus on the BES algebraic approach, due to Murphy and
Robshaw [8].

An Overview on AES-128
2
Here is a sketch of AES encryption algorithm.
“ Input a plaintext x. Initialize State = x, and perform an operation
AddRoundKey, in w= hich we xor the RoundKey with the State.
“ For each round but the last one, perform a substitution operation called
SubBytes on State, using an S-box, perform a permutation ShiftRows
on State, perform an operation MixColumns on State, and perform
AddRoundKey.
“ Perform SubBytes, ShiftRows, and AddRoundKey.
“ De¬ne the ciphertext y to be State.
All of AES operations are byte-oriented. The cleartext, ciphertext, and each
output of mid-steps of encryption and decryption algorithms are thought of as
4 — 4 matrices of bytes. The arithmetic operations performed on each byte are
those of the ¬nite ¬eld F = GF (28 ). The elements are thought of as univari-
ate polynomials with coe¬cients in GF (2), mod (m(t)), the so-called Rijndael
polynomial:
m(t) = t8 + t4 + t3 + t + 1 = 11b (1)
86 I. Toli and A. Zanoni

s00 s01 s02 s03 s00 s01 s02 s03
s10 s11 s12 s13 s11 s12 s13 s10
=’
s20 s21 s22 s23 s22 s23 s20 s21
s30 s31 s32 s33 s33 s30 s31 s32

Fig. 1. The ShiftRows operation on AES

They are represented as couples of integers in hexadecimal representation. If
interpreted as eight-bit binary strings, the numbers give the exponents of the
terms in the polynomial representation.
The SubBytes operation substitutes each of the given bytes x with S(x):

S(x) = 63+8fx127 +b5x191 +01x223 +f4x239 +25x247 +f9x251 +09x253 +05x254
(2)
Actually, S(x) is a permutation polynomial.
The ShiftRows operation permutes bytes in each row, as shown in Figure 1.
The MixColumns operation performs a permutation of bytes in each column
by means of a certain matrix from the linear group GL(F, 16), explicitely given
later in section 3. In practice, the columns are considered as polynomials from
F[x], and multiplied mod(x4 + 1) with the polynomial a(x):

a(x) = 03x3 + 01x2 + 01x + 02. (3)


2.1 The Key Schedule
The key used in every cipher round is successively obtained by the key of the
precedent one. The whole procedure is sketched below.

“ Input a key h0 . Initialize H0 = h0 .
“ For each round r = 1, . . . , 10, perform a permutation called RotWord on
the sub-vector formed by the last four elements (word) of Hr’1 , as shown
in Figure 2.
“ Perform the SubWord (S-box on each byte) operation on the obtained
word, and add the constant vector Rconr = (tr’1 , 0, 0, 0). De¬ne the other
elements by means of bitwise xor operations in terms of the obtained result
and other words from Hr’1 .
“ De¬ne the complete set of keys h to be {Hr | r = 0, . . . , 10}.

We consider each vector as divided into four words, indicated with a second
index ranging from 0 to 3. For y ∈ F4 we put

•r (y) = SubWord(RotWord(y)) + Rconr ,
A


a0 a1 a2 a3 a1 a2 a3 a0
=’

Fig. 2. The RotWord operation on AES
An Algebraic Interpretation of AES’128 87

while the xor operation corresponds to the sum in F. The rth round for the AES
key generation scheme is the following one:
§
= •r (Hr’1,3 )
⎪ Hr0

⎨ A
Hr1 = Hr0 + Hr’1,1
KA = =’ Hr = (Hr0 , Hr1 , Hr2 , Hr3 ) (4)
⎪ Hr2 = Hr1 + Hr’1,2

©
Hr3 = Hr2 + Hr’1,3




3 An Overview on the Big Encryption System (BES)
Our starting point is the BES cipher, in which the AES is embedded by a
“natural” mapping. The BES operations involve no computations in GF(2), only
in F. This allows us to describe AES by means of polynomial equation systems.
Solving the systems means to ¬nd the key or an alias of its, and therefore to
break the code.
The state spaces of AES and BES are respectively A = F16 and B = F128 .
The basic tool for the embedding is the conjugation operation φ, that considers
for each value in F the vector of its successive square powers.

0 1 7
F a ’’ φ(a) = a = (a2 , a2 , ..., a2 ) ∈ F8
˜ (5)
Fn a ’’ φ(a) = a = φ(a0 ), ..., φ(a7 ) ∈ F8n
˜ (6)

Thanks to the easy-to-verify properties (with 0’1 = 0) :

φ(a’1 ) = φ(a)’1 ,
φ(a + a ) = φ(a) + φ(a ) and (7)

we can put a one-to-one correspondence between AES and BES operations:

BA = φ(A) ‚ B (8)

as the subset of B corresponding to A.
Let p, c ∈ B be the plaintext and ciphertext, respectively; wi , xi ∈ B (0 ¤
i ¤ 9) the mapped state vectors before and after the inversion phases that occur
in the codifying process, and hi ∈ B the used keys.
All the phases of Rijndael algorithm may be translated in B using just lin-
ear algebra in F, apart from inversion, which is simply done component-wise, as
follows.

The matrix LA : F GF (2)8 ’ GF (2)8 F for the a¬ne transformation
for one byte in the S-box phase can be represented by the polynomial function
f : F ’ F:
88 I. Toli and A. Zanoni

7
k
f (a) = »k a2 (9)
k=0




»0 = t2 + 1 »4 = t7 + t 6 + t 5 + t 4 + t 2
»1 = t3 + 1 »5 =1
(10)
»2 = t7 + t 6 + t 5 + t 4 + t 3 + 1 »6 = t7 + t 5 + t 4 + t 2 + 1
»3 = t5 + t 2 + 1 »7 = t7 + t 3 + t 2 + t + 1

0 7
Working in B, LB (a) = φ(LA (a)) = (f (a)2 , . . . , f (a)2 ) and we must compute
the successive squares of f : this is accomplished by ¬nite induction, with basic
step:

2
7 7 7
k k k+1
»2 a2 ·2
»k a »2 a2
2 2
(f (a)) = = = (11)
k k
k=0 k=0 k=0


8
Simply speaking, it is su¬cient to iteratively square and circularly shift (a2 =
0
a = a2 ) the coe¬cients. The resulting matrix, which we still indicate with LB ,
is


i
LB = [lij ]i,j=0,...7 lij = »2
with (12)
(8’i+j) mod 8



The global transformation LinB : F128 ’ F128 is the block diagonal matrix with
16 blocks equal to LB .
The AES constant cA = 63 = t6 + t5 + t + 1 ∈ F used in the S-box maps
into:


φ(cA ) = (63, C2, 35, 66, D3, 2F, 39, 36)
= (t6 + t5 + t + 1, t7 + t6 + t, t5 + t4 + t2 + 1, t6 + t5 + t2 + t,
t7 + t6 + t4 + t + 1, t5 + t3 + t2 + t + 1, t5 + t4 + t3 + 1,
t5 + t4 + t2 + t) (13)


The corresponding BES vector cB is simply obtained by the juxtaposition of 16
consecutive copies of φ(c), such that:


cB = φ(cA , . . . , cA ) = (φ(cA ), . . . , φ(cA )) [cB ]i = [φ(cA )]i mod 8 (14)
16 16
An Algebraic Interpretation of AES’128 89

The AES ShiftRows transformation is given by the matrix RA : F16 ’ F16 :
⎛ ⎞
1000000000000000
⎜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 0 0 0 0 0 0 0 0 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 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 1 0 0 0 0 0 0 0 0 0 0 0 0⎟
RA = ⎜ ⎟ (15)
⎜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 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 0⎟
⎜ ⎟
⎜0 0 0 0 0 0 0 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 1 0 0 0 0 0 0 0 0 0⎠
0000000000010000
The corresponding BES matrix is obtained simply “expanding” each one in RA
with an identity matrix of order 8, I8 , and each 0 with a zero (8 — 8) matrix.
The result is RB : F128 ’ F128 .
The AES MixColumns may be represented using the CA : F4 ’ F4 matrix:
⎛ ⎞
t t+1 1 1
⎜1 t t+1 1 ⎟
CA = ⎜ ⎟ (16)
⎝1 t t + 1⎠
1
t+1 1 t
1

The AES transformation is given by the MixA : F16 ’ F16 block diagonal matrix
having as blocks four copies of CA . In order to obtain the corresponding matrix
(k)
we ¬rst need to compute the following matrices CB , for k = 0, . . . , 7:
⎛ ⎞
k k
t2 (t + 1)2 1 1
⎜ ⎟
k k
t2
⎜ ⎟
(t + 1)2
1 1
(k)
CB = ⎜ k⎟ (17)
k
⎝ (t + 1)2 ⎠
t2
1 1
k k
t2
(t + 1)2 1 1

with:
0 3 6
t2 = t t 2 = t4 + t 3 + t + 1 t2 = t6 + t3 + t2 + 1
1 4 7
t2 = t2 t2 = t6 + t 4 + t 3 + t 2 + t t2 = t7 + t6 + t5 + t4 + t3 + t
2 5
t2 = t4 t2 = t7 + t 6 + t 5 + t 2
(18)
2k 2k
from which (t + 1) = t + 1 may be very easily computed.
Using an appropriate basis (see below), the resulting matrix MB : F128 ’
F128 may be written as a block diagonal one, having as blocks for all possible k
90 I. Toli and A. Zanoni

(k)
four consecutive copies of CB . The change of basis is necessary because of the
di¬erent positioning of value powers in φ™s image with respect to what we need.
Indeed, if a ∈ F16 , then:
7 7 7
φ(a) = (a0 , ..., a2 , a1 , . . . , a2 , . . . , a15 , . . . , a2 ) (19)
0 1 15

while in order to use the block diagonal representation, we would need the vector
rearranged in this way:
7 7
a = (a0 , ..., a15 , a2 , . . . , a2 , . . . , a2 , . . . , a2 ) (20)
0 15 0 15

The corresponding permutation matrix PermB : F128 ’ F128 permits to do this
transformation. To write it down easily, suppose to divide it into (16 — 8) sub-
matrices, called Phk , h = 0, . . . , 7, k = 0, . . . , 15. Each sub-matrix element (with
i = 0, . . . , 15, j = 0, . . . , 7) is thus de¬ned:
1 if i = k and j = h
[Phk ]ij = (21)
0 else
Its inverse matrix Perm(’1) is equally easy to describe: viewing it as composed of
(’1)
(8 — 16) sub-matrices Phk , with h = 0, . . . , 15, k = 0, . . . , 7, the generic element
(’1)
[Phk ]ij (with i = 0, . . . , 7, j = 0, . . . , 15) is de¬ned exactly as [Phk ]ij is. We
therefore have MixB = Perm’1 · MB · PermB .
B
It is possible to avoid using cA slightly modifying the key generation scheme
with respect to the original proposal. We show here how. If b, (hB )i ∈ B are
the state and key vectors for the generic ith round of BES associated to the
corresponding one in AES, we have:
RoundB (b, (hB )i ) = MixB (RB (LinB (b’1 ) + cB )) + (hB )i
= MB · (b’1 ) + CB (cB ) + (hB )i (22)
= MB · (b’1 ) + (kB )i
with:
MB = MixB · RB · LinB , CB = MixB · RB , (kB )i = CB (cB ) + (hB )i (23)
The change on key generation scheme consists in adding a constant vector to
each obtained round key, and this will be the form of the system we will work
with.

BES Key Schedule Translation
3.1
“ The AES RotWord operation is represented by a matrix RWA : F4 ’’ F4 .
⎛ ⎞
0100
⎜0 0 1 0⎟
RWA = ⎜ ⎟ (24)
⎝0 0 0 1⎠
1000
The BES version RWB : F32 ’’ F32 is obtained by replacing the ones with
the identity matrix I8 , and the zeroes with the (8 — 8) zero matrix.
An Algebraic Interpretation of AES’128 91

“ The S-box is applied only to a part of the whole vector, and therefore the cor-
responding matrix dimension changes. The resulting block diagonal matrix
is Link : F32 ’’ F32 , with four blocks equal to LB .
B
“ The constant ck is obtained with just four copies of φ(cA ):
B

ck = φ(cA , cA , cA , cA ) = (φ(cA ), φ(cA ), φ(cA ), φ(cA )), [ck ]i = [φ(cA )]i mod 8
B B
(25)
“ The constant vectors Rconi = (t , 0, 0, 0) are mapped into:
i’1


(RconB )i = φ(Rconi ) = (φ(tr’1 =), 0, . . . , 0) (26)
24

In order to compute them, we need the tj normal forms with respect to m(t).

To write in a very compact way the round key equations, we keep using the
matrix notation, but in a functional sense. It is not possible to avoid here the
use of constants.
If •i : F32 ’ F32 is the BES ith -round mapping function for a conjugated
B
word x:
•i (x) = Link (RWB (x))’1 + ck + (RconB )i (27)
B B B

the generic AES and BES round matrices are M KA and M KB :
i i

⎛ ⎞ ⎛ ⎞
•i •i
00 0 00 0
A B
⎜ 0 I4 0 ⎟ ⎜ ⎟
•i ⎟ and M KB = ⎜ 0 I32 0 •i
⎜ ⎟
M KA = ⎝
i i
A B (28)
⎠ ⎝ 0 I32 I32 ⎠
0 I4 I4 •i •i
A B
0 I4 I4 I4 + •i 0 I32 I32 I32 + •i
A B

A key round is given by the computation of hi = M KB (hr’1 ).
i




4 The Systems
We indicate how the processes for encryption and key generation can be rep-
resented by algebraic systems. We underline here once and for all that all the
indicated variables satisfy the F-belonging equation y 256 + y = 0.

4.1 Encryption

Remembering that the last round di¬ers slightly from the other ones, with MB =
RB · LinB , the resulting system for codi¬cation is [8]:
§
⎪ w0 = p + k0


xi = wi ’1 i = 0, ..., 9
(29)
⎪ wi = MB xi’1 + ki i = 1, ..., 9

© —
c = MB x9 + k10

Let here and in the rest of this paper the (8j + m)th component of all the
vectors be indicated using the indexes expression (j, m), with j = 0, . . . , 15 and
92 I. Toli and A. Zanoni

m = 0, . . . , 7. Under the hypothesis that no 0-inversion occurs (true for the 53%
of encryptions and 85% of 128-bit keys), it is possible to expand the above system
as follows, for all possible values of j and m
§
⎪ 0 = w0,(j,m) + p(j,m) + k0,(j,m)


0 = xi,(j,m) wi,(j,m) + 1 i = 0, . . . , 9
(30)
⎪ 0 = wi,(j,m) + (MB xi’1 )(j,m) + ki,(j,m) i = 1, . . . , 9

© —
0 = c(j,m) + (MB x9 )(j,m) + k10,(j,m)

Let ±, β ∈ F be the generic coe¬cients of MB and MB , respectively. Now, adding
the fact that the above equations should be valid for the BA subset, that is, the
state vectors must have the conjugation property, we ¬nally have (with m + 1
considered mod8):
§
⎪ 0 = w0,(j,m) + p(j,m) + k0,(j,m)


⎪0 = w
⎪ i,(j,m) + ki,(j,m) + ±(j,m),(j ,m ) xi’1,(j ,m ) i = 1, . . . , 9





⎪ (j ,m )

0 = c(j,m) + k10,(j,m) + β(j,m),(j ,m ) x9,(j ,m )
S= (31)

⎪ (j ,m )

⎪ 0 = xi,(j,m) wi,(j,m) + 1 i = 0, . . . , 9



⎪ 0 = x2
i,(j,m) + xi,(j,m+1) i = 0, . . . , 9



© 0 = w2 +w i = 0, . . . , 9
i,(j,m+1)
i,(j,m)

Let S , = 1, . . . , 6 indicate the equations in the th line of the above system
for all the possible values of i, j and m, and I the ideal they generate. As we
see, the system is very sparse, with S = {S1 , S2 , S3 } linear, and the remaining
equations in S = {S4 , S5 , S6 } quadratic.
With k = {ki }, w = {wi }, x = {xi }, the numbers of the system are given in
the following tables.
Line Number of equations
S1 16 · 8 = 128
Block Number of variables
S2 9 · 16 · 8 = 1152
k 11 · 16 · 8 = 1408
S3 16 · 8 = 128
x 10 · 16 · 8 = 1280
S4 10 · 16 · 8 = 1280
w 10 · 16 · 8 = 1280
S5 10 · 16 · 8 = 1280
Total = 3968
S6 10 · 16 · 8 = 1280
S Total = 5248

4.2 Key Generation
It is possible to write down an analogous system for the key generation. It is more
convenient to translate directly the AES procedure KA into its BES counterpart
KB , without explicitly expanding all the equations, as it is done in M KB . The i

equations express all the hi,(j,m) variables in term of the h0,(j,m) ones. The index
ranges for the equations are: i = 1, . . . , 10, j, j = 0, . . . , 3 and m, m = 0, . . . , 7,
˜˜
while the LinB matrix coe¬cients are indicated with γ.
k
An Algebraic Interpretation of AES’128 93
§
⎪ Hi0 = •B (Hi’1,3 )
˜ i˜

⎨˜ ˜ ˜
H = Hi0 + Hi’1,1
KB = ˜ i1
⎪ Hi2 = Hi1 + Hi’1,2
˜ ˜

©˜ ˜ ˜
Hi3 = Hi2 + Hi’1,3
§
⎪ zi,(˜,m) = hi’1,(12+[(˜+1) mod 4],m)
254
⎪j j

= hi,(˜,m) = (cB + (RconB )i )(˜,m) + γ(˜,m)(˜ ,m ) zi,(˜ ,m )
k
j j j j j


© (˜ ,m )
j
hi,(4s+˜,m)= hi,(4(s’1)+˜,m) + hi’1,(4s+˜,m) s = 1, 2, 3
j j j

Let cRi = ck + (RconB )i be the constant vector occurring in each round, and
B
its elements be indicated with δi . Remembering the third equivalence of (23),
with t = 0, . . . , 15 and the conjugation property, we can obtain the keys with:
§
⎪ 0 = zi,(˜,m) + h254
⎪ j
⎪ i’1,(12+[(˜+1) mod 4],m)
j



⎪0 = h
⎪ i,(˜,m) + δi,(˜,m) + γ(˜,m)(˜ ,m ) zi,(˜ ,m )

⎪ j j j j j


⎨ (˜ ,m )
j
0 = hi,(4s+˜,m) + hi,(4(s’1)+˜,m) + hi’1,(4s+˜,m) s = 1, 2, 3
K= j j j




⎪ 0 = ki,(t,m) + (CB (cB ))(t,m) + hi,(t,m)



⎪ 0 = z2
⎪ i,(˜,m) + zi,(˜,m+1)

⎪ j
j
© 0 = h2
i,(˜,m) + hi,(˜,m+1)
j
j
(32)


5 System Solving
Actually, we are interested to recover the key out of the systems S and K, that is
the original key h = φ’1 (k ) = {h0 , . . . , h15 }, where k = {k0,(0,m) , . . . , k0,(15,m) }.
This is the task of this section.
In order to obtain equations relating h (k) components we have to eliminate
all other variables. We will do this by:
“ modifying the way the systems are written,
“ doing some variable substitutions “by hand” (see below), and ¬nally
“ perform Gr¨bner bases computations (more complicated substitutions, ex-
o
pansions and simpli¬cations) in order to obtain the ¬nal system.
First of all, we write the systems in a more appropriate way for our purposes.
Observe that, for each variable v ∈ k, w, z, h, the conjugation property of BES
vectors may be synthesized by the obvious following relations:
m
vi,(j,m) = vi,(j,0) m = 0, . . . , 7
2
(33)

5.1 Encryption
We rewrite S as follows: ¬rst of all, we remove the imposed restriction about
inversion, and we substitute S4 with an equation expressing the true de¬nition
94 I. Toli and A. Zanoni

of the general inverse of an element of F. Then we use (33), in order to remove
all the variables with index m > 0, and obtain:
§ 2m m
2m
⎪ 0 = w0,(j,0) + p2 + k0,(j,0)

⎪ (j,0)




⎪ 0 = w 2m + k 2m + m
⎪ ±(j,m),(j ,m ) x2 i = 1, . . . , 9

⎨ i,(j,0) i,(j,0) i’1,(j ,0)
(j ,m )
S= (34)



⎪ 0 = c2m + k 2m m
β(j,m),(j ,m ) x2 ,0)
⎪ +

⎪ (j,0) 10,(j,0) 9,(j


⎪ (j ,m )
©0 = x
i,(j,0) + wi,(j,0) i = 0, . . . , 9
254


We use the last equation to remove all the xi,(j,0) , and, being each line a set of
successive square powers, we keep only the ones with m = 0, obtaining:
§
⎪ 0 = w0,(j,0) + p(j,0) + k0,(j,0)




⎨ 0 = wi,(j,0) + ki,(j,0) + 254·2m
±(j,0),(j ,m ) wi’1,(j ,0) i = 1, . . . , 9
S= (35)
⎪ (j ,m )


⎪ 0 = c(j,0) + k10,(j,0) + m
β(j,0),(j ,m ) w9,(j ,0)
⎪ 254·2
©
(j ,m )

Because of the block structure of matrices LinB and RB , the β coe¬cients do
not depend on j and j , and the values are simply the coe¬cients of f . To further
simplify the notations, hereafter we take, mod255:

ω = (ω0 , . . . , ω7 ) = (254 · 20 , . . . , 254 · 27 ) = (254, 253, 251, 247, 239, 223, 191, 127),
ω = (ω0 , . . . , ω7 ) = (ω0 ’ 127, . . . , ω7 ’ 127) = (127, 126, 124, 120, 112, 96, 64, 0) .
be two auxiliary vectors. We can now avoid writing m index, and ¬nally write:
§
⎪ 0 = w0,j + pj + k0,j




⎨0 = w + k + ωm
±(j,0),(j ,m ) wi’1,j i = 1, . . . , 9
i,j i,j
S= (36)
⎪ (j ,m )


⎪ 0 = k10,j + cj + »m wωm

© 9,j
m

The system so obtained has 16 + 9 · 16 + 16 = 176 equations in 11 · 16 + 10 ·
16 = 336 variables. Obviously, it expresses nothing but a series of successive
substitutions, down to the last equation. If we consider the block lex order for
which, independently from the lex order inside each block,
k10 > w9 > k9 > · · · > w0 > k0 (37)
we have a (not reduced) Gr¨bner basis [1], and the above substitutions may be
o
considered as the complete reduction computation. The resulting set of the last
16 equations, where all the w variables disappeared, is what we were looking for.
Indicating with qj the polynomials resulting from the substitutions, we have:
S


k10,j + cj + qj (k0 , . . . , k9 , p) = 0 j = 0, . . . , 15
S
(38)
An Algebraic Interpretation of AES’128 95

5.2 Key Generation
We now try to get more informations analyzing K. We may:
“ substitute z variables in the second line equations, to get rid of them.
“ use the conjugation property, expressing everything in terms of variables
with m = 0.
“ note that the CB (cB ) constant vector has cA = t6 + t5 + t + 1 in each of its
(j, 0) positions, and opportune powers in the other ones. In other words, the
equations on the fourth line of K, K4 , may be reduced (the other ones are
powers of it) to:
hi,(j,0) + ki,(j,0) + cA = 0 (39)
“ for the above considerations, express everything directly in term of k vari-
ables.
“ observe that Link is a block diagonal matrix, and therefore just j = j is
˜ ˜
B
“active” for each single equation, and what remains is nothing more than
the set of coe¬cients of the f polynomial.
After the elaboration and always keeping present that we work in F, the
modi¬ed key generation scheme translates into the following system (where i =
1, . . . , 10; s, j = 0, . . . , 3 and in the las= t version we omit m). For brevity, we
˜
de¬ne the function:

in : N n ’ in(n) = 12 + [(n + 1) mod 4] ∈ N (40)
§
⎪ 0 = hi,(˜,0) + δi,(˜,0) + m
γ(˜,0)(˜ ,m ) h254·2 j ),0)


⎨ j j j j i’1,(in(˜
(˜ ,m )
j
K=
⎪ 0 = hi,(4s+˜,0) + hi,(4(s’1)+˜,0) + hi’1,(4s+˜,0)
⎪ j j j

©
0 = hi,(˜,0) + (ki,(˜,0) + cA )
j j
§
⎨ 0 = (ki,(˜,0) + cA ) + δi,(˜,0) + ωm
γ(˜,0)(˜,m ) ki’1,(in(˜),0) + cA
j j j j j
=
© m
0 = ki,(4s+˜,0) + cA + ki,(4(s’1)+˜,0) + cA + ki’1,(4s+˜,0) + cA
j j j
§
⎪ 0 = ki,˜ + cA + δi,(˜,0)
⎪ j j
⎨ 127 ω
+ ki’1,in(˜) + cA · »m (ki’1,in(˜) + cA m
= j j


© m
0 = ki,4s+˜ + ki,4(s’1)+˜ + ki’1,4s+˜ + cA
j j
j

Now only k variables remain, 160 equations in 176 variables, and by successive
substitutions we can express all the ones with i > 0 as polynomials in the
“parameters” k0 . The equations are a Gr¨bner basis for several suitable lex
o
orderings. Its complete reduction may be computed considering, for example,
the one such that

k10,15 > · · · > k10,0 > · · · > k0,15 > · · · > k0,0 (41)

Now we can do backward substitutions, a la Gauss. Note that it is possible to
`
work with h variables in order to have the equations following the original AES
96 I. Toli and A. Zanoni

de¬nition, and use (39) only at the end, in order to obtain the modi¬ed key
generation scheme. In any case, the result is:

ki,j = qi,j (k0 ) i = 1, . . . , 10 , j = 0, . . . , 15
K
(42)

The ¬nal step consists in putting together the results obtained in the former
sections. Now we have two main possibilities, depending on the number of (p, c)
pairs we may use.
A single (p, c) pair. We have to eliminate all the generated intermediate keys,
putting together the systems S and K , with the re¬nement of (37) sug-
gested by (41). In this way we obtain the entire substitution process once
and for all. It is summarized by the insertion of (42) into (38):

C1 = { q10,j (k0 )+cj +qj k0 , q1,j (k0 ), . . . , q9,j (k0 ), p = 0 |
j = 0, . . . , 15 }
K S K K

(43)
which is a system of 16 equations in 16 variables, whose roots give the desired
keys.
Eleven or more (p, c) pairs. We may simply use a copy of (38) for each (p, c)
pair, in order to obtain a system in 176 variables with 176 or more equations,
whose roots give all the desired keys, too.
(n)
C2 = { k10,j + cj + qj k0 , . . . , k9 , p(n) = 0 | n = 1, . . . , d , j = 0, . . . , 15 }
S

(44)
These systems are extremely dense, and a very big computation power is required
to solve them. Obviously, making use of more (p, c) pairs, we may render the
system to be solved overdetermined. We may use these tools jointly, and so on.


6 Conclusions
We presented some algebraic aspects of representing AES as a system of poly-
nomial equations following the BES approach. By means of successive substi-
tutions, we were able to eliminate all the intermediate variables, and obtain
two systems S and K whose solution corresponds exactly to code breaking.
Actually, they are rather complicated. Solving them is not trivial at all.
K and most of S are invariant for all choices of keys. When extended, their
joint size is of about 500 Kb. Each of them is a (not reduced) Gr¨bner basis for
o
several lex orderings, their union is not. Probably there exists some ordering for
which the calculus of a Gr¨bner basis is easier. If we ever can obtain this with
o
reasonable computational resources, then AES can be declared broken.
Succeeding to calculate the Hilbert series of K ∪ S , we should easily obtain
the number ns of its solutions. We suspect that ns is invariant for all key and
(p, c) choices. Furthermore, we expect that ns expresses the redundancy of the
keyspace of AES. That is, it tells us how many key choices will set up the same
bijection between the cleartext space and ciphertext space. The number of such
bijections is expected to be:
An Algebraic Interpretation of AES’128 97

#
(AES Keyspace)
(45)
ns
Probably a reasonably simple canonical representation of such bijections can
be found. In this case, if ns is big enough, probably the right (unique up to the
isomorphism) key can be found using exhaustive search.



References
1. D. A. Cox, J. Little, D. O™Shea. Ideals, Varieties, and Algorithms, An Introduc-
tion to Computational Algebraic Geometry and Commutative Algebra. Springer-
Verlag, New York, 1992.
2. N. Courtois, J. Pieprzyk. Cryptanalysis of block ciphers with overde¬ned systems
of equations. IACR eprint server www.iacr.org, April 2002.
3. J. Daemen, V. Rijmen. AES proposal: Rijndael (Version 2). NIST AES website:
csrc.nist.gov/encryption/aes, 1999.
4. J. Daemen, V. Rijmen. The design of Rijndael: AES - The Advanced Encryption
Standard. Springer-Verlag, 2002.
5. National Institute of Standards and Technology. Advanced Encryption Standard.
FIPS 197. 26 November 2001.
6. N. Ferguson, R. Schroeppel, D. Whiting. A simple algebraic representation of
Rijndael. In Selected Areas in Cryptography, Proc. SAC 2001, Lecture Notes in
Computer Science 2259, pp. 103-111, Springer Verlag, 2001.
7. Grayson, Daniel R. and Stillman, Michael E. Macaulay 2, a software system
for research in algebraic geome= try. Available at http://www.math.uiuc.edu/
Macaulay2/.
8. G.-M. Greuel, G. P¬ster, H. Sch¨nemann. Singular 2-0-3. A Computer Algebra
o
System for Polynomial Computations. Center for Computer Algebra, University
of Kaiser slautern, 2003. www.singular.uni-kl.de.
9. S. Murphy M. J.B. Robshaw. Essential Algebraic Structure within the AES. M.
Yung (ed.): CRYPTO 2002, LNCS 2242, pp. 1-16, Springer-Verlag 2002.
10. E. Oswald, J. Daemen, and V. Rijmen. The State of the Art of Rijndael™s Se-
curity. Technical report. Available at www.a-sit.at/technologieb/evaluation/
aes report e.pdf.
11. D. R. Stinson. CRYPTOGRAPHY, Theory and Practice. Chapman & Hall/CRC,
2002. Second edition.
E¬cient AES Implementations on ASICs
and FPGAs

Norbert Pramstaller, Stefan Mangard, Sandra Dominikus,
and Johannes Wolkerstorfer

Institute for Applied Information Processing and Communications (IAIK),
Graz University of Technology, In¬eldgasse 16a, A-8010 Graz, Austria
{firstname.surname}@iaik.at




Abstract. In this article, we present two AES hardware architectures:
one for ASICs and one for FPGAs. Both architectures utilize the simi-
larities of encryption and decryption to provide a high throughput using
only a relatively small area. The presented architectures can be used in a
wide range of applications. The architecture for ASIC implementations
is suited for full-custom as well as for semi-custom design ¬‚ows. The ar-
chitecture for the FPGA implementation does not require on-chip block
RAMs and can therefore even be used for low-cost FPGAs.

Keywords: Advanced Encryption Standard (AES), FPGA, ASIC.



1 Introduction
The symmetric block cipher Rijndael [4] has been standardized by NIST1 as
Advanced Encryption Standard (AES) [10] in November 2001. Today, AES is
the most widely used symmetric block cipher and it is implemented in many
di¬erent devices to secure wired as well as wireless connection links.
The requirements for an implementation of AES strongly depend on the
application running on the device and of course also on the type of the device.
In many scenarios, it is su¬cient to implement AES in software. However, there
are also many very relevant scenarios, where the requirements concerning the
implementation of AES can only be met by dedicated hardware implementations.
Encryption engines for high speed communication links, for example, often
need to be implemented in hardware due to the high throughput requirements.
In applications that need to be resistant against side-channel attacks, AES is
also often implemented in special hardware modules [11]. The reason for this
is simply that it is easier to secure a small AES module against side-channel
attacks rather than to secure an entire processor. In devices where the power
consumption is critical, hardware implementations are also the preferred choice,
because they consume considerably less power than software implementations.

1
National Institute of Standards and Technology.

H. Dobbertin, V. Rijmen, A. Sowa (Eds.): AES 2004, LNCS 3373, pp. 98“112, 2005.
c Springer-Verlag Berlin Heidelberg 2005
E¬cient AES Implementations on ASICs and FPGAs 99

In this article, we present e¬cient hardware implementations for ASICs and
FPGAs that can be used for a wide range of applications. Both architectures use
similarities of encryption and decryption to provide a high level of performance
using only a relatively small area. While most publications on implementations of
AES only provide performance and area ¬gures without interfaces and registers
for CBC mode, the architectures presented in this article are complete. Both
architectures include an AMBA APB [1] interface and can perform encryptions
and decryptions in CBC mode.
Our architecture for ASICs is presented in Section 2 and the one for FPGAs
is discussed in Section 3. Conclusions about both architectures can be found in
Section 4.


2 ASIC Implementation of AES
During the last years, several proposals [8, 12, 13, 16, 19] on how to implement
AES on an ASIC have been published. Most of these publications focus mainly
on the throughput of the implementation. In this article however, we describe
an architecture that in addition is highly regular and scalable. Therefore, it can
be used for a wide range of applications.
The architecture discussed in this article has balanced combinational paths
in order to fully utilize every clock cycle. The fact that the combinational paths
are short compared to other published AES architectures, makes the presented
architecture a favorable choice for low-power applications. This is due to the fact
that glitches, which occur more frequently in long combinational paths than in
short ones, cause a signi¬cant power consumption.
The regularity of the presented architecture helps to keep the size of the
AES architecture small during place-and-route of a semi-custom design ¬‚ow and
facilitates the creation of full-custom designs. Full-custom approaches are inter-
esting for smart card implementations that are required to provide protection
against power analysis attacks [7]. In a full-custom approach, the designer can
well balance the capacitive loads of output nodes, as it is for example desired
for logic styles like the one described in [14, 15].
The performance of our AES architecture can gradually be increased at the
cost of an increased chip size. The overall structure of this architecture, which is
capable of performing AES encryptions and decryptions, is shown in Fig. 1. The
AES hardware module consists of the following four components:

“ The Interface: The AMBA APB interface handles all communication of
the AES module with its environment.
“ The Data Unit: The data unit is the main module of the architecture.
It can perform any kind of AES encryption or decryption round using the
round key that is assigned to its key input. Although the number of rounds
is di¬erent for the three standardized key sizes, the types of rounds which
need to be executed are the same for all key sizes. Consequently, the data
unit is independent of the key size.
100 N. Pramstaller et al.


32
output
data
CBC 32
cell cell cell cell
32
data_out 32
input
cell cell cell cell


data unit




interface
storage
cell cell cell cell
key
32
input
key unit
128
cell cell cell cell


32
generator

<<

. 4
( 7)



>>