Feistel Block Cipher

Feistel block cipher is a structure used to derive many symmetric block ciphers such as DES which we have discussed in our previous content. Feistel cipher proposed a structure which implements substitution and permutation alternately to obtain cipher text from the pain text and vice-versa.

In the Feistel block cipher, each block has to undergo many rounds where each round has the same function. In this context, we will discuss the structure proposed by Feistel for developing the block ciphers.

Content: Feistel Block Cipher

1. What is Feistel Block Cipher?
2. Feistel Cipher Structure
3. Feistel Decryption Algorithm
4. Key Takeaways

What is Feistel Cipher?

Feistel cipher is a structure proposed by a Horst Feistel which was considered while developing many symmetric block ciphers. Actually, the structure proposed by Feistel is based on the Shannon structure which was proposed in 1945. The Shannon structure shows the implementation of confusion and diffusion alternately.

Confusion fabricates a complex relation between the cipher text and encryption key by implementing a complex substitution algorithm. Whereas, the diffusion fabricates a complex relation between plain text and cipher text by implementing more complex permutation algorithm.

The Shannon structure was successful in achieving a more complex block cipher and thus confusion and diffusion were adopted by the Feistel structure.

Feistel cipher proposed the structure that alternately implements substitution and permutation. Substitution is implemented by replacing the elements of plain text or the set of elements of plain text by the element of cipher text or set of elements of cipher text.

A permutation is implemented by changing the order of elements of the plain text. No element here is replaced by any other element, only the order of elements is changed. Now, let us proceed towards the structure of Feistel cipher.

Feistel Cipher Structure

To understand the Feistel cipher in a better way observe the figure below:

Step 1: The plain text is divided into the blocks of a fixed size and only one block is processed at a time. So, the input to encryption algorithm is a plain text block and a key K.

Step 2: The plain text block is divided into two equal halves which we will denote as a LE₀ as the left half of the plain text block and RE₀ as the right half of the plain text block. Now, both these halves of the plain text block (LE₀ & RE₀) undergoes multiple rounds to produce ciphertext block.

In each round, the encryption function is applied on the right half RE_i of the plaintext block along with the key K_i. The result of this encryption function is then XORed with the left half LE_i. The result of XOR function becomes the new right half for next round RE_i+1. Whereas, the old right half RE_i becomes the new left half LE_i+1 for the next round as you can see in the figure above.

Each round executes the same function. In each round initially, a substitution function is implemented by applying the round function or the encryption function on the right half of the plain text block. The result of this round function is XORed by the with the left half of the block. After this substitution function, a permutation function is implemented by swapping the two halves and the result of this permutation is provided to the next round.

This is how Feistel cipher structure presents the application of substitution and permutation alternately which is similar to the Shannon structure.

The design features of Feistel cipher that are considered while implementing any block cipher are as follow:

• Block Size
  The block cipher is considered more secure if the block size is larger. But the larger block size can reduce the execution speed of encryption and decryption. Generally, the block size of a block cipher is of 64-bit. But, the modern-day block cipher such as AES has 128-bit block size.
• Key Size
  The security of block cipher increases with the increasing key size. But the large key size may decrease the speed of encryption and decryption. Earlier the key of 64-bit was considered to adequate. But the modern cipher uses a key of size 128-bit.
• Number of rounds
  The number of rounds also increases the security of the block cipher. More are the number of rounds more complex is the cipher.
• Subkey generation function
  More the subkey generation function is complex, difficult it is for a cryptanalyst to crack it.
• Round Function
  Complex round function enhances the security of the block cipher.
• Fast Software Encryption/Decryption
  The block cipher is implemented in a software application to achieve better execution speed.
• Easy Analysis
  The block cipher algorithm should be easy to analyze because it would ease in analyzing the cryptanalytic weakness and develop more strength in the algorithm.
  

Feistel Decryption Algorithm

Feistel Cipher structure does not have a different algorithm for decryption. The encryption and decryption function proposed by Feistel cipher are same with some rules which are as follows:

1. The input to the decryption algorithm is a cipher text block produced by the encryption algorithm.
2. The sequence of subkeys used in encryption are reversed. The key K_n is used in the first round of decryption, key K_n-1 in the second round of decryption and so on, until the last round occurs where key K₁ is used.

To understand the structure of decryption, look at the figure below:

As you can observe in the figure above the cipher text block has two halves left half (LD₀) and the right half (RD₀). Where LD₀ = RE₁₆ and RD₀ = LE_16.

Now as in encryption algorithm, the round function is performed on the right half of cipher block with the key K₁₆ and the result of the round function is XORed with the left half of the cipher text block.

The output of the XOR function is now considered as new right half i.e.RD₁ and the RD₀ swaps with LD₀ and becomes the new left half LD₁ for the next round.

Each round has the same function and after the fixed number of rounds, the plain text block is obtained.

Key Takeaways

So, this is all about the Feistel block cipher, its structure, design features.