# Question about hash collisions

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

-

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

## 1 Answer

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.
-

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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9336927533149719, "perplexity_flag": "head"}