Security Analysis of CMAC in the Multi-user Model

CMAC, also known as OMAC1, is an efficient message authentication code (MAC) and has been standardized by NIST and other organizations. It has been widely applied in IPSec, IKE and many wireless networks. Multi-user security captures a practical scenario where an adversary targets a particular service related to multiple users. Lots of MAC constructions have been rigorously analyzed in the multi-user model. However, the concrete analysis for CMAC in the multi-user model is still a blank in the literature. To fill the gap, we provide a concrete multi-user security bound for CMAC in this paper. Our bound is better than that from generic reduction and we observe that the online security of CMAC in the multi-user model does not degrade from the single-user model.

1. 1.

   We omit lower-order terms and constant factors.

2. 2.

   In the single-user model, the assumption is \(\ell \le 2^{n/3 }.\).

This study was funded by the National Key Research and Development Program of China (2019YFB2101601) and the National Natural Science Foundation of China (62372294).

Authors and Affiliations

1. Shanghai Jiao Tong University, Shanghai, 200240, China

   Xiangyang Zhang & Lei Wang

2. Xiamen University, Xiamen, 361005, China

   Yaobin Shen

Corresponding author

Correspondence to Lei Wang .

Editors and Affiliations

1. Strativia, NIST Associate, Largo, MD, USA

   Nicky Mouha

2. Stony Brook University, Stony Brook, NY, USA

   Nick Nikiforakis

A A Proof Details of Lemma 1

Firstly we establish an upper bound on \({\text {Pr}}[\tau \in \mathsf {bad_{1}}]\). Recall that the event \(\mathsf {bad_{1}}\) occurs when there exist two distinct users i and j such that \(K_i=K_j\). As the keys of each user are sampled independently and uniformly at random in the ideal world, for any two fixed i and j, the probability that \(K_i=K_j\) holds is exactly \(2^{-k}\). Therefore, considering all the pairs of the users, we can conclude that

Then we establish an upper bound on \({\text {Pr}}[\tau \in \mathsf {bad_{2}}]\). Recall that the event \(\mathsf {bad_{2}}\) occurs when there exists an entry \((x,y)_J\in \textsf{P}\) such that \(x=0^n\) and \(J=K_i\) with \(i\in [u]\). \(\mathcal {D}\) can make p primitive queries at most and thus he can guess p different keys at most. For a particular user \(i\in [u]\), the chance that there exists a primitive query such that \(J=K_i\) holds is bounded by \(p/2^k\). Considering all the users, we have

Next we establish an upper bound on \({\text {Pr}}[\tau \in \mathsf {bad_{3}}]\). Observe that CMAC processes the first \(m-1\) blocks of a message M in a CBC MAC manner, where m represents the total block length of M. For any two distinct messages \(M_1\) and \(M_2\) with block length \(m \le 2^{n/4}\), Bellare et al. [4, 22] show that

Building on this, we can derive the following lemma.

Lemma 2

For any \(M \in \{0,1\}^{mn}\) with \(m \le 2^{n/4}\) and any \(Y \in \{0,1\}^{n}\) it follows that

Proof

Let \(M_1 = X\Vert Y \) and \(M_2 = 0^n\). Then the event \(\textsf{CBC}_K(M)=Y\) is the same as \(\textsf{CBC}_K(M_1)=\textsf{CBC}_K(M_2)\). Hence we can obtain

Now we consider domain collisions between \(\textsf{P}'_i\) and a primitive entry \((x,y)_J\). For a fixed primitive entry \((x,y)_J\) and a specific user, the probability that \(K_i=J\) holds is \(1/2^k\). Assume that \(\ell \) is the maximum block length of messages for all evaluation queries. By Lemma 2, for fixed \((x,y)\in \textsf{P}^{K_i}\) and \((x',y')\in \textsf{P}'_i\), the probability that \(x'=x\) holds is bounded by \(\frac{2\sqrt{\ell }}{2^{n}}+\frac{16 \ell ^{4}}{2^{2n}}\). With \(|\textsf{P}'_i| \le q_i\) and \(|\textsf{P}^{K_i}| \le p\), such a bad event happens for a user is bounded \(\frac{2q_ip\sqrt{\ell }}{2^{n+k}}+\frac{16q_ip \ell ^{4}}{2^{2n+k}}\). Therefore, taking into account all the users, we can get

