Score:0

Merkle-Damgård construction

bw flag

Let $H^f$ be a hash function designed using Merkle-Damgård construction on $f:\{0,1\}^{2n}\to\{0,1\}^n$. Write an algorithm that makes approximately $2.2^{n/2}$ many queries to $f$ and find four messages that all hash to same value under $H^f$.

I get an idea to use length extension and 2 birthday attack to get four collision. But I am not able to write the appropriate solution. Can anyone help me to figure out.

fgrieu avatar
ng flag
I suggest you (A) write down the definition you get of the hash function for the largest input that requires two evaluations of $f$; (B) explain how you find an internal collision by varying the message input of the first $f$; (C) explain how you find a collision by varying the message input of the second $f$; (D) conclude. I don't get how we obtain $2.2^{n/2}$, I think the expected number of evaluations of $f$ is like $2^{n/2+1.326}$ (which is less for large $n$).
bw flag
yes this is approx value @fgrieu
poncho avatar
my flag
Perhaps instead of $2.2^{n/2}$, what was meant was $2 \cdot 2^{n/2} = 2 \times 2^{n/2}$
kelalaka avatar
in flag
[cross-posted at CS](https://cs.stackexchange.com/q/141917/94479)
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.