) This question is about why one should use different keys when doing encrypt-then-MAC. It is based on Exercise 9.8 in Boneh-Shoup. Suppose Enc is a block cipher with n-bit blocks. We build an authenticated encryption scheme from Enc by using CBC-mode with random IV , and using a MAC also built from CBC-mode. So an encryption of an n-bit message m is a triple (c0, c1, t) where c0 = IV , c1 = Enck(IV ⊕ m), and t = Enck(Enck(c0) ⊕ c1). (a) Write down the operations and checks performed by the authenticated decryption algorithm on input (r, c, t). (b) Write down an encryption of the n-bit zero message and explain why an attacker who asks for encryptions of zero can get many pairs (r, Enck(r)) for random n-bit strings r. (c) Suppose an attacker who does not know k is given r, c = Enck(r) and r 0 , c0 = Enck(r 0 ) for random r = r 0 . Show that (r, r0 ⊕ c, c0 ) is accepted by the decryption algorithm.

(a) The authenticated decryption algorithm would perform the following operations and checks on input (r, c, t):

1. Compute t' = Enck(Enck(r) ⊕ c). This is the expected MAC value.
2. Check if t' equals t. If not, reject the message as it indicates that the message has been tampered with.
3. If t' equals t, decrypt the ciphertext c using the key k and the IV r to get the plaintext message m. This is done by computing m = Dec_k(c) ⊕ r.

(b) An encryption of the n-bit zero message would be (r, c, t) where r is a random n-bit string (the IV), c = Enck(r) (since the message m is zero, IV ⊕ m = r), and t = Enck(Enck(r) ⊕ c) = Enck(Enck(r) ⊕ Enck(r)) = Enck(0) (since Enck(r) ⊕ Enck(r) = 0).

An attacker who asks for encryptions of zero can get many pairs (r, Enck(r)) for random n-bit strings r because the ciphertext c is simply the encryption of the IV r when the plaintext message m is zero.

(c) Given r, c = Enck(r) and r0, c0 = Enck(r0) for random r ≠ r0, the tuple (r, r0 ⊕ c, c0) would be accepted by the decryption algorithm. Here's why:

1. The decryption algorithm would first compute t' = Enck(Enck(r) ⊕ (r0 ⊕ c)). Since c = Enck(r), this simplifies to t' = Enck(Enck(r) ⊕ (r0 ⊕ Enck(r))) = Enck(r0).
2. The provided MAC value t is c0, which is equal to Enck(r0), so the check t' = t passes.
3. The decryption algorithm then decrypts the ciphertext r0 ⊕ c to get the plaintext message. Since c = Enck(r), this is equivalent to decrypting r0 ⊕ Enck(r), which results in the message m = Dec_k(r0 ⊕ Enck(r)) = r ⊕ r = 0. So the decryption algorithm accepts the tuple.