Consider the following DES-like encryption method. Start with a message of $2n$ bits. Divide it into two blocks of length $n$ (a left half and a right half): $M_0{M}_1$. The key $K$ consists of $k$ bits, for some integer $k$. There is a function $f(K\text{,}M)$ that takes an input of $k$ bits and $n$ bits and gives an output of $n$ bits. One round of encryption starts with a pair $M_j{M}_{j+1}$. The output is the pair $M_{j+1}{M}_{j+2}$, where

($\oplus$ means XOR, which is addition mod 2 on each bit). This is done for $m$ rounds, so the ciphertext is $M_m{M}_{m+1}$.

1. If you have a machine that does the $m$-round encryption just described, how would you use the same machine to decrypt the ciphertext $M_m{M}_{m+1}$ (using the same key $K$)? Prove that your decryption method works.

2. Suppose $K$ has $n$ bits and $f(K\text{,}M)=K\oplus M$, and suppose the encryption process consists of $m=2$ rounds. If you know only a ciphertext, can you deduce the plaintext and the key? If you know a ciphertext and the corresponding plaintext, can you deduce the key? Justify your answers.

3. Suppose $K$ has $n$ bits and $f(K\text{,}M)=K\oplus M$, and suppose the encryption process consists of $m=3$ rounds. Why is this system not secure?

Bud gets a budget 2-round Feistel system. It uses a 32-bit $L$, a 32-bit $R$, and a 32-bit key $K$. The function is $f(R\text{,}K)=R\oplus K$, with the same key for each round. Moreover, to avoid transmission errors, he always uses a 32-bit message $M$ and lets $L_0=R_0=M$. Eve does not know Bud’s key, but she obtains the ciphertext for one of Bud’s encryptions. Describe how Eve can obtain the plaintext $M$ and the key $K$.

As described in Section 7.6, a way of storing passwords on a computer is to use DES with the password as the key to encrypt a fixed plaintext (usually 000 . . . 0). The ciphertext is then stored in the file. When you log in, the procedure is repeated and the ciphertexts are compared. Why is this method more secure than the similar-sounding method of using the password as the plaintext and using a fixed key (for example, $000\dots 0$)?

Nelson produces budget encryption machines for people who cannot afford a full-scale version of DES. The encryption consists of one round of a Feistel system. The plaintext has 64 bits and is divided into a left half $L$ and a right half $R$. The encryption uses a function $f(R)$ that takes an input string of 32 bits and outputs a string of 32 bits. (There is no key; anyone naive enough to buy this system should not be trusted to choose a key.) The left half of the ciphertext is $C_0=R$ and the right half is $C_1=L\oplus f(R)$. Suppose Alice uses one of these machines to encrypt and send a message to Bob. Bob has an identical machine. How does he use the machine to decrypt the ciphertext he receives? Show that this decryption works (do not quote results about Feistel systems; you are essentially justifying that a special case works).

1. Let $K=111\dots 111$ be the DES key consisting of all 1s. Show that if $E_K(P)=C$, then $E_K(C)=P$, so encryption twice with this key returns the plaintext. (Hint: The round keys are sampled from $K$. Decryption uses these keys in reverse order.)

2. Find another key with the same property as $K$ in part (a).

Alice uses quadruple DES encryption. To save time, she chooses two keys, $K_1$ and $K_2$, and encrypts via $c=E_{K_1}(E_{K_1}(E_{K_2}(E_{K_2}(m))))$. One day, Alice chooses $K_1$ to be the key of all 1s and $K_2$ to be the key of all 0s. Eve is planning to do a meet-in-the-middle attack, but after examining a few plaintext–ciphertext pairs, she decides that she does not need to carry out this attack. Why? (Hint: Look at Exercise 5.)

For a string of bits $S$, let $\bar{S}$ denote the complementary string obtained by changing all the 1s to 0s and all the 0s to 1s (equivalently, $\bar{S}=S\oplus 11111\dots$). Show that if the DES key $K$ encrypts $P$ to $C$, then $\bar{K}$ encrypts $\bar{P}$ to $\bar{C}$. (Hint: This has nothing to do with the structure of the S-boxes. To do the problem, just work through the encryption algorithm and show that the input to the S-boxes is the same for both encryptions. A key point is that the expansion of $\bar{C}$ is the complementary string for the expansion of $C$.)

Suppose we modify the Feistel setup as follows. Divide the plaintext into three equal blocks: $L_0$, $M_0$, $R_0$. Let the key for the $i$th round be $K_i$ and let $f$ be some function that produces the appropriate size output. The $i$th round of encryption is given by

This continues for $n$ rounds. Consider the decryption algorithm that starts with the ciphertext $A_n\text{,}{B}_n\text{,}{C}_n$ and uses the algorithm

This continues for $n$ rounds, down to $A_0\text{,}{B}_0\text{,}{C}_0$. Show that $A_i=L_i\text{,}{B}_i=M_i\text{,}{C}_i=R_i$ for all $i$, so that the decryption algorithm returns the plaintext. (Remark: Note that the decryption algorithm is similar to the encryption algorithm, but cannot be implemented on the same machine as easily as in the case of the Feistel system.)

Suppose $E_K(M)$ is the DES encryption of a message $M$ using the key $K$. We showed in Exercise 7 that DES has the complementation property, namely that if $y=E_K(M)$ then $\bar{y}=E_{\bar{K}}(\bar{M})$, where $\bar{M}$ is the bit complement of $M$. That is, the bitwise complement of the key and the plaintext result in the bitwise complement of the DES ciphertext. Explain how an adversary can use this property in a brute force, chosen plaintext attack to reduce the expected number of keys that would be tried from $2^{55}$ to $2^{54}$. (Hint: Consider a chosen plaintext set of $(M_1\text{,}{C}_1)$ and $(\overline{M_1}\text{,}{C}_2)$).