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