Due Thursday October 27

Problem 1. Given four DES keys, K1, K2, K3, K4 (56 bits each) define 4-DES as follows: 4-DES(x) = E-DES-K1(E-DES-K2(E-DES-K3(E-DES-K4(x)))).

(a) What would the corresponding decryption function be for 4-DES?

(b) Describe a meet-in-the-middle attack on 4-DES. How much time would it take? How much space? How many plaintext-ciphertext pairs would be needed to ensure a reasonable probability of success?

Problem 2. IDEAL-DES is defined as follows: For each of 2⁵⁶ possible 56 bit keys, one of the possible (2⁶⁴)! permutations of 64-bit numbers is chosen at random. Assume you are given two boxes, one of which implements IDEAL-DES and one which implements DES (encryption and decryption for both).

(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: the algorithm need not work 100% of the time but should work for almost any the random choices made in the construction of the IDEAL-DES box.)

(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 this case. (Note: it may not be as efficient as (a).)

Problem 3. 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? Assuming that Alice insists on using ECB mode for sending long messages how might she slightly modify the above to make it significantly more secure? Even if secure, why would this method be a bad idea?

Problem 4. The official standard for 3-DES (or Triple DES) uses three 56 bit DES keys and encrypts a message x using the following DES operations: E-DES-K3(D-DES-K2(E-DES-K1(x))). What is the corresponding decryption function? Explain why they chose to do a decryption as the second step.

Problem 5. Alice uses CBC mode with a random IV and AES key K to encrypt a plaintext consisting of blocks P1, P2, ..., Pk to get cipher blocks C0 = IV, C1, C2, ... , Ck. She again uses CBC mode with a different random IV but the same AES key K to encrypt a plaintext consisting of blocks Q1, Q2, ... , Qn to get cipher blocks D0 = IV, D1, D2, ... , Dn. Assume Eve knows P1, ... , Pk and sees C0, ... , Ck as well as D0, ... , Dn. Further assume that it turns out that Ci = Dj for some i and j. Does Eve have enough information to recover any blocks of the the second message Q1, ... , Qn? If so, which part can she recover? Assume that instead Alice uses OFB mode for both messages. What blocks, if any, can Eve recover with the same information. What if Alice uses CFB mode?

Report problems to dkrizanc at wesleyan dot edu