# Proving collision resistance of a hash function?

Let $f$, $g$, and $h$ be hash functions that each map binary strings of length $2n$ to binary strings of length $n$. Suppose that $h(x) = f(g(x)||g(x))$. Prove that if $f$ and $g$ are collision resistant then $h$ is also collision resistant.

This question was asked on an earlier assignment and my professor had taken it up in class using proof by contrapositive. I am expecting a question like this to show up on our final but I have forgotten how he answered it. Could anyone off some insight into how I can answer this?

• If you just write out the contrapositive statement you are pretty much there. – otus Nov 17 '15 at 16:20
• That is, "suppose $h$ is not collision resistant; that is, we knew of a collision in $h$, two values $x \ne x'$ where $h(x) = h(x')$. What does that imply about $f$ or $g$?" – poncho Nov 17 '15 at 16:54
• Next step is making two cases, according to if $g(x)=g(x')$, or not. – fgrieu Nov 17 '15 at 21:21

Recall that randomly chosen functions, used to model good hash functions, are collision resistant if we need on the order of $2^{n/2}$ queries in order to discover a collision with success probability a constant bounded away from zero.

Proof by contrapositive:

Assume $h$ is NOT collision resistant. Then we can find such collisions much faster than specified above, i.e., we can find $x\neq x'$ $x,x' \in \{0,1\}^{2n}$ with $h(x)=h(x')$. There are two possibilites.

In the first case $g(x)=g(x')$, in which case any function $f$ would yield a collision in $h$.

If on the other hand, $g$ is collision resistant and thus $g(x)\neq g(x')$, we must now have $f(g(x) || g(x)) = f(g(x') || g(x'))$ which implies that $f$ is not collision resistant since it is giving a collision to distinct inputs.