One-key MAC explained

One-key MAC (OMAC) is a family of message authentication codes constructed from a block cipher much like the CBC-MAC algorithm. It may be used to provide assurance of the authenticity and, hence, the integrity of data. Two versions are defined:

• The original OMAC of February 2003, which is seldom used. The preferred name is now "OMAC2".
• The OMAC1 refinement, which became an NIST recommendation in May 2005 under the name CMAC.^[1]

OMAC is free for all uses: it is not covered by any patents.^[2]

History

The core of the CMAC algorithm is a variation of CBC-MAC that Black and Rogaway proposed and analyzed under the name "XCBC"^[3] and submitted to NIST.^[4] The XCBC algorithm efficiently addresses the security deficiencies of CBC-MAC, but requires three keys.

Iwata and Kurosawa proposed an improvement of XCBC that requires less key material (just one key) and named the resulting algorithm One-Key CBC-MAC (OMAC) in their papers.^[5] They later submitted the OMAC1 (= CMAC),^[6] a refinement of OMAC, and additional security analysis.^[7]

Algorithm

To generate an ℓ-bit CMAC tag (t) of a message (m) using a b-bit block cipher (E) and a secret key (k), one first generates two b-bit sub-keys (k₁ and k₂) using the following algorithm (this is equivalent to multiplication by x and x² in a finite field GF(2^b)). Let ≪ denote the standard left-shift operator and ⊕ denote bit-wise exclusive or:

1. Calculate a temporary value k₀ = E_k(0).
2. If msb(k₀) = 0, then k₁ = k₀ ≪ 1, else k₁ = (k₀ ≪ 1) ⊕ C; where C is a certain constant that depends only on b. (Specifically, C is the non-leading coefficients of the lexicographically first irreducible degree-b binary polynomial with the minimal number of ones: 0x1B for 64-bit, 0x87 for 128-bit, and 0x425 for 256-bit blocks.)
3. If, then, else .
4. Return keys (k₁, k₂) for the MAC generation process.

As a small example, suppose,, and . Then and .

The CMAC tag generation process is as follows:

1. Divide message into b-bit blocks, where m₁, ..., m_n−1 are complete blocks. (The empty message is treated as one incomplete block.)
2. If m_n is a complete block then else .
3. Let .
4. For, calculate .
   1. Output .

The verification process is as follows:

1. Use the above algorithm to generate the tag.
2. Check that the generated tag is equal to the received tag.

Variants

CMAC-C1^[8] is a variant of CMAC that provides additional commitment and context-discovery security guarantees.

Implementations

• Python implementation: see the usage of the AES_CMAC function in "impacket/blob/master/tests/misc/test_crypto.py", and its definition in "impacket/blob/master/impacket/crypto.py"^[9]
• Ruby implementation^[10]

External links

• The AES-CMAC Algorithm
• The AES-CMAC-96 Algorithm and Its Use with IPsec
• The Advanced Encryption Standard-Cipher-based Message Authentication Code-Pseudo-Random Function-128 (AES-CMAC-PRF-128)
• OMAC Online Test
• More information on OMAC
• Rust implementation

Notes and References

1. Dworkin. Morris. Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication. 10.6028/nist.sp.800-38b. 2016. free.
2. Web site: CMAC: Non-licensing . Rogaway . Phillip . May 27, 2020 . Phillip Rogaway's statement on intellectual property status of CMAC.
3. Book: Advances in Cryptology – CRYPTO 2000. Black. John. Rogaway. Phillip. 2000-08-20. Springer, Berlin, Heidelberg. 978-3540445982. 197–215. en. 10.1007/3-540-44598-6_12.
4. Black. J. Rogaway. P. A Suggestion for Handling Arbitrary-Length Messages with the CBC MAC.
5. Book: Fast Software Encryption. 2887. Iwata. Tetsu. Kurosawa. Kaoru. 2003-02-24. Springer, Berlin, Heidelberg. 978-3-540-20449-7. 129–153. en. OMAC: One-Key CBC MAC. 10.1007/978-3-540-39887-5_11. Lecture Notes in Computer Science.
6. Iwata. Tetsu. Kurosawa. Kaoru. 2003. OMAC: One-Key CBC MAC – Addendum. In this note, we propose OMAC1, a new choice of the parameters of OMAC-family (see [4] for the details). Test vectors are also presented. Accordingly, we rename the previous OMAC as OMAC2. (That is to say, test vectors for OMAC2 were already shown in [3].) We use OMAC as a generic name for OMAC1 and OMAC2..
7. Book: Progress in Cryptology - INDOCRYPT 2003 . limited. Iwata. Tetsu. Kurosawa. Kaoru. 2003-12-08. Springer Berlin Heidelberg. 9783540206095. Johansson. Thomas. Lecture Notes in Computer Science. 2904 . 402–415. en. Stronger Security Bounds for OMAC, TMAC, and XCBC. 10.1007/978-3-540-24582-7_30. Maitra. Subhamoy. 10.1.1.13.8229.
8. Book: Bhaumik . Ritam . Chakraborty . Bishwajit . Choi . Wonseok . Dutta . Avijit . Govinden . Jérôme . Shen . Yaobin . The Committing Security of MACs with Applications to Generic Composition . Lecture Notes in Computer Science . 2024 . 14923 . Reyzin . Leonid . Stebila . Douglas . Advances in Cryptology – CRYPTO 2024 . https://link.springer.com/chapter/10.1007/978-3-031-68385-5_14 . en . Cham . Springer Nature Switzerland . 425–462 . 10.1007/978-3-031-68385-5_14 . 978-3-031-68385-5.
9. Web site: Impacket is a collection of Python classes for working with network protocols.: SecureAuthCorp/impacket. 15 December 2018. GitHub.
10. Web site: Ruby C extension for the AES-CMAC keyed hash function (RFC 4493): louismullie/cmac-rb. 4 May 2016. GitHub.