2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Related question. Another on why we have this XOR (or group operation; in practice it tends to be addition with a few suppressed carries). Yet another. Indeed, the question is different. $\endgroup$ – fgrieu Nov 6 '20 at 9:22
  • 1
    $\begingroup$ @fgrieu - I have read the other explanations even earlier. My question here is about making sense of Dan Boneh's explanation. $\endgroup$ – user93353 Nov 6 '20 at 10:10
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Dan Boneh is allowed to chose H′ because he aims at exhibiting a collision for h. - but in reality how would an attacker be able to influence the value of H'? Isn't that necessary for the attack to succeed? $\endgroup$ – user93353 Nov 9 '20 at 5:40
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – fgrieu Nov 9 '20 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.