Now we establish an upper bound on \({\text {Pr}}[\tau \in \mathsf {bad_{4}}]\). In this case, we consider range collisions between \(\textsf{P}'_i\) and a primitive entry \((x,y)_J\). For a fixed primitive entry \((x,y)_J\) and a specific user i, the probability that \(K_i=J\) holds is \(1/2^k\). Further, for a primitive entry \((x,y)_J\) and a fixed \((x',y')\in \textsf{P}'_i\) the probability that \(y=y'\) satisfies is \(1/2^{n+k}\). For a specific user i, considering all the primitive entries and \(|\textsf{P}'_i| \le q_i\) the probability that such a bad event happens is bounded by \(q_i p/2^{n+k}\). Therefore, by varying over all possible choices of users, we have

Next we establish an upper bound on \({\text {Pr}}[\tau \in \mathsf {bad_{5}}]\). All the elements in \(\textsf{rng}(\textsf{P}'_i)\), that are the set of the responded tags for evaluation queries, are sampled uniformly at random. Then for any fixed \((x,y), (x',y')\in \textsf{P}'_i\), the probability of \(y=y'\) is \(1/2^n\). with \(|\textsf{P}'_i|\le q_i\), it follows that, for each user i, the probability of \(y=y'\) is bounded by \(q_i^2/2^n\). Therefore, considering all the users, we can obtain:

Next we jointly constrain the probabilities of \(\mathsf {bad_6}\) and \(\mathsf {bad_7}\). Prior to this, we introduce the following lemma extracted from the referenced paper [31] For additional details, please refer to the paper.

Lemma 3

([31]). For CMAC in the single-user setting, if the distinguisher makes q evaluation queries of total block length of \(\sigma \) with block length of each message is \(m_i\) for \(1\le i\le q\), the probability that there exist collisions between final inputs and intermediate inputs is upper bounded by

Note that in Lemma 3, “collisions between final inputs and intermediate inputs” encompass both the collisions between two final inputs and the collisions between a final input and an intermediate input. That is the reason that we bound the probabilities of \(\mathsf {bad_6}\) and \(\mathsf {bad_7}\) together. As Lemma 3 specifically pertains to a single user, expanding our consideration to include all users, we have

Now we establish an upper bound on \({\text {Pr}}[\tau \in \mathsf {bad_{8}}]\). For each user i, the set \(\textsf{P}_i\) contains, at most, \(\sigma _i-q_i\) pairwise distinct elements When \(|\textsf{P}_i|=\sigma _i-q_i\) it indicates that there exist no collisions among intermediate inputs (excluding final inputs) and among intermediate outputs, and in such circumstances \(\textsf{bad}_{8}\) is most likely to occur. To streamline the analysis, we systematically index the elements in \(\textsf{P}_i\) based on their order of occurrence. Specifically, \(\textsf{P}_i=\{(x^{i}_{1},y^{i}_{1}),\cdots ,(x^{i}_{\sigma _i-q_i},y^{i}_{\sigma _i-q_i})\}\). We set an event \(\textsf{E}^{i}_j\) as true if \(y_{j}^{i} \notin \textsf{rng}(\textsf{P}'_i)\) with \(1 \le i \le u, 1\le j \le \sigma _i-q_i\). Additionally, we define another event \(\textsf{E}^{i}_{\le j}\) as \(\bigcup _{t=1}^{j}\textsf{E}^{i}_{t}\). It is observed that

and hence

The consideration of all users leads us to conclude that

Assuming that \(\sigma \le 2^{n-1}\), we can get

Reprints and permissions

© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG

Policies and ethics