# 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  of 64 bits, and consists of three stages:

1. The bits of  are permuted by a fixed initial permutation to obtain . Write , where  is the first 32 bits of  and  is the last 32 bits.

2. For , perform the following:



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

3. Switch left and right to obtain , then apply the inverse of the initial permutation to get the ciphertext .

Decryption is performed by exactly the same procedure, except that the keys  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  becomes the first bit of , the 50th bit of  becomes the second bit of , etc.

The function , depicted in Figure 7.5, is described in several steps.

1. First,  is expanded to  by the following table.

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

2. Compute , which has 48 bits, and write it as , where each  has six bits.

3. There are eight S-boxes , given on page 150.  is the input for . Write . The row of the S-box is specified by  while  determines the column. For example, if , 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  in this location is 3, which is 3 in binary. Therefore, the output of  is 0011 in this case. In this way, we obtain eight four-bit outputs .

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

The resulting 32-bit string is .

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

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

Write the result as , where  and  have 28 bits.

2. For , let  and . Here  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  according to the following table. The output is .

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  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 -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  and  and encrypt a plaintext  by . Does this increase the security?

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  keys could be replaced by a search of length around , which would be quite easy to do.

For affine ciphers (Section 2.2) and for RSA (Chapter 9), double encrypting with two keys  and  is equivalent to encrypting with a third key . Is the same true for DES? Namely, is there a key  such that ? 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  represent encryption with the key consisting entirely of 0s and let  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  repeatedly to certain plaintexts yielded the original plaintext after around  iterations. A sequence of encryptions (for some plaintext )



where  is the smallest positive integer such that , is called a cycle of length .

# Lemma

If  is the smallest positive integer such that  for all , and  is the length of a cycle (so  for a particular ), then  divides .

Proof. Divide  into , with remainder . This means that  for some integer , and . Since , encrypting  times with  leaves  unchanged. Therefore,



Since  is the smallest positive integer such that , and , we must have . This means that , so  divides .

Suppose now that DES is closed under composition. Then  for some key . Moreover,  are also represented by DES keys. Since there are only  possible keys, we must have  for some integers  with  (otherwise we would have  distinct encryption keys). Decrypt  times: , which is the identity map. Since , the smallest positive integer  such that  is the identity map also satisfies .

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