The Feistel Cipher
Feistel proposed [FEIS73] 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 2k possible transformations, rather than the
2n! transformations available with the
ideal block cipher.
In particular, Feistel proposed the use of a cipher that
alternates substitutions and permutations. In fact, this is a practical
application of a proposal by Claude Shannon to develop a product cipher that
alternates confusion and diffusion functions [SHAN49]. We look next at these
concepts of diffusion and confusion and then present the Feistel cipher. But
first, it is worth commenting on this remarkable fact: The Feistel cipher
structure, which dates back over a quarter century and which, in turn, is based
on Shannon's proposal of 1945, is the structure used by many significant
symmetric block ciphers currently in use.
Diffusion and Confusion
The terms diffusion and confusion were introduced by Claude Shannon to capture
the two basic building blocks for any cryptographic system [SHAN49].[2] Shannon's concern was to thwart
cryptanalysis based on statistical analysis. The reasoning is as follows. Assume
the attacker has some knowledge of the statistical characteristics of the
plaintext. For example, in a human-readable message in some language, the
frequency distribution of the various letters may be known. Or there may be
words or phrases likely to appear in the message (probable words). If these
statistics are in any way reflected in the ciphertext, the cryptanalyst may be
able to deduce the encryption key, or part of the key, or at least a set of keys
likely to contain the exact key. In what Shannon refers to as a strongly ideal
cipher, all statistics of the ciphertext are independent of the particular key
used. The arbitrary substitution cipher that we discussed previously (Figure 3.1) is such a cipher, but as we have
seen, is impractical.
[2] Shannon's 1949 paper appeared originally as a classified report in 1945. Shannon enjoys an amazing and unique position in the history of computer and information science. He not only developed the seminal ideas of modern cryptography but is also responsible for inventing the discipline of information theory. In addition, he founded another discipline, the application of Boolean algebra to the study of digital circuits; this last he managed to toss off as a master's thesis.
Other than recourse to ideal systems, Shannon suggests two
methods for frustrating statistical cryptanalysis: diffusion and confusion. In
diffusion, the statistical structure of
the plaintext is dissipated into long-range statistics of the ciphertext. This
is achieved by having each plaintext digit affect the value of many ciphertext
digits; generally this is equivalent to having each ciphertext digit be affected
by many plaintext digits. An example of diffusion is to encrypt a message M = m1, m2, m3,... of characters with an averaging
operation:
Every block cipher involves a transformation of a block of
plaintext into a block of ciphertext, where the transformation depends on the
key. The mechanism of diffusion seeks to make the statistical relationship
between the plaintext and ciphertext as complex as possible in order to thwart
attempts to deduce the key. On the other hand, confusion seeks to make the
relationship between the statistics of the ciphertext and the value of the
encryption key as complex as possible, again to thwart attempts to discover the
key. Thus, even if the attacker can get some handle on the statistics of the
ciphertext, the way in which the key was used to produce that ciphertext is so
complex as to make it difficult to deduce the key. This is achieved by the use
of a complex substitution algorithm. In contrast, a simple linear substitution
function would add little confusion.
As [ROBS95b] points out, so successful
are diffusion and confusion in capturing the essence of the desired attributes
of a block cipher that they have become the cornerstone of modern block cipher
design.
Feistel Cipher Structure
Figure 3.2 depicts the
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,
L0 and R0. 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 Li-1 and Ri-1, derived from the previous round, as
well as a subkey Ki, derived from the
overall K. In general, the subkeys Ki are different from K and from each other.
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 Ki. Following this substitution, a permutation is performed that consists of the
interchange of the two halves of the data.[4] This structure is a particular form
of the substitution-permutation network (SPN) proposed by Shannon.
[4] The final round is followed by an interchange that undoes the interchange that is part of the final round. One could simply leave both interchanges out of the diagram, at the sacrifice of some consistency of presentation. In any case, the effective lack of a swap in the final round is done to simplify the implementation of the decryption process, as we shall see.
The exact realization of a Feistel network depends on the
choice of the following 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.
[Page 69]
-
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.
[Page 70] -
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 Ki in reverse order. That is, use Kn in the first round, Kn-1 in the second round, and so on until
K1 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, consider Figure
3.3, which 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
(the result would be the same for any number of rounds). For clarity, we use the
notation LEi and REi for data traveling through the encryption
algorithm and LDi and RDi for data traveling through the decryption
algorithm. The diagram indicates that, at every round, the intermediate value of
the decryption process is equal to the corresponding value of the encryption
process with the two halves of the value swapped. To put this another way, let
the output of the ith encryption round be
LEi||REi (Li
concatenated with Ri). Then the
corresponding input to the (16 i)th decryption
round is REi||LEi or, equivalently, RD16-i||LD16-i.
Now we would like to show that the output of the first round of
the decryption process is equal to a 32-bit swap of the input to the sixteenth
round of the encryption process. First, consider the encryption process. We see
that
LE16 = RE15
RE16 = LE15 x F(RE15, K16)
LD1 = RD0
= LE16 = RE15
RD1 = LD0 x F(RD0, K16)
= RE16 x F(RE15, K16)
= [LE15 x F(RE15, K16)] x F(RE15, K16)
The XOR has the following properties:
[A x B] x C = A x [B x C]
D x D = 0
E x 0 = E
Thus, we have LD1 =
RE15 and RD1 = LE15. Therefore, the output of
the first round of the decryption process is LE15||RE15,
which is the 32-bit swap of the input to the sixteenth round of the encryption.
This correspondence holds all the way through the 16 iterations, as is easily
shown. We can cast this process in general terms. For the ith iteration of the encryption algorithm,
LEi = REi-1
REi =LEi-1 x F(REi-1, Ki)
Rearranging terms,
REi-1 = LEi
LEi-1 = REi x F(REi-1, Ki2 = REi x F(LEi, Ki)
Thus, we have described the inputs to the ith iteration as a function of the outputs, and these
equations confirm the assignments shown in the right-hand side of Figure 3.3.
Finally, we see that the output of the last round of the
decryption process is RE0||LE0. A 32-bit swap recovers the
original plaintext, demonstrating the validity of the Feistel decryption
process.
Note that the derivation does not require that F be a
reversible function. To see this, take a limiting case in which F produces a
constant output (e.g., all ones) regardless of the values of its two arguments.
The equations still hold.
No comments:
Post a Comment