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$:

   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!

  • $\begingroup$ 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$. $\endgroup$
    – Daniel S
    Commented Oct 10, 2023 at 6:38
  • $\begingroup$ @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. $\endgroup$
    – HughJass24
    Commented Oct 10, 2023 at 16:45
  • $\begingroup$ Try choosing any $k_1$, $m_1$ and $k_2$; can you then find a $m_2$. $\endgroup$
    – Daniel S
    Commented Oct 11, 2023 at 2:39
  • $\begingroup$ @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. $\endgroup$
    – HughJass24
    Commented Oct 11, 2023 at 5:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – HughJass24
    Commented Oct 12, 2023 at 4:21


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.