Traditional Block Cipher Structure- Fiestel Structure

Several important symmetric block encryption algorithms in current use are based on a structure referred to as a Feistel block cipher. For that reason, it is important to examine the design principles of the Feistel cipher.

A block cipher operates on a plaintext block of $n$ bits to produce a ciphertext block of $n$ bits. There are $2^n$ possible different plaintext blocks and, for the encryption to be reversible (i.e., for decryption to be possible), each must produce a unique ciphertext block. Such a transformation is called reversible, or nonsingular. The following examples illustrate nonsingular and singular transformations for $n = 2.$   There are $2^n!$ reversible mappings.

Figure 4.2 illustrates the logic of a general substitution cipher for $n = 4$. A 4-bit input produces one of 16 possible input states, which is mapped by the substitution cipher into a unique one of 16 possible output states, each of which is represented by 4 ciphertext bits. The encryption and decryption mappings can be defined by a tabulation, as shown in Table 4.1. This is the most general form of block cipher and can be used to define any reversible mapping between plaintext and ciphertext. Feistel refers to this as the ideal block cipher, because it allows for the maximum number of possible encryption mappings from the plaintext block .

(Pic Courtesy: Cryptography and Network Security :William stallings )

But there is a practical problem with the ideal block cipher. If a small block size, such as $n = 4$, is used, then the system is equivalent to a classical substitution cipher. Such systems, as we have seen, are vulnerable to a statistical analysis of the plaintext. This weakness is not inherent in the use of a substitution cipher but rather results from the use of a small block size. If $n$ is sufficiently large and an arbitrary reversible substitution between plaintext and ciphertext is allowed, then the statistical characteristics of the source plaintext are masked to such an extent that this type of cryptanalysis is infeasible.

An arbitrary reversible substitution cipher (the ideal block cipher) for a large block size is not practical, however, from an implementation and performance point of view. For such a transformation, the mapping itself constitutes the key. Consider again Table 4.1, which defines one particular reversible mapping from plaintext to ciphertext for $n = 4$. The mapping can be defined by the entries in the second column, which show the value of the ciphertext for each plaintext block. This, in essence, is the key that determines the specific mapping from among all possible mappings. In this case, using this straightforward method of defining the key, the required key length is $(4 bits) * (16 rows) = 64 bits$. In general, for an $n$-bit ideal block cipher, the length of the key defined in this fashion is $n * 2^n$ bits. For a 64-bit block, which is a desirable length to thwart statistical attacks, the required key length is $64 * 2^{64} = 2^{70} ≈ 10^{21}$ bits.

In considering these difficulties, Feistel points out that what is needed is an approximation to the ideal block cipher system for large $n$, built up out of components that are easily realizable. But before turning to Feistel’s approach, let us make one other observation. We could use the general block substitution cipher but, to make its implementation tractable, confine ourselves to a subset of the $2^n!$ possible reversible mappings. For example, suppose we define the mapping in terms of a set of linear equations. In the case of $n = 4$, we have

$y_1 = k_{11}x_1 + k_{12}x_2 + k_{13}x_3 + k_{14}x_4 $

$y_2 = k_{21}x_1 + k_{22}x_2 + k_{23}x_3 + k_{24}x_4 $

$y_3 = k_{31}x_1 + k_{32}x_2 + k_{33}x_3 + k_{34}x_4 $

$y_4 = k_{41}x_1 + k_{42}x_2 + k_{43}x_3 + k_{44}x_4$

where the $x_i$ are the four binary digits of the plaintext block, the $y_i$ are the four binary digits of the ciphertext block, the $k_{ij}$ are the binary coefficients, and arithmetic is mod 2. The key size is just $n^2$, in this case 16 bits. The danger with this kind of formulation is that it may be vulnerable to cryptanalysis by an attacker that is aware of the structure of the algorithm. In this example, what we have is essentially the Hill cipher discussed earlier, applied to binary data rather than characters. As we saw before, a simple linear system such as this is quite vulnerable.

The Feistel Cipher

Feistel proposed  that we can approximate the ideal block cipher by utilizing the concept of a product cipher, which is the execution of two or more simple ciphers in sequence in such a way that the final result or product is cryptographically stronger than any of the component ciphers. The essence of the approach is to develop a block cipher with a key length of $k$ bits and a block length of $n$ bits, allowing a total of $2^k$ possible transformations, rather than the $2^n!$ transformations available with the ideal block cipher.

In particular, Feistel proposed the use of a cipher that alternates substitutions and permutations, where these terms are defined as follows:

Substitution: Each plaintext element or group of elements is uniquely replaced by a corresponding ciphertext element or group of elements.

Permutation: A sequence of plaintext elements is replaced by a permutation of that sequence. That is, no elements are added or deleted or replaced in the sequence, rather the order in which the elements appear in the sequence is changed.

In fact, Feistel’s is a practical application of a proposal by Claude Shannon to develop a product cipher that alternates confusion and diffusion functions.

Confusion and Diffusion

1. Confusion:

