Effcient collision attack for the Davies-Meyer compression function

RudeusGreyrat

12/27/23, 11:13 PM

We have a block cipher $E:\{0,1\}^{128}\times\{0,1\}^{128}\rightarrow\{0,1\}^{128}$.

We know that the PRP advantage of E is Adv$_E^{PRP}=t/2^{128}$ where $t$ is the time needed by the algorithm to get the maximum advantage.

From $E$ we define $E'$ such that $E':\{0,1\}^{128}\times\{0,1\}^{128}\rightarrow\{0,1\}^{128}$ and $E'(k,\cdot)=E(k\bmod126,\cdot)$

Two questions:

What is the PRP advantage of $E'$
Propose an efficient collision attack for the Davies-Meyer compression function associated with $E'$

My guesses were for Q1 was $t/2^{128}$ also for $E'$ but it was really out of intuition so I am not sure.

The attack I propose for Q2 is the one with birthday bound but I was not able to elaborate any longer. Any help will be much appreciated specially because I lack some expertise in the basic concepts ...

0 + 1

block-cipher

pseudo-random-permutation

fgrieu

12/28/23, 4:13 PM

Homework dump is off-[topic](https://crypto.stackexchange.com/help/on-topic) unless it's shown what was done and where one is stuck. Throwing vague (and, it happens, invalid) "guesses" do not count. The $k\bmod126$ part of the question may have a typo. Suggestions: Get an understanding of what $E'$ is w.r.t. $E$, and what _"a collision attack for the Davies-Meyer compression function associated with $E′$"_ aims at producing. The second question is then easy. For the first question, write down the definition of $\mathsf{Adv}_E^{PRP}$, which is an indispensable step towards a solution.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Effcient collision attack for the Davies-Meyer compression function

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.