XSL attack facts for kids

In cryptography, the XSL attack is a method of cryptanalysis for block ciphers. The attack was first published in 2002 by researchers Nicolas Courtois and Josef Pieprzyk. It was claimed that it may break the Advanced Encryption Standard (AES) cipher faster than a brute force attack.

AES is already widely used in commerce and government for the transmission of secret and classified information. Finding a technique that can decrease the amount of time it takes to break the secret message without having the key could cause wide damage.

In 2004 it was shown by one of the cryptanalysts, that the algorithm does not perform as described in its published paper. In addition, the method requires long effort. Unless shortened, the technique does not reduce the effort to break AES in comparison to a brute force attack. Therefore, it does not affect the real-world security of block ciphers in the near future. However, the attack has caused some experts to insert complexities in the algebraic simplicity of the current AES.

The XSL attack relies on first analyzing the internal design of a cipher then deriving a system of quadratic simultaneous equations. These systems of equations are typically very large, for example 8000 equations with 1600 variables for the 128-bit AES. Several methods for solving such systems are known. In the XSL attack, a specialized algorithm, termed XSL (eXtended Sparse Linearization), is then applied to solve these equations and compute the key.

The attack is well-known and famous for requiring only a handful of known plaintexts to perform. Previous methods of cryptanalysis, such as linear and differential cryptanalysis, often require unrealistically large numbers of known or chosen plaintexts, which make them impossible to realize.