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?