Why is AES not a Feistel cipher?

Question

I am studying for an exam right now. And I wanted to make sure I got this point correct.

AES is not a Feistel cipher because the operations in AES are not invertible.

Is the above statement correct? If not, why isn't it a Feistel cipher?

Answer 1

Well, AES is not a Feistel cipher because it's a substitution-permutation network instead. If I were taking a test that asked me why AES was not a Feistel cipher, this would be my argument: namely, that the structure of substitution-permutation networks is fundamentally different from that of Feistel networks. (Here one could elaborate on invertibility and other differences.)

That said, your statement is not correct. In a Feistel cipher, the round function is not necessarily invertible (DES's round function is not), but in AES, like any substitution-permutation network, the rounds are invertible. This is a property of the construction itself.

Answer 2

By definition, a Feistel network uses a series of rounds that split the input block into two sides, uses one side to permute the other side, then swaps the sides. As always, Wikipedia has a nice diagram.

AES doesn't do this. Performing a round necessarily permutes the entire state. Each round consists of the SubBytes, ShiftRows, MixColumns, and AddRoundKey steps, none of which behave in a Feistel network-like manner:

• SubBytes performs byte-wise substitution from a constant table, no byte's value influences another byte's permuted value.
• ShiftRows permutes 4-byte words at a time using only those 4 bytes, no byte from another word influences their permuted output.
• MixColumns permutes 4-byte words at a time using only those 4 bytes, no byte from another word influences their permuted output.
• AddRoundKey is a permutation using the derived round key, no byte's value influences another byte's permuted value.

So only the ShiftRows and MixColumns steps even allow a byte to influence the permutation of any other bytes in the state, and in both of those steps a given byte only influences the permutation of other bytes when it itself is also being permuted.

None of that matches the "split the block into A and B and use A to permute B" style of a Feistel network.

Answer 3

The simple answer is "Because its an SPN cipher".

What is difference between Feistel and SPN?

SPN operates on whole data in one round, where as Feistel divides data into N parts where N>=2 , then operate upon X parts where 0

Image Sources: FEISTEL, SPN

In balanced, data is divided in Two parts i.e N = 2, and X=1 (example is camellia cipher) In Unbalanced, data is divided in more than two parts, i.e N > 2, (example is SMS4 cipher)

Now talking about invertible issue.

SPN has to be invertible, otherwise decryption will not be possible. where as in Feistel cipher, the F function can be invertible or non-invertible. And you will still be able to get encryption and decryption.

Another beauty of Feistel Cipher is that code for Encryption and Decryption is same, you only need to use the round keys in reverse order. (even if your F function is invertible, you need not to write its inversion in the code)

One more point to note is, in Feistel your F function can be a simple SPN.