Cryptanalysis of Modern Ciphers

Cryptanalysis of Modern Ciphers

Introduction:

I have studied the security of specific kind of ciphers categorized as XSL Ciphers (e.g Rijndael and Serpent). I have focused mainly on studying the Algebraic properties of S-boxes in AES ciphers and summarize how they can be used to describe it as an overdefined system of algebraic equations which are true with probability 1. Then briefly describe an attack on these kinds of ciphers known as XSL attack (Quadratic Cryptanalysis) which uses the sparsity of these equations and their specific structure.

XSL ciphers:

XSL ciphers are restricted class of Substitution-Affine ciphers. Their rounds are composed of the XOR of key material, a nonlinear substitution provided by an S-box, and a linear diffusion stage.

Before we can start looking into the algebraic properties of S-boxes in Rijndael and Serpent, which are exploited by XSL attack, I will give a brief summary of both these ciphers.

Description of Rijndael:

Rijndael encryption routine consists of 10..14 rounds. All rounds in succession are similar. The plaintext is fed through an XOR function, against a round key, of 128 - 256 bits. The bits of key material are fed into the side of XOR routines. These bytes are then utilized as a mapping index, for identical S-boxes, which maps inputs of 8 bits to outputs of 8 bits. The arrangement of bytes is then altered in a particular order. These bytes are then mixed via a linear function grouped in four.

Description of Serpent:

Serpent is a 32-round SP-network operating on four 32-bit words, thus giving a block size of 128 bits. The key length is 128, 192 or 256 bits. The S-boxes consists of 4-bit permutations each with 4-bit input and 4-bit output. The cipher consists of the following steps:

- An initial permutation of IP

- 32 rounds, each consisting of a key mixing operation, a pass through S-boxes, and (in all but the last round) a linear transformation. In the last round, this linear transformation is replaced by an additional key mixing operation.

- A final permutation of FP

S-Boxes and Overdefined Algebraic Equations:

The only non-linear part of XSL ciphers are the S-boxes. The paper by Courtois and Pieprzyk [1] describes that, for Rijndael and Serpent, for very different reasons a great number of implicit multivariate quadratic equations exist.

For a specific degree of equations (usually d = 2), if ‘r’ number of such equations exists, and this number ‘r’ is much bigger than the output bits of S-boxes, then the system is considered as overdefined. Another important factor is the number of monomials ‘t’ that appear in those equations. If ‘r’ is close to ‘t’, then most of the terms can be eliminated by linear elimination, and obtain simpler equations that are sparse and maybe even linear. This is a good check for measuring the quality of the system by calculating the ratio t/r. If it is close to 1 then S-box is considered to be bad. This means systems with both big values of ‘r’ (overdefined) and smaller values of ‘t’ (sparse) are considered bad.

Rijndael S-box Properties:

Courtois and Pieprzyk have described in their paper [1] that for Rijndael S-box, if x is always different than 0, then there are 24 linearly independent quadratic equations. For one S-box the probability of this 24th equation to be true is 255/256. So the probability that it is true for all S-boxes in the execution of Rijndael is very high. So if the attack uses only one executions of the cipher then we can assume r = 24, otherwise we have r = 23.

One interesting thing here is the truth probability of 24th equation. If we apply this probability to all S-boxes then it comes out to be:

1/2 for 128-bit

1/9 for 256-bit

It the attack works much better on all 24 equations, then all are ussally used, with the attack iterated between 2 to 9 times. If the iterations range from 1-2, then set r = 24, otherwise set r = 23.

Serpent S-box Properties:

Serpent gives an overdefined system of multivariate equations because of smaller S-box sizes. Serpent has only 4-bit S-boxes, so we can write it as a 16 X 37 matrix containing in each row the values of t = 37 monomials for each of the 16 possible entries. So this will give atleast 21 quadratic equations for each S-box. This is very overdefined system where t/r ratio is approximately 1.75.

MQ attack on XSL Ciphers:

As we have shown above, in the case of Rijndael and Serpent, their S-boxes can be described in terms of a system of multivariate quadratic equations. So the cryptanalysis of these ciphers can be written as a problem of solving this system of equations.

These system of equations are typically very large, for example to recover a 128-bit Rijndael key from a single plaintext, you can write the problem as a system of 8000 quadratic equations, accompanied by 1600 binary unknowns. This ideology is that of displaying Rijndael as an over defined multivariate quadratic system of equations. So, a practical method for solving these equations would break these ciphers.

