Paper 2002/044

Cryptanalysis of Block Ciphers with Overdefined Systems of Equations

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 is very powerful, but heuristic and it is very difficult to evaluate its complexity. 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. We demonstrated by computer simulations that the XSL attack works well enough on a toy cipher. It seems however that P will rather increase very slowly with Nr. More simulations are needed for bigger ciphers. Our optimistic evaluation shows that the XSL attack might be able to break Rijndael 256 bits and Serpent for key lengths 192 and 256 bits. However if only $P$ is increased by 2 (respectively 4) the XSL attack on Rijndael (respectively Serpent) would become slower than the exhaustive search. At any rate, it seems that the security of these ciphers does NOT grow exponentially with the number of rounds.

Note: This paper contains a general description of the so called first and second XSL attack on block ciphers. This paper is kept on e-print as an archive of the early work, was written between November 2001 and Mai 2002, and is kept unchanged since, except correcting some small errors and typos. The best attacks on AES that seem to be in about 2^87 or 2^100, comes from a simple adaptation of the second XSL attack described here, proposed by Murphy and Robshaw, in which equations are writen over GF(256). When studying such attacks, intuition is very tricky, and though Coppersmith and Moh once claimed that they know that such attacks will not work, so far we did not see any serious argument against XSL.