30-06-2012, 12:44 PM
Automatic Search of Attacks on round-reduced AES and Applications
[attachment=26260]
Abstract
. In this paper, we describe versatile and powerful algorithms for searching guess-anddetermine
and meet-in-the-middle attacks on some byte-oriented symmetric primitives. To demonstrate
the strengh of these tools, we show that they allow to automatically discover new attacks on
round-reduced AES with very low data complexity, and to nd improved attacks on the AES-based
MACs Alpha-MAC and Pelican-MAC, and also on the AES-based stream cipher LEX. Finally, the
tools can be used in the context of fault attacks. These algorithms exploit the algebraically simple
byte-oriented structure of the AES. When the attacks found by the tool are practical, they have
been implemented and validated experimentally..
Introduction
Since the introduction of the AES in 2001, it has been questioned whether its simple algebraic structure
could be exploited by cryptanalysts. Soon after its publication as a standard [NIS01], Murphy and
Robshaw showed in 2002 an interesting algebraic property: the AES encryption process can be described
only with simple algebraic operations in GFp28q [MR02]. Such a result paved the way for multivariate
algebraic techniques [CP02,Cid04] since the AES encryption function can be described by a very sparse
overdetermined multivariate quadratic system over GFp2q. However, so far this approach has not been
so promising [MV04,CL05], and the initial objective of this simple structure, providing good security
protections against di erential and linear cryptanalysis, has been ful lled.
Related Work.
In this security model, statistical attacks may be not the best possible attacks, since
they usually require many pairs with speci c input di erence and algebraic attacks seem to be more wellsuited.
However, such attacks using either SAT solvers or Grobner basis algorithms [MR02,BPW06], have
never been able, so far, to endanger even very reduced versions of the AES even though its structure
exhibits some algebraic properties. These attacks encode the problem into a system of equations, then
feeds the equations to a generic, sometimes o -the-shelf equation solver, such as a SAT-solver or a
Grobner basis algorithm. The main obstacle in these approaches is the S-box, that only admits \bad"
representations (for instance, it is a high degree polynomial over the AES nite eld), and increases the
complexity of the equations, even though low degree implicit equations may also exist.
Our Techniques and Results.
Our tools try to nd attacks automatically by searching some classes
of guess-and-determine and meet-in-the-middle attacks. They take as input a system of equations that
describes the cryptographic primitive and some constraints on the plaintext and ciphertext variables for
example. Then, it solves the equations by rst running a (potentially exponential) search for a customized
solver for the input system. Then, the solver is run, and the solutions are computed.
We describe two tools. Our preliminary tool uses a depth- rst branch-and-bound search to nd
\good" guess-and-determine attacks. It has been (covertly) used to generate some of the attacks found
in [BDD
[attachment=26260]
Abstract
. In this paper, we describe versatile and powerful algorithms for searching guess-anddetermine
and meet-in-the-middle attacks on some byte-oriented symmetric primitives. To demonstrate
the strengh of these tools, we show that they allow to automatically discover new attacks on
round-reduced AES with very low data complexity, and to nd improved attacks on the AES-based
MACs Alpha-MAC and Pelican-MAC, and also on the AES-based stream cipher LEX. Finally, the
tools can be used in the context of fault attacks. These algorithms exploit the algebraically simple
byte-oriented structure of the AES. When the attacks found by the tool are practical, they have
been implemented and validated experimentally..
Introduction
Since the introduction of the AES in 2001, it has been questioned whether its simple algebraic structure
could be exploited by cryptanalysts. Soon after its publication as a standard [NIS01], Murphy and
Robshaw showed in 2002 an interesting algebraic property: the AES encryption process can be described
only with simple algebraic operations in GFp28q [MR02]. Such a result paved the way for multivariate
algebraic techniques [CP02,Cid04] since the AES encryption function can be described by a very sparse
overdetermined multivariate quadratic system over GFp2q. However, so far this approach has not been
so promising [MV04,CL05], and the initial objective of this simple structure, providing good security
protections against di erential and linear cryptanalysis, has been ful lled.
Related Work.
In this security model, statistical attacks may be not the best possible attacks, since
they usually require many pairs with speci c input di erence and algebraic attacks seem to be more wellsuited.
However, such attacks using either SAT solvers or Grobner basis algorithms [MR02,BPW06], have
never been able, so far, to endanger even very reduced versions of the AES even though its structure
exhibits some algebraic properties. These attacks encode the problem into a system of equations, then
feeds the equations to a generic, sometimes o -the-shelf equation solver, such as a SAT-solver or a
Grobner basis algorithm. The main obstacle in these approaches is the S-box, that only admits \bad"
representations (for instance, it is a high degree polynomial over the AES nite eld), and increases the
complexity of the equations, even though low degree implicit equations may also exist.
Our Techniques and Results.
Our tools try to nd attacks automatically by searching some classes
of guess-and-determine and meet-in-the-middle attacks. They take as input a system of equations that
describes the cryptographic primitive and some constraints on the plaintext and ciphertext variables for
example. Then, it solves the equations by rst running a (potentially exponential) search for a customized
solver for the input system. Then, the solver is run, and the solutions are computed.
We describe two tools. Our preliminary tool uses a depth- rst branch-and-bound search to nd
\good" guess-and-determine attacks. It has been (covertly) used to generate some of the attacks found
in [BDD