1
$\begingroup$

I learned that the output of hash function from Merkle Damgard is

H(x) = ZB+1 = h(ZB || L) = h(ZB - 1 || XB || L) where XB = block of padded x and L = XB+1

and it is proven that H(x) is collision resistant. However, what if I tweak the H(x) by extracting L from the compression function h(x) s.t

H(x) = h(ZB - 1 || XB) || L

I feel like this makes H(x) to be not collision resistant, but I don't know how to design an attack for this hash function. Can someone give me an idea (perhaps hint) to design such attack?

NOTE: Before anyone screams at me about anything, I want to say YES this is a practice question from a cryptography textbook. That is why I asked for a HINT not an answer. Thanks :)

$\endgroup$
1
$\begingroup$

Why don't you look at it the other way; suppose you could find a collision with your modified H(x) = h(ZB - 1 || XB) || L; could you use that collision to find a collision in the original H?

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Sorry, I don't really get it. I thought my newly modified H(x) needs to be compared with its h(x), instead of the original H, to prove whether it is collision resistant or not. Am I wrong? $\endgroup$ – ThomasWest Nov 20 '17 at 18:13
  • $\begingroup$ @ThomasWest: if you prove that, if you can find a collision in the new $H$, you can find a collision in the original $H$, then you've proven that the new $H$ is at least as collision resistant as the original. $\endgroup$ – poncho Nov 20 '17 at 18:17
  • $\begingroup$ Can you give more hint? I recently thought that this case is actually a collision-resistant problem $\endgroup$ – ThomasWest Nov 20 '17 at 18:54
1
$\begingroup$

I am new to this too but would like to give it a try (as a test to my understanding). The compression function h(x) is collision resistance to start with, and length(L) << length(X), so the adversary can find a collision by brute force. However the same attack requires the adversary to brute force the whole message space X to find collision, hence the new H(x) is not as secure as the original Merkle Damgard scheme.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Interesting, I just thought that this problem might be a collision-resistant case. $\endgroup$ – ThomasWest Nov 20 '17 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.