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
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 LE0 as the left half of the plain text block and RE0 as the right half of the plain text block. Now, both these halves of the plain text block (LE0 & RE0) undergoes multiple rounds to produce ciphertext block.
In each round, the encryption function is applied on the right half REi of the plaintext block along with the key Ki. The result of this encryption function is then XORed with the left half LEi. The result of XOR function becomes the new right half for next round REi+1. Whereas, the old right half REi becomes the new left half LEi+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:
- The input to the decryption algorithm is a cipher text block produced by the encryption algorithm.
- The sequence of subkeys used in encryption are reversed. The key Kn is used in the first round of decryption, key Kn-1 in the second round of decryption and so on, until the last round occurs where key K1 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 (LD0) and the right half (RD0). Where LD0 = RE16 and RD0 = LE16.
Now as in encryption algorithm, the round function is performed on the right half of cipher block with the key K16 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.RD1 and the RD0 swaps with LD0 and becomes the new left half LD1 for the next round.
- Feistel cipher was based on the structure proposed by Shannon.
- Shannon structure has an alternate implementation of diffusion and confusion to obtain cipher text block.
- Feistel cipher structure has alternate application substitution and permutation on plain text block to obtain cipher text block.
- Feistel block cipher operates on each block independently.
- The encryption and decryption algorithm in Feistel cipher is the same.
- The key used for encryption and decryption is the same but the sequence of application of subkey is reversed.
- During encryption a plain text block undergoes multiple rounds. But the function performed in each round is same.
- Generally, 16 rounds are performed in Feistel cipher.
- Typical block size of Feistel cipher is 64-bit but modern block cipher uses 128-bit block.
- Typical key size of Feistel cipher is 64-bit but modern block cipher has 128-bit key size.
So, this is all about the Feistel block cipher, its structure, design features.