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 $m_0=IP(m)$. Write $m_0=L_0{R}_0$, where $L_0$ is the first 32 bits of $m_0$ and $R_0$ is the last 32 bits.

2. For $1\le i\le 16$, perform the following:

   $$\begin{array}{rcl}{L}_i& =& R_{i-1}\\ R_i& =& L_{i-1}\oplus f(R_{i-1}\text{,}{K}_i)\text{,}\end{array}$$

   where $K_i$ 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 $R_{16}{L}_{16}$, then apply the inverse of the initial permutation to get the ciphertext $c=I{P}^{-1}(R_{16}{L}_{16})$.

Figure 7.4 The DES Algorithm

Decryption is performed by exactly the same procedure, except that the keys $K_1\text{,}\dots \text{,}{K}_{16}$ 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 $m_0$, the 50th bit of $m$ becomes the second bit of $m_0$, etc.

The function $f(R\text{,}{K}_i)$, depicted in Figure 7.5, is described in several steps.

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

   

   7.4-3 Full Alternative Text

   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)\oplus K_i$, which has 48 bits, and write it as $B_1{B}_2\cdots B_8$, where each $B_j$ has six bits.

3. There are eight S-boxes $S_1\text{,}\dots \text{,}{S}_8$, given on page 150. $B_j$ is the input for $S_j$. Write $B_j=b_1{b}_2\cdots b_6$. The row of the S-box is specified by $b_1{b}_6$ while $b_2{b}_3{b}_4{b}_5$ determines the column. For example, if $B_3=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 $S_3$ in this location is 3, which is 3 in binary. Therefore, the output of $S_3$ is 0011 in this case. In this way, we obtain eight four-bit outputs $C_1\text{,}{C}_2\text{,}\dots C_8$.

4. The string $C_1{C}_2\cdots C_8$ is permuted according to the following table.

   

   7.4-4 Full Alternative Text

   The resulting 32-bit string is $f(R\text{,}{K}_j)$.

Figure 7.5 The DES Function $f(R_{i-1}\text{,}{K}_i)$

Finally, we describe how to obtain $K_1\text{,}\dots K_{16}$. 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.

   

   7.4-5 Full Alternative Text

   Write the result as $C_0{D}_0$, where $C_0$ and $D_0$ have 28 bits.

2. For $1\le i\le 16$, let $C_i=L{S}_i(C_{i-1})$ and $D_i=L{S}_i(D_{i-1})$. Here $L{S}_i$ means shift the input one or two places to the left, according to the following table.

   

   7.4-6 Full Alternative Text

3. 48 bits are chosen from the 56-bit string $C_i{D}_i$ according to the following table. The output is $K_i$.

   

   7.4-7 Full Alternative Text

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 $K_1$ and $K_2$ and encrypt a plaintext $P$ by $E_{K_2}(E_{K_1}(P))$. Does this increase the security?

S-Boxes

Full Alternative Text

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 $2^{56}$ keys could be replaced by a search of length around $2^{28}$, which would be quite easy to do.

For affine ciphers (Section 2.2) and for RSA (Chapter 9), double encrypting with two keys $K_1$ and $K_2$ is equivalent to encrypting with a third key $K_3$. Is the same true for DES? Namely, is there a key $K_3$ such that $E_{K_3}=E_{K_2}{E}_{K_1}$? 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 $E_0$ represent encryption with the key consisting entirely of 0s and let $E_1$ 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 $E_1\circ E_0$ repeatedly to certain plaintexts yielded the original plaintext after around $2^{32}$ iterations. A sequence of encryptions (for some plaintext $P$)

$$E_1{E}_0(P)\text{,}{E}_1{E}_0(E_1{E}_0(P))\text{,}{E}_1{E}_0(E_1{E}_0(E_1{E}_0(P)))\text{,}\dots \text{,}(E_1{E}_0{)}^n(P)=P\text{,}$$

where $n$ is the smallest positive integer such that $(E_1{E}_0{)}^n(P)=P$, is called a cycle of length $n$.

Lemma

If $m$ is the smallest positive integer such that $(E_1{E}_0{)}^m(P)=P$ for all $P$, and $n$ is the length of a cycle (so $(E_1{E}_0{)}^n(P_0)=P_0$ for a particular $P_0$), then $n$ divides $m$.

Proof. Divide $n$ into $m$, with remainder $r$. This means that $m=nq+r$ for some integer $q$, and $0\le r<n$. Since $(E_1{E}_0{)}^n(P_0)=P_0$, encrypting $q$ times with $(E_1{E}_0{)}^n$ leaves $P_0$ unchanged. Therefore,

$$P_0=(E_1{E}_0{)}^m(P_0)=(E_1{E}_0{)}^r(E_1{E}_0{)}^{nq}(P_0)=(E_1{E}_0{)}^r(P_0)\text{.}$$

Since $n$ is the smallest positive integer such that $(E_1{E}_0{)}^n(P_0)=P_0$, and $0\le r<n$, we must have $r=0$. This means that $m=nq$, so $n$ divides $m$.

Suppose now that DES is closed under composition. Then $E_1{E}_0=E_K$ for some key $K$. Moreover, $E_K^2\text{,}{E}_K^3\text{,}\dots$ are also represented by DES keys. Since there are only $2^{56}$ possible keys, we must have $E_K^j=E_K^i$ for some integers $i\text{,}j$ with $0\le i<j\le 2^{56}$ (otherwise we would have $2^{56}+1$ distinct encryption keys). Decrypt $i$ times: $E_K^{j-i}=D_K^i{E}_K^j=D_K^i{E}_K^i$, which is the identity map. Since $0<j-i\le 2^{56}$, the smallest positive integer $m$ such that $E_K^m$ is the identity map also satisfies $m\le 2^{56}$.

Coppersmith found the lengths of the cycles for 33 plaintexts $P_0$. 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 ${10}^{277}$. But if DES is closed under composition, we showed that $m\le 2^{56}$. Therefore, DES is not closed under composition.