Solving with XL:

A paper was published by Shamir proposed an attack called XL, that seemingly solves this system of equations in sub-exponential time. This technique is known as 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. With this in mind, the security of ciphers, like Rijndael, would not see exponential growth as the number of rounds is increased.

But practically the XL algorithm fails on solving MQ equations for cipher like Rijndael.

XSL attack:

Rijndael’s rendered system has no random nature, but is an overdefined structure. With this in mind, Courtois and Pieprzyk came up with a new and improved class of attack, based on XL algorithm, for solving this system of equations more efficiently. It adapts to the special algebraic properties of Rijndael and Serpent as we saw above.

As we have already learned that AES ciphers like Rijndael and Serpent could be expressed as not only a system of overdefined quadratic equations, but sparse as well. This attack uses the sparsity of the equations to solve them more effieciently then XL algorithm. The way it works is an S-box of an XSL cipher, called “active S-box”, which has only a small number of monomials in the equation are multiplied by one of “t” monomials existing for some other S-box, called “passive S-boxes”. This will give rise to a new set of equations. Since it takes into consideration executions of the cipher, so S will be equal to:

The critical parameter in this attack is P, in this attack each equation of “active S-box” is multiplied by all possible terms for all subsets of (P-1) other “passive S-boxes”. This attack is designed in such a way that, for bigger values of P we will obtain something which is very similar to XL attack. But due to the special structure of the equation, a much smaller P should be sufficient.

The total number of equations generated by this method is:

The total number of terms in these equations will be about:

The attack described by Courtois and Pieprzyk also mentions that in order to generate equations which does not have any linear dependency, while multiplying an “active” equation one had to restrict to only one of the monomials for some “passive” S-box of the system, and also add the equations containing products of several “active” S-boxes. This seems to remove any obvious linear dependencies. This also reduces the number of equations in the first part of XSL to:

Now, some new equations are introduced into the system so it can have one unique solution. These equations are constructed in a way that they can be multiplied by many terms, and still they can be written with the same T monomials. These equations are written by eliminating all the key variables and are of the following form:

We can get such equations. Each of these equations, called “active equations”, will be multiplied by products of terms for some (P-1) “passive S-boxes”. Terms for a few neighboring S-boxes (that have common variables with the active equations) are excluded. As we already noted earlier one only needs to generate a part of these equations, the remaining have to be linearly dependent. So the number of new equations is about:

The variables represent not just the plaintext, ciphertext and key bits, but also various intermediate values within the algorithm. The S-box of Rijndael seems especially vulnerable to this type of analysis as it is based on the algebrically simple inverse function. The interesting thing here is unlike other forms of cryptanalysis, such as differential and linear cryptanalysis, only one or two known plaintext are required in this attack.

An optimistic evaluation by Courtois and Pieprzyk shows that the complexity of solving these equations is a polynomial in the block size and the number of rounds. Which basically means the security of XSL-ciphers will not grow exponentially with the number of rounds.

The Consequence of XSL Attack:

A very optimistic evaluation by Courtois and Pieprzyk estimates that the XSL attack might be able to break Rijndael 256-bits and Serpent 192 and 256 bits. But no one is yet able to prove that this analysis is correct, a lot of renowned cryptographers have pointed out various problems in the theory of XSL attack. But the problem is even though we can’t prove that an attack exists, we can’t disprove it also.

Even though the practicality of an XSL attack on AES ciphers like Rijndael and Serpent is very low as the resources required are still huge, still some cryptographers have expressed unease at the algebraic simplicity of these ciphers. It is enough justification to be skeptical as algorithm design hasn’t been extensively approached from this angle.

The following quote from Bruce Schneier and Niels Ferguson shows this concern:

"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."

References:

1. Nicolas T. Courtois and Josef Pieprzyk, “Cryptanalysis of Block Ciphers with Overdefined Systems of Equations”. Available at:
2. Nicolas Courtois, Alexander Klimov, Jacques Patarin, Adi Shamir: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations.
3. Joan Daemen, Vincent Rijmen: AES Proposal Rijndael
4. Ross Anderson, Eli Biham, Lars Knudsen: Serpent: A proposal for the Advanced Encryption Standard