Why is AES not a Feistel cipher?

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?

-
If the operations were not invertible we wouldn't be able to decrypt anything. Read the links in Reid's answer and try to memorize the schematics and what a Feistel network looks like. That's very different from a simple sub-perm network (link also in Reid's answer). A Feistel cipher is a cipher that uses a Feistel structure in its design - AES does not. – rath Sep 28 '13 at 6:36
@rath you would not be able to decrypt anything if the cipher was not augmented with a mode that only requires one way encryption such as CTR mode – Maarten Bodewes Sep 28 '13 at 12:51
@owlstead Good point. [+1] – e-sushi Sep 29 '13 at 7:10
@rath Besides my previous comment, it is very possible to use constructions that are not invertible for a construction that - in total - isn't. As prime example the sub key derivation may well be non-invertible. – Maarten Bodewes Jun 9 at 13:38

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.

-

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.

-

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

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.

-
Unless you created the image yourself, you might credit it to its author. – CodesInChaos Jun 9 at 20:32
combined two separate images from google search results. – Raza Jun 9 at 20:34
Unless you created the images yourself, you might credit it to its authors. – Maarten Bodewes Jun 10 at 13:18
I think i already answered this comment – Raza Jun 10 at 15:16
• AES does not use Feistel structure. Instead, each full round consists of four separate function: byte substitution, permutation, arithmetic operations over a finite field, and XOR with a key.

From cryptography and network security principles and practices 5th edition Chapter 5 page 148

-

protected by e-sushi♦Jun 9 at 20:56

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?