Dan Boneh's explanation of why Davies-Meyer requires the final step of XOR with the previous Hash

Question

This is from this video https://www.coursera.org/learn/crypto/lecture/XZt5V/constructing-compression-functions

At 2:44, Dan Boneh explains why the XOR is required.

This is his explanation

m - message to be hashed
H - output of previous hash (chaining input)
h - hash function
E - Encryption function
D - Decryption function

h(H, m) = E(m, H)

(instead of h(H, m) = E(m, H) XOR H )

You can choose a random H, m & m' & construct a

H' = D(m', E(m, H))
which will give you a collision for m & m'

He says that the Decryption will cancel out the Encryption which will result in the collision.

1. Can someone explain how?
2. Why is he allowed to choose H'? Shouldn't you be allowed only to choose m' for an attack? Why do you get to choose H' also?

IMP: I have read other explanations for why the XOR is needed & I am convinced also. However, here I am trying to understand Dan Boneh's explanation.

Answer 1

Dan Boneh's explanation is about finding a collision for the compression function $h$ defined by $h:\ (H,m)\mapsto h(H,m)\underset{\text{def}}=E(m,H)$ where $E$ is a block cipher with first parameter as key. Notice that the input of function $h$ is neither $H$ nor $m$; it's the pair $(H,m)$, or equivalently the bitstring $H\mathbin\|m$.

Finding a collision for $h$ is finding two distinct inputs to the function $h$ such that the output is the same. That is finding an $(H,m)$ and a different $(H',m')$ such that $h(H,m)=h(H',m')$.

The method Dan Boneh uses is to choose arbitrarily $H$, $m$, and $m'\ne m$; then compute $H'=D(m',E(m,H))$, where $D$ us the decryption function for the block cipher $E$. We'll use that $D$ is such that $\forall k,\ \forall c$, $E(k,D(k,c))=c$. This can be readily proven from the more usual $\forall k,\ \forall p$, $D(k,E(k,p))=p$.

From $H'=D(m',E(m,H))$, it follows $E(m',H')=E(m',D(m',E(m,H)))$. And then applying the above property of $D$ with $k=m'$ and $c=E(m,H)$, it comes $E(m',H')=E(m,H)$. And since we have chosen $m'\ne m$, it holds $(m',H')\ne(m,H)$. Dan Boneh's method thus always exhibits a collision for $h$.

Dan Boneh is allowed to chose $H'$ because he aims at exhibiting a collision for $h$. He would not be allowed that if he was trying to exhibit a collision for the different functions $h_H:\ m\mapsto h_H(m)\underset{\text{def}}=E(m,H)$, where $H$ is a fixed parameter rather than part of the input. Neither would he for a collision of a hash function built per the Merkle-Damgård construction using $h$ as the compression function.