6
$\begingroup$

Is hashing the last block in the Merkle-Damgård necessary in preventing collisions? i.e. What if I just outputted $z_B || L$, where $z_i$ is the hash of the last block of the message, L is the length of the message and B is the number of blocks, instead of $H(z_B || L)$?

| improve this question | | | | |
$\endgroup$
2
$\begingroup$

There are many variants of the Merkle-Damgård idea, but it all boils down to fixing a problem in a reduction.

The cryptographic object we are considering is a hash function on sequences of blocks defined by iteratively applying a compression function.

The reduction we are talking about is the reduction that takes a collision in the hash function and turns it into a collision for the compression function, by starting at the end of the messages and searching backwards for a collision.

The problem with the reduction is that when the two colliding messages are of unequal length, chasing down a collision in the compression function may fail when we get to the beginning of the shorter message.

The fix is to ensure that messages of unequal length must produce a collision somewhere, for instance by encoding the length at the end of the sequence that is hashed. Messages of unequal length must then produce a collision.

Another possible fix, as you suggest, is to append the length to the hash value. This trivially forces any two colliding messages to be of equal length. And that removes the obstruction to the naive reduction.

Why don't we do this? It will significantly increase the length of the hash value, without giving us any real security increase for that extra length. One could also imagine that it reduces the utility of the hash function, since one may not want to reveal the length of the message in certain applications (far from all). However, there would be trivial fixes available for those cases.

| improve this answer | | | | |
$\endgroup$
3
$\begingroup$

The purpose of hashing the last block is simply to prevent leaking information like, $L$, the length of the input. It's also important so that if $L\leq \langle 2 \rangle$, then $H$ is still compressing the input.

That being said, if you don't hash the last block of the Merkle-Damgård transform, $H$ is still collision-resistant, assuming that $h$ is collision resistant.

Let $\Pi=(Gen,H)$ and $\Pi'=(Gen,h)$. Assume $h$ is a collision-resistant hash function. Suppose for a contradiction that we can find a poly-time adversary $\mathcal{A}$ that finds a collision in $H$ with non-negligible probability $\delta(n)$. We will now construct a poly-time adversary $\mathcal{A}'$ that will find a collision in $h$.

$\mathcal{A}'$ begins by running $\mathcal{A}$ and finding a collision in $H$ such that $H^s(x)=x_B\Vert L=x_B'\Vert L'=H^s(x')$ and $x\neq x'$. Since the length is sent in the open and $x_B\Vert L=x_B'\Vert L'$, then it must be the case that $L=L'$. Define $\mathcal{A}'$ to output whatever $\mathcal{A}$ outputs.

Because $|x|=|x'|=L$, then we can find a collision by proceeding inductively. Since $x\neq x'$, then there must exist some $i$ where $1\leq i\leq B$ such that $x_i\Vert z_{i-1} \neq x_i'\Vert z_{i-1}'$.

Working backwards from the output, find the first such $i$. It must be the case that $h^s(x_i\Vert z_{i-1}) = h^s(x_i'\Vert z_{i-1}')$ and so we have found a collision in $h$. Have $\mathcal{A}$ output $x_i\Vert z_{i-1}$ and $x_i'\Vert z_{i-1}'$.

But this means that we have found a collision in $h$ by calling $\mathcal{A}$ only a polynomial number of times which implies that $\mathcal{A}'$ also runs in polynomial time i.e. $$\text{Pr[Hash-Coll}_{\mathcal{A}',\Pi'}(n)=1]$$ is not bounded by any negligible function, contradicting the collision-resistance of $h$.

| improve this answer | | | | |
$\endgroup$

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.