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$