18
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Dec 17, 2017 at 13:06

2 Answers 2

17
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$
    – J.D.
    Sep 29, 2013 at 18:54
  • 2
    $\begingroup$ @J.D. wouldn't pseudo-random functions work there, too, if indistinguishable from a random oracle or such? $\endgroup$ Sep 29, 2013 at 21:26
  • 2
    $\begingroup$ @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. $\endgroup$
    – J.D.
    Sep 29, 2013 at 21:54
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.