XSL on serpent and rijndael - which is most affected?

Question

So I've often looked at serpent and thought it was a very strong contender in AES. Not so long ago I was looking for evidence as to why it didn't beat rijndael. So far, the closest I've got answering that is this:

The 32 rounds means that Serpent has a higher security margin than Rijndael; however, Rijndael with 10 rounds is faster and easier to implement for small blocks. Hence, Rijndael was selected as the winner in the AES competition.

Which is from the wikipedia article and is marked citation needed. So further down the page I came across this other interesting piece of information:

The XSL attack, if effective, would weaken Serpent (though not as much as it would weaken Rijndael, which became AES). However, many cryptanalysts believe that once implementation considerations are taken into account the XSL attack would be more expensive than a brute force attack.

Also citation needed. So my question is now - to what extent is this true? Is Serpent more resistant to XSL attacks? Given that XSL works by representing a cipher as a system of equations, isn't it then only a matter of finding an efficient way to solve a particular set of equations? I.e. isn't the very fact an algorithm can be represented as a set of equations the key issue, or are there certain sets of equations that are provably harder to solve?

(I'm really interested in working out which has the better security margin, but given these statements I think the first step for me is to clarify the XSL issue).

Answer 1

First, from a direct witness of the events (i.e. myself): Serpent was indeed felt as "too slow" when compared with Rijndael, by a factor of 2 to 3. The performance of Rijndael was not the best there was on a PC (RC6 was faster) but it wasn't abysmal on any platform, especially 8-bit smartcard (contrary to, say, RC6). Serpent performance was consistently lower than Rijndael's. See this page for benchmarks of the AES candidates on various software platforms at the time of the competition.

XSL attacks were discovered in 2002, hence after the choice of Rijndael as the AES; therefore, they could not have been a parameter in the choice.

In their paper, Courtois and Pierprzyk "show" that AES (i.e. Rijndael) with a 256-bit key, and Serpent with a 192-bit or 256-bit key, are "broken", which means that the attack ought to recover the key with less work than the CPU needed to evaluate the block cipher $2^{256}$ times (resp. $2^{192}$). They certainly did not go below $2^{128}$, so the break is only theoretical and unverifiable. That's part of the problem, too: the analysis is based on a number of probabilistic assumptions on an equation-solving algorithm in a situation where it is out of the question to actually run it on existing hardware. So XSL attacks are an effective break only insofar as their description is intellectually convincing. Don Coppersmith has publicly expressed that he was not convinced. And when Coppersmith says that your research stinks, it is time to worry.

Anyway, that an algorithm can be represented as a set of multivariate polynomial equations is not the key issue: any algorithm which can be implemented as a circuit is amenable to such a representation (e.g. because a NAND of $x$ and $y$ is equal to $1+xy$, when computing modulo 2, and every boolean operator can be built out of NAND gates). Generally speaking, solving a set of multivariate polynomial equations is hard. Courtois and Pieprzyk argue that the specific structure of the equations in the case of Rijndael and Serpent can be exploited into running a dedicated variant of Shamir's re-linearization solving algorithm fast enough to be considered, academically speaking, as a "break".

The interesting part in XSL attacks is that resistance grows with the number of rounds, but not exponentially, contrary to more mundane differential or linear cryptanalysis. The bad part of XSL is that most cryptographers do not believe that it works as advertised, or at all. On the other hands, most think that Serpent is a more "conservative" design than AES, with a correspondingly "higher" security margin (but there is no really scientific way of quantifying such a "margin" so these are really all fuzzy feelings).

On the matter of attacks of debatable success, you could consider cache timing attacks, which are not an issue with the algorithm per se, but with its implementation. At least that attack could be demonstrated in lab conditions (the debate being whether the lab conditions have any similarity with whatever could occur in the field). Serpent is "naturally" immune to such attacks, because the normal implementations on software platforms will not use any table at all.