Editing XSL attack (section)

==Application to block ciphers==
Courtois and Pieprzyk (2002) observed that [[Advanced Encryption Standard|AES]] (Rijndael) and partially also [[Serpent (cipher)|Serpent]] could be expressed as a system of quadratic equations. The variables represent not just the [[plaintext]], [[ciphertext]] and key bits, but also various intermediate values within the algorithm. The [[S-box]] of AES appears to be especially vulnerable to this type of analysis, as it is based on the algebraically simple [[inverse function]]. Subsequently, other ciphers have been studied to see what systems of equations can be produced ([[Alex Biryukov|Biryukov]] and De Cannière, 2003), including [[Camellia (cipher)|Camellia]], [[KHAZAD]], [[MISTY1]] and [[KASUMI]]. Unlike other forms of cryptanalysis, such as [[differential cryptanalysis|differential]] and [[linear cryptanalysis|linear]] cryptanalysis, only one or two (in the case of a 128 bit block size and a 256 bit key size) [[known plaintext]]s are required.

The XSL algorithm is tailored to solve the type of equation systems that are produced. Courtois and Pieprzyk estimate that an "optimistic evaluation shows that the XSL attack might be able to break Rijndael [with] 256 bits and Serpent for key lengths [of] 192 and 256 bits." Their analysis, however, is not universally accepted. For example:
{{quote|I believe that the Courtois–Pieprzyk work is flawed. They overcount the number of linearly independent equations. The result is that they do not in fact have enough linear equations to solve the system, and the method does not break Rijndael… The method has some merit, and is worth investigating, but it does not break Rijndael as it stands.|[[Don Coppersmith]]|[https://www.schneier.com/crypto-gram/archives/2002/1015.html#8 Crypto-Gram October 15, 2002: Comments from Readers]}}

In AES 4 Conference, Bonn 2004, one of the inventors of Rijndael, [[Vincent Rijmen]], commented, "The XSL attack is not an attack. It is a dream." Promptly Courtois answered, "XSL may be a dream. It may also be a very bad dream and turn into a nightmare."<ref>{{cite web
| url=http://www.cosic.esat.kuleuven.ac.be/nessie/forum/read.php?f=1&i=82&t=82
| title=Re: Rijndael and other block ciphers
| author=Vincent Rijmen
| date=2002-12-18
| archive-url=https://web.archive.org/web/20040803093228/http://www.cosic.esat.kuleuven.ac.be/nessie/forum/read.php?f=1&i=82&t=82
| archive-date=2004-08-03
| url-status=dead
| access-date=2015-03-16| author-link=Vincent Rijmen
}}</ref> However neither any later paper or any actions by the [[NSA]] or [[NIST]] give any support to this remark by Courtois.

In 2003, [[Sean Murphy (cryptographer)|Murphy]] and [[Matt Robshaw|Robshaw]] discovered an alternative description of AES, embedding it in a larger cipher called "BES", which can be described using very simple operations over a single [[field (mathematics)|field]], GF(2<sup>8</sup>). An XSL attack mounted on this system yields a simpler set of equations which would break AES with complexity of around 2<sup>100</sup>, if the Courtois and Pieprzyk analysis is correct. In 2005 Cid and Leurent gave evidence that, in its proposed form, the XSL algorithm does not provide an efficient method for solving the AES system of equations; however Courtois disputed their findings.{{Citation needed|date=February 2018}} At FSE 2007, Chu-Wee Lim and Khoongming Khoo showed that the XSL attack was worse than brute force on BES.  {{Citation needed|date=February 2018}} 

Even if XSL works against some modern algorithms, the attack currently poses little danger in terms of practical security. Like many modern cryptanalytic results, it would be a so-called "certificational weakness": while faster than a [[brute force attack]], the resources required are still huge, and it is very unlikely that real-world systems could be compromised by using it. Future improvements could increase the practicality of an attack, however. Because this type of attack is new and unexpected, some [[cryptographer]]s have expressed unease at the algebraic simplicity of ciphers like Rijndael. [[Bruce Schneier]] and [[Niels Ferguson]] write, "We have one criticism of AES: we don't quite trust the security… What concerns us the most about AES is its simple algebraic structure… No other block cipher we know of has such a simple algebraic representation. We have no idea whether this leads to an attack or not, but not knowing is reason enough to be skeptical about the use of AES." (''Practical Cryptography'', 2003, pp. 56–57)