Editing XSL attack (section)

{{Short description|Theoretical attack on block ciphers}}
{{more footnotes|date=November 2018}}
<!-- Image with disputed fair-use status removed:  [[Image:New-sci-xsl.png|right|thumb|250px|[[New Scientist]] magazine featured the XSL attack in June 2003 with an article billed as "Cipher crisis: the end of internet privacy".]] -->
In [[cryptography]], the '''''eXtended Sparse Linearization'' (XSL) attack''' is a method of [[cryptanalysis]] for [[block cipher]]s. The attack was first published in 2002 by researchers [[Nicolas Courtois]] and [[Josef Pieprzyk]]. 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 [[brute force attack|exhaustive search]]. Since AES is already widely used in commerce and government for the transmission of secret information, finding a technique that can shorten the amount of time it takes to retrieve the secret message without having the key could have wide implications.

The method has a high work-factor, which unless lessened, means the technique does not reduce the effort to break AES in comparison to an exhaustive search. Therefore, it does not affect the real-world security of block ciphers in the near future. Nonetheless, the attack has caused some experts to express greater unease at the algebraic simplicity of the current AES.

In overview, the XSL attack relies on first analyzing the internals of a cipher and deriving a set of [[quadratic polynomial|quadratic]] [[simultaneous equation]]s. These systems of equations are typically very large, for example 8,000 equations with 1,600 [[Variable (programming)|variables]] for the 128-bit AES. Several methods for solving such systems are known. In the XSL attack, a specialized algorithm, termed ''eXtended Sparse Linearization'', is then applied to solve these equations and recover the [[key (cryptography)|key]].

The attack is notable for requiring only a handful of [[known plaintext]]s to perform; previous methods of cryptanalysis, such as [[linear cryptanalysis|linear]] and [[differential cryptanalysis]], often require unrealistically large numbers of known or [[chosen plaintext]]s.