Mathematical proof of a combined hash function

Question

I´ve just started with crypto and I am trying to solve an exercise sheet. I am, however, not good at mathematical proofs and got a bit stuck on a certain - probably easy - question:

I´ve got three hash functions:

• $H_1:= \{0,1\}^* \to \{0,1\}^a$
• $H_2:= \{0,1\}^* \to \{0,1\}^b$
• $H_3:=\{0,1\}^* \to \{0,1\}^b$

And I have to proof that: If at least one of $H_1, H_2, H_3$ are collision resistant $M:= \{0,1\}^* \to \{0,1\}^{a+b}$ for $M:= H_1(x)||H_2(x)||H_3(x)$ is collision resistant, too.

Intuitively I would say that $H_2$ and $H_3$ are not collision resistant, since they are shortened to the same length $b$.

I have started with assuming that $M$ is not collision resistant by changing the definition to:

$h(x_1) = h(x_2) = h(x_3) $ for a triplet $(x_1,x_2,x_3)$.

But I am not quite sure, if this is the correct way to do it.

Can I even proof it in one go? Or do I need several steps - like proofing $H_2 = H_3$ first?

Answer 1

Ignoring the issue of output length I mention in the comments, you should be able to prove this without intermediate steps. Here is an outline of how I would do it.

1. Without loss of generality let one particular hash function be the one that is collision resistant. It doesn't matter which one. Say $H_3$.
2. Assume that $M$ is not collision resistant. This means, you can find $m_0\neq m_1$ such that $M(m_0)=M(m_1)$.
3. Show how this would lead to a collision in $H_3$ directly. This leads to a contradiction, so $M$ must be collision resistant.

This is a proof by contradiction.