Welcome to the webpage for the EPSRC research project Security Aspects of the Advanced Encryption Standard (GR/S42637/01). The Belgian block cipher Rijndael was chosen as the Advanced Encryption Standard (AES) in 2000. The AES was created as a result of the U.S. government's National Institute of Standards' (NIST) programme to choose a block cipher to succeed the Data Encryption Standard (DES). The AES has a very high degree of algebraic and geometric structure. The aim of this research project was to investigate this structure both from a mathematical and a security viewpoint.
This project and was based in the Information Security Group (part of the Department of Mathematics) at Royal Holloway (University of London), and the EPSRC funding ran from October 2003 to February 2007. The named investigators on this project were Prof. Sean Murphy, Dr Matt Robshaw (now at France Telecom) and Prof. Simon Blackburn. The researchers employed by this project were Dr Carlos Cid and Dr Maura Paterson.
The main motivation for the project was the structure in the AES discussed in the following paper from 2002 by two of the project investigators. In summary, this paper shows that a round of the AES can be regarded as a component-wise finite field inversion followed by an affine transformation. Thus the AES possesses an algebraic structure with an elegance unmatched by any similar block cipher.
At the same time, other researchers were making proposals for methods to analyse block ciphers using algebraic methods, such as the XSL method, though doubt was cast upon the XSL method by some noted cryptographers. However, this proposed XSL method, if valid, could exploit the algebraic structure revealed in the above CRYPTO paper to give a cryptanalysis faster than exhaustive search. These issues were discussed in the paper below by two of the project investigators.
There was scientific and press speculation at this time as to the long-term security of the AES. It was clearly important that the mathematical and security properties of the AES were thoroughly investigated. These issues formed the basis of the project submission to the EPSRC.
The most important outcome of the project is the research mongraph detailed below, which was published as part of Springer's Advances in Information Security series. The purpose of the book is to provide both an overview and to give the background to the algebraic analysis of the AES.
One consequence of the above CRYPTO paper is that the AES encryption process can be described by a very sparse multivariate quadratic system. A major component of the project was the consideration of the possible use of techniques from computational algebra, such as Groebner basis techniques, in the analysis of such AES equation systems. The above CRYPTO paper also shows that the transformations used by the AES can also be regarded as "geometric" transformations of suitably defined spaces. Another component of the project was to investigate such geometric properties of the AES.
The first paper of the project was a general survey of the known algebraic properties of the AES at the start of the project (2003-04). It was an invited presentation at the Fourth Conference on the Advanced Encryption Standard, the first three conferences having been part of the AES selection process.
The paper below was given at a computational algebra workshop, rather than a cryptology conference. It is intended to bring these algebraic AES issues to the notice of researchers in computational algebra.
The paper below specifies some block ciphers that have most of the fundamental properties of the AES but with smaller parameters. This is to enable experimentation with these smaller versions using computer algebra, and a number of such results are reported. An equation system generator for the small scale AES variants is available with the open-source mathematics software Sage together with documentation .
One important part of the project was a thorough analysis of the XSL algorithm. Whilst some general doubts were cast on the general idea of the XSL algorithm, there had been no work on its behaviour as applied to AES-like ciphers. Such a complete analysis in the case of the AES is given by the paper below, which conclusively shows that XSL-style algorithms do not work as described.
The crucial idea used to give the simple description of the AES in the above CRYPTO paper is that of embedding a cipher in a larger cipher. The paper below develops a general framework for so doing and gives some classification criteria for different embeddings.
The paper below uses some of these ideas from computational algebra to analyse an asymmetric cipher proposal.
The paper below analyses the inversion function used by the AES. It discusses the group generated by a cipher, and gives a characterisation of the AES XOR-Table (used in differential cryptanalysis) as a projective plane.
The paper below considers the geometric propertites of the XL-type algorithms for solving multivariate systems. It propose the GeometricXL algorithm, a geometrically-invariant version of the XL algorithm for nonzero small characteristic. The GeometricXL is significantly more efficient than the XL algorithm or Groebner basis techniques for some equation systems.
Professor Sean Murphy,