7.4 DES – Introduction to Cryptography with Coding Theory, 3rd Edition

7.4 DES

A block of plaintext consists of 64 bits. The key has 56 bits, but is expressed as a 64-bit string. The 8th, 16th, 24th, ..., bits are parity bits, arranged so that each block of eight bits has an odd number of 1s. This is for error detection purposes. The output of the encryption is a 64-bit ciphertext.

The DES algorithm, depicted in Figure 7.4, starts with a plaintext m of 64 bits, and consists of three stages:

  1. The bits of m are permuted by a fixed initial permutation to obtain m0=IP(m). Write m0=L0R0, where L0 is the first 32 bits of m0 and R0 is the last 32 bits.

  2. For 1i16, perform the following:

    Li=Ri1Ri=Li1f(Ri1, Ki), 

    where Ki is a string of 48 bits obtained from the key K and f is a function to be described later.

  3. Switch left and right to obtain R16L16, then apply the inverse of the initial permutation to get the ciphertext c=IP1(R16L16).

Figure 7.4 The DES Algorithm

Decryption is performed by exactly the same procedure, except that the keys K1, , K16 are used in reverse order. The reason this works is the same as for the simplified system described in Section 7.2. Note that the left–right switch in step 3 of the DES algorithm means that we do not have to do the left–right switch that was needed for decryption in Section 7.2.

We now describe the steps in more detail.

The initial permutation, which seems to have no cryptographic significance, but which was perhaps designed to make the algorithm load more efficiently into chips that were available in 1970s, can be described by the Initial Permutation table. This means that the 58th bit of m becomes the first bit of m0, the 50th bit of m becomes the second bit of m0, etc.

The function f(R, Ki), depicted in Figure 7.5, is described in several steps.

  1. First, R is expanded to E(R) by the following table.

    This means that the first bit of E(R) is the 32nd bit of R, etc. Note that E(R) has 48 bits.

  2. Compute E(R)Ki, which has 48 bits, and write it as B1B2B8, where each Bj has six bits.

  3. There are eight S-boxes S1, , S8, given on page 150. Bj is the input for Sj. Write Bj=b1b2b6. The row of the S-box is specified by b1b6 while b2b3b4b5 determines the column. For example, if B3=001001, we look at the row 01, which is the second row (00 gives the first row) and column 0100, which is the 5th column (0100 represents 4 in binary; the first column is numbered 0, so the fifth is labeled 4). The entry in S3 in this location is 3, which is 3 in binary. Therefore, the output of S3 is 0011 in this case. In this way, we obtain eight four-bit outputs C1, C2, C8.

  4. The string C1C2C8 is permuted according to the following table.

    The resulting 32-bit string is f(R, Kj).

Figure 7.5 The DES Function f(Ri1, Ki)

Finally, we describe how to obtain K1, K16. Recall that we start with a 64-bit K.

  1. The parity bits are discarded and the remaining bits are permuted by the following table.

    Write the result as C0D0, where C0 and D0 have 28 bits.

  2. For 1i16, let Ci=LSi(Ci1) and Di=LSi(Di1). Here LSi means shift the input one or two places to the left, according to the following table.

  3. 48 bits are chosen from the 56-bit string CiDi according to the following table. The output is Ki.

It turns out that each bit of the key is used in approximately 14 of the 16 rounds.

A few remarks are in order. In a good cipher system, each bit of the ciphertext should depend on all bits of the plaintext. The expansion E(R) is designed so that this will happen in only a few rounds. The purpose of the initial permutation is not completely clear. It has no cryptographic purpose. The S-boxes are the heart of the algorithm and provide the security. Their design was somewhat of a mystery until IBM published the following criteria in the early 1990s (for details, see [Coppersmith1]).

  1. Each S-box has six input bits and four output bits. This was the largest that could be put on one chip in 1974.

  2. The outputs of the S-boxes should not be close to being linear functions of the inputs (linearity would have made the system much easier to analyze).

  3. Each row of an S-box contains all numbers from 0 to 15.

  4. If two inputs to an S-box differ by one bit, the outputs must differ by at least two bits.

  5. If two inputs to an S-box differ in exactly the middle two bits, then the outputs differ in at least two bits.

  6. If two inputs to an S-box differ in their first two bits but have the same last two bits, the outputs must be unequal.

  7. There are 32 pairs of inputs having a given XOR. For each of these pairs, compute the XOR of the outputs. No more than eight of these output XORs should be the same. This is clearly to avoid an attack via differential cryptanalysis.

  8. A criterion similar to (7), but involving three S-boxes.

