Consider the following DES-like encryption method. Start with a message of bits. Divide it into two blocks of length (a left half and a right half): . The key consists of bits, for some integer . There is a function that takes an input of bits and bits and gives an output of bits. One round of encryption starts with a pair . The output is the pair , where
( means XOR, which is addition mod 2 on each bit). This is done for rounds, so the ciphertext is .
If you have a machine that does the -round encryption just described, how would you use the same machine to decrypt the ciphertext (using the same key )? Prove that your decryption method works.
Suppose has bits and , and suppose the encryption process consists of 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.
Suppose has bits and , and suppose the encryption process consists of rounds. Why is this system not secure?
Bud gets a budget 2-round Feistel system. It uses a 32-bit , a 32-bit , and a 32-bit key . The function is , with the same key for each round. Moreover, to avoid transmission errors, he always uses a 32-bit message and lets . 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 and the key .
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, )?
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 and a right half . The encryption uses a function 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 and the right half is . 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).
Let be the DES key consisting of all 1s. Show that if , then , so encryption twice with this key returns the plaintext. (Hint: The round keys are sampled from . Decryption uses these keys in reverse order.)
Find another key with the same property as in part (a).
Alice uses quadruple DES encryption. To save time, she chooses two keys, and , and encrypts via . One day, Alice chooses to be the key of all 1s and 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 , let denote the complementary string obtained by changing all the 1s to 0s and all the 0s to 1s (equivalently, ). Show that if the DES key encrypts to , then encrypts to . (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 is the complementary string for the expansion of .)
Suppose we modify the Feistel setup as follows. Divide the plaintext into three equal blocks: , , . Let the key for the th round be and let be some function that produces the appropriate size output. The th round of encryption is given by
This continues for rounds. Consider the decryption algorithm that starts with the ciphertext and uses the algorithm
This continues for rounds, down to . Show that for all , 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 is the DES encryption of a message using the key . We showed in Exercise 7 that DES has the complementation property, namely that if then , where is the bit complement of . 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 to . (Hint: Consider a chosen plaintext set of and ).