Security Aspects of the Advanced Encryption Standard

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.

Project Motivation

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.

  • S. Murphy and M. Robshaw, `Essential Algebraic Structure within the AES', Advances in Cryptology -- CRYPTO 2002, LNCS 2442, pp. 1-16, Springer, 2002.

    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.

  • S.Murphy and M.Robshaw, `Comments on the Security of the AES and the XSL Technique', Electronic Letters, Vol. 39, pages 36-38, 2003.

    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.

    Project Book

    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.

  • Carlos Cid, Sean Murphy and Matthew Robshaw, Algebraic Aspects of the Advanced Encryption Standard, Springer, ISBN 0-387-24363-1, 2006.

    Research Publications

    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.

  • C. Cid. 'Some Algebraic Aspects of the Advanced Encryption Standard', Proceedings of the Fourth Conference on the Advanced Encryption Standard (AES4), LNCS 3373, pp. 58-66, Springer 2004.

    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.

  • C. Cid, S. Murphy and M. Robshaw, `Computational and Algebraic Aspects of the Advanced Encryption Standard', Seventh International Workshop on Computer Algebra in Scientific Computing, CASC‘ 2004, pp. 93-103, St. Petersburg, Russia, 2004.

    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 .

  • C. Cid, S. Murphy and M. Robshaw, Small Scale Variants of the AES, Fast Software Encryption - FSE2005, LNCS 3557, pages 145-162, 2005.

    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.

  • C. Cid and G. Leurent. 'An Analysis of the XSL Algorithm', Proceedings of ASIACRYPT 2005, LNCS 3788, pp 333-352, Springer 2005.

    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.

  • C. Cid, S. Murphy and M.Robshaw, 'An Algebraic Framework for Cipher Embeddings', Proceedings of the 10th IMA International Conference on Coding and Cryptography, LNCS 3796, pages 278-289, 2005.

    The paper below uses some of these ideas from computational algebra to analyse an asymmetric cipher proposal.

  • C. Cid, S. Blackburn and S. Galbraith, 'Cryptanalysis of a Cryptosystem based on Drinfeld Modules', IEE Proceedings Information Security, Volume 153, p. 12-14, 2006.

    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.

  • Wen-Ai Jackson and S. Murphy, `Projective Aspects of the AES Inversion', Designs, Codes and Cryptography, Vol. 43, pp 167-179, 2007. Available as Departmental Technical Report RHUL-MA-2006-4.

    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.

  • S. Murphy and M.B. Paterson `A Geometric View of Cryptographic Equation Solving', Journal of Mathematical Cryptology. Vol. 2, pages 63-1-7, 2008. A version is available as Departmental Technical Report RHUL-MA-2007-4.

    Note that the copyright of most of the above publications belongs to the relevant publisher.

    Sean Murphy

    Professor Sean Murphy,
    Information Security Group,
    Department of Mathematics,
    Royal Holloway, University of London,
    Egham, Surrey TW20 0EX, U.K.
    Phone: +44 (0)1784 443699
    Fax : +44 (0)1784 430766