What is the definition of Feistel Cipher?

Question

I know how Feistel Network works, but I want to know the exact definition of "Feistel Cipher" to solve several questions below:

question 1: Is it correct to say DES (Data Encryption Standard) is Feistel Cipher?

Opinion: I think the statement "DES uses Feistel Network" is correct. Also, since the encryption and decryption process is same, except key scheduling, somebody can say that DES is Feistel Cipher. But I think somebody else can say that DES is not a Feistel Cipher since DES has initial and final permutations.

question 2: Does "DES_Encrypt'(M,K1,K2) = DES_Encrypt(M,K1) xor K2" is also Feistel Cipher?

Opinion: I think the statement "The above modified DES uses Feistel structure" is correct. But, since the above modified scheme's encryption and decryption structure are not same, somebody can say that the above modified scheme is not Feistel Cipher.

There can be several options to solve this definitional problem:

1. We call an encryption scheme a Feistel Cipher, if it uses Feistel Network;
2. We call an encryption scheme a Feistel Cipher, if it only use Feistel Network;
3. We call an encryption scheme a Feistel Cipher, if it uses Feistel Network and the encryption and decryption procedure is same, except the key scheduling process.

Which one is correct? Or, are there any other opinions?

I know that this problem is not that important, but I want to make it clear.

Answer 1

According to Definition 7.81 given by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography,

A Feistel cipher is an iterated cipher mapping a $2t$-bit plaintext $(L_0,R_0)$, for $t$-bit blocks $L_0$ and $R_0$, to a ciphertext $(R_r,L_r)$, through an $r$-round process where $r\ge1$.
For $1\le i\le r$, round $i$ maps $(L_{i−1},R_{i−1})\xrightarrow{K_i} (L_i,R_i)$ as follows: $L_i=R_{i−1}$, $R_i=L_{i−1}\oplus f(R_{i−1},K_i)$, where each subkey $K_i$ is derived from the cipher key $K$.
Typically in a Feistel cipher, $r\ge3$ and often is even. The Feistel structure specifically orders the ciphertext output as $(R_r,L_r)$ rather than $(L_r,R_r)$; the blocks are exchanged from their usual order after the last round. Decryption is thereby achieved using the same $r$-round process but with subkeys used in reverse order (...)

On the next page they state, with the contradiction pointed in the question's Q1:

DES is a Feistel cipher (...)
An initial bit permutation (IP) precedes the first round; following the last round, the left and right halves are exchanged and, finally, the resulting string is bit-permuted by the inverse of IP.

---

In Q1: DES is a Feistel cipher, except for IP and IP^-1; that deviation keeps the notable property of a pure Feistel cipher that only the order of subkeys differs for encryption and decryption.

In Q2: the construction is a Feistel cipher, except for the above deviation, and an additional final XOR with $K_2$ on encryption, and correspondingly an additional initial XOR with $K_2$ on decryption; this looses the aforementioned notable property of a pure Feistel cipher, and adds a key-dependent transformation.

I would say the answer to Q1 is yes for Jim Kirk, and no for Mr. Spock; while they could agree on no for Q2. The Captain is on option 3 in the question (perhaps also requiring that any key-dependent transformation is thru the Feistel structure); while the logician sticks to 2 (and wants any deviation to be explicit). Nobody on the deck stands for 1.

Answer 2

The initial and final permutations in DES have no effect on its security, since they are fixed and independent of the key. Their sole purpose was to slightly simplify early hardware DES implementations.

Thus, for all cryptanalytic purposes, DES is a pure Feistel cipher. When studying the security of DES, we can simply assume that the permutations have already been applied to the plaintext and ciphertext blocks, and just consider the core Feistel structure. If we can break DES without the permutations, then we can also equally well break it with them, and vice versa.