# XSL on serpent and rijndael - which is most affected?

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

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