Hash Function Security

In a certain network protocol, each datagram consists of a 128-bit header and a 128-bit payload. An organisation decides to store hashed datagrams for analytic purposes. These hash values need to be calculated on resource-limited devices that can only process data in 128-bit chunks. Thankfully, the devices have hardware implementations of the following cryptographic algorithms:

AESwitha128-bitkey,a128-bitinputblock,anda128-bitoutputblock,and

a secure internal hash function H with a 128-bit input and a 64-bit output.

Since the internal hash function H cannot process entire datagrams, it is necessary to design a hashing method that can compute datagram hashes based on the internally implemented algorithms. The engineers come up with the following designs for hashing datagrams:

Design A: hash separately, then XOR, i.e. Hash(datagram) = H(header) H(payload)

Design B: hash separately, then hash the concatenated results, i.e. Hash(datagram) = H( H(header) H(payload) )

Design C: apply AES on payload (as input block) using header as key, then XOR the result with header, i.e.

Hash(datagram) = AESheader(payload) header

In these formulas, denotes the bitwise exclusive or operation and denotes string concatenation. The designed datagram hashing method is called Hash to distinguish it from the internal hash function H.

Questions

1. (i) The organisation needs to develop a program that looks at the stored datagram hash values and for any two hashed datagrams reliably distinguishes if the original datagrams were identical or not. Assume at this stage that datagrams are all generated in a trusted environment. Identify the security requirement on datagram hashing in this case, and briefly justify your answer.

2. (ii) Consider the three candidate designs, i.e. Designs A, B, and C, above. For each design, discuss if it satisfies the security requirement identified in part (i). In each case, whether or not the design satisfies the security requirement, provide a convincing argument or a counterexample to support your answer.