Instructor: Adam O’Neill COMPSCI-466, UMass Amherst, Spring 2020 adamo@cs.umass.edu
COMPSCI-466: Homework 5
Problem 1. (100 points.) Let D be the set of all strings whose length is a positive multiple of 128. Define hash function H : {0, 1}128 × D → {0, 1}128 as follows:
Algorithm HK(M):
Parse M as M[1]M[2]…M[m] C[0] ← 0128
For i = 1 to m do:
B[i] ← AESK(C[i − 1] ⊕ M[i])
C[i] ← AESK(B[i] ⊕ M[i]) Return C[m]
Above we parse M as consisting of m blocks of 128-bits each. Show that H is not collision- resistant by giving a practical adversary A such that its advantage Advcr(A) is high. As usual,
your adversary should be given in concise pseudocode (70 points) and you should formally analyze its advantage and resource usage (30 points).
1
H