# Why CBC-MAC encrypts at each step

Considering CBC-MAC as:

$$\qquad H_0 = IV = 0$$

$$\qquad H_i = E_k(P_i \oplus H_{i-1})$$

$$\qquad MAC = H_n$$

What are the properties that makes this "safer" (less exposed to failure) than just:

$$\qquad H_0 = IV = 0$$

$$\qquad H_i = P_i \oplus H_{i-1}$$

$$\qquad MAC = E_k(H_n)$$

Please use simple terms (a didactic explanation for non cryptographers is appreciated)

• Example: Given a tag for the two block message consisting of all-zeroes, try and find a tag for the two-block message consisting of all-ones. – SEJPM Apr 16 '19 at 15:40
• I do not get it, can you please elaborate? – user1156544 Apr 16 '19 at 16:09

## 1 Answer

What are the properties that makes this "safer" (less exposed to failure) than just: [simple construction]

Well, there's an easy attack on the simple construction: Pick any message block $$P$$ and construct a message $$M=P\|P$$ (so $$P$$ twice). Now compute the MAC-tag of that message: $$\text{MAC}=E_k(\text{IV}\oplus P\oplus P)$$ which is just $$E_k(\text{IV})$$ because $$x\oplus x=0$$. Now pick any different message $$P'$$ and $$M'=P'\|P'$$ and compute the tag for that message: $$\text{MAC}'=E_k(\text{IV}\oplus P'\oplus P')$$ which again is $$E_k(\text{IV})$$. So both messages have the same tag. As soon as you see the tag for any of them, you can make somebody accept the other one as well. This is a property that we don't want from MACs.

If it helps your imagination: $$P=0^n$$ and $$P'=1^n$$, i.e. they are the message of all-zeroes and all-ones.

• Good answer! But I am afraid we still haven't answered why the CBC-MAC is good(in theory) apart from the fact it doesn't suffer this particular attack. CBC-MAC security requires that the input are carefully encided (prefix-free). But if we apply the same encoding to the broken Mac, the attack becomes more involved maybe impossible. – Marc Ilunga Apr 17 '19 at 11:35
• @MarcIlunga well, actually CBC-MAC is secure for fixed-length attackers, or if the message length is prepended to the plaintext. I carefully chose my forgery example so that it would still work in both of these scenarios. – SEJPM Apr 19 '19 at 9:17
• @SEPJM I agree with your answer, that's what I would give(you beat me to it ;) ). But thinking about it later I thought it's a bit "unfair" because in CBC we assume a proper encoding. If we use the same encoding with the broken Mac the attack is not possible as is. We could still use the same trick with messages of the form $0\ldots1$ that would be padded with same block. Similarly for $0\ldots 0|0\ldots 10$. Padded with $0\ldots 10$. – Marc Ilunga Apr 20 '19 at 8:31