Here's an attack on Rijndael and Serpent. It's polynomial in number of rounds with a huge multiplicative constant (double-exponential in the size of the S-box).

by Nicolas Courtois and Josef Pieprzyk

Abstract. Several recently proposed ciphers are built with layers of small S-boxes, interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr.

In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this hypothesis is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties).

We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt'00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure.

The XSL attack has a parameter P, and in theory we show that P should be a constant. The XSL attack would then be polynomial in Nr, with a huge constant that is double-exponential in the size of the S-box. In this case we are able to break Rijndael 256 bits and Serpent for key lengths 192 and 256 bits.

We demonstrated by computer simulations that the XSL attack works. Unfortunately they show that P will not be constant but increases very slowly with Nr. If only P is increased by 2 (respectively 4), our attack on Rijndael (respectively Serpent) will become slower than the exhaustive search. Even so, we claim that the security of these ciphers does not grow exponentially with the number of rounds.