Timeline for Show that the CBC-MAC construction applied to a PRP is not collision resistant
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2019 at 19:01 | comment | added | fgrieu♦ | Hint: Fix any distinct $m_1$ and $m'_1$, and any $m_2$. Since $k$ is known, you can compute $c_1$, $c'_1$, and $c_2$. Chose an $m'_2$ that will cause $c_2=c'_2$. Then build a collision from that. Extra hint: you do not even need to compute $c_2$, much less $c_3$. | |
| Feb 26, 2019 at 13:10 | comment | added | poncho | That's a bit more complicated than what I was thinking (remember, unlike CBC-MAC, you know the 'key' $k$, and so can see the values of the internal variables $c_1, c_2$); however that is the right path. | |
| Feb 26, 2019 at 8:01 | history | edited | kelalaka | CC BY-SA 4.0 |
Cut he middle part from the image.
|
| Feb 26, 2019 at 7:48 | comment | added | Jonathan Harvey | @poncho your hint is helping me down a good path I think. I'm thinking it's related to the insecurity of CBC-MAC for variable-length messages? Given x = π»(π,π1||π2||m3), and y = π»(π,π1'||π2'||m3'), we can generate a collision by XORING m1' with x and then computing z = π»(π,m1||m2||m3||(π1' β x)||π2'||m3')...We know that y == z? | |
| Feb 26, 2019 at 6:43 | comment | added | Jonathan Harvey | @poncho Thanks for your input. This is due tonight and still hoping to make a final push to be able to solve. Is m2' something that the collision-finding algorithm would compute with the results of the previous hash function? Or does it have to do with the malleability of the encryption? I think your comment is saying, "encrypt once with m1 || m2, change m1, and there is a predictable way you can change m2 in order to see π»(π,π1||π2)=π»(π,πβ²1||πβ²2)"...? Wonder is whether that predicability depends on prior input or if it is a trivial change on any m1 to form m1' and see m2 change | |
| Feb 26, 2019 at 4:09 | comment | added | poncho | 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)$? | |
| Feb 26, 2019 at 3:17 | comment | added | Squeamish Ossifrage | What is the defining characteristic of F^-1 in relation to F? Might it help, perhaps, if you write it as $F_k(F_k^{-1}(x))$, or as the composition $(F_k \circ F_k^{-1})(x)$? | |
| Feb 26, 2019 at 3:11 | comment | added | Jonathan Harvey | @SqueamishOssifrage I think simplifying F(k, F^-1(k, 0)) is the missing piece. I don't know of any special facts about F(k, F^-1(k, 0)) that would be an equivalent expression, other than if we let m1 = F^-1(k, 0), and so c1 = F(k, F^-1(k, 0)). If we take that, and substitute it into F(k, m2 β F(k, F^-1(k, 0))) => F(k, m2 β c1), then the final expression => F(k, m3 β F(k, m2 β c1)). If we do not let m1 = F^-1(k, 0), I don't know how to simplify the expression. Also, you're right! Taking a break now to play some basketball. Hopefully the blood flow helps. Thank you! | |
| Feb 26, 2019 at 3:04 | comment | added | Squeamish Ossifrage | Side note: If you've spent six hours on this problem, that's a sign not that you're incompetent but that it's a good time for a breakβtake a walk around a pond, do something with your hands instead of your head like cooking a meal or playing some music, and then come back to this after your mind has had some time to relax. | |
| Feb 26, 2019 at 2:56 | comment | added | Squeamish Ossifrage | F(k, m2 β F(k, F^-1(k, 0)) is not F(k, m2 β F^-1(k, 0)). Simplify it piece by piece: What's a simpler way to write F(k, F^-1(k, 0))? Substitute that into F(k, m2 β F(k, F^-1(k, 0))); then simplify again, and so on. $$$$ Using the result of a previous hash lets you forge messages, if you use CBC-MAC (verbatim) as a MAC where the attacker doesn't know the key, but that's different from finding a collision under a known key. | |
| Feb 26, 2019 at 2:24 | comment | added | Jonathan Harvey | @SqueamishOssifrage Thank you for bearing with me. I should probably get it by now. F(k, m2 β c1) is the simpler way to write F(k, m2 β F^-1(k, 0)) but that is given in the problem so it seems circular to re-write it that way. Is there another way to write it? There is also F(k, m2 β F(k, (F(k, m1))) but I wouldn't call that simpler. That expression is given for c3 with different numbering (m3, c2) later in the problem, but I don't see the connection. . In my collision-finding algorithm, will I ever have to use the result of a previous hash (c3) as an input block to make this work? | |
| Feb 26, 2019 at 1:56 | comment | added | Squeamish Ossifrage | Can you write F(k, m2 β F(k, F^-1(k, 0)) in another, simpler way? Does the resulting expression appear anywhere elseβperhaps with different numberingβin the definition of H? | |
| Feb 26, 2019 at 1:54 | comment | added | Jonathan Harvey | @SqueamishOssifrage Okay. I have been thinking about this more for a few minutes. I'm thinking there is a core axiom or principle I'm not understanding how to apply. My first attempt at using F^-1(k, 0) as stated was to try and pass that expression into the hash function as either block m1 or m2 or m3 to see how that affected the final expression returned. I end up with something along the lines of F(k, m3 β F(k, F^-1(k, 0)) depending on which block I use as F^-1(k, 0). I have spent about 6 hours on this question, as a good gauge of how incompetent I appear to be in crypto. | |
| Feb 26, 2019 at 1:36 | comment | added | Squeamish Ossifrage | It is not true that F(k, F(k, x)) = F^-1(k, x) for a PRPβthat would make an excellent PRP distinguisher! (What is the probability that it holds for a uniform random permutation?) The hint I'm giving is just to try to use the inverse direction of the permutation F in order to construct a collision. Maybe try using the block x = F^-1(k, 0) whose encryption F(k, x) is 0. | |
| Feb 26, 2019 at 1:28 | comment | added | Jonathan Harvey | @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. | |
| Feb 26, 2019 at 1:18 | comment | added | Squeamish Ossifrage | 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)? | |
| Feb 26, 2019 at 1:17 | comment | added | Jonathan Harvey | 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. | |
| Feb 26, 2019 at 1:15 | comment | added | Squeamish Ossifrage | Remember that you can decrypt any block you want too, like the all-zero block. | |
| Feb 26, 2019 at 1:10 | review | First posts | |||
| Feb 26, 2019 at 7:28 | |||||
| Feb 26, 2019 at 1:10 | history | asked | Jonathan Harvey | CC BY-SA 4.0 |