This is a cryptology question from the book Introduction to Modern Cryptography

Question

This is a cryptology question from the book Introduction to Modern Cryptography by Katz and Lindell. If needed, please refer to the textbook's online pdf to answer the question. Please answer BOTH parts of the question fully, and with any necessary examples/proofs. Please show ALL steps and explain logic fully. For each of the following modifications to the Merkle-Damgard transform, determine whether the result is collision resistant. If yes, provide a proof; if not, demonstrate an attack. Modify the construction so that the input length is not included at all (i.e., output z_B and not z_B + 1 = h*(z_B||L)). (Assume the resulting hash is only defined for inputs whose length is an integer multiple of the block length.) Modify the construction so that instead of outputting z = h^s(z_B||L), the algorithm outputs z_B||L.

Explanation / Answer

consider H(x)=H(x) which means

that zB=h(zB1||xB)=h(zB1||xB)=zBzB=h(zB1||xB)=h(zB1||xB)=zB,

but this can't happen since the hash compression function hh is supposed to be

collision resistant.

It's also obvious that if xB=xB and zB1=zB1then there's a

collision zB=zB because zB1=h(zB2||xB1)=h(zB2||xB1)=zB1

and apply this recursively until reach x1 or x1.

b) In order for this construction to not be collision resistant, a collision in the

underlying h^8 must be found, but this contradicts the assumption that h^8 is

collision resistant, thus such construction is collision resistant.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.