It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard (AES) cipher, also known as Rijndael, faster than an exhaustive search.
In the XSL attack, a specialized algorithm, termed eXtended Sparse Linearization, is then applied to solve these equations and recover the key.
Solving multivariate quadratic equations (MQ) over a finite set of numbers is an NP-hard problem (in the general case) with several applications in cryptography.
In 2000, Courtois et al. proposed an improved algorithm for MQ known as XL (for eXtended Linearization), which increases the number of equations by multiplying them with all monomials of a certain degree.
In 2003, Murphy and 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, GF(28).
An XSL attack mounted on this system yields a simpler set of equations which would break AES with complexity of around 2100, 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] At FSE 2007, Chu-Wee Lim and Khoongming Khoo showed that the XSL attack was worse than brute force on BES.
[citation needed] 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.