One-key MAC

One-key MAC (OMAC) is a message authentication code constructed from a block cipher much like the CBC-MAC algorithm.

Officially there are two OMAC algorithms (OMAC1 and OMAC2) which are both essentially the same except for a small tweak. OMAC1 is equivalent to CMAC, which became an NIST recommendation in May 2005.

It is free for all uses: it is not covered by any patents.^[1] In cryptography, CMAC is a block cipher-based message authentication code algorithm.^[2] It may be used to provide assurance of the authenticity and, hence, the integrity of data. This mode of operation fixes security deficiencies of CBC-MAC (CBC-MAC is secure only for fixed-length messages).^{[citation needed]}

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 and named the resulting algorithm One-Key CBC-MAC (OMAC) in their papers.^[5] They later submitted OMAC1,^[6] a refinement of OMAC, and additional security analysis.^[7] The OMAC algorithm reduces the amount of key material required for XCBC. CMAC is equivalent to OMAC1.

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 msb(k₁) = 0, then k₂ = k₁ ≪ 1, else k₂ = (k₁ ≪ 1) ⊕ C.
4. Return keys (k₁, k₂) for the MAC generation process.

As a small example, suppose b = 4, C = 0011₂, and k₀ = E_k(0) = 0101₂. Then k₁ = 1010₂ and k₂ = 0100 ⊕ 0011 = 0111₂.

The CMAC tag generation process is as follows:

1. Divide message into b-bit blocks m = m₁ ∥ ... ∥ m_n−1 ∥ m_n, 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 m_n′ = k₁ ⊕ m_n else m_n′ = k₂ ⊕ (m_n ∥ 10...0₂).
3. Let c₀ = 00...0₂.
4. For i = 1, ..., n − 1, calculate c_i = E_k(c_i−1 ⊕ m_i).
5. c_n = E_k(c_n−1 ⊕ m_n′)
6. Output t = msb_ℓ(c_n).

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.

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"^[8]
• Ruby implementation^[9]

References[]

External links[]

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