Why do m and m' both hash to H2? I'm trying to understand the following text:


  


I'm having trouble understanding why $m$ and $m'$ both hash to $H_2$. I tried doing truth tables for $m_1'$ and $m_2'$ given the equations but I don't seem to be getting anywhere with them.

Is it also possible to justify that claim with high probability that $m \neq m'$?
OK, lets go through this step by step:

Given:

$H_1 = E(m_1)$

$H_2 = E(E(m_1) \oplus m_2)$

and

$H_1' = E(m_2 \oplus E(m_1))$ because $m_1' = m_2 \oplus E(m_1)$

$H_2' = E(H_1' \oplus H_2 \oplus m_2 \oplus H_1)$ because $m_2' = H_1' \oplus H_2 \oplus m_2 \oplus H_1$

then substitute $H_1'$ in $H_2'$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus H_2 \oplus m_2 \oplus H_1)$

then substitute $H_2$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus E(E(m_1) \oplus m_2) \oplus m_2 \oplus H_1)$

and $H_1$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus E(E(m_1) \oplus m_2) \oplus m_2 \oplus E(m_1))$

re-arrange the parameters of XOR:

$H_2' = E(E(E(m_1) \oplus m_2) \oplus E(E(m_1) \oplus m_2) \oplus E(m_1) \oplus m_2)$

now we can see that two parts can be stricken out:

$H_2' = E( \require{cancel}\cancel{E(E(m_1) \oplus m_2) \oplus E(E(m_1) \oplus m_2)} \oplus E(m_1) \oplus m_2)$

so we are left with:

$H_2' = E(E(m_1) \oplus m_2)$

meaning that $H_2' = H_2$.

Given that $m_1'$ and $m_2'$ are unlikely to be equal to $m_1$ and $m_2$ we can clearly see that many pairs of related, but different messages hash to the same result, creating collisions.

Here $E$ is of course the AES function.