Join Log in
Score:2
avatar Crypto

Why this function isn't second preimage resistant?

in flag
Emma

Why is $h(k,m)$ not second-preimage resistant? Let $E_k$ be a block cipher where the message space is the same as the key space. $$h(k,m)=E_k(m\oplus k)\oplus k$$

I've been reading about second preimage resistance and attempting to try this example.

What I currently know is that given an input $m$, and therefore the hash $h(k,m)$, I need to find another input $\hat{m} \ne m$ such that $h(k,m) = h(k,\hat{m})$.

I have a feeling that a collision might be something like this (but I'm not sure): \begin{align*} E_k(m\oplus k)\oplus k & = E_k(\hat{m}\oplus k)\oplus k= E_k(h(k,m)\oplus k)\oplus k \end{align*}

108
0 + 0
poncho avatar
my flag
poncho
Why do you believe that it is not second-preimage resistant?
1
Reply
kelalaka avatar
in flag
kelalaka
How do you control the $k$ ?
0
Reply
in flag
Emma
I've corrected the formula, it should XOR with the $k$ instead of $m$. Thank you @kelalaka for pointing that out.
0
Reply
in flag
Emma
@poncho I made a mistake before, now that I have edited the question, do you believe that it is second-preimage resistant?
0
Reply
fgrieu avatar
ng flag
fgrieu
"I need to find another input $\hat{m} \ne m$ such that $h(k,m) = h(k,\hat{m})$" is wrong. To exhibit a second preimage for a function given an input, you need to find another input with the same output. What's an "input" for the function at hand? What's the given input? So what exactly do you need to exhibit? Now, just do that.
2
Reply
in flag
Emma
@fgrieu I'm not sure I understand your point correctly, so please correct me if I am wrong. The given (fixed) input is $m$, so I need to find another input $\hat{m}$, s.t. $\hat{m} \ne m \wedge h(k,m) = h(k,\hat{m})$. Have I misunderstood something?
0
Reply
in flag
Emma
@kelalaka I think the key $k$ is known to the adversary if that is what you atually asking.
0
Reply
kelalaka avatar
in flag
kelalaka
Do we have a fixed key $k$ or not? For a fixed $k$, the $h(k,m)$ is a permutation.
0
Reply
in flag
Emma
the key is fixed. yes $h(k,m)$ is assumed to be a bijective function.
0
Reply
kelalaka avatar
in flag
kelalaka
In this case, there is only one pre-image. If the key is known to the adversary it is easy to find the pre-image.
0
Reply
fgrieu avatar
ng flag
fgrieu
My reading of the question: "why is $h(k,m)=E_k(m\oplus k)\oplus k$ not second preimage resistant?" is that it asks how, given input $(k,m)$, we can find an input $(\hat k,\hat m)$ with $h(\hat k,\hat m)=h(k,m)$ and $(\hat k,\hat m)\ne(k,m)$ (that is $\hat k\ne k$ or/and $\hat m\ne m$). Just do that!
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

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.