A recent paper by Nicolas Courtois and Josef Pieprzyk, made available in preprint form, caused considerable excitement in the world of cryptography when it appeared in the fall of 2002. Most of the comments below simply echo what is stated in the paper, but perhaps I manage to explain one point with slightly greater explicitness.
This paper concerned a cryptanalytic method called the XSL attack. In this paper, ciphers like Rijndael were referred to as XSL ciphers, because their rounds are composed of the XOR of key material, a nonlinear substitution provided by an S-box, and a linear diffusion stage. The attack was presented in a form adapted to that kind of cipher, but the principle could still be applied to ciphers based on Feistel rounds instead; the paper noted that this had been addressed in earlier work.
This attack requires finding equations which are almost certainly true which relate the input and output bits from an S-box, and which are at most quadratic in degree. In the paper, the equations are shown in the form of sums of terms that are either individual input or output bits, or the product of an input bit and an output bit. In modulo-2 arithmetic, addition is XOR, and multiplication is AND.
Thus, one doesn't see the square of any bit in the equations, but one does see the products of two bits. In the example of equations for the Rijndael S-box, all the products of two bits are the product of an input bit with an output bit; but in the example of a toy cipher, the products involve two input bits or two output bits in some cases.
Having quadratic equations that describe the S-box itself is one thing. Once one is dealing even with two rounds of the cipher, wouldn't one now be dealing with polynomials in the fourth degree, and with three rounds, equations of the sixth degree? Two rounds would involve the XOR of three subkeys, with two S-boxes between them, and also some linear operations. What would be involved in finding quadratic equations in this case?
One of the things to remember is that modulo-2 arithmetic has the distributive property, like ordinary arithmetic. Thus, a AND (b XOR c) is equivalent to (a AND b) XOR (a AND c). So, the fact that an input bit involved in a product is the XOR of a number of previous input bits and subkey bits does not in itself stop the equations from remaining quadratic.
In order to express an equation in terms of subkey bits and inputs and outputs from the overall cipher, however, one does have to solve the equations available, by finding a set of them which refer to the same group of bits in the area between the two S-boxes. Straightforwards substitution would lead to fourth-degree equations after two S-boxes, sixth-degree equations after three S-boxes, and so on, or even worse, since the path through the cipher could easily be a zigzag one.
Since intermediate round results are not available, equations involving them are only useful if those equations can be combined in some way to form equations that deal with the input and output, which are visible, and the subkeys, which are what it is desired to determine. This is the task which, although an NP-hard problem in the general case, is simplified if a sufficiently large set of genuinely independent equations are available for the S-box in use. Even on the toy cipher used as an example in the paper, computer simulations were needed to solve the equations, but this was carried out to numerous rounds, showing that the difficulty of breaking such ciphers may not grow as quickly with the number of rounds as previously believed.
If one has just enough such equations to describe the S-box, simplifying them in a manner that is useful for determining the subkeys of a cipher from known plaintext and ciphertext is a difficult problem, but the important discovery which led to the attack is that if one has a greater number of such equations available, it becomes easier to find possible solutions. An attack was found against Serpent because its S-boxes had only 16 elements, and one was found against Rijndael because its S-box, although highly resistant to previously known forms of attack, had a special mathematical form. While the attacks were not sufficient to overturn the security of these ciphers, they did indicate that increasing the number of rounds of such ciphers did not cause the security of the cipher to increase as quickly as had previously been believed.
The paper also notes that the attack against Rijndael only approaches being practical because the key schedule of Rijndael also involves operations that lead to equations of a similar form. Thus, either a more non-linear key schedule, or different, more random, S-boxes, would be sufficient to protect a cipher against such an attack at present. But the paper notes the possibility of extending the attack to consider cubic equations; since it is a novel type of attack, apparently considerably more powerful than previous techniques, it is reasonable to suspect it may eventually lead to attacks with broader applicability.
Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page