Given a two-key triple encryption for block cipher. Let F be a block cipher with n-bit block length and key length, and set F 0 k1,k2 (x) def = Fk1 (F 1 k2 (Fk1 (x)).

(a) Assume that given a pair (m1, m2) it is possible to find in constant time all keys k2 such that m2 = F 1 k2 (m1). Show how to recover the entire key for F 0 (with high probability) in time roughly 2n using three known input/output pairs. (10 Points)

(b) In general, it will not be possible to find k2 as above in constant time. However, show that by using a pre-processing step taking 2n time it is possible, given m2, to find in (essentially) constant time all keys k2 such that m2 = F 1 k2 (0n ). (10 Points)

(c) Assume k1 is known and that the pre-processing step above has already been run. Show how to use the value y = F 0 k1,k2 (x) for a single chosen plaintext x to determine k2 in constant time. (10 Points)

(d) Put the above components together to devise an attack that recovers the entire key of F 0 by running in roughly 2n time and requesting the encryption of roughly 2n chosen inputs. (10 Points)