 |
Quo vadis cryptology ?AES Under Attack: Designing Secure Ciphers and the Challenge of Algebraic Attacks2nd International Workshop on the state of the art in cryptology and new challenges aheadWarsaw, PolandThursday, May 13th, 2004Gromada Hotel (near the Warsaw Airport) Scope: The tutorial will consist of two lectures presenting differing points of view on the security of the Advanced Encryption Standard, followed by a panel discussion offering an opportunity for a direct exchange of arguments on this subject. The lectures will be given by Vincent Rijmen, one of the designers of the AES and still confident in its security, and Nicolas Courtois, one of the inventors of the class of algebraic attacks which threaten to break the AES. The lectures and the discussion will attempt to develop in the listeners an understanding of the current status of the security of the AES and the state of the art in attacks designed to break it, as well as an awareness of current activities in this field. The tutorial will be held one day after the end of the AES4 conference and will contain a summary of the latest developments reported during that conference. Program:
Location & fees:Location: or other hotels in the Warsaw airport area. Visas: Organizer: Abstracts:Security and Implementation of the AES We briefly introduce the Wide Trail strategy, that was used to design Rijndael and present an overview of the most succesful attacks on reduced version of the cipher.Next, we show how the design principles facilitate efficient implementations of the cipher. Finally, we discuss side-channel attacks. Side-channel attacks exploit weaknesses in implementations, rather than weaknesses in the functional description of the cipher. With the current state of the art, it appears that Rijndael's flexibility for implementation on various platforms, make it an ideal cipher for implementations that have to resist side-channel attacks. New Attacks on Block Ciphers, the AES S-box
and Multivariate Polynomial Relations How to design secure ciphers? All that we know are mostly negative answers: how not to design ciphers. We have general classes of attacks on various levels of abstraction, and constructions that are provably not susceptible to these attacks. From these we derive good practices. However trying to make it too good on one set of criteria may be catastrophic for the other criteria: special is dangerous. Rijndael is a cipher that does push some of the design principles such as high non-linearity or good diffusion to their theoretical limits. This makes it an interesting (and challenging) topic to study: giving us the opportunity and motivation to explore these limits, and uncover possible pitfalls (are they serious or not). If we look at the current paradigm for the design of the low-level components of block and stream ciphers, it concentrates on their functional aspect: their components should be “good” Boolean functions / or “good” vectorial functions (S-boxes) with several desirab le properties. For example the resistance of the inverse function in GF(2^m) to linear, differential and higher-order differential attacks is exceptional. In their earlier paper on Shark, page 6, the designers of AES write: “[...] The disadvantage of these boxes is that they have a simple description in GF (2^m), which is also the field in which the diffusion layer is linear. This may create uneasy feelings, but we are not aware of any vulnerability caused by this property. For the time being we challenge cryptanalysts to demonstrate any vulnerability caused by this property. Should such a vulnerability exist, one can always replace the Sboxes by Sboxes with similar properties, that are not algebraic over GF(2^m). [...]”. Unfortunately an important vulnerability of the inverse S-box does exist. It follows the line of research that has already been around for some time. Historically the idea goes back to cryptanalysis of Matsumoto-Imai public key scheme by Patarin at Crypto 95, greatly improved and extended to HFE by Courtois et al., and followed without proper acknowledgment by Faugère and Joux at Crypto 2004. The seminal idea (due to Patarin) is to study the security of a cipher component not in terms of Boolean/algebraic functions, but in terms of Boolean/algebraic relations that involve both inputs and output bits. This idea is very powerful, and in the last two years, it has lead to a sudden collapse of several important families of stream ciphers, as demonstrated by Courtois, Meier, Armknecht and others in a dozen of recent papers (all references can be found at http://www.cryptosystem.net/stream/). Clearly the paradigm of “good Boolean functions” is a total failure. Good Boolean functions insure that many attacks will provably not work, but are definitely NOT magical objects that make ciphers secure. But does it matter at all for block ciphers ? An early warning has been issued by Jakobsen, Crypto 98, Section 6. The author proposes attacks on block ciphers based on univariate (and tentatively also multivariate) polynomial approximations, and already speaks explicitly of using (probabilistic) algebraic relations. Jakobsen clearly makes his point showing that to obtain secure ciphers ``[...] it is not enough that round functions have high Boolean complexity. Likewise, good properties against differential and linear attacks are no guarantee either. In fact, many almost prefect non-linear functions should be avoided exactly because they are too simple algebraically [...]''. Yet, Jakobsen did not propose neither really surprising nor really devastating attacks except for some contrived ciphers. In the same line of research, being a kind of generalized linear cryptanalysis of highly non-linear flavour, it is for example possible, (and we will explain how, extending the ideas of Jakobsen and Knudsen), to build practical block ciphers that are extremely secure against all known attacks, and yet can be broken in practice for a very important number of rounds (e.g. 1 million rounds). Similar results (will be presented at Crypto 2004) were recently obtained with Feistel ciphers, using the inverse function that can be mixed with arbitrary components, yet the cipher is badly broken. We will also present these results that lead to new attacks on block ciphers being types of generalised linear cryptanalysis of highly non-linear flavour. The attacks described above will probably never be devastating for AES because of the wide trail stategy. Unfortunately there is also a direct algebraic approach. Each Rijndael S-box, though very complex when regarded as a function, can be characterized in several ways by algebraic relations [CF. Courtois-Pieprzyk and later Murhpy-Robshaw]. These equations are true with very high probability, usually 1. Using this in cryptanalysis goes back to Shannon that suggests in 1949 that 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 […]”. This was neglected because it seemed that large systems of equations become intractable very easily. However, what makes the problem hard is not the number of variables, but the balance between the number of equations and the number of monomials. Hence XL method (exploits additional equations) and XSL method (exploits small number of monomials). When the XL attack was first introduced by Courtois, Klimov, Patarin and Shamir, it became sensible to combine these ideas and to write the problem of recovering the AES key as solving a system of multivariate quadratic equations. This seemed, at first sight, rather extensively stupid, as obviously we are facing an NP-complete problem, and any other cipher can be attacked in a similar way. Even though for AES the system is somewhat over-determined, and even with an optimistic evaluation of XL, there is clearly no hope to get an attack faster than 2^{300}. Yet with time, this idea appeared less and less stupid. Courtois and Pieprzyk proposed a method called XSL that should be able to substantially lower the (still naive) complexity estimation of an algebraic attack, by adapting the basic idea of XL to the sparsity and the specific structure of these equations. Then Murphy and Robshaw followed with an (in theory) equivalent version of the same approach, writing quadratic equations o ver GF(256) instead of GF(2), yet yielding more sparsity, and giving hopes for even faster attacks. Thus a rather outrageous idea appeared: this version of XSL attack appears (in first, very naive estimations) to have a potential to recover an AES key in less than 2^{128} AES computations, given only one single known plaintext.. So far the real feasibility of such attacks is far from being clear. Algebraic attacks are composed of 3 parts that can and should be studied separately. In this talk we will describe all these in details and outline what is (and what is not) known about them. A compilation of reference pointers is available at http://aes.cryptosystem.net/ We will discuss plausible ways to break AES, and those that cannot work. Finally, we will explain how to design ciphers that do resist algebraic attacks (whether they are practical attacks or not). We argument that the cost of protecting the cipher against all known attacks is small. And that we have to prevent ciphers against all present and future attacks. The conclusion is that all serious ciphers proposed from now on should be resistant to algebraic attacks. This does not end the current paradigm for (block and steam) cipher components that stipulates that they should behave “well” as Boolean functions. The paradigm should be complemented by requiring that there is no “simple” algebraic relations. Speaker bios:Prof. dr. Vincent Rijmen In 1997, Rijmen finished his doctoral dissertation on the design and analysis of block ciphers. Continuing his research, he worked on several occasions together with his former colleague, dr. Joan Daemen. One of their joint projects resulted in the block cipher Rijndael, which in October 2000 was selected by the National Institute for Standards and Technology (NIST), to become the Advanced Encryption Standard (AES). Rijmen has been working as chief cryptographer for Cryptomathic since August 2001. Starting with the summer semester of 2000, Rijmen has been teaching at the Graz University of Technology, Austria. The collaboration has increased over the years and includes now also research activities in the fields of cryptography and side-channel analysis.
Dr. Nicolas T. Courtois Nicolas Courtois was born in Poland. He attended the elite Magistère classes at Ecole Normale Supérieure in Paris and later received his PhD in cryptography from Paris 6 University. He is currently employed by Axalto Smart Cards, France. He is the author of more than 20 papers in cryptography. His main interest is cryptanalysis of various ciphers using multivariate polynomial equations. His web page is www.nicolascourtois.net. Related links:The Rijndael Page
|
 |