• Definition: Confusion refers to making the relationship between the ciphertext and the encryption key as complex as possible. In simple terms, confusion ensures that even if someone tries to analyze the ciphertext, they can't easily deduce what the key is or how it relates to the plaintext.
• Purpose: The idea is to obscure the key from an attacker. This means that small changes to the key should cause unpredictable changes in the ciphertext.
• How it is Achieved in Feistel Ciphers: Confusion is primarily introduced through non-linear substitutions, like using S-boxes (substitution boxes) in block ciphers like DES (Data Encryption Standard). These S-boxes take input bits and transform them in a non-linear, complex way to produce output bits, making it difficult to trace the input-output relationships.

2. Diffusion:

• Definition: Diffusion refers to spreading out the influence of each bit of the plaintext over many bits of the ciphertext. The idea is that a change in a single bit of the plaintext or the key should cause changes in many parts of the ciphertext, ideally affecting half the bits (this is called the avalanche effect).
• Purpose: Diffusion hides the statistical structure of the plaintext, making it hard for an attacker to find patterns in the ciphertext that correspond to the plaintext.
• How it is Achieved in Feistel Ciphers: Diffusion is typically achieved through permutations and bitwise operations, where bits of the data are shuffled or rearranged across different rounds of the cipher. This ensures that even a tiny change in input ripples across many output bits, distributing the influence widely.

FEISTEL CIPHER STRUCTURE The left-hand side of Figure 4.3 depicts the encryption structure proposed by Feistel. The inputs to the encryption algorithm are a plaintext block of length $2w$ bits and a key $K$. The plaintext block is divided into two halves, $LE_0$ and $RE_0$. The two halves of the data pass through $n$ rounds of processing and then combine to produce the ciphertext block. Each round $i$ has as inputs $LE_{i - 1}$ and $RE_{i - 1}$ derived from the previous round, as well as a subkey $K_i$ derived from the over- all $K$. In general, the subkeys $K_i$ are different from $K$ and from each other. In Figure 4.3, 16 rounds are used, although any number of rounds could be implemented.

All rounds have the same structure. A substitution is performed on the left half of the data. This is done by applying a round function $F$ to the right half of the data and then taking the exclusive-OR of the output of that function and the left half of the data. The round function has the same general structure for each round but is parameterized by the round subkey $K_i.$ Another way to express this is to say that $F$ is a function of right-half block of $w$ bits and a subkey of $y$ bits, which produces an output value of length $w$ bits: $F(RE_i, K_i + 1)$. Following this substitution, a permutation is performed that consists of the interchange of the two halves of the data.This structure is a particular form of the substitution-permutation network (SPN) proposed by Shannon.

The exact realization of a Feistel network depends on the choice of the follow- ing parameters and design features:

Block size: Larger block sizes mean greater security (all other things being equal) but reduced encryption/decryption speed for a given algorithm. The greater security is achieved by greater diffusion. Traditionally, a block size of 64 bits has been considered a reasonable tradeoff and was nearly universal in block cipher design. However, the new AES uses a 128-bit block size.

Key size: Larger key size means greater security but may decrease encryption/ decryption speed. The greater security is achieved by greater resistance to brute-force attacks and greater confusion. Key sizes of 64 bits or less are now widely considered to be inadequate, and 128 bits has become a common size.

Number of rounds: The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security. A typical size is 16 rounds.

Subkey generation algorithm: Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis.

Round function F: Again, greater complexity generally means greater resistance to cryptanalysis.

There are two other considerations in the design of a Feistel cipher:

Fast software encryption/decryption: In many cases, encryption is embedded in applications or utility functions in such a way as to preclude a hardware implementation. Accordingly, the speed of execution of the algorithm becomes a concern.

Ease of analysis: Although we would like to make our algorithm as difficult as possible to cryptanalyze, there is great benefit in making the algorithm easy to analyze. That is, if the algorithm can be concisely and clearly explained, it is easier to analyze that algorithm for cryptanalytic vulnerabilities and therefore develop a higher level of assurance as to its strength. DES, for example, does not have an easily analyzed functionality.

FEISTEL DECRYPTION ALGORITHM The process of decryption with a Feistel cipher is essentially the same as the encryption process. The rule is as follows: Use the ciphertext as input to the algorithm, but use the subkeys $K_i$ in reverse order. That is, use $K_n$ in the first round, $K_{n - 1}$ in the second round, and so on, until $K_1$ is used in the last round. This is a nice feature, because it means we need not implement two different algorithms; one for encryption and one for decryption.

To see that the same algorithm with a reversed key order produces the correct  result, Figure 4.3 shows the encryption process going down the left-hand side and the decryption process going up the right-hand side for a 16-round algorithm.For clarity, we use the notation $LE_i$ and $RE_i$ for data traveling through the encryption algorithm and $LD_i$ and $RD_i$ for data traveling through the decryption algorithm.

Let us walk through Figure 4.3 to demonstrate the validity of the preceding assertions. After the last iteration of the encryption process, the two halves of the output are swapped, so that the ciphertext is $RE_{16}||LE_{16}. $The output of that round is the ciphertext. Now take that ciphertext and use it as input to the same algorithm. The input to the first round is $RE_{16}||LE_{16}$, which is equal to the 32-bit swap of the output of the sixteenth round of the encryption process.