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 λ. The hash function H is shown below and only accepts inputs of length 2λ:
H(x):
k | m <-- x
return F(k, m)
I'm having a lot of trouble trying to come up with a distinguisher.
I was told as a hint 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.
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!
What I have tried:
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λ, but the output length is λ.
I'm not sure how to apply the above 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.
Submit an article or tip