Show that the CBC-MAC construction applied to a PRP is not collision resistant

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.

• Remember that you can decrypt any block you want too, like the all-zero block. – Squeamish Ossifrage Feb 26 '19 at 1:15
• 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. – Jonathan Harvey Feb 26 '19 at 1:17
• 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)? – Squeamish Ossifrage Feb 26 '19 at 1:18
• @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. – Jonathan Harvey Feb 26 '19 at 1:28
• 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)$? – poncho Feb 26 '19 at 4:09