Exercise 1

(20 points) Let m = m1 ∥m2 ∥ · · · ∥ml be an l-block message, and suppose c = c0 ∥ c1 ∥ c2 ∥ · · · ∥ cl is a valid encryption of m . For each of the CBC, OFB, and CTR modes of operation, explain how the following transmission errors affect the decryption of the received ciphertext.

(a) The recipient receives c ′  = c0 ∥ · · · ∥ ci−1 ∥ ci(′)∥ ci+1 ∥ · · · ∥ cl, where ci(′)  differs from ci  in a

(b) The recipient receives c ′ = c0 ∥ · · · ∥ ci−1∥ ci+1∥ · · · ∥ cl, where the ith ciphertext block is dropped.

Solution

Exercise 2

(20 points) The CPA game doesn’t always capture the full power of an eavesdropping adversary. For example, the sender might send an encrypted stream of message data over a period of time, and the adversary may have some influence over the later parts of the data after seeing the previous parts of the ciphertext. To capture this scenario we consider a modified, “streaming” CPA game for modes of operation that process each message block individually.

In the“streaming” CPA game, an adversary can make k = poly(n) queries to a stateful “left-or-right” encryption oracle. On the ith query, the adversary produces a one-block- message pair (mi(L), m i(R))  and receives the ciphertext block ci .   The resulting ciphertext c = c0 ∥c1 ∥ · · · ∥ck  is the encryption of either the “left”message mL  = m1(L)∥ · · · ∥mk(L) or the “right” message mR  = m 1(R)∥ · · · ∥mk(R) under the specified mode of operation.

advantage in the“streaming” CPA game against CBC mode instantiated with any PRP.

Solution

Exercise 3

(20 points) Let F : {0, 1}n × {0, 1}n  → {0, 1}n be pseudorandom function. Show that each of the following MACs is insecure, even if used to authenticate fixed-length messages. (In each case Gen outputs a uniform k  ∈  {0, 1}n , n being even, and ⟨i⟩ denotes an n/2-bit encoding of the integer i).

(a) To authenticate a message m = m1 ∥ · · · ∥ml, where mi  ∈ {0, 1}n, compute

t := Fk(m1) ⊕ · · · ⊕ Fk(ml).

(b) To authenticate a message m = m1 ∥ · · · ∥ml, where mi  ∈ {0, 1}n/2, compute

t := Fk(⟨1⟩∥m1) ⊕ · · · ⊕ Fk(⟨l ⟩∥ml).

Solution

Exercise 4

(20 points)

(a) Max Bankman has a payment system in which users’devices send messages indicating how much money they want to send to other users.  After attending 475 lectures, Max realizes that these messages need to have authenticity, or else the amounts and recipients might be modified in transit by an attacker. However, the protocol format for the messages has room for only 3 more bytes of data (regardless of the message length n), so Max goes looking for a MAC with a 3-byte-long tag.  Show that no such MAC can be CMA-secure, by describing and analyzing a forger that has good advantage in the CMA game.

(b) Prove that the following modifications of basic CBC-MAC do not yield a secure MAC:

A random initial block is chosen each time a message is authenticated. That is, choose uniform t0  ∈  {0, 1}n , run basic CBC-MAC over the "message" t0 ∥m1 ∥ · · · ∥ml, where each mi  ∈ {0, 1}n and output the tag ⟨t0 , tl⟩ . Verification is done in the natural way.

Solution

Exercise 5

(20 points) Let F  :  {0, 1}n  × {0, 1}n   →   {0, 1}n  be a pseudorandom function.   Show that the following MAC for messages of length 2n is insecure:  Gen outputs a uniform k  ∈  {0, 1}n .  To authenticate a message m1 ∥m2 with |m1 |  =  |m2 |  = n, compute the tag Fk(m1)∥Fk(Fk(m2)).

Solution