Substitution-permutation networks and Feistel networks – Block Ciphers and Their Modes of Operation
14.2.5 Substitution-permutation networks and Feistel networks
Modern block ciphers are often constructed as iterated functions, where a so-called round function fk : {0,1}b →{0,1}b is repeatedly applied on the plaintext m, with varying round keys k1,k2,…,kr. More formally, we can write this process as
or even
where ○ stands for the composition of functions. Figure 14.3 visualizes this process.
Figure 14.3: Working principle of an iterated block cipher
Here, in each of the r rounds, a different round key ki is derived from k and used as a parameter for the round function. The process of deriving the round keys from k is called key scheduling. As the block cipher may be written as the composition of the round functions, each fki must be an invertible function. We therefore model the round function in an iterated block cipher as a strong pseudorandom permutation.
Note that in order to build the decryption function dk, one needs not only to invert the round function but also to apply the round keys in reverse order.
This construction can be efficiently implemented in software because once the round function is implemented, the block cipher is realized by a loop with r iterations.
In order to achieve both confusion and diffusion, the round function should contain a substitution part S (also called an S-Box) and a permutation part P (sometimes called a P-box). Therefore, this construction principle is also called a substitution-permutation network.
The older Data Encryption Standard (DES) algorithm, developed in the 1970s by Horst Feistel of IBM, was the dominating block cipher in the 20th century. Its round function f also contains S-boxes and P-boxes, but it is not an iterated block cipher, because the round function does not act on the complete plaintext, but only on its right half R.
More precisely, let Li and Ri be the left and right halves of the plaintext after i rounds, respectively, then after the next encryption round, the left and right halves are given by
where ki is the i−th round key. This construction is called a Feistel network (see Figure 14.4).
Figure 14.4: Three rounds of a Feistel network
Remarkably, in a Feistel network, the round function does not have to be invertible, because we can solve the equations above for Li and Ri, provided we know the round key ki:
Thus, we can reverse one round of encryption (and therefore decrypt the complete cipher) without having to use the inverse function of the round function. The DES algorithm therefore uses a non-invertible round function: each of its eight S-boxes maps six input bits onto four output bits. We will have to say more on the history of the DES algorithm and its S-boxes shortly.
The DES algorithm has a block length of 64 bits and consists of 16 rounds. Technically, a DES key is 64 bits long, but, allegedly by the intervention of the NSA, this was artificially shortened to 56 bits by making every eighth key bit a parity bit. Apart from an exhaustive key search, there have never been any practically relevant cryptographic attacks on the DES, including differential [32] and linear cryptanalysis [112]. Still, because of the short key length, already in the 1990s one had to resort to the so-called Triple-DES or 3DES, where the DES algorithm is applied three times on the plaintext with three independent 56-bit keys k1,k2,k3. For reasons of backward compatibility, the exact formula is
Naturally, this approach does not only triple the key length, but also the computation time. Moreover, the design of the DES algorithm proved to be not efficient enough when encrypting large amounts of data or when being used on platforms with limited resources. Therefore, by the turn of the century, the need for a successor to the DES algorithm became apparent. This successor was called the Advanced Encryption Standard (AES).