Why was the winner of the AES competition not a Feistel cipher?

The winner of the AES competition has a structure that does not qualify as a Feistel cipher, as explained in answers to this recent question.

However, most many of the AES candidates, and all 3 out of 4 some other finalists (Twofish, MARS) are Feistel ciphers, if we define that as a cipher transforming a block of data using a number of rounds which each can be expressed as:

• split all the bits of the block $B_j$ into two disjoint portions $L_j$ and $R_j$ (typically of equal size);
• compute some (typically round-dependent) function of $R_j$ and key with output $F_j$ of same width as $L_j$;
• compute $L_j'=L_j\oplus F_j$ where $\oplus$ is binary addition with removal of some carry bits (e.g. exclusive-OR, where all carry bits are removed);
• recombine bits of $L_j'$ and the unmodified $R_j$ into a new block $B_{j+1}$.

Note: Serpent and RC6 can not be put in this framework (thanks to @Reid and @J.D. for pointing that). Neither can Rijndael/AES.

At the time of the AES competition, Feistel ciphers already enjoyed a well understood theory. In particular DES was among them, and essentially unbroken in practice except for its small key and block size. It would seem that proposing anything else than a Feistel cipher would be an uphill battle.

Yet, Rijndael won the AES competion, and does not fall under the above definition. Did a desirable characteristic of Rijndael made it preferred to the other candidates despite the apparent drawback of using a relatively untested structure? And if that characteristic could not be matched by a Feistel cipher, why?

-
Serpent is a substitution-permutation network, not a Feistel cipher. –  Reid Sep 29 '13 at 17:47
@Reid and fgrieu - wasn't sure… killed my comment instantly. Next up: a slap in my face for wrong flagging. Sorry for the mess guys. Sure didn't want to step on any toes or something. –  e-sushi Sep 29 '13 at 20:05
@Reid and fgrieu - also I would argue RC6 and Mars are not Feistel ciphers, but rather are more 'Feistel-like'. Mars because it uses overlapping operations from different Groups when mixing one part of the state with a function of another part, and RC6 because the mixing functions include another sort of non-linear component (the data dependent rotations). –  J.D. Sep 29 '13 at 20:19
We are getting into mushy semantics here, but I would argue that the classic Feistel structure requires linear mixing (i.e. $L_i = R_{i-1}+F_{K_i}(L_{i-1})$ where "+" is a linear operation in some Group that mixes the right half of the state with a function of the left half and the round key). But this is not the case with Mars because it uses operations from different Groups (also, unkeyed rounds, which are weird). Thus some round functions are mixed non-linearly with the state, no matter which Group you try to express the cipher in. –  J.D. Sep 29 '13 at 20:49
@J.D: I see your point that if I rewrite MARS in my definition of Feistel, the ⊕ group operations that I use are not the same at each round, and the resulting cipher has much more rounds than claimed in the normal description of MARS. –  fgrieu Sep 29 '13 at 21:07

DES actually demonstrated that a Feistel structure was not a guarantee against attacks. In "academic" terms, DES is broken by both differential and linear cryptanalysis, because they require, respectively, $2^{47}$ chosen plaintexts and $2^{43}$ known plaintexts, whereas the DES key is (effectively) 56 bits. Of course, for practical attacks, we would brute force the key: computing the function $2^k$ times is vastly easier than obtaining $2^k$ known plaintext/ciphertext pairs (or, even worse, chosen plaintext/ciphertext pairs). But in the usual "academic" evaluation of security, both linear and differential cryptanalysis count as breaks.

Luby and Rackoff have demonstrated in 1988 that given "perfect" round functions, a four-round Feistel structure is secure. However, this proof has two practical issues:

• It is relative to the output size of the round function, i.e. 32 bits for a 64-bit block cipher. For 128-bit security, blocks have to be 256-bit wide for the proof to actually apply; but the AES call for candidates requested 256-bit security with 128-bit blocks, not the other way round.

• DES has amply demonstrated that concrete round functions cannot be assumed to be perfect.

So while the security provided by a Feistel structure was already quite well understood at that time (around 1997, when AES candidates were being designed), it was also quite known to be "suboptimal" in the following sense: to get the most out of the existing security proofs, you had to go to impractical block sizes or number of rounds. Indeed, many researchers were dissatisfied with the Feistel structure, and eager to explore new structures. The AES competition was at the right time to become a test bed for such novel designs, and the accumulated research has shown substitution-permutation networks (as used by Rijndael) to be valid competitors to Feistel structures.

-
Another 'practical' problem with the Luby & Rackoff proof is that the construction requires 4 different round functions selected uniformly at random from the set of all functions from $\{0,1\}^{\frac{b}{2}}$ to $\{0,1\}^{\frac{b}{2}}$ -- which requires a preposterous amount of key material for blocks of usable size. Even worse, it would be more efficient (in that you could actually encrypt more text) to just use the huge key as a provably secure one time pad rather than a provably secure block cipher. –  J.D. Sep 29 '13 at 18:54
@J.D. wouldn't pseudo-random functions work there, too, if indistinguishable from a random oracle or such? –  Paŭlo Ebermann Sep 29 '13 at 21:26
@PaŭloEbermann - yes, a pseudo random function would work (though not against an information theoretic opponent, only a computationally bounded opponent). Sadly, the efficiency point remains -- if you have a cryptographically secure PRNG, then it would be more efficient to just use it to directly encrypt the data. If it isn't cryptographically secure (e.g. the DES round function), then the proof does not apply, and you have to rely on heuristic arguments and lots of additional rounds. –  J.D. Sep 29 '13 at 21:54

As a page at ibm.com indicates, there could have been a bit of a "contra" attitude against Feistel ciphers thanks to DES having seen the first breaks in it's security etc.

Down with the Feistel structure!

In most ciphers, the round transformation has the well-known Feistel structure. In this structure typically part of the bits of the intermediate State are simply transposed unchanged to another position. (An example of this linear kind of structure are those tables we discussed back in the DES discussion that substitute bits by a fixed tabular means.) The round transformation of Rijndael does not have this venerable Feistel structure. Instead, the round transformation is composed of three distinct invertible uniform transformations, called layers. ("Uniform" here means that every bit of the State is treated in a similar way.)

The linear mixing layer guarantees high diffusion over multiple rounds. The non-linear layer uses parallel application of S-boxes that have the desired (hence optimum) worst-case nonlinearity properties. The S-boxes are non-linear. That's the key conceptual difference between DES and Rijndael…

So, I guess one of the reasons they chose a non-Feistel cipher could well have been that they wanted to guarantee higher security through higher diffusion etc. while hoping that — in case Feistel ciphers should collapse sooner than expected — the next crypto they were about to recommend wouldn't automatically join in and break down too.

Serpent for example was designed so that all operations can be executed in parallel, using 32 1-bit slices. While this maximizes parallelism, it also allowed immediate use of the extensive cryptanalysis work performed on DES. A good reason not to give Serpent that final go and prefer "something else" (most probably because Serpent's origins were too close to a theoretically broken Feistel — DES).

This would also go in canon with what @thomas-pornin mentioned in the first lines of his great answer.

-