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.

If we have a hash function $h(x)$ and then a hash function $H(X) = h(h(X_0) || h(X_1))$ where $X_0$ is the first half of $X$, $X_1$ is the second half of $X$ and $||$ is concatenation. Then assuming we can easily find a collision for $H$, then it would be easy to find a collision for $h$ as well - Therefore finding a collision for $H$ is as hard as finding one for $h$.

Why is this? I can to some extent understand why that might be the case, but I can't logically connect the dots. Can anyone help me with some logic or math behind it or link to some resources where it is explained. I have tried google, but without the precise correct terminology I'm having a hard time finding the right pages.

Thanks

share|improve this question
    
If you extend this scheme directly to a tree-hash it will be trivially vulnerable to collisions with a different length. That's why tree-hashes typically use a different hash function for inner hashes and leaf hashes. –  CodesInChaos Apr 23 '12 at 18:27
add comment

1 Answer 1

up vote 8 down vote accepted

The general idea is that either one of the inner hashes, or the combining hash must collide, since there is not other place to introduce the collision.

Assume we found a collision for H. This means we have X, Y with $X \neq Y$ such that:

$h(h(X_0)||h(X_1)) = h(h(Y_0)||h(Y_1))$

Now we define: $A = h(X_0)||h(X_1)$ and $B = h(Y_0)||h(Y_1)$

This gives us a new equation h(A) = h(B)

  • If $A \neq B$, we found a collision, and are done.
  • If $A=B$ we know that $h(X_0)||h(X_1) = h(Y_0)||h(Y_1)$, which we can split into $h(X_0)=h(Y_0) \land h(X_1)=h(Y_1)$. From $X \neq Y$ follows $X_0 \neq Y_0 \lor X_1 \neq Y_1$. Thus at least one of $h(X_0)=h(Y_0)$ and $h(X_1)=h(Y_1)$ has different inputs on both sides of the equation, and thus represents a collision.
share|improve this answer
    
Don't you mean h(A) = h(B) instead of h(A) = A(B) or am I missing something? –  Mads Apr 23 '12 at 19:09
    
@Mads yes of course. –  CodesInChaos Apr 23 '12 at 19:26
    
Thank you for your time :) Appreciate it –  Mads Apr 23 '12 at 19:28
add comment

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.