Cryptography question:

Problem 4Flawed MAC designs, 24 marks For this problem, you need to carefully trace through the given MAC algorithms to understand the given attacks and explain how computation resistance is defeated (a) Recall that iterated hash functions employ a compression function f in multiple rounds; SHA-1 is an example of such a hash function. Here, f takes as input pairs of n-bit blocks and outputs nbit blocks, for some n N. The compression function f is assumed to be public, i.e. anyone can compute values of f. As a result, the hash function is also public, so any one can compute hash values. For simplicity, we assume that the bit length of any message to be hashed is a multiple of n, i.e. messages have been padded appropriately prior to hashing. Then the input to an iterated hash function is a message M consisting of L blocks Pi, P2, , Pl, each of length n. An algorithmic description of an n-bit iterated hash function is given as follows (as usual. ""denotes concatenation of strings and "-" means "is replaced by") Algorithin THASH Input: A message M = PPI . . . IPL Output: An n-bit hash of M Algorithm: 1. Initialize H 0" (n zeros) 2. For i = 1 to L do H f(H, P) 3. Output H The following attacks show that the two "obvious" designs for using an iterated haslh function as the basis for a MAC-prepending or appending the key to the message and then hashing are not computation resistant. For simplicity, assume that keys also have length1 n i. (5 marks) Define a message authentication function PHMAC ("Prepend Hash MAC") via for any message M- PPlP Suppose an attacker knows a message/PHMAC pair (Mi, PHMACK(Mi)). Let X be an arbitrary n-bit block and put M2- Mi|X. Show how an attacker can compute PHMACK(M2) without knowledge of K, thereby defeating computation resistance for PHMAC Hint: Suppose Mi consists of L blocks. Tracing through the ITHASH algorithm compare the outputs of the first L+1 rounds of PHMACK(Mi and PHMACK(M2) ii. (7 marks) Define a message authentication function AHMACK ("Append Hash MAC") via for any message MP..PL Assume that ITHASH is not weakly collision resistant, and suppose an attacker knows a message/AHMAC pair (Mi, AHMACK(Mi)). Show how she can find (without The attack in part i) will in fact work for any key length, but for part (ii), this key length restriction is required Problem 4Flawed MAC designs, 24 marks For this problem, you need to carefully trace through the given MAC algorithms to understand the given attacks and explain how computation resistance is defeated (a) Recall that iterated hash functions employ a compression function f in multiple rounds; SHA-1 is an example of such a hash function. Here, f takes as input pairs of n-bit blocks and outputs nbit blocks, for some n N. The compression function f is assumed to be public, i.e. anyone can compute values of f. As a result, the hash function is also public, so any one can compute hash values. For simplicity, we assume that the bit length of any message to be hashed is a multiple of n, i.e. messages have been padded appropriately prior to hashing. Then the input to an iterated hash function is a message M consisting of L blocks Pi, P2, , Pl, each of length n. An algorithmic description of an n-bit iterated hash function is given as follows (as usual. ""denotes concatenation of strings and "-" means "is replaced by") Algorithin THASH Input: A message M = PPI . . . IPL Output: An n-bit hash of M Algorithm: 1. Initialize H 0" (n zeros) 2. For i = 1 to L do H f(H, P) 3. Output H The following attacks show that the two "obvious" designs for using an iterated haslh function as the basis for a MAC-prepending or appending the key to the message and then hashing are not computation resistant. For simplicity, assume that keys also have length1 n i. (5 marks) Define a message authentication function PHMAC ("Prepend Hash MAC") via for any message M- PPlP Suppose an attacker knows a message/PHMAC pair (Mi, PHMACK(Mi)). Let X be an arbitrary n-bit block and put M2- Mi|X. Show how an attacker can compute PHMACK(M2) without knowledge of K, thereby defeating computation resistance for PHMAC Hint: Suppose Mi consists of L blocks. Tracing through the ITHASH algorithm compare the outputs of the first L+1 rounds of PHMACK(Mi and PHMACK(M2) ii. (7 marks) Define a message authentication function AHMACK ("Append Hash MAC") via for any message MP..PL Assume that ITHASH is not weakly collision resistant, and suppose an attacker knows a message/AHMAC pair (Mi, AHMACK(Mi)). Show how she can find (without The attack in part i) will in fact work for any key length, but for part (ii), this key length restriction is required