# MAC forgery using the DES's Complementary Property

I've started reading on MACs and working on a problem where given a MAC construction as $$H_0=IV$$ and for every $$i>0$$ $$H_i=H_{i−1} \oplus E_{M[i]}(H_{i−1})$$ and the tag is $$(IV,E_{k_1}(H_ℓ))$$, I would like to show for a DES as a cipher this construction does not give message integrity.

The way I'm thinking of approaching this is, I can start by using the complementary property of DES cipher, to show that for message $$M_1$$ given that $$H_1=H_{0} \oplus E_{M}(H_{0})$$ is equal $$-H_1$$ for message $$-M_1$$ (complement of message $$M_1$$). Hence, under the chosen message attack with given construction, I can perform existential forgery. Based on my reading and the details defined in Coursera I think I almost got the concept but not sure if I'm on right track?

Yes, you are on the right track.

Let the MAC is given as

• $$H_0 = IV$$
• $$H_i=H_{i−1}\oplus E_{M[i]}(H_{i−1})$$ and for every $$i>0$$, and
• $$tag = (IV,E_{k_1}(H_\ell))$$

and the attacker has the tag $$t$$. The observation is that the message is used as a key in the encryption. If the attackers can use some property of the cipher like a fixed point or more then they can forge. Actually more than the existential forgery, if we omit the keeping the IV same, they can find another message that is exactly the same MAC output.

The simple case: one block message $$m$$ and its tag;

$$t = (IV, IV \oplus E_{m}(IV))$$ for a fixed IV, and this is hard. We need some weaknesses in the Encryption algorithm. As you noted the DES has complementation property

$$E_K(P)=C \iff E_{\overline{K}}(\overline{P})=\overline{C}$$ then the attacker can use this as;

Let $$C = E_m(IV)$$ then with DES complement property $$\overline{C} = E_\overline{m}(\overline{IV})$$ Then

$$\overline{IV} \oplus E_{\overline{m}}(\overline{IV}) = \overline{IV} \oplus \overline{C} = IV \oplus C$$ therefore this is a forge with almost the same tag $$t$$ with just complemented IV $$t' = (\overline{IV},\overline{IV} \oplus E_{\overline{m}}(\overline{IV})).$$