XSL attack
Encyclopedia
In cryptography
, the 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 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 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 recover the key
.
The attack is notable 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.
problem (in the general case) with several applications in cryptography. The XSL attack requires an efficient algorithm for tackling MQ. In 1999, Kipnis and Shamir
showed that a particular public key algorithm—known as the Hidden Field Equations scheme (HFE)—could be reduced to an overdetermined system
of quadratic equations (more equations than unknowns). One technique for solving such systems is linearization, which involves replacing each quadratic term with an independent variable and solving the resultant linear system using an algorithm such as Gaussian elimination
. To succeed, linearization requires enough linearly independent equations (approximately as many as the number of terms). However, for the cryptanalysis of HFE there were too few equations, so Kipnis and Shamir proposed re-linearization, a technique where extra non-linear equations are added after linearization, and the resultant system is solved by a second application of linearization. Re-linearization proved general enough to be applicable to other schemes.
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 monomial
s of a certain degree
. Complexity estimates showed that the XL attack would not work against the equations derived from block ciphers such as AES. However, the systems of equations produced had a special structure, and the XSL algorithm was developed as a refinement of XL which could take advantage of this structure. In XSL, the equations are multiplied only by carefully selected monomials, and several variants have been proposed.
Research into the efficiency of XL and its derivative algorithms remains ongoing (Yang and Chen, 2004).
(Rijndael) and partially also 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 (Biryukov
and De Cannière, 2003), including Camellia
, KHAZAD
, MISTY-1 and KASUMI. Unlike other forms of cryptanalysis, such as differential
and linear cryptanalysis
, only one or two known plaintexts 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:
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." http://www.cosic.esat.kuleuven.ac.be/nessie/forum/read.php?f=1&i=82&t=82 Promptly Courtois answered "It will become your nightmare". However neither any later paper or any actions by the NSA or NIST give any support to this remark by Courtois.
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 disputes their findings. In a paper in the AES 4 Conference (Lecture Notes in Computer Science 3373), Toli and Zanoni proved that the work of Murphy and Robshaw was flawed. At FSE 2007, Chu-Wee Lim and Khoongming Khoo showed that it cannot possibly work as presented.
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 cryptographers 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, pp56–57)
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, the XSL attack is a method of cryptanalysis
Cryptanalysis
Cryptanalysis is the study of methods for obtaining the meaning of encrypted information, without access to the secret information that is normally required to do so. Typically, this involves knowing how the system works and finding a secret key...
for block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s. The attack was first published in 2002 by researchers Nicolas Courtois
Nicolas Courtois
Nicolas Tadeusz Courtois is a cryptographer, a senior lecturer in computer science at University College London.Courtois was one of the co-authors of both the XSL attack against block ciphers such as the Advanced Encryption Standard and the XL system for solving systems of algebraic equations, used...
and Josef Pieprzyk
Josef Pieprzyk
Josef Pieprzyk is a professor at Macquarie University in Sydney, Australia.He has worked on cryptography, in particular the XSL attack. He collaborated in the invention of the LOKI and LOKI97 block ciphers and the HAVAL cryptographic hash function....
. It has caused some controversy as it was claimed to have the potential to break the Advanced Encryption Standard
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
(AES) cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
—also known as Rijndael—faster than an exhaustive search
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
. 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 system of quadratic
Quadratic polynomial
In mathematics, a quadratic polynomial or quadratic is a polynomial of degree two, also called second-order polynomial. That means the exponents of the polynomial's variables are no larger than 2...
simultaneous equations. These systems of equations are typically very large, for example 8000 equations with 1600 variables
Variable (programming)
In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...
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 recover the key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
.
The attack is notable for requiring only a handful of known plaintexts to perform; previous methods of cryptanalysis, such as linear
Linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers...
and differential cryptanalysis
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
, often require unrealistically large numbers of known or chosen plaintexts.
Solving multivariate quadratic equations
Solving multivariate quadratic equations (MQ) over a finite set of numbers is an NP-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
problem (in the general case) with several applications in cryptography. The XSL attack requires an efficient algorithm for tackling MQ. In 1999, Kipnis and Shamir
Adi Shamir
Adi Shamir is an Israeli cryptographer. He is a co-inventor of the RSA algorithm , a co-inventor of the Feige–Fiat–Shamir identification scheme , one of the inventors of differential cryptanalysis and has made numerous contributions to the fields of cryptography and computer...
showed that a particular public key algorithm—known as the Hidden Field Equations scheme (HFE)—could be reduced to an overdetermined system
Overdetermined system
In mathematics, a system of linear equations is considered overdetermined if there are more equations than unknowns. The terminology can be described in terms of the concept of counting constraints. Each unknown can be seen as an available degree of freedom...
of quadratic equations (more equations than unknowns). One technique for solving such systems is linearization, which involves replacing each quadratic term with an independent variable and solving the resultant linear system using an algorithm such as Gaussian elimination
Gaussian elimination
In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations. It can also be used to find the rank of a matrix, to calculate the determinant of a matrix, and to calculate the inverse of an invertible square matrix...
. To succeed, linearization requires enough linearly independent equations (approximately as many as the number of terms). However, for the cryptanalysis of HFE there were too few equations, so Kipnis and Shamir proposed re-linearization, a technique where extra non-linear equations are added after linearization, and the resultant system is solved by a second application of linearization. Re-linearization proved general enough to be applicable to other schemes.
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 monomial
Monomial
In mathematics, in the context of polynomials, the word monomial can have one of two different meanings:*The first is a product of powers of variables, or formally any value obtained by finitely many multiplications of a variable. If only a single variable x is considered, this means that any...
s of a certain degree
Degree (mathematics)
In mathematics, there are several meanings of degree depending on the subject.- Unit of angle :A degree , usually denoted by ° , is a measurement of a plane angle, representing 1⁄360 of a turn...
. Complexity estimates showed that the XL attack would not work against the equations derived from block ciphers such as AES. However, the systems of equations produced had a special structure, and the XSL algorithm was developed as a refinement of XL which could take advantage of this structure. In XSL, the equations are multiplied only by carefully selected monomials, and several variants have been proposed.
Research into the efficiency of XL and its derivative algorithms remains ongoing (Yang and Chen, 2004).
Application to block ciphers
Courtois and Pieprzyk (2002) observed that AESAdvanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
(Rijndael) and partially also Serpent
Serpent (cipher)
Serpent is a symmetric key block cipher which was a finalist in the Advanced Encryption Standard contest, where it came second to Rijndael. Serpent was designed by Ross Anderson, Eli Biham, and Lars Knudsen....
could be expressed as a system of quadratic equations. The variables represent not just the plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
, ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
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
Inverse function
In mathematics, an inverse function is a function that undoes another function: If an input x into the function ƒ produces an output y, then putting y into the inverse function g produces the output x, and vice versa. i.e., ƒ=y, and g=x...
. Subsequently, other ciphers have been studied to see what systems of equations can be produced (Biryukov
Alex Biryukov
Alex Biryukov is a cryptographer, currently an assistant professor at the University of Luxembourg. His notable work includes the design of the stream cipher LEX, as well as the cryptanalysis of numerous cryptographic primitives. In 1998, he developed impossible differential cryptanalysis together...
and De Cannière, 2003), including Camellia
Camellia (cipher)
In cryptography, Camellia is a 128-bit block cipher jointly developed by Mitsubishi and NTT. The cipher has been approved for use by the ISO/IEC, the European Union's NESSIE project and the Japanese CRYPTREC project...
, KHAZAD
KHAZAD
In cryptography, KHAZAD is a block cipher designed by Paulo S. L. M. Barreto together with Vincent Rijmen, one of the designers of the Advanced Encryption Standard . KHAZAD is named after Khazad-dûm, the fictional dwarven realm in the writings of J. R. R. Tolkien...
, MISTY-1 and KASUMI. Unlike other forms of cryptanalysis, such as differential
Differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in an input can affect the resultant difference at the output...
and linear cryptanalysis
Linear cryptanalysis
In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers...
, only one or two known plaintexts 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:
- "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 CoppersmithDon CoppersmithDon Coppersmith is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S-boxes, strengthening them against differential cryptanalysis...
, http://www.schneier.com/crypto-gram-0210.html#8.
In AES 4 Conference, Bonn 2004, one of the inventors of Rijndael, Vincent Rijmen
Vincent Rijmen
Vincent Rijmen is a Belgian cryptographer and one of the two designers of the Rijndael, the Advanced Encryption Standard. Rijmen is also the co-designer of the WHIRLPOOL cryptographic hash function, and the block ciphers Anubis, KHAZAD, Square, NOEKEON and SHARK.In 1993, Rijmen obtained a degree...
, commented, "The XSL attack is not an attack. It is a dream." http://www.cosic.esat.kuleuven.ac.be/nessie/forum/read.php?f=1&i=82&t=82 Promptly Courtois answered "It will become your nightmare". However neither any later paper or any actions by the NSA or NIST give any support to this remark by Courtois.
In 2003, Murphy
Sean Murphy (cryptographer)
Sean Murphy is a cryptographer, currently a professor at Royal Holloway, University of London. He worked on the NESSIE and ECRYPT projects. His notable research includes the cryptanalysis of FEAL and the Advanced Encryption Standard, and the use of stochastic and statistical techniques in...
and Robshaw
Matt Robshaw
Matthew John Barton "Matt" Robshaw is a cryptographer. Formerly a lecturer at Royal Holloway, University of London, Robshaw currently belongs to the cryptography research group at France Telecom's Orange Labs. He also coordinates the Symmetric Techniques Virtual Lab for ECRYPT...
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
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
, 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 disputes their findings. In a paper in the AES 4 Conference (Lecture Notes in Computer Science 3373), Toli and Zanoni proved that the work of Murphy and Robshaw was flawed. At FSE 2007, Chu-Wee Lim and Khoongming Khoo showed that it cannot possibly work as presented.
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
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
, 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 cryptographers have expressed unease at the algebraic simplicity of ciphers like Rijndael. Bruce Schneier
Bruce Schneier
Bruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
and Niels Ferguson
Niels Ferguson
Niels T. Ferguson is a Dutch cryptographer and consultant who currently works for Microsoft. He has worked with others, including Bruce Schneier, designing cryptographic algorithms, testing algorithms and protocols, and writing papers and books...
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, pp56–57)
External links
- Courtois' page on AES
- "Quadratic Cryptanalysis", an explanation of the XSL attack by J. J. G. Savard
- "AES is NOT broken" by T. Moh
- Courtois and Pieprzyk paper on ePrint
- Commentary in the Crypto-gram newsletter: http://www.schneier.com/crypto-gram-0209.html#1, http://www.schneier.com/crypto-gram-0210.html#2, http://www.schneier.com/crypto-gram-0211.html#7.
- An overview of AES and XSL