# Having trouble providing a distinguisher proving this hash function is not collision-resistant

As suggested by the title, I'm working on an exercise where I'm given a hash function $$H$$ that takes in an input string $$x$$. I'm supposed to construct a distinguisher that proves $$H$$ isn't collision-resistant. I'm given a block cipher $$F$$, $$F^{-1}$$ as well. $$F$$ generates outputs of length $$\lambda$$. The hash function $$H$$ is shown below and only accepts inputs of length $$2\lambda$$:

H(x):
k | m <-- x
return F(k, m)


I'm having a lot of trouble trying to come up with a distinguisher. I get that the block cipher $$F$$ is only one-to-one if the key is fixed, so $$F(k, .)$$ is one-to-one, but $$F(., .)$$ isn't. I know this makes sense as the input for $$F(., .)$$ would be of length $$2\lambda$$, but the output length is $$\lambda$$.

I was also told that to consider that it's a block cipher and not a PRF. I get that this means that for a fixed key $$k$$, the outputs will be unique for each input $$x$$ for a block cipher, but this isn't the case for a PRF.

Additionally, I was told that the property of being able to invert is useful for this problem.

I'm not sure how to apply these hints into solving the question. I don't have a clue on how to come up with a distinguisher besides using brute-force (which is obviously not the answer I should be doing because this would be really slow), and I'm not sure how $$F$$ being a block cipher would help here. All this would suggest is that the collision comes from different keys (so the first half of the two different strings will differ) because $$F$$ is a one-to-one function. But I'm not sure how to produce a collision with different keys other than brute force.

Does anyone have some tips that can guide me in the right direction? I have been trying to solve this question for a while, but I haven't been able to get anywhere. Any sort of help is appreciated!

• HINT: Rather than looking at showing that it isn't collision resistant, can you think of a way to fins a second pre-image for an input $x_1=k_1|m_1$. Oct 10 at 6:38
• @DanielS Are we supposed to show that the hash isn't second pre-image resistant? Wouldn't that require something that has the exact same hash as $H(x_1)$? In other words an input where the output is equal to the output of $F(k_1, m_1)$? In that case, I'm still not sure how to approach that because the block cipher is one-to-one, so the key would have to be different, so I'm still not sure how to tackle this problem other than brute force, which we shouldn't be doing. Oct 10 at 16:45
• Try choosing any $k_1$, $m_1$ and $k_2$; can you then find a $m_2$. Oct 11 at 2:39
• @DanielS I get that we're supposed to be doing that, but it still doesn't appear very clear how we could possibly get a collision with an $m_2$ without brute forcing. We end up with $F(k_1, m_1)$ and $F(k_2, m_2)$, but somehow, $F(k_2, m_2) = F(k_1, m_1)$ because we know it has to be collision-resistant. It still doesn't appear clear to me how we can easily get $F(k_2, m_2) = F(k_1, m_1)$ through two different keys. Oct 11 at 5:06
• RESOLVED: The collision case was $x_1 = k_1 | F^{-1}(k_1, c)$, $x_2 = k_2 | F^{-1}(k_2, c)$, where $c$ is just a random 128-bit string. Oct 12 at 4:21