# Collision resistance of composed hash functions

Consider the following hash function

$H^{1\circ2}(x)=H^1(H^2(x))$

I have been asked to prove that if $H^1$ is CR, $H^{1\circ2}$ will not generally itself be CR. I am assuming $H^2$ is not CR, this is not explicitly stated. I have seen similar questions here but they always consider a double hash with a single function, not two.

I understand that by "not generally" or similar wording it is meant that there exists at least a case where $H^{1\circ2}$ is not CR. Admittedly however I thought that since $H^1$ is hashing $H^2(x)$, this makes the resulting hash function CR as well. Is this not always the case?

• What happens if I can find a collision in $H^2$? – Squeamish Ossifrage Dec 27 '17 at 2:54
• A collision in $H^2$ means there is a $x'$ different from $x$ with $H^2(x) = H^2(x')$ But what would that mean for $H^1$ (and therefore $H^{1°2}$), that you could replace $H^2(x)$ with $H^2(x')$ and have $H^1(H^2(x'))$? That would mean that $H^1$ is somehow not CR anymore, but I am supposed to assume it is. Or am I not on the right track? – Nooby Dec 27 '17 at 3:36
• How is $H^1(H^2(x))$ related to $H^1(H^2(x'))$, if $H^2(x) = H^2(x')$? Let's say $h$ is the common value of $H^2(x)$ and $H^2(x')$. – Squeamish Ossifrage Dec 27 '17 at 3:43

Suppose you have found a collision for $H^2$, ie a pair $(x_1,x_2), x_1\neq x_2$ such that $H^2(x_1)=H=H^2(x_2)$.
Now let $F$ be a deterministic function (like $H^1$?). Does $$(F\circ H^2)(x_1)=F(H^2(x_1))=F(H)=F(H^2(x_2))=(F\circ H^2)(x_2)$$ yield anything interesting?
• Thank you for your answer. As I mentioned before what I see is that you could replace $H^2(x_1)$ with $H^2(x_2)$ in $H^1$, or $F$ in your example, pretty much what you did. What I see then are two different inputs that would yield the same result i.e. a collision. But I thought CR for $H^1$ was to be assumed. – Nooby Dec 27 '17 at 19:21
• @Nooby well, the above shows how to construct a collision on $H^{1\circ 2}$ from a collision on $H^2$, the fact that $H^1$ is CR is irrelevant at that point, because it gets the same (intermediate) input both times. – SEJPM Dec 27 '17 at 19:25
• I see, it is the wording of the question that confused me then, since I was asked to prove that such statement "does not hold in general", it sounded to me that it was the case most of the times (i.e. that $H^{1°2}$ is CR). I guess it did not make sense in my head that at all it took was a collision in the input to make the CR of the function irrelevant. But it seems to be as simple as that. – Nooby Dec 27 '17 at 19:31