Due Wednesday November 1 in class

Problem 1. IDEAL-DES is defined as follows: For each of the 2⁵⁶ possible 56 bit keys, one of the possible (2⁶⁴)! permutations of 64-bit numbers is chosen at random. The permutation assigns to each 64-bit plaintext block a corresponding 64-bit ciphertext. Assume you are given two boxes, one of which implements IDEAL-DES and one which implements DES (encryption and decryption for both) but you don't know which is which.

(a) Assume you can input any number of keys and plaintexts to each box. Give an algorithm which decides which box is the DES box and which is IDEAL-DES. (Note 1: The algorithm need not work 100% of the time but should work for almost any of the random choices made in the construction of the IDEAL-DES box. Note 2: You can assume that you can compute DES yourself by directly applying the algorithm to plaintext-key pairs.)

(b) Assume that the keys for each box were already chosen (randomly) and all you can do is input plaintexts to get ciphertexts. Give an algorithm for distinguishing the boxes in this case. (Note: it may not be as efficient as (a).)

Problem 2. Consider the following method of using DES to encipher a message consisting of English text assuming Alice and Bob share a secret key K: For each letter in the message, pad the ascii equivalent with 0s to make it 64 bits long, encrypt the result using E-DES-K() and send the resulting 64 bit cipher letter. Why isn't this very secure? What could Alice and Bob do to make it more secure (at least for relatively short messages with say 1000s of letters)?

Problem 3. Let K be the DES key consisting of 56 0s. Show that, for this key, the decryption function is the same as the encryption function, i.e., E-DES-K(E-DES-K(m)) = m for all m. (Such a key is called a weak key. For more on this see chapter 7 of the Handbook of Applied Cryptography.)

Problem 4. Assume your are using DES in EBC mode to send a long message and a random error occurs changing a single bit from a 0 to a 1 in the ciphertext while the message is being transmitted. How many bits will be lost by the receiver at the other end? What if you are using CBC mode?

Problem 5. Suppose you know that the plaintext 0110011111 is enciphered as 1011010111 by a five stage Linear Feedback Shift Register (LSFR) stream cipher. (In a five stage LSFR each bit, starting with the sixth, is a linear combination of the previous five bits of the stream.) What are the key bits that were used to encipher the plaintext? Can you find the linear combination that produces the stream? (For more on LSFRs see chapter 6 of the Handbook of Applied Cryptography.)

Report problems to dkrizanc at wesleyan dot edu