In class we discussed CBC-MAC for message authentication.  For our purposes, let's only consider CBC-MAC with the AES block cipher, and assume that CBC-MAC only takes inputs that are a multiple of 128 bits long.  But we do allow CBC-MAC to takes inputs that have different lengths (up to 8 blocks).  So that means that inputs of length 128 bits, 256 bits, ..., and 1024 bits are all possible.  (These exercises are designed to help highlight some challenges with designing secure cryptographic protocols.  CBC-MAC, as defined below, should only be used on fixed-length inputs.  E.g., all inputs for a particular deployment setting should be 1024-bits long, or all inputs should be 512 bits long --- or one should use a different MAC.)

Here's CBC-MAC in more detail.

	CBC-MAC(K, M) // K is the 128-bit key, M is the message
		n = |M| / 128		// the number of blocks -- n must be between 1 and 8.
		Break M into 128-bit blocks M[1], M[2], ... M[n]
		C[0] = 0
		For i = 1 to n do
			C[i] = AES(K, M[i] xor C[i-1])
		T = C[n]
		Return(T)

Here's how the CBC-MAC verification algorithm works:

	CBC-MAC-Verify(K, M, T)
		T' = CBC-MAC(K, M)
		If T == T' return VALID
		Else return INVALID

1. You should already (basically) know the answer to this problem if you attended lecture on Feb 2.  But this will be helpful for you to recall.  Describe a chosen-plaintext attack against this MAC.  Your answer should be of the form:

	1. Attacker forces the user to compute CBC-MAC(K, M) for some message M of the attacker's choosing.
	2. Attacker produces a new message M' and a new tag T' such that CBC-MAC-Verify(K, M', T') return VALID but M' does not equal M

The difference between what we discussed on Feb 2 and the above is that on Feb 2 we chose two chosen plaintext messages, not one.

2. There are several ways that you might think about fixing CBC-MAC.  One way is the always append an all-zero block to the end of the message.  Your job is to show that this doesn't work.  Here's the revised CBC-MAC tagging algorithm

	CBC-MAC-ENDZERO(K, M) // K is the 128-bit key, M is the message
		n = |M| / 128		// the number of blocks -- n must be between 1 and 8.
		Break M into 128-bit blocks M[1], M[2], ... M[n]
		M[n+1] = a block of all zero
		C[0] = 0
		For i = 1 to n+1 do
			C[i] = AES(K, M[i] xor C[i-1])
		T = C[n+1]
		Return(T)

Here's how the CBC-MAC verification algorithm works:

	CBC-MAC-ENDZERO-Verify(K, M, T)
		T' = CBC-MAC-ENDZERO(K, M)
		If T == T' return VALID
		Else return INVALID

Describe a chosen-plaintext attack against this MAC.  Your answer should be of the form:

	1. Attacker forces the user to compute CBC-MAC-ENDZERO(K, M) for some message M of the attacker's choosing.
	2. Attacker produces a new message M' and a new tag T' such that CBC-MAC-ENDZERO-Verify(K, M', T') return VALID but M' does not equal M

3.  Here's another possible defense:  add the length of the message to the end.  We also talked about this potential defense --- but not how to attack it --- in class on Feb 2.

Here's the revised CBC-MAC tagging algorithm

	CBC-MAC-ENDLEN(K, M) // K is the 128-bit key, M is the message
		n = |M| / 128		// the number of blocks -- n must be between 1 and 8.
		Break M into 128-bit blocks M[1], M[2], ... M[n]
		M[n+1] = n encoded as a 128-bit block in big-endian format
		C[0] = 0
		For i = 1 to n+1 do
			C[i] = AES(K, M[i] xor C[i-1])
		T = C[n+1]
		Return(T)

Here's how the CBC-MAC verification algorithm works:

	CBC-MAC-ENDLEN-Verify(K, M, T)
		T' = CBC-MAC-ENDLEN(K, M)
		If T == T' return VALID
		Else return INVALID


Describe a chosen-plaintext attack against this MAC.  Now you may need more than one chosen message.   Your answer should be of the form:

	1. Attacker forces the user to compute CBC-MAC-ENDLEN(K, M) for some message M of the attacker's choosing.
	2. Attacker forces the user to compute CBC-MAC-ENDLEN(K, M') for some message M' of the attacker's choosing.
	3. Attacker forces the user to compute CBC-MAC-ENDLEN(K, M'') for some message M'' of the attacker's choosing.
	4. Attacker forces the user to compute CBC-MAC-ENDLEN(K, M''') for some message M''' of the attacker's choosing.
	5. Attacker produces a new message X and a new tag Y such that CBC-MAC-ENDLEN-Verify(K, X, Y) return VALID but X does not equal M, M', M'', M'''.

(You might not need steps 2, 3, or 4. )