Consider the following message authentication code (MAC): The secret key is a un
ID: 3677314 • Letter: C
Question
Consider the following message authentication code (MAC): The secret key is a uniformly at random chosen bitstring k {0,1}256 for a block cipher that operates on 256-bit blocks. We consider only messages m whose length is an integer multiple of 256. Let m=m1||…||mr with mi{0,1}256. To generate an authentication tag, we proceed as follows, where Enck stands for encrypting with the block cipher and is the XOR-operation:
1. compute x1= Enck (m1)
2. compute x2 = Enck (m2 x1)
3. compute x3 = Enck (m3 x2)
r. compute xr = Enck (mr xr1)
r+1. output xr.
To verify a tag, the recipient reproduces the tag and checks for equality. Show that this MAC is insecure: It is possible to derive a valid authentication tag for a new message m’ from given (message,tag)-pairs?
Explanation / Answer
ECB-MAC: We consider the last block of the ECB encryption of a message as the MAC of this message. Obviously, this scheme is highly insecure since the MAC of the message
m = m1|| . . . ||mn||mn+l ,
where || stands for concatenation, is equal to the MAC of
m = m 1 || . . . ||m n ||mn+l
for any blocks ml , . . . , mn.
OFB-MAC: We consider the last block of the OFB encryption of a message as the MAC of this message. Once again, the scheme is insecure. Given the MAC c of a one-block message m,i.e., c = m E(IV ), it is easy to forge the MAC of the message
m = m x
as it simply is
c = m E(IV ) = c x
F: K × {0, 1} n {0, 1} n .
Our first scheme MAC1: K × {0, 1} {0, 1} works as follows:
algorithm MAC1K(M)
if (|M| mod n 6= 0 or |M| = 0) then return
Break M into n-bit blocks M = M1 . . . Mm
for i 1 to m do Yi FK(Mi)
T Y1 · · · Yn
return T