Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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$?

share|improve this question
    
Are you asking if someone can find a way to find a collision in the above construction? –  poncho Jan 19 '13 at 20:15
    
Yes, exactly -- without having one for $h$. –  user4797 Jan 19 '13 at 20:36
    
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? –  poncho Jan 19 '13 at 20:44
    
Just concatenating them together. –  user4797 Jan 19 '13 at 20:48
    
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. –  Paŭlo Ebermann Jan 20 '13 at 1:23

1 Answer 1

up vote 2 down vote accepted

The answer is that you can't; if you have a collision in $h^*$, you also have a collsion 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)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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