Sebery J.Cryptography.An introduction to computer security.1989

Fig. 3.6. Feistel permutation

{Avalanche property { a single input bit change should force the complementation of approximately half of the output bits [169].

{Completeness property { each output bit should be a complex function of every input bit [266].

In general, to implement product ciphers, it is necessary to have two algorithms: one for encryption and the other for decryption. This can be expensive in terms of both hardware and software. Feistel [169] showed an elegant variant of S-P networks that could be implemented using a single algorithm for both encryption and decryption. A single round of this variant is shown in Figure 3.6. Note the following interesting properties of the round:

{It is always a permutation regardless of the form of the f function.

{As Li = Ri 1, the function f is evaluated on the same input for both encryption and decryption.

92 3 PRIVATE-KEY CRYPTOSYSTEMS

A cryptographic system is called a Feistel-type cryptosystem if it applies ` rounds of a Feistel transformation (Feistel permutation) yielding an encryption function of the form:

The decryption applies the inverse Feistel transformations in the reverse order. The cryptographic key is k = (k1; : : : ; k`).

An encryption algorithm should allow a user to select an encryption function from a large enough collection of all possible functions through the random selection of a cryptographic key. Note that for a plaintext/ciphertext block of n bits, the collection of all possible permutations contains 2n! elements and is called the symmetric group. If we assume that the size of the key block is also n bits, then the selection of permutations is restricted to 2n out of 2n! by random selection of the key. To generate a random permutation eÆciently, it is enough to iterate Feistel permutations many times. The single iteration is controlled by a shorter partial key which is usually generated from the cryptographic key. Therefore the iteration has to be seen as a collection of permutations, each of which is indexed by the partial key.

Coppersmith and Grossman [109] studied iterations of basic permutations and their suitability to encryption. They de ned the k-functions. Each k- function along with its connection topology produces a single iteration permutation which can be used as a generator of other permutations by composing them. Coppersmith and Grossman proved that these generators produce at least the alternating group using a nite number of their compositions. It means that using composition and with generators of relatively simple structure, it is possible to produce at least half of all the permutations. Even and Goldreich [165] proved that the Feistel permutations can also generate the alternating group. It turns out [408] that even if the function f (k; R) is restricted to one-to-one mappings, the Feistel permutations still generate the alternating

group. In other words, having (2n=2)! generators, it is possible to produce (2n)!

2

di erent permutations. Bovey and Williamson reported in [52] that an ordered pair of generators can produce either the alternating group AVn or the symmetric group SVn with the probability greater than 1 exp( log1=2 2n). So if we select the pair at random, there is a high probability that it generates at least

AVn .

The rst cryptosystem developed using Feistel transformations, was the Lucifer algorithm. It was designed at the IBM Watson Research Laboratory in the early 1970s by a team including Horst Feistel, William Notz, and J. Lynn Smith [169, 170, 487].

The Lucifer operates on 128-bit messages and encrypts them into 128-bit cryptograms under a 128-bit key. The general scheme of Lucifer is given in Figure 3.7. The core element is the function f (Figure 3.8). It translates 64-bit inputs into 64-bit outputs using a 64-bit partial key ki; i = 1; : : : ; 16. A 64-bit input Ri 1 to the function f goes to eight identical S-boxes. Each S-box is a simple substitution cipher with a single bit key (0 or 1). The eight bits needed to control S-boxes are extracted from the partial key ki. The outputs from S- boxes are XORed with the partial key ki. Finally, bits of the resulting sequence are permuted according to the xed wire-crossing topology of the block P.

The key schedule of Lucifer is very regular. Partial keys are selected from 64 lower bits of the key. After every extraction of the partial key, the contents of the 128-bit key register is rotated 56 bits to the left.

3.2.3 The DES Algorithm

The Data Encryption Standard (DES) [384] or Data Encryption Algorithm (DEA) was developed at IBM in the mid '70s and was the outgrowth of Lucifer. There is an interesting story behind the design and adoption of DES as a US encryption standard for nonmilitary applications. Readers are referred to Schneier's book [452] for details. It is no surprise to learn that the DES algorithm repeats the Lucifer general structure. The algorithm is summarized in

94 3 PRIVATE-KEY CRYPTOSYSTEMS

Fig. 3.7. Lucifer

Figure 3.9. DES processes 64-bit blocks of data under a 56-bit key using 16 rounds (or iterations).

There was a disagreement over whether 56-bit key is suÆciently long. DiÆe and Hellman [153] had predicted the DES algorithm would be vulnerable to the exhaustive search attack by a special purpose machine. Indeed, Michael Wiener [529] at the Crypto '93 rump session gave technical details of a key search chip

Fig. 3.8. Lucifer function f

which can test 5 107 keys per second. A search machine which uses 5760 chips will search the entire DES key space in 35 hours and cost $100,000.

The algorithm can be used for both encryption and decryption. An input x can be either a plaintext or a ciphertext block. The sequence x is rst transposed under an initial permutation (IP). The 64-bit output IP (x) is divided into halves L0 and R0. The pair (L0; R0) is subject to 16 Feistel transformations each of which uses the function f(ki; Li); i = 1; : : : ; 16. Finally, the pair (L16; R16) is transposed under the inverse permutation IP 1 to produce the output y. The permutations IP and IP 1 are given in Table 3.5. The IP and IP 1 tables (as well as the other permutation tables described later) should be read left-to- right, top-to-bottom (e.g. IP transposes a binary string x = (x1x2 : : : x64) into (x58x50 : : : x7)). All tables are xed.

Note that after the last iteration, the left and right halves are not exchanged; instead the concatenated block (R16L16) is input to the nal permutation IP 1. This is necessary to ensure that the algorithm can be used both to encipher and decipher.

The Function f and S-boxes. Figure 3.10 shows the components of the function f(ki; Ri 1). First Ri 1 is expanded to a 48-bit string E(Ri 1) using the bit-selection function E shown in Table 3.6. This table is used in the same way as the permutation tables, except that some bits of Ri 1 are selected more

98 3 PRIVATE-KEY CRYPTOSYSTEMS

Table 3.6. Bit-selection function E

16 7 20 21

29 12 28 17

1 15 23 26

5 18 31 10

2 8 24 14

32 27 3 9

19 13 30 6

22 11 4 25

Table 3.7. Permutation P

then S7 returns the value in row 3, column 2; this is 13, which is represented as 1101.

Although the DES algorithm was made public, the collection of tests used to select S-boxes and the P-box was not revealed until 1994 [108]. The collection of tests is equivalently referred in the literature as the design criteria/properties. A summary of the design properties used during the design of S-boxes and the P-box can be found in [67] and [380]. Some S-box design properties are:

{Each row function in an S-box is a permutation (S-boxes produce sequences with balanced number of zeroes and ones).

{No S-box is linear or aÆne function of the input (S-boxes are nonlinear),

{A single-bit change on the input of an S-box changes at least two output bits (S-boxes provide \avalanche" e ect).

{For each S-box S, S(x) and S(x 001100) must di er in at least two bits.

{S(x) 6= S(x 11ef 00) for any choice of bits e and f.

{The S-boxes minimize the di erence between the number of ones and zeroes

in any S-box output when any single bit is constant.

S-box design criteria can be de ned using the information theory concept of mutual information. This approach was applied by Forre in [188] and Dawson and Tavares in [128]. They argued that the mutual information between inputs and outputs of S-boxes should be as small as possible. The study of the DES S-boxes gave rise to a new eld called the S-box theory.

Davies [124] and Davio, Desmedt, Goubert, Hoornaert and Quisquater [125] analyzed the concatenation of the P-box and bit-selection function E. Assume that the input to an S-box is abcdef. The following observations can be made [67]:

{Each S-box input bit comes from the output of a di erent S-box.

{No input bit to a given S-box comes from the output of the same S-box.

{An output from Si 1 goes to one of the ef input bits of Si and further via E an output from Si 2 goes to one of the ab input bits.

{An output of Si+1 goes to one of the cd inputs bits of Si.

{For each S-box output, two bits go to ab or ef input bits, the other two go to cd input bits.

The above properties allow a quick di usion of partial cryptograms between two consecutive rounds.

DES Key Scheduling. Each iteration uses a di erent 48-bit key ki derived from the initial key k. Figure 3.11 illustrates how this is done. The initial key is input as a 64-bit block, with 8 parity bits in positions 8, 16, : : :, 64. The permutation PC1 (permuted choice 1) discards the parity bits and transposes the remaining 56 bits as shown in Table 3.9. The result, PC1(k), is then split into halves C0 and D0 used to derive each partial key ki. Subsequent values of (Ci; Di) are calculated as follows:

Ci = LSs(Ci 1); Di = LSs(Di 1);

where LSs is a left circular shift by the number of positions shown in Table 3.10. Key ki is then given by,

ki = P C2(CiDi)

where PC2 is the permutation shown in Table 3.11.

The key schedule works well for most keys. However, if the key is k = 01010101 01010101x, then all partial keys are ki = 0000000 0000000x where the