Network Working Group JH. Song
Request for Comments: 4493 R. Poovendran
Category: Informational University of Washington
J. Lee
Samsung Electronics
T. Iwata
Nagoya University
June 2006
The AES-CMAC Algorithm
Status of This Memo
This memo provides information for the Internet community. It does
not specify an Internet standard of any kind. Distribution of this
memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2006).
Abstract
The National Institute of Standards and Technology (NIST) has
recently specified the Cipher-based Message Authentication Code
(CMAC), which is equivalent to the One-Key CBC MAC1 (OMAC1) submitted
by Iwata and Kurosawa. This memo specifies an authentication
algorithm based on CMAC with the 128-bit Advanced Encryption Standard
(AES). This new authentication algorithm is named AES-CMAC. The
purpose of this document is to make the AES-CMAC algorithm
conveniently available to the Internet Community.
Song, et al. Informational [Page 1]
RFC 4493 The AES-CMAC Algorithm June 2006
Table of Contents
1. Introduction ....................................................2
2. Specification of AES-CMAC .......................................3
2.1. Basic Definitions ..........................................3
2.2. Overview ...................................................4
2.3. Subkey Generation Algorithm ................................5
2.4. MAC Generation Algorithm ...................................7
2.5. MAC Verification Algorithm .................................9
3. Security Considerations ........................................10
4. Test Vectors ...................................................11
5. Acknowledgement ................................................12
6. References .....................................................12
6.1. Normative References ......................................12
6.2. Informative References ....................................12
Appendix A. Test Code .............................................14
1. Introduction
The National Institute of Standards and Technology (NIST) has
recently specified the Cipher-based Message Authentication Code
(CMAC). CMAC [NIST-CMAC] is a keyed hash function that is based on a
symmetric key block cipher, such as the Advanced Encryption Standard
[NIST-AES]. CMAC is equivalent to the One-Key CBC MAC1 (OMAC1)
submitted by Iwata and Kurosawa [OMAC1a, OMAC1b]. OMAC1 is an
improvement of the eXtended Cipher Block Chaining mode (XCBC)
submitted by Black and Rogaway [XCBCa, XCBCb], which itself is an
improvement of the basic Cipher Block Chaining-Message Authentication
Code (CBC-MAC). XCBC efficiently addresses the security deficiencies
of CBC-MAC, and OMAC1 efficiently reduces the key size of XCBC.
AES-CMAC provides stronger assurance of data integrity than a
checksum or an error-detecting code. The verification of a checksum
or an error-detecting code detects only accidental modifications of
the data, while CMAC is designed to detect intentional, unauthorized
modifications of the data, as well as accidental modifications.
AES-CMAC achieves a security goal similar to that of HMAC [RFC-HMAC].
Since AES-CMAC is based on a symmetric key block cipher, AES, and
HMAC is based on a hash function, such as SHA-1, AES-CMAC is
appropriate for information systems in which AES is more readily
available than a hash function.
This memo specifies the authentication algorithm based on CMAC with
AES-128. This new authentication algorithm is named AES-CMAC.
Song, et al. Informational [Page 2]
RFC 4493 The AES-CMAC Algorithm June 2006
2. Specification of AES-CMAC
2.1. Basic Definitions
The following table describes the basic definitions necessary to
explain the specification of AES-CMAC.
x || y Concatenation.
x || y is the string x concatenated with the string
y.
0000 || 1111 is 00001111.
x XOR y Exclusive-OR operation.
For two equal length strings, x and y,
x XOR y is their bit-wise exclusive-OR.
ceil(x) Ceiling function.
The smallest integer no smaller than x.
ceil(3.5) is 4. ceil(5) is 5.
x << 1 Left-shift of the string x by 1 bit.
The most significant bit disappears, and a zero
comes into the least significant bit.
10010001 << 1 is 00100010.
0^n The string that consists of n zero-bits.
0^3 means 000 in binary format.
10^4 means 10000 in binary format.
10^i means 1 followed by i-times repeated
zeros.
MSB(x) The most-significant bit of the string x.
MSB(10010000) means 1.
padding(x) 10^i padded output of input x.
It is described in detail in section 2.4.
Key 128-bit (16-octet) long key for AES-128.
Denoted by K.
First subkey 128-bit (16-octet) long first subkey,
derived through the subkey
generation algorithm from the key K.
Denoted by K1.
Song, et al. Informational [Page 3]
RFC 4493 The AES-CMAC Algorithm June 2006
Second subkey 128-bit (16-octet) long second subkey,
derived through the subkey
generation algorithm from the key K.
Denoted by K2.
Message A message to be authenticated.
Denoted by M.
The message can be null, which means that the length
of M is 0.
Message length The length of the message M in octets.
Denoted by len.
The minimum value of the length can be 0. The
maximum value of the length is not specified in
this document.
AES-128(K,M) AES-128(K,M) is the 128-bit ciphertext of AES-128
for a 128-bit key, K, and a 128-bit message, M.
MAC A 128-bit string that is the output of AES-CMAC.
Denoted by T.
Validating the MAC provides assurance of the
integrity and authenticity of the message from
the source.
MAC length By default, the length of the output of AES-CMAC is
128 bits. It is possible to truncate the MAC.
The result of the truncation should be taken in most
significant bits first order. The MAC length must be
specified before the communication starts, and
it must not be changed during the lifetime of the
key.
2.2. Overview
AES-CMAC uses the Advanced Encryption Standard [NIST-AES] as a
building block. To generate a MAC, AES-CMAC takes a secret key, a
message of variable length, and the length of the message in octets
as inputs and returns a fixed-bit string called a MAC.
The core of AES-CMAC is the basic CBC-MAC. For a message, M, to be
authenticated, the CBC-MAC is applied to M. There are two cases of
operation in CMAC. Figure 2.1 illustrates the operation of CBC-MAC
in both cases. If the size of the input message block is equal to a
positive multiple of the block size (namely, 128 bits), the last
block shall be exclusive-OR’ed with K1 before processing. Otherwise,
the last block shall be padded with 10^i (notation is described in
section 2.1) and exclusive-OR’ed with K2. The result of the previous
Song, et al. Informational [Page 4]
RFC 4493 The AES-CMAC Algorithm June 2006
process will be the input of the last encryption. The output of
AES-CMAC provides data integrity of the whole input message.
+-----+ +-----+ +-----+ +-----+ +-----+ +---+----+
| M_1 | | M_2 | | M_n | | M_1 | | M_2 | |M_n|10^i|
+-----+ +-----+ +-----+ +-----+ +-----+ +---+----+
| | | +--+ | | | +--+
| +--->(+) +--->(+)<-|K1| | +--->(+) +--->(+)<-|K2|
| | | | | +--+ | | | | | +--+
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
|AES_K| | |AES_K| | |AES_K| |AES_K| | |AES_K| | |AES_K|
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
| | | | | | | | | |
+-----+ +-----+ | +-----+ +-----+ |
| |
+-----+ +-----+
| T | | T |
+-----+ +-----+
(a) positive multiple block length (b) otherwise
Figure 2.1. Illustration of the two cases of AES-CMAC
AES_K is AES-128 with key K.
The message M is divided into blocks M_1,...,M_n,
where M_i is the i-th message block.
The length of M_i is 128 bits for i = 1,...,n-1, and
the length of the last block, M_n, is less than or equal to 128 bits.
K1 is the subkey for the case (a), and
K2 is the subkey for the case (b).
K1 and K2 are generated by the subkey generation algorithm
described in section 2.3.
2.3. Subkey Generation Algorithm
The subkey generation algorithm, Generate_Subkey(), takes a secret
key, K, which is just the key for AES-128.
The outputs of the subkey generation algorithm are two subkeys, K1
and K2. We write (K1,K2) := Generate_Subkey(K).
Subkeys K1 and K2 are used in both MAC generation and MAC
verification algorithms. K1 is used for the case where the length of
the last block is equal to the block length. K2 is used for the case
where the length of the last block is less than the block length.
Song, et al. Informational [Page 5]
RFC 4493 The AES-CMAC Algorithm June 2006
Figure 2.2 specifies the subkey generation algorithm.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Algorithm Generate_Subkey +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ +
+ Input : K (128-bit key) +
+ Output : K1 (128-bit first subkey) +
+ K2 (128-bit second subkey) +
+-------------------------------------------------------------------+
+ +
+ Constants: const_Zero is 0x00000000000000000000000000000000 +
+ const_Rb is 0x00000000000000000000000000000087 +
+ Variables: L for output of AES-128 applied to 0^128 +
+ +
+ Step 1. L := AES-128(K, const_Zero); +
+ Step 2. if MSB(L) is equal to 0 +
+ then K1 := L << 1; +
+ else K1 := (L << 1) XOR const_Rb; +
+ Step 3. if MSB(K1) is equal to 0 +
+ then K2 := K1 << 1; +
+ else K2 := (K1 << 1) XOR const_Rb; +
+ Step 4. return K1, K2; +
+ +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Figure 2.2. Algorithm Generate_Subkey
In step 1, AES-128 with key K is applied to an all-zero input block.
In step 2, K1 is derived through the following operation:
If the most significant bit of L is equal to 0, K1 is the left-shift
of L by 1 bit.
Otherwise, K1 is the exclusive-OR of const_Rb and the left-shift of L
by 1 bit.
In step 3, K2 is derived through the following operation:
If the most significant bit of K1 is equal to 0, K2 is the left-shift
of K1 by 1 bit.
Otherwise, K2 is the exclusive-OR of const_Rb and the left-shift of
K1 by 1 bit.
In step 4, (K1,K2) := Generate_Subkey(K) is returned.
Song, et al. Informational [Page 6]
RFC 4493 The AES-CMAC Algorithm June 2006
The mathematical meaning of the procedures in steps 2 and 3,
including const_Rb, can be found in [OMAC1a].
2.4. MAC Generation Algorithm
The MAC generation algorithm, AES-CMAC(), takes three inputs, a
secret key, a message, and the length of the message in octets. The
secret key, denoted by K, is just the key for AES-128. The message
and its length in octets are denoted by M and len, respectively. The
message M is denoted by the sequence of M_i, where M_i is the i-th
message block. That is, if M consists of n blocks, then M is written
as
- M = M_1 || M_2 || ... || M_{n-1} || M_n
The length of M_i is 128 bits for i = 1,...,n-1, and the length of
the last block M_n is less than or equal to 128 bits.
The output of the MAC generation algorithm is a 128-bit string,
called a MAC, which is used to validate the input message. The MAC
is denoted by T, and we write T := AES-CMAC(K,M,len). Validating the
MAC provides assurance of the integrity and authenticity of the
message from the source.
It is possible to truncate the MAC. According to [NIST-CMAC], at
least a 64-bit MAC should be used as protection against guessing
attacks. The result of truncation should be taken in most
significant bits first order.
The block length of AES-128 is 128 bits (16 octets). There is a
special treatment if the length of the message is not a positive
multiple of the block length. The special treatment is to pad M with
the bit-string 10^i to adjust the length of the last block up to the
block length.
For an input string x of r-octets, where 0 <= r < 16, the padding
function, padding(x), is defined as follows:
- padding(x) = x || 10^i where i is 128-8*r-1
That is, padding(x) is the concatenation of x and a single ’1’,
followed by the minimum number of ’0’s, so that the total length is
equal to 128 bits.
Figure 2.3 describes the MAC generation algorithm.
Song, et al. Informational [Page 7]
RFC 4493 The AES-CMAC Algorithm June 2006
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Algorithm AES-CMAC +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ +
+ Input : K ( 128-bit key ) +
+ : M ( message to be authenticated ) +
+ : len ( length of the message in octets ) +
+ Output : T ( message authentication code ) +
+ +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Constants: const_Zero is 0x00000000000000000000000000000000 +
+ const_Bsize is 16 +
+ +
+ Variables: K1, K2 for 128-bit subkeys +
+ M_i is the i-th block (i=1..ceil(len/const_Bsize)) +
+ M_last is the last block xor-ed with K1 or K2 +
+ n for number of blocks to be processed +
+ r for number of octets of last block +
+ flag for denoting if last block is complete or not +
+ +
+ Step 1. (K1,K2) := Generate_Subkey(K); +
+ Step 2. n := ceil(len/const_Bsize); +
+ Step 3. if n = 0 +
+ then +
+ n := 1; +
+ flag := false; +
+ else +
+ if len mod const_Bsize is 0 +
+ then flag := true; +
+ else flag := false; +
+ +
+ Step 4. if flag is true +
+ then M_last := M_n XOR K1; +
+ else M_last := padding(M_n) XOR K2; +
+ Step 5. X := const_Zero; +
+ Step 6. for i := 1 to n-1 do +
+ begin +
+ Y := X XOR M_i; +
+ X := AES-128(K,Y); +
+ end +
+ Y := M_last XOR X; +
+ T := AES-128(K,Y); +
+ Step 7. return T; +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Figure 2.3. Algorithm AES-CMAC
Song, et al. Informational [Page 8]