Section 12.4. CMAC

[Page 372 (continued)]

12.4. CMAC

The Data Authentication Algorithm defined in FIPS PUB 113, also known as the CBC-MAC (cipher block chaining message authentication code), is described in Chapter 11. This cipher-based MAC has been widely adopted in government and industry. [BELL00] demonstrated that this MAC is secure under a reasonable set of security criteria, with the following restriction. Only messages of one fixed length of mn bits are processed, where n is the cipher block size and m is a fixed positive integer. As a simple example, notice that given the CBC MAC of a one-block message X, say T = MAC(K, X), the adversary immediately knows the CBC MAC for the two-block message X||(X T.

Black and Rogaway [BLAC00] demonstrated that this limitation could be overcome using three keys: one key of length k to be used at each step of the cipher block chaining and two keys of length n, where k is the key length and n is the cipher block length. This proposed construction was refined by Iwata and Kurosawa so that the two n-bit keys could be derived from the encryption key, rather than being provided separately [IWAT03]. This refinement has been adopted by NIST cipher-based message authentication code (CMAC) mode of operation, for use with AES and triple DES. It is specified in NIST Special Publication 800-38B.

First, let us consider the operation of CMAC when the message is an integer multiple n of the cipher block length b. For AES, b = 128 and for triple DES, b = 64. The message is divided into n blocks, M₁, M₂,...,M_n. The algorithm makes use of a k-bit encryption key K and an n-bit constant K₁. For AES, the key size k is 128, 192, or 256 bits; for triple DES, the key size is 112 or 168 bits. CMAC is calculated as follows (Figure 12.12a):

---

[Page 373]

C1	= E(K,M1)
C2	= E(K,[M2 C3	= E(K,[M3 ·
·
·
Cn	= E(K,[Mn n1 T	= MSBTlen(Cn)

where

T	= message authentication code, also referred to as the tag
Tlen	= bit length of T
MSBs(X)	= the s leftmost bits of the bit string X

Figure 12.12. Cipher-Based Message Authentication Code (CMAC)

If the message is not an integer multiple of the cipher block length, then the final block is padded to the right (least significant bits) with a 1 and as many 0s as necessary so that the final block is also of length b. The CMAC operation then proceeds as before, except that a different n-bit key K₂ is used instead of K₁.

The two n-bit keys are derived from the k-bit encryption key as follows:

L = E(K, 0ⁿ)

K₁ = L · x

K₂ = L · x² = (L · x) · x

where multiplication (·) is done in the finite field (2ⁿ) and x and x² are first and second order polynomials that are elements of GF(2ⁿ) Thus the binary representation of x consists of n - 2 zeros followed by 10; the binary representation of x² consists of n - 3 zeros followed by 100. The finite field is defined with respect to an irreducible polynomial that is lexicographically first among all such polynomials with the minimum possible number of nonzero terms. For the two approved block sizes, the polynomials are and x⁶⁴ + x⁴ + x³ + x + 1 and x¹²⁸ + x⁷ + x² + x + 1.

---

[Page 374]

To generate K₁ and K₂ the block cipher is applied to the block that consists entirely of 0 bits. The first subkey is derived from the resulting cipher text by a left shift of one bit, and, conditionally, by XORing a constant that depends on the block size. The second subkey is derived in the same manner from the first subkey. This property of finite fields of the form GF(2ⁿ)was explained in the discussion of MixColumns in Chapter 5.