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 Sboxes, interconnected by linear keydependent 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 Sbox 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 Sboxes) 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 doubleexponential in the size of the Sbox. 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 eprint 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.
Metadata
 Available format(s)
 PDF PS
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. A different version, so called compact version of the first XSL attack, is published in Asiacrypt 2002.
 Keywords
 block ciphersAESRijndaelSquareSerpentCamelliamultivariate quadratic equationsMQ problemXL algorithmGrobner basessparse multivariate polynomials.
 Contact author(s)
 courtois @ minrank org
 History
 20021109: last of 9 revisions
 20020411: received
 See all versions
 Short URL
 https://ia.cr/2002/044
 License

CC BY
BibTeX
@misc{cryptoeprint:2002/044, author = {Nicolas Courtois and Josef Pieprzyk}, title = {Cryptanalysis of Block Ciphers with Overdefined Systems of Equations}, howpublished = {Cryptology {ePrint} Archive, Paper 2002/044}, year = {2002}, url = {https://eprint.iacr.org/2002/044} }