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'$$?

• "you can verify this in the exercises at the end of this chapter" ... did you try and perform the exercises? Have you tried simply substituting $m_i$ with $m_i'$ in the AES based function given? – Maarten Bodewes Oct 14 '18 at 22:25
• which book? did you look for errata? The exercise is same? – kelalaka Oct 14 '18 at 22:42
• @kelalaka Yes, the book is Crpytography Engineering: Design Principles and Practical Applications. – Miraclefruit Oct 14 '18 at 22:47
• @MaartenBodewes I did try as I mentioned below the picture. If I substitute mi with mi' then I would get H2 = AESk(H1 XOR m2') correct? – Miraclefruit Oct 14 '18 at 22:48

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.

• I was definitely going about this the wrong way. This is clear, thank you! – Miraclefruit Oct 15 '18 at 15:18