Stanford UniversityCS 255hw2-sol CS255: Cryptography and Computer Security Winter 2010 Assignment #2: Solutions

CS255: Cryptography and Computer Security Winter 2010 Assignment #2: Solutions Problem 1 Suppose we can find two message/hash pairs (M1; h(M1)) and (M2; h(M2)) such that M1 6= M2 and h(M1) = h(M2) . Then, there exists two distinct Merkle hash trees T1 and T2 whose outputs are identical. We can find a collision for the compression function using a top-down side-by-side comparison of our two tree’s, looking across trees for a case where the outputs of f are the same, but the inputs differ. Starting at the root, suppose that either the first block or msg-length (thus height) of our trees differ, in this case, clearly we have found a collision in f, so we can stop our search. We can continue down examining the ith node of T1 and T2 and compare the inputs. If they differ, then we have found a collision for the compression function, and the procedure terminates. If not, we proceed to level i + 1 and repeat the same procedure. Note that since M1 6= M2, we cannot go through the entire tree without finding a collision. It follows that one can find a collision in the compression function. Problem 2 To construct a collision for the first hash construction with f1(x; y) = E(y; x) ⊕ y, choose any y and non-zero x so that y 6= (x ⊕ y). Let: x1 = D(y; x ⊕ y); y1 = y x2 = D(x ⊕ y; y); y2 = x ⊕ y So then: f1(x1; y1) = E(y; x1) ⊕ y = E(y; D(y; x ⊕ y)) ⊕ y = (x ⊕ y) ⊕ y = x f1(x2; y2) = E(y2; x2) ⊕ y2 = E(x ⊕ y; D(x ⊕ y; y) ⊕ (x ⊕ y) = y ⊕ (x ⊕ y) = x = f1(x1; y1) For the second compression function f2(x; y) = E(x; x) ⊕ y, choose any x1 6= x2, any y1, and let y2 = E(x1; x1) ⊕ E(x2; x2) ⊕ y1. Then f2(x2; y2) = E(x2; x2) ⊕ y2 = E(x2; x2) ⊕ (E(x1; x1) ⊕ E(x2; x2) ⊕ y1) = E(x1; x1) ⊕ y1 = f2(x1; y1) Problem 3 Collision resistance from discrete log. Let G be a finite cyclic group of prime oreder q. Let g be a generator of G. a. Suppose that u = gα for some x. Consider the following compression function h : Z2 q ! G defined by h(x; y) = gxuy. Show that any collision on h enables an attacker to compute the discrete log α.