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 = IV, c = Enck(r) and t = Enck(Enck(r) ⊕ c). An attacker who asks for encryptions of zero can get many pairs (r, Enck(r)) for random n-bit strings r because the encryption of the zero message only depends on the random IV r and the key k, and does not change with different messages. Therefore, by repeatedly asking for encryptions of the zero message with different random IVs, the attacker can obtain many pairs (r, Enck(r)).

(c) Suppose an attacker who does not know k is given r, c = Enck(r) and r0, c0 = Enck(r0) for random r ≠ r0. The attacker can construct a new message (r, r0 ⊕ c, c0). The decryption algorithm would perform the following operations and checks:

1. Compute t' = Enck(Enck(r) ⊕ (r0 ⊕ c)). Since r0 ⊕ c = Enck(r), this simplifies to t' = Enck(Enck(r) ⊕ Enck(r)) = Enck(0) = c0.
2. Check if t' equals c0. Since we have shown that t' = c0, this check passes.
3. Decrypt the ciphertext r0 ⊕ c using the key k and the IV r to get the plaintext message m. Since r0 ⊕ c = Enck(r), this simplifies to m = Dec_k(Enck(r)) ⊕ r = 0 ⊕ r = r.

Therefore, the message (r, r0 ⊕ c, c0) is accepted by the decryption algorithm.