Suppose we are given the specification of a block cipher which operates on 64-bit blocks and has a key length of k=56 bits. To protect against an exhaustive key search, plaintext blocks m are encrypted twice, using two independently chosen random keys k, k {0,1}56: c=Enck(Enck(m)) . Let us assume that the adversary has access to two plaintext-ciphertext pairs (m1,c1), (m2,c2) such that the condition c1=Enck(Enck(m1)) and c2=Enck(Enck(m2)) determines the secret key (k, k) {0,1}56+56 uniquely. Show that, given adequate memory, the adversary can recover the 112-bit key (k, k) using less than 264 executions of the 56-bit block cipher. (We count decrypting and encrypting each as one application of the block cipher).