1
$\begingroup$

enter image description here

I'm trying answer the following question. Yes, it is a homework question, so I'm not asking for the answer directly but would like to get some pointers on how to solve it.

So far I have spent several hours thinking about this to no avail. I know I'm missing something incredibly simple. I have tried various permutations of fixing messages m1 or m2 or m3 to be constant while others change and seeing how that affects the value of c3 when it is returned, as well as various permutations of fixing the messages to be 0^blen in order to try to find a collision. Hoping to get some pointers in the right direction.

Improve this question
$\endgroup$
17
  • 2
    $\begingroup$ Remember that you can decrypt any block you want too, like the all-zero block. $\endgroup$
    – Squeamish Ossifrage
    Commented Feb 26, 2019 at 1:15
  • $\begingroup$ Thank you @SqueamishOssifrage , when you say that I can decrypt any block I want to, you mean decryption using that fact that by definition a PRP has an inverse F^-1(k, F(k, x))? I'm sorry, new to crypto and really struggling with some of the core concepts. $\endgroup$
    – Jonathan Harvey
    Commented Feb 26, 2019 at 1:17
  • 1
    $\begingroup$ Correct. And it works for any block y, F^-1(k, y), whether or not you know the x such that y = F(k, x) in advance. For example, can you use F^-1(k, 0)? $\endgroup$
    – Squeamish Ossifrage
    Commented Feb 26, 2019 at 1:18
  • $\begingroup$ @SqueamishOssifrage When you say use F^-1(k, 0), would that be a fact that I use literally as a decryption step in the algorithm I devise to find collisions, or used to show a relation between the ciphertexts in the given hash function? For example, is it true that c2 = F(k, F(k, m1)) = m1 when m2 is the all-zero block? Based on my understanding of PRPs it is guaranteed there is is some inverse function F^-1(k, y) = x. Is it true that for all PRPs F, F^1 = F(k, F(k, x))? I appreciate your help. I feel as though I'm circling around all the right concepts but need to put them together. $\endgroup$
    – Jonathan Harvey
    Commented Feb 26, 2019 at 1:28
  • 4
    $\begingroup$ Actually, you don't need to compute $F^{-1}$; you can trivially find collisions even if $F$ is noninvertible. Hint: suppose you have $m_1, m_2$ and $m'_1$ where $m_1 \ne m'_1$; how could you compute $m'_2$ such that $H(k, m_1 || m_2) = H(k, m'_1 || m'_2)$? $\endgroup$
    – poncho
    Commented Feb 26, 2019 at 4:09

0

Reset to default

Your Answer

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