Consider the following hash function


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?

  • $\begingroup$ What happens if I can find a collision in $H^2$? $\endgroup$ – Squeamish Ossifrage Dec 27 '17 at 2:54
  • $\begingroup$ 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? $\endgroup$ – Nooby Dec 27 '17 at 3:36
  • $\begingroup$ 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')$. $\endgroup$ – 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?

  • $\begingroup$ 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. $\endgroup$ – Nooby Dec 27 '17 at 19:21
  • $\begingroup$ @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. $\endgroup$ – SEJPM Dec 27 '17 at 19:25
  • $\begingroup$ 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. $\endgroup$ – Nooby Dec 27 '17 at 19:31
  • $\begingroup$ Don't forget to mark this answer as accepted if it solved your question as I presume it did (?) $\endgroup$ – Maarten Bodewes Dec 29 '17 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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