0
$\begingroup$

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!

Improve this question
$\endgroup$
7
  • $\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
    Oct 10 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
    Oct 10 at 16:45
  • $\begingroup$ Try choosing any $k_1$, $m_1$ and $k_2$; can you then find a $m_2$. $\endgroup$
    – Daniel S
    Oct 11 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
    Oct 11 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
    Oct 12 at 4:21

0

Reset to default

Your Answer

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