Finding a collision for a hash function 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$?
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&lt;i$, that means there must be a $j \le k &lt; 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)$