In the early 1970s, it took several months of searching for a computer to find appropriate S-boxes. Now, such a search could be completed in a very short time.

7.4.1 DES Is Not a Group

One possible way of effectively increasing the key size of DES is to double encrypt. Choose keys K1 and K2 and encrypt a plaintext P by EK2(EK1(P)). Does this increase the security?

S-Boxes

Meet-in-the-middle attacks on cryptosystems are discussed in Section 6.5. It is pointed out that, if an attacker has sufficient memory, double encryption provides little extra protection. Moreover, if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption.

In addition, if double encryption is equivalent to single encryption, then the (single encryption) cryptosystem is much less secure than one might guess initially (see Exercise 3 in Chapter 12). If this were true for DES, for example, then an exhaustive search through all 256 keys could be replaced by a search of length around 228, which would be quite easy to do.

For affine ciphers (Section 2.2) and for RSA (Chapter 9), double encrypting with two keys K1 and K2 is equivalent to encrypting with a third key K3. Is the same true for DES? Namely, is there a key K3 such that EK3=EK2EK1? This question is often rephrased in the equivalent form “Is DES a group?” (The reader who is unfamiliar with group theory can ask “Is DES closed under composition?”)

Fortunately, it turns out that DES is not a group. We sketch the proof. For more details, see [Campbell-Wiener]. Let E0 represent encryption with the key consisting entirely of 0s and let E1 represent encryption with the key consisting entirely of 1s. These keys are weak for cryptographic purposes (see Exercise 5). Moreover, D. Coppersmith found that applying E1E0 repeatedly to certain plaintexts yielded the original plaintext after around 232 iterations. A sequence of encryptions (for some plaintext P)

E1E0(P), E1E0(E1E0(P)), E1E0(E1E0(E1E0(P))), , (E1E0)n(P)=P, 

where n is the smallest positive integer such that (E1E0)n(P)=P, is called a cycle of length n.

Lemma

If m is the smallest positive integer such that (E1E0)m(P)=P for all P, and n is the length of a cycle (so (E1E0)n(P0)=P0 for a particular P0), then n divides m.

Proof. Divide n into m, with remainder r. This means that m=nq+r for some integer q, and 0r<n. Since (E1E0)n(P0)=P0, encrypting q times with (E1E0)n leaves P0 unchanged. Therefore,

P0=(E1E0)m(P0)=(E1E0)r(E1E0)nq(P0)=(E1E0)r(P0).

Since n is the smallest positive integer such that (E1E0)n(P0)=P0, and 0r<n, we must have r=0. This means that m=nq, so n divides m.

Suppose now that DES is closed under composition. Then E1E0=EK for some key K. Moreover, EK2, EK3,  are also represented by DES keys. Since there are only 256 possible keys, we must have EKj=EKi for some integers i, j with 0i<j256 (otherwise we would have 256+1 distinct encryption keys). Decrypt i times: EKji=DKiEKj=DKiEKi, which is the identity map. Since 0<ji256, the smallest positive integer m such that EKm is the identity map also satisfies m256.

Coppersmith found the lengths of the cycles for 33 plaintexts P0. By the lemma, m is a multiple of these cycle lengths. Therefore, m is greater than or equal to the least common multiple of these cycle lengths, which turned out to be around 10277. But if DES is closed under composition, we showed that m256. Therefore, DES is not closed under composition.