I'm trying to find a collision for the following (modified) Merkle–Damgård hash function.

Suppose we already have a hash function $h : \mathbb{Z}_2^{2·n} \to \mathbb{Z}_2^n$ for fixed length bit strings, with $h(0\ldots 0)= 0\ldots 0$.

The input $x$ (bit string, variable size) is divided into blocks $x_j$ of $n$ bit each, padding the last block with zeroes if necessary: $$ \overbrace{x_0}^{n \text{ bit}}|| \overbrace{x_1}^{n \text{ bit}}|| \ldots|| \overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1}|| 0\ldots 0}^{n \text{ bit}} $$

We add another block $x_{i}$ of $n$ bit, containing the binary representation of $|x|$ (length of x), resulting in:

$$ \overbrace{x_0}^{n \text{ bit}}||\overbrace{x_1}^{n \text{ bit}}||\ldots||\overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1} 0\ldots 0}^{n \text{ bit}}||\overbrace{|x|}^{n \text{ bit}} $$

Therefore we have $i+1$ blocks of $n$ bit each. For $0\leq j\leq i$, refer to the $j$th block as $b_j$.
Define $y_0 := 0\ldots 0||b_0$ and $y_j := h(y_{j-1})||b_j$ for $1\leq j\leq i$
($0\ldots 0||b_0$ and respectively $h(y_{j-1})||b_j$ means concatenating everything together).

The hash function $h^*$ is then defined as $$h^*(x) := h(y_i)$$

How can one find a collision for $h^*$ without having one for $h$?

  • $\begingroup$ Are you asking if someone can find a way to find a collision in the above construction? $\endgroup$
    – poncho
    Jan 19, 2013 at 20:15
  • $\begingroup$ Yes, exactly -- without having one for $h$. $\endgroup$
    – user4797
    Jan 19, 2013 at 20:36
  • $\begingroup$ What precisely does $y_j := h(y_{j-1}) b_j$ mean? What operation are you using to combine $h(y_{j-1})$ and $b_j$ together? $\endgroup$
    – poncho
    Jan 19, 2013 at 20:44
  • $\begingroup$ Just concatenating them together. $\endgroup$
    – user4797
    Jan 19, 2013 at 20:48
  • $\begingroup$ Welcome to Cryptography Stack Exchange. I edited your question to use the more usual $||$ notation for concatenation, and to make the input and output size of $h$ clear. Feel free to edit again if you don't like this. $\endgroup$ Jan 20, 2013 at 1:23

1 Answer 1


The answer is that you can't; if you have a collision in $h^*$, you also have a collision in $h$.

The standard way to prove a collision-resistant hash based on a hash-resistant primitive is to show that if we are given a collision in the full hash, we can show that gives us a collision in the primitive. Hence if we believe we can't find a collision in the primitive, we hence can't find a collision in the full hash.

That technique appears to work quite well here.

Suppose we are given two colliding messages $M$ and $M'$, that is $M \neq M'$ and $h^*(M) = h^*(M')$. We will show how to examine how the two messages $M$ and $M'$ are processed by $h^*$ to show that there must have been some internal collision on one of the calls to $h$.

First, consider the case that $y_i \ne y'_i$. If that is the case, then we immediately have a collision, because $h(y_i) = h^*(M) = h^*(M') = h(y'_i)$

The other possible case is that $y_i = y'_i$. This implies that the length of the messages $M, M'$ are the same (because the lengths of $M, M'$ are included in the values $y_j, y'_j$.

We also know that $M, M'$ differ somewhere, that is, in at least one $n$-bit block. Let us call $j$ one of the positions that $M$ and $M'$ differ; that is, $b_j \neq b'_j$. This immediately implies that $y_j \neq y'_j$ (because $y_j, y'_j$ contain $b_j, b'_j$ as substrings).

Because $y_j \ne y'_j$ and $y_i = y'_i$ and $j<i$, that means there must be a $j \le k < i$ where $y_k \ne y'_k$ and $y_{k+1} = y'_{k+1}$. That immediately gives us a hash collision in h, because $h(y_k) = h(y'_k)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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