Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
