2
$\begingroup$

Why do you need padding block at the end of Merkle Damgard if the input is multiple of block length? I learned that it was not collision resistant if a dummy block is not added to the end but I want to understand why this is the case.

Let's say MD outputs Zb instead of H(Zb||L). What is the reasoning for why this particular construction isn't collision resistant?

$\endgroup$
2
$\begingroup$

Let's say we have a message $m$ whose length is not a multiple of the block length, and that our hashing scheme pads it to a multiple of the block length by appending the padding $p_m$ to it. That is to say, $$\textsf{Pad}(m) = m \,\|\, p_m,$$ where the length of $m \,\|\, p_m$ is a multiple of the block size.

Now, if messages whose length was a multiple of the block size were not padded at all, consider what would happen if one deliberately tried to hash the modified message $m' = m \,\|\, p_m$. Since the length of $m'$, by construction, is a multiple of the block size, we'd have $$\textsf{Pad}(m') = m \,\|\, p_m = \textsf{Pad}(m).$$

And since the final hash value is calculated from the padded message, this would mean that $m$ and $m'$ would have the same hash value.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Addition: this answer shows why we must pad messages that are multiple of the block length if hashing messages not matching this criteria is allowed. There is another reason to pad with the message length including if the hash is restricted to messages multiple of the block size, see this question $\endgroup$ – fgrieu Apr 16 '18 at 14:01

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.