# How to combine AES-CMACs

I have a primitive that is able to generate a AES-128-CMAC from a message.

$\operatorname{CMAC}(\text{MessageAddress}, \text{MessageLength}) \rightarrow \text{result}$

I cannot change this primitive. I don't have direct access to the key, nor to the internals of that function.

Let's say that I want to authenticate a message that is split over non-contiguous chunks. How is it possible to chain calls to this primitive while not opening a breach to an attack?

For example, if $M = M_1 || M_2 || \ldots || M_n$, compute

$\operatorname{CMAC}(\operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || \ldots || \operatorname{CMAC}(M_n))$

Of course, the result is completely different than $\operatorname{CMAC}(M)$ but that doesn't matter because both sides would implement the same algorithm for signing and verification.

However, is it still secure? Would it be better to use a XOR operation instead?

$\operatorname{CMAC}(\operatorname{CMAC}(M_1) \oplus \operatorname{CMAC}(M_2) \oplus \ldots \oplus \operatorname{CMAC}(M_n))$

Any other idea?

For example, if $$M = M_1 || M_2 || \ldots || M_n$$, compute

$$\operatorname{CMAC}(\operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || \ldots || \operatorname{CMAC}(M_n))$$

If we assume that the attacker cannot find two distinct messages $$M_1, M_2$$ with $$\operatorname{CMAC}(M_1) =\operatorname{CMAC}(M_2)$$ (which he is unlikely to if the number of messages being MAC'ed is considerably below $$2^{64}$$), then you're good.

That is, if the attacker is able to produce a message/MAC pair that validates with this construct, then either:

• He is able to construct a message/MAC pair for CMAC which we hasn't previously observed; that is $$CMAC( M' )$$, where $$M' = \operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || ... || \operatorname{CMAC}(M_n)$$ which he has not previously observed, or

• He finds a collision $$\operatorname{CMAC}(M_i) = \operatorname{CMAC}(M'_i)$$ (and reuses a top-level CMAC he has observed)

(Note that this initial analysis does not consider the possibility of an interaction between the bottom-level and top-level CMAC's, where the attack has actually observed the message $$M'$$ in one of the bottom level MACs; a full proof would need to address that)

Would it be better to use a XOR operation instead?

$$\operatorname{CMAC}(\operatorname{CMAC}(M_1) \oplus \operatorname{CMAC}(M_2) \oplus \ldots \oplus \operatorname{CMAC}(M_n))$$

That's far worse; consider the MAC of the message $$M_2 || M_1 || M_3 || M_4 || ... || M_n$$

• Thanks a lot. One question though: "consider the MAC of the message M2||M1": is that a typo, or did you mean I should consider reordering message chunks? – Cilyan Oct 10 '17 at 20:14
• @Cilyan: Reordering; suppose an attacker took a valid message (with a valid MAC), and reordered the block; how would that affect the MAC? – poncho Oct 10 '17 at 20:24
• You're right. Now I understand what you meant. – Cilyan Oct 10 '17 at 21:32

The XOR of the tags is trivially vulnerable to multiple easy attacks by an active attacker, which will yield the same tag, for example:

1. They can reorder chunks, because XOR is associative ($a \oplus (b \oplus c) = (a \oplus b) \oplus c$) and commutative ($a \oplus b = b \oplus a$).
2. They can triplicate any chunk, because $a \oplus a = 0$ and $a \oplus 0 = a$, therefore $a \oplus a \oplus a = a$.

Two simple alternatives:

• Compute the CMAC of the concatenation of the chunks, as you propose and poncho approves.
• For each chunk $M_i$, compute its tag as $T_i = \mathrm{CMAC}_K(T_{i-1} || M_i)$ (prepend the previous chunk's tag to the message for tag computation).

The latter has an advantage that you could transmit each $T_i$ along with its chunk $M_i$ to allow the recipient to fail fast on forgery attempts. (But beware the easy mistake of assuming that because $M_i$ is authentic it's therefore safe to act on the data that it contains.) The other, subtler advantage is that it authenticates no only the content of your messages, but also their context within the transcript of the communication.

• Thanks for the answer. Yes, I now understand how foolish that is with the XOR process. I cannot concatenate the previous CMAC with the next chunk, unfortunately, but that would have been a neat idea as it reduces the amount of storage necessary for all message chunks. – Cilyan Oct 10 '17 at 21:31