< draft-songlee-aes-cmac-01.txt   draft-songlee-aes-cmac-02.txt >
JunHyuk Song JunHyuk Song
Radha Poovendran
University of Washington
Jicheol Lee Jicheol Lee
INTERNET DRAFT Samsung Electronics Samsung Electronics
Expires: November 30, 2005 May 31 2005 Tetsu Iwata
INTERNET DRAFT Ibaraki University
Expires: May 6, 2006 November 7 2005
The AES-CMAC Algorithm The AES-CMAC Algorithm
draft-songlee-aes-cmac-01.txt draft-songlee-aes-cmac-02.txt
Status of This Memo Status of This Memo
By submitting this Internet-Draft, each author represents that any By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79. aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that Task Force (IETF), its areas, and its working groups. Note that
skipping to change at page 1, line 41 skipping to change at page 1, line 44
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
Copyright Notice Copyright Notice
Copyright (C) The Internet Society (2005). Copyright (C) The Internet Society (2005).
Abstract Abstract
National Institute of Standards and Technology (NIST) has newly National Institute of Standards and Technology (NIST) has newly
specified the Cipher based MAC (CMAC) which is equivalent to the specified the Cipher-based Message Authentication Code (CMAC)
One-Key CBC-MAC1 (OMAC1) algorithm submitted by Iwata and Kurosawa. which is equivalent to the One-Key CBC MAC1 (OMAC1) submitted by
OMAC1 efficiently reduces the key size of Extended Cipher Block Iwata and Kurosawa. This memo specifies the authentication algorithm
Chaining mode (XCBC). This memo specifies the authentication based on CMAC with 128-bit Advanced Encryption Standard (AES).
mechanism based on CMAC mode of operation with 128-bit Advanced This new authentication algorithm is named AES-CMAC.
Encryption Standard (AES) cipher block. This new authentication The purpose of this document is to make the AES-CMAC algorithm
algorithm is named AES-CMAC conveniently available to the Internet Community.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2
2. Specification of Language . . . . . . . . . . . . . . . . 2 2. Specification of AES-CMAC . . . . . . . . . . . . . . . . 3
3. AES-CMAC Algorithm . . . . . . . . . . . . . . . . . . . . 3 2.1 Basic definitions . . . . . . . . . . . . . . . . . . . . 3
3.1 Basic Definitions. . . . . . . . . . . . . . . . . . . . . 3 2.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.3 Subkey Generation Algorithm . . . . . . . . . . . . . . . 5
3.3 Input and Output . . . . . . . . . . . . . . . . . . . . . 5 2.4 MAC Generation Algorithm . . . . . . . . . . . . . . . . . 7
3.3.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.5 MAC Verification Algorithm . . . . . . . . . . . . . . . . 9
3.3.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . 5 3. Security Considerations . . . . . . . . . . . . . . . . . . 10
3.4 Padding . . . . . . . . . . . . . . . . . . . . . . . . . 6 4. Test Vector . . . . . . . . . . . . . . . . . . . . . . . . 11
3.5 Subkey Generation . . . . .. . . . . . . . . . . . . . . . 6 5. Acknowledgement . . . . . . . . . . . . . . . . . . . . . . 12
3.6 AES-CMAC Generation . . . . . . . . . . . . . . . . . . . 7 6. Authors address . . . . . . . . . . . . . . . . . . . . . . 12
4. Security Considerations . . . . . . . . . . . . . . . . . . 9 7. References . . . . . . . . . . . . . . . . . . . . . . . . 13
5. Test Vector . . . . . . . . . . . . . . . . . . . . . . . . 9 Appendix A. Test Code . . . . . . . . . . . . . . . . . . . . 14
6. Acknowledgement . . . . . . .. . . . . . . . . . . . . . . 10
7. Authors address . . . . . . . . . . . . . . . . . . . . . . 10
8. References . . . . . . . . . . . . . . . . . . . . . . . . 10
Appendix A. Test Code . .. . . . . . . . . . . . . . . . . . . 11
1. Introduction 1. Introduction
National Institute of Standards and Technology (NIST) has newly National Institute of Standards and Technology (NIST) has newly
specified the Cipher based MAC (CMAC). CMAC [NIST-CMAC] is a keyed specified the Cipher-based Message Authentication Code (CMAC).
hashed function that is based on a symmetric key block cipher such CMAC [NIST-CMAC] is a keyed hash function that is based on a
as Advanced Encryption Standard [AES]. CMAC is equivalent to the symmetric key block cipher such as the Advanced Encryption
One-Key CBC-MAC1 (OMAC1) algorithm submitted by Iwata and Kurosawa Standard [NIST-AES]. CMAC is equivalent to the One-Key CBC MAC1
[OMAC1]. Although the OMAC1 algorithm is based on the eXtended Cipher (OMAC1) submitted by Iwata and Kurosawa [OMAC1a, OMAC1b]. OMAC1
Block Chaining mode (XCBC) algorithm submitted by Rogaway and Black is an improvement of the eXtended Cipher Block Chaining mode (XCBC)
[XCBC], OMAC1 efficiently reduces the key size of XCBC. This memo submitted by Black and Rogaway [XCBCa, XCBCb], which itself is an
specifies the authentication mechanism based on CMAC mode of improvement of the basic CBC-MAC. XCBC efficiently addresses the
operation with 128-bit Advanced Encryption Standard(AES) cipher security deficiencies of CBC-MAC, and OMAC1 efficiently reduces the
block. This new authentication algorithm is named AES-CMAC key size of XCBC.
2. Specification of Language 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.
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", AES-CMAC achieves the similar security goal of HMAC [RFC-HMAC].
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this Since AES-CMAC is based on a symmetric key block cipher, AES,
document are to be interpreted as described in RFC 2119 [3]. while 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.
In addition, the following words are used to signify the requirements This memo specifies the authentication algorithm based on CMAC with
of the specification. AES-128. This new authentication algorithm is named AES-CMAC.
3. AES-CMAC Algorithm 2. Specification of AES-CMAC
3.1 Basic definitions 2.1 Basic definitions
The following table describes the basic definitions necessary to The following table describes the basic definitions necessary to
explain CMAC algorithm and definitions. explain the specification of AES-CMAC.
|| Concatenation.
a || b means the concatenation a with following b.
XOR Exclusive OR.
a XOR b means the result of exclusive-OR'ing a
with b.
[x] Ceiling function.
[3.5] results 4. [5] results 5.
<< Left-shift operation. x || y Concatenation.
10010001 << 1 is equal to 00100010. x || y is the string x concatenated with string y.
0000 || 1111 is 00001111.
x^y y-times repeated x. x XOR y Exclusive-OR operation.
0^3 means that 000 in binary format For two equal length strings x and y,
10^4 means that 10000 in binary format x XOR y is their bit-wise exclusive-OR.
10^i means that 1 and i-times repeated 0.
CBC Cipher Block Chaining mode of operation for message ceil(x) Ceiling function.
authentication code. The smallest integer no smaller than x.
ceil(3.5) is 4. ceil(5) is 5.
MAC Message Authentication Code. x << 1 Left-shift of the string x by 1 bit.
A bitstring of a fixed length, computed by MAC The most significant bit disappears and a zero
generation algorithm, that is used to established comes into the least significant bit.
the authority and hence, the integrity of a message. 10010001 << 1 is 00100010.
CMAC Cipher-based MAC based on an approved symmetric key 0^n The string that consists of n zero-bits.
block cipher, such as the Advanced Encryption 0^3 means that 000 in binary format.
Standard. 10^4 means that 10000 in binary format.
10^i means that 1 followed by i-times repeated
zero's.
MSB(x) The most-significant bit of x. MSB(x) The most-significant bit of the string x.
MSB(10010001) means 1. MSB(10010000) means 1.
padding(x) 10^i padded output of input x. padding(x) 10^i padded output of input x.
It is described in detail in section 3. It is described in detail in section 2.4.
Key (K) 128-bits (16bytes) long key for AES-128 cipher block. Key 128 bits (16 bytes) long key for AES-128.
Denoted by K. Denoted by K.
K1 First subkey, K1 is generated by subkey generation First subkey 128 bits (16 bytes) long first subkey,
method. derived through the subkey
generation algorithm from the key K.
Denoted by K1.
K2 Second subkey, K2 is generated by subkey generation Second subkey 128 bits (16 bytes) long second subkey,
method. derived through the subkey
generation algorithm from the key K.
Denoted by K2.
Message (M) Message to be authenticated. Message A message to be authenticated.
Denoted by M. Denoted by M.
The total message M is denoted by sequence of M_i The message can be null, which means that the length
where M_i is the i'th block with size 128-bit. of M is 0.
Message can be null message which means that the
length of M is 0.
Length (len) The length of message M in bytes. Message length The length of the message M in bytes.
Denoted by len. Denoted by len.
Minimum value of the length can be 0. The maximum Minimum value of the length can be 0. The maximum
value of the length is not specified in this document. value of the length is not specified in this document.
AES-128(K,M) 128-bit ciphertext, output of performing AES-128 AES-128(K,M) AES-128(K,M) is the 128-bit ciphertext of AES-128
cipher block of 128-bit plaintext M with 128-bit for a 128-bit key K and a 128-bit message M.
Key K
AES-CMAC CMAC generation function based on AES block cipher
with 128-bits key
3.2 Overview
The Advanced Encryption Standard [AES] is recently defined symmetric
key block cipher by NIST. AES-CMAC algorithm uses the CBC mode of
operation based on block cipher with 128-bit key for message
authentication code generation. In CBC-mode uses output of the
cipher block in order to exclusive-or with next input block.
The output of CMAC-mode will provide data integrity over whole
input message.
There are two cases of operation in CMAC. Figure 3.1 illustrated the
operation of CBC-MAC with two cases. If the size of input
message block is equal to multiple of block size namely 128-bits,
the last block processing shall be exclusive-OR'ed with K1.
Otherwise, the last block shall be padded with 10^i (notation is
described in section 3.1) and exclusive-OR'ed with K2. The result
of the previous process will be the input of the last CBC operation.
+-----+ +-----+ +-----+ +-----+ +-----+ +---+----+
| M_1 | | M_2 | | M_n | | M_1 | | M_2 | |M_n|10^i|
+-----+ +-----+ +-----+ +-----+ +-----+ +---+----+
| | | | | |
| +--->(+) +--->(+)<- K1 | +--->(+) +--->(+)<- K2
| | | | | | | | | |
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
| E_k | | | E_k | | | E_k | | E_k | | | E_k | | | E_k |
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
| | | | | | | | | |
+-----+ +-----+ | +-----+ +-----+ |
| |
T T
(a) multiple block size (b) not multiple block size
Figure 3.1 Illustration of two cases of CMAC generation
E_k is cipher block function with key, k. In this memo, MAC A 128-bit string which is the output of AES-CMAC.
E is the AES-128 cipher block and k is input key namely K. Denoted by T.
M_i means the message block with length 128-bit where i = 1...n. Validating the MAC provides assurance of the
K1 is the key for the case (a). integrity and authenticity over the message from
K2 is the key for the case (b). the source.
K1 and K2 is generated by subkey generation method described in
section 3.4.2.
3.3 Input and Output MAC length By default, the length of the output of AES-CMAC is
128 bits. It is possible to truncate the MAC.
Result of truncation should be taken in most
significant bits first order. MAC length must be
specified before the communication starts, and
it must not be changed during the life time of the key.
3.3.1 Input 2.2 Overview
A given block cipher and key typically fixed across most CMAC AES-CMAC uses the Advanced Encryption Standard [NIST-AES] as a
invocations are called prerequisites. A given block cipher in building block. To generate a MAC, AES-CMAC takes a secret key,
this memo is AES-128 and length of key is 128-bits (16bytes). a message of variable length and the length of the message in bytes
Other input parameters defined in this memo are 'M' denoting as inputs, and returns a fixed bit string called a MAC.
the message to be authenticated and 'len' denoting the length
of message M in bytes. The total message M is denoted by sequence
of M_i where M_i is the i'th block with size 128-bit.
3.3.2 Output 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 illustrated the operation of CBC-MAC
with two cases. If the size of input message block is equal to
multiple of block size namely 128 bits, the last block processing
shall be exclusive-OR'ed with K1. 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 process will be
the input of the last CBC operation. The output of AES-CMAC provides
data integrity over whole input message.
The output of AES-CMAC can validate the input message. +-----+ +-----+ +-----+ +-----+ +-----+ +---+----+
Validating the message provide assurance of the integrity and | M_1 | | M_2 | | M_n | | M_1 | | M_2 | |M_n|10^i|
authenticity over the message from the source. According to +-----+ +-----+ +-----+ +-----+ +-----+ +---+----+
[NIST-CMAC] at least 64-bits should be used for against guessing | | | +--+ | | | +--+
attack. Result of truncation should be taken in most significant | +--->(+) +--->(+)<-|K1| | +--->(+) +--->(+)<-|K2|
bits first order. | | | | | +--+ | | | | | +--+
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
|AES_K| | |AES_K| | |AES_K| |AES_K| | |AES_K| | |AES_K|
+-----+ | +-----+ | +-----+ +-----+ | +-----+ | +-----+
| | | | | | | | | |
+-----+ +-----+ | +-----+ +-----+ |
| |
+-----+ +-----+
| T | | T |
+-----+ +-----+
3.4 Padding (a) positive multiple block length (b) otherwise
AES-CMAC uses cipher block with fixed length (128-bit). There Figure 2.1 Illustration of two cases of AES-CMAC.
should be a special treatment in case that the length of plaintext is
not divided by cipher block length. The special treatment is to pad
10^i bit-string for adjusting size of the last-block up to the cipher
block length.
The method of padding is described as [OMAC1]. AES_K is AES-128 with key K.
Padding(x) means 10^i padded output with 128-bit length. The message M is divided into blocks M_1,...,M_n,
If the input x has length r-bytes, padding(x) is defined as follows: 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.
- padding(x) = x || 10^i where i is 128-8*r-1 2.3 Subkey Generation Algorithm
3.5 Subkey Generation The subkey generation algorithm, Generate_Subkey(), takes a secret
key, K, which is just the key for AES-128.
AES-CMAC algorithm requires the subkeys K1 and K2. K1 is used The output of the subkey generation algorithm is two subkeys, K1
for the case that the size of last block is equal to cipher block and K2. We write (K1,K2) := Generate_Subkey(K).
size. K2 is used for the case that the size of last block is less
than cipher block size.
Through Generate_Subkey algorithm, we get K1 and K2 from the input K Subkeys K1 and K2 are used in both MAC generation and MAC
which is the input key described 3.3. 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.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Algorithm Generate_Subkey + + Algorithm Generate_Subkey +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ + + +
+ Input : K (128-bit Key described in section 4.1) + + Input : K (128-bit key) +
+ Output : K1 (128-bit subkey) + + Output : K1 (128-bit first subkey) +
+ K2 (128-bit subkey) + + K2 (128-bit second subkey) +
+-------------------------------------------------------------------+ +-------------------------------------------------------------------+
+ + + +
+ Constants: const_Zero is 0x00000000000000000000000000000000 + + Constants: const_Zero is 0x00000000000000000000000000000000 +
+ const_Rb is 0x00000000000000000000000000000087 + + const_Rb is 0x00000000000000000000000000000087 +
+ Variables: L for output of AES-128 applied to 0^128 + + Variables: L for output of AES-128 applied to 0^128 +
+ + + +
+ Step 1. L := AES-128(K, const_Zero); + + Step 1. L := AES-128(K, const_Zero); +
+ Step 2. if MSB(L) is equal to 0 + + Step 2. if MSB(L) is equal to 0 +
+ then K1 := L << 1; + + then K1 := L << 1; +
+ else K1 := (L << 1) XOR const_Rb; + + else K1 := (L << 1) XOR const_Rb; +
+ Step 3. if MSB(K1) is equal to 0 + + Step 3. if MSB(K1) is equal to 0 +
+ then K2 := K1 << 1; + + then K2 := K1 << 1; +
+ else K2 := (K1 << 1) XOR const_Rb; + + else K2 := (K1 << 1) XOR const_Rb; +
+ Step 4. return K1, K2; + + Step 4. return K1, K2; +
+ + + +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Figure 3.2 Generate_Subkey Algorithm Figure 2.2 Algorithm Generate_Subkey
Figure 3.2 describes the algorithm generating subkeys.
In step 1. AES-128 is applied to all zero bits with key K.
In step 2 K1 is derive through following operation: Figure 2.2 specifies the subkey generation algorithm.
If the most significant bit of L is equal to 0, left-shift L by 1 In step 1, AES-128 is applied to all zero bits with the input
bit. Otherwise, exclusive-OR const_Rb with the result of 1-bit key K.
left-shift of L.
In step 3. K2 is derived through following operation: In step 2, K1 is derived through the following operation:
If the most significant bit of K1 is equal to 0, left-shift If the most significant bit of L is equal to 0, K1 is
K1 by 1 bit. Otherwise, exclusive-OR const_Rb with the result the left-shift of L by 1-bit.
of 1-bit left-shift of K1. Otherwise, K1 is the exclusive-OR of const_Rb and
In step 4. return K1 and K2. the left-shift of L by 1-bit.
The mathematical meaning of procedure in step 2 and step 3 including In step 3, K2 is derived through the following operation:
const_Rb can be found in [OMAC1]. 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.
3.6 AES-CMAC Generation In step 4, (K1,K2) := Generate_Subkey(K) is returned.
To perform the algorithm, we should have Generate_Subkey algorithm The mathematical meaning of procedure in step 2 and step 3
which is described in section 3.4.2 and padding function which is including const_Rb can be found in [OMAC1a].
used in case that the size of last block is less than the cipher
block size.
Inputs of AES-CMAC are K, M, len which are described in section 3.3. 2.4 MAC Generation Algorithm
Output of AES-CMAC is T which is the authentication code described The MAC generation algorithm, AES-CMAC(), takes three inputs,
in section 3.3. a secret key, a message, and the length of the message in bytes.
The secret key, denoted by K, is just the key for AES-128.
The message and its length in bytes 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 can be 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 over the message from the source.
It is possible to truncate the MAC. According to [NIST-CMAC] at
least 64-bit MAC should be used for against guessing attack.
Result of truncation should be taken in most significant bits first
order.
The block length of AES-128 is 128 bits (16 bytes). There is a
special treatment in case that the length of the message is
not a positive multiple of the block length. The special treatment
is to pad 10^i bit-string for adjusting the length of the last
block up to the block length.
For the input string x of r-bytes, where 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.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Algorithm AES-CMAC + + Algorithm AES-CMAC +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ + + +
+ Input : K ( 128-bit Symmetric Key ) + + Input : K ( 128-bit key ) +
+ : M ( message to be authenticated ) + + : M ( message to be authenticated ) +
+ : len ( length of message in bytes ) + + : len ( length of the message in bytes ) +
+ Output : T ( message authenticated code ) + + Output : T ( message authenticated code ) +
+ + + +
+-------------------------------------------------------------------+
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Constants: const_Zero is 0x00000000000000000000000000000000 + + Constants: const_Zero is 0x00000000000000000000000000000000 +
+ const_Rb is 0x00000000000000000000000000000087 + + const_Rb is 0x00000000000000000000000000000087 +
+ const_Bsize is 16 in bytes for 128-bit block + + const_Bsize is 16 +
+ + + +
+ Variables: K1, K2 for 128-bit subkeys + + Variables: K1, K2 for 128-bit subkeys +
+ M_i means i'th 128-bit block (i=1..[M/const_Bsize]) + + M_i is the i-th block (i=1..ceil(len/const_Bsize)) +
+ M_last for last block xor-ed with K1 or K2 + + M_last is the last block xor-ed with K1 or K2 +
+ n for number of block to be processed + + n for number of blocks to be processed +
+ r for number of bytes of last block + + r for number of bytes of last block +
+ flag for denoting if last block is complete or not + + flag for denoting if last block is complete or not +
+ + + +
+ Step 1. (K1,K2) := Generate_Subkey(K); + + Step 1. (K1,K2) := Generate_Subkey(K); +
+ Step 2. n := [ len/const_Bsize ]; + + Step 2. n := ceil(len/const_Bsize); +
+ Step 3. if n = 0 + + Step 3. if n = 0 +
+ then + + then +
+ n := 1; + + n := 1; +
+ flag := false; + + flag := false; +
+ else + + else +
+ if len mod const_Bsize is 0 + + if len mod const_Bsize is 0 +
+ then flag := true; + + then flag := true; +
+ else flag := false; + + else flag := false; +
+ + + +
+ Step 4. if flag is true + + Step 4. if flag is true +
+ then M_last := M_n XOR K1; + + then M_last := M_n XOR K1; +
+ else M_last := padding(M_n) XOR K2; + + else M_last := padding(M_n) XOR K2; +
+ Step 5. X := const_Zero; + + Step 5. X := const_Zero; +
+ Step 6. for i := 1 to n-1 do + + Step 6. for i := 1 to n-1 do +
+ begin + + begin +
+ Y := X XOR M_i; + + Y := X XOR M_i; +
+ X := AES-128(K,Y); + + X := AES-128(K,Y); +
+ end + + end +
+ Y := M_last XOR X; + + Y := M_last XOR X; +
+ X := AES-128(K,Y); + + T := AES-128(K,Y); +
+ Step 7. return T; + + Step 7. return T; +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Figure 2.3 Algorithm AES-CMAC
Figure 3.3 AES-CMAC Algorithm Figure 2.3 describes the MAC generation algorithm.
Figure 3.3 describes the AES-CMAC authentication code generation In step 1, subkeys K1 and K2 are derived from K through the subkey
algorithm generation algorithm.
In step 1, Derive subkeys, K1 and K2 with K In step 2, the number of blocks, n, is calculated. The number of
blocks is the smallest integer value greater than or equal to
quotient by dividing length parameter by the block length, 16
bytes.
In step 2, Calculate the number of blocks. The number of blocks In step 3, the length of the input message is checked.
is a smallest integer value greater than or equal to quotient by If the input length is less than 128 bits (including null), the
dividing length parameter by 128-bit (16 bytes). number of blocks to be processed shall be 1 and mark the flag as
not-complete-block (false). Otherwise, if the last block length
is 128 bits, mark the flag as complete-block (true), else mark the
flag as not-complete-block (false).
In step 3, Check if the last block is complete block. In step 4, M_last is calculated by exclusive-OR'ing
If the input length is less than 128-bit (16 bytes), the number of M_n and previously calculated subkeys. If the last block is a
blocks to be processed shall be 1 and mark the flag as not-complete complete block (true), then M_last is the exclusive-OR of M_n and
-block (false). Otherwise, if the last block size is 128-bit, mark K1. Otherwise, M_last is the exclusive-OR of padding(M_n) and K2.
the flag as complete-block (true), else mark the flag as not-
complete-block (false).
In step 4, Pre-calculate the M_last block with exclusive-OR'ing In step 5, the variable X is initialized.
previously calculated subkeys. If the last block is complete block
(true), exclusive-OR the last block with K1.
Otherwise, exclusive-OR the padded last block with K2.
In step 5. Initialize the variable X. In step 6, the basic CBC-MAC is applied to M_1,...,M_{n-1},M_last.
In step 6. Perform AES-CBC mode of operation with the input In step 7, the 128-bit MAC, T := AES-CMAC(K,M,len), is returned.
message M_1 to M_{n-1}. And the M_last which is calculated in step
4, shall be the last input block for CBC mode of operation.
In step 7. we finally return authentication code with 128-bit.
4. Security Considerations If necessary, truncation of the MAC is done before returning the
MAC.
2.5 MAC Verification Algorithm
The verification of the MAC is simply done by a MAC recomputation.
We use the MAC generation algorithm which is described in section
2.4.
The MAC verification algorithm, Verify_MAC(), takes four inputs,
a secret key, a message, the length of the message in bytes, and
the received MAC.
They are denoted by K, M, len, and T' respectively.
The output of the MAC verification algorithm is either INVALID or
VALID.
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Algorithm Verify_MAC +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ +
+ Input : K ( 128-bit Key ) +
+ : M ( message to be verified ) +
+ : len ( length of the message in bytes ) +
+ : T' ( the received MAC to be verified ) +
+ Output : INVALID or VALID +
+ +
+-------------------------------------------------------------------+
+ +
+ Step 1. T* := AES-CMAC(K,M,len); +
+ Step 2. if T* = T' +
+ then +
+ return VALID; +
+ else +
+ return INVALID; +
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Figure 2.4 Algorithm Verify_MAC
Figure 2.4 describes the MAC verification algorithm.
In step 1, T* is derived from K, M and len through the MAC generation
algorithm.
In step 2, T* and T' are compared. If T*=T', then return VALID,
otherwise return INVALID.
If the output is INVALID, then the message is definitely not
authentic, i.e., it did not originate from a source that executed
the generation process on the message to produce the purported MAC.
If the output is VALID, then the design of the AES-CMAC provides
assurance that the message is authentic and, hence, was not
corrupted in transit; however, this assurance, as for any MAC
algorithm, is not absolute.
3. Security Considerations
The security provided by AES-CMAC is based upon the strength of AES. The security provided by AES-CMAC is based upon the strength of AES.
At the time of this writing there are no practical cryptographic At the time of this writing there are no practical cryptographic
attacks against AES or AES-CMAC. attacks against AES or AES-CMAC.
As is true with any cryptographic algorithm, part of its strength As is true with any cryptographic algorithm, part of its strength
lies in the correctness of the algorithm implementation, the security lies in the correctness of the algorithm implementation, the
of the key management mechanism and its implementation, the strength security of the key management mechanism and its implementation, the
of the associated secret key, and upon the correctness of the strength of the associated secret key, and upon the correctness of
implementation in all of the participating systems. This document the implementation in all of the participating systems.
contains test vectors to assist in verifying the correctness of
AES-CMAC code.
5. Test Vectors This document contains test vectors to assist in verifying the
correctness of AES-CMAC code.
Following test vectors are same as those of [NIST-CMAC]. 4. Test Vectors
Following test vectors are the same as those of [NIST-CMAC].
The following vectors are also output of the test program in The following vectors are also output of the test program in
appendix A. appendix A.
-------------------------------------------------- --------------------------------------------------
Subkey Generation Subkey Generation
K 2b7e1516 28aed2a6 abf71588 09cf4f3c K 2b7e1516 28aed2a6 abf71588 09cf4f3c
AES_128(key,0) 7df76b0c 1ab899b3 3e42f047 b91b546f AES-128(key,0) 7df76b0c 1ab899b3 3e42f047 b91b546f
K1 fbeed618 35713366 7c85e08f 7236a8de K1 fbeed618 35713366 7c85e08f 7236a8de
K2 f7ddac30 6ae266cc f90bc11e e46d513b K2 f7ddac30 6ae266cc f90bc11e e46d513b
-------------------------------------------------- --------------------------------------------------
-------------------------------------------------- --------------------------------------------------
Example 1: len = 0 Example 1: len = 0
M <empty string> M <empty string>
AES_CMAC bb1d6929 e9593728 7fa37d12 9b756746 AES-CMAC bb1d6929 e9593728 7fa37d12 9b756746
-------------------------------------------------- --------------------------------------------------
Example 2: len = 16 Example 2: len = 16
M 6bc1bee2 2e409f96 e93d7e11 7393172a M 6bc1bee2 2e409f96 e93d7e11 7393172a
AES_CMAC 070a16b4 6b4d4144 f79bdd9d d04a287c AES-CMAC 070a16b4 6b4d4144 f79bdd9d d04a287c
-------------------------------------------------- --------------------------------------------------
Example 3: len = 40 Example 3: len = 40
M 6bc1bee2 2e409f96 e93d7e11 7393172a M 6bc1bee2 2e409f96 e93d7e11 7393172a
ae2d8a57 1e03ac9c 9eb76fac 45af8e51 ae2d8a57 1e03ac9c 9eb76fac 45af8e51
30c81c46 a35ce411 30c81c46 a35ce411
AES_CMAC dfa66747 de9ae630 30ca3261 1497c827 AES-CMAC dfa66747 de9ae630 30ca3261 1497c827
-------------------------------------------------- --------------------------------------------------
Example 4: len = 64 Example 4: len = 64
M 6bc1bee2 2e409f96 e93d7e11 7393172a M 6bc1bee2 2e409f96 e93d7e11 7393172a
ae2d8a57 1e03ac9c 9eb76fac 45af8e51 ae2d8a57 1e03ac9c 9eb76fac 45af8e51
30c81c46 a35ce411 e5fbc119 1a0a52ef 30c81c46 a35ce411 e5fbc119 1a0a52ef
f69f2445 df4f9b17 ad2b417b e66c3710 f69f2445 df4f9b17 ad2b417b e66c3710
AES_CMAC 51f0bebf 7e3b9d92 fc497417 79363cfe AES-CMAC 51f0bebf 7e3b9d92 fc497417 79363cfe
-------------------------------------------------- --------------------------------------------------
6. Acknowledgement 5. Acknowledgement
Portions of this text were borrowed from [NIST-CMAC]. We would like Portions of this text here in is borrowed from [NIST-CMAC].
to thank to OMAC1 author Tetsu Iwata and Kaoru Kurosawa, and CMAC We appreciate OMAC1 authors and SP 800-38B author, and Russ Housley
author Morris Dworkin, and special thanks to David Johnston for for his useful comments and guidance that have been incorporated
providing AES cipher block test code. herein. We also appreciate David Johnston for providing code of
the AES block cipher.
7. Author's Address 6. Author's Address
Junhyuk Song Junhyuk Song
University of Washington
Samsung Electronics Samsung Electronics
+82-31-279-3639 (206) 853-5843
santajunman@hanafos.com songlee@ee.washington.edu
junhyuk.song@samsung.com
Jicheol Lee Jicheol Lee
Samsung Electronics Samsung Electronics
+82-31-279-3605 +82-31-279-3605
jicheol.lee@samsung.com jicheol.lee@samsung.com
8. References Radha Poovendran
Network Security Lab
University of Washington
(206) 221-6512
radha@ee.washington.edu
[NIST-CMAC] NIST, Special Publication 800-38B Draft,"Recommendation Tetsu Iwata
for Block Cipher Modes of Operation: The CMAC Method Ibaraki University
for Authentication," March 9, 2005 iwata@cis.ibaraki.ac.jp
[AES] NIST, FIPS 197, "Advanced Encryption Standard (AES)," 7. References
November 2001. http://csrc.nist.gov/publications/fips/
[NIST-CMAC] NIST, SP 800-38B, "Recommendation for Block Cipher
Modes of Operation: The CMAC Mode for Authentication,"
May 2005.
http://csrc.nist.gov/publications/nistpubs/800-38B/
SP_800-38B.pdf
[NIST-AES] NIST, FIPS 197, "Advanced Encryption Standard (AES),"
November 2001. http://csrc.nist.gov/publications/fips/
fips197/fips-197.pdf fips197/fips-197.pdf
[OMAC1] "OMAC: One-Key CBC MAC," Tetsu Iwata and Kaoru Kurosawa, [RFC-HMAC] Hugo Krawczyk, Mihir Bellare and Ran Canetti,
Department of Computer and Information Sciences, "HMAC: Keyed-Hashing for Message Authentication,"
Ilbaraki University, March 10, 2003. RFC2104, February 1997.
[XCBC] Black, J. and P. Rogaway, "A Suggestion for Handling [OMAC1a] Tetsu Iwata and Kaoru Kurosawa, "OMAC: One-Key CBC MAC,"
Arbitrary-Length Messages with the CBC MAC," NIST Fast Software Encryption, FSE 2003, LNCS 2887,
Second Modes of Operation Workshop, August 2001. pp. 129-153, Springer-Verlag, 2003.
[OMAC1b] Tetsu Iwata and Kaoru Kurosawa, "OMAC: One-Key CBC MAC,"
Submission to NIST, December 2002.
Available from the NIST modes of operation web site at
http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/
omac/omac-spec.pdf
[XCBCa] John Black and Phillip Rogaway, "A Suggestion for
Handling Arbitrary-Length Messages with the CBC MAC,"
NIST Second Modes of Operation Workshop, August 2001.
Available from the NIST modes of operation web site at
http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/ http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/
xcbc-mac/xcbc-mac-spec.pdf xcbc-mac/xcbc-mac-spec.pdf
[XCBCb] John Black and Phillip Rogaway, "CBC MACs for
Arbitrary-Length Messages: The Three-Key
Constructions," Journal of Cryptology, Vol. 18, No. 2,
pp. 111-132, Springer-Verlag, Spring 2005.
Appendix A. Test Code Appendix A. Test Code
/****************************************************************/ /****************************************************************/
/* AES-CMAC with AES-128 bit */ /* AES-CMAC with AES-128 bit */
/* AES-128 from David Johnston (802.16) */ /* AES-128 from David Johnston (802.16) */
/* CMAC Algorithm described in SP800-38B draft */ /* CMAC Algorithm described in SP800-38B draft */
/* Author: Junhyuk Song (junhyuk.song@samsung.com) */ /* Author: Junhyuk Song (junhyuk.song@samsung.com) */
/* Jicheol Lee (jicheol.lee@samsung.com) */ /* Jicheol Lee (jicheol.lee@samsung.com) */
/****************************************************************/ /****************************************************************/
skipping to change at page 17, line 34 skipping to change at page 20, line 4
} }
void print96(unsigned char *bytes) void print96(unsigned char *bytes)
{ {
int j; int j;
for (j=0; j<12;j++) { for (j=0; j<12;j++) {
printf("%02x",bytes[j]); printf("%02x",bytes[j]);
if ( (j%4) == 3 ) printf(" "); if ( (j%4) == 3 ) printf(" ");
} }
} }
/* AES-CMAC Generation Function */
/* CMAC-AES Generation Function */
void leftshift_onebit(unsigned char *input,unsigned char *output) void leftshift_onebit(unsigned char *input,unsigned char *output)
{ {
int i; int i;
unsigned char overflow = 0; unsigned char overflow = 0;
for ( i=15; i>=0; i-- ) { for ( i=15; i>=0; i-- ) {
output[i] = input[i] << 1; output[i] = input[i] << 1;
output[i] |= overflow; output[i] |= overflow;
overflow = (input[i] & 0x80)?1:0; overflow = (input[i] & 0x80)?1:0;
skipping to change at page 20, line 4 skipping to change at page 22, line 29
0x9e, 0xb7, 0x6f, 0xac, 0x45, 0xaf, 0x8e, 0x51, 0x9e, 0xb7, 0x6f, 0xac, 0x45, 0xaf, 0x8e, 0x51,
0x30, 0xc8, 0x1c, 0x46, 0xa3, 0x5c, 0xe4, 0x11, 0x30, 0xc8, 0x1c, 0x46, 0xa3, 0x5c, 0xe4, 0x11,
0xe5, 0xfb, 0xc1, 0x19, 0x1a, 0x0a, 0x52, 0xef, 0xe5, 0xfb, 0xc1, 0x19, 0x1a, 0x0a, 0x52, 0xef,
0xf6, 0x9f, 0x24, 0x45, 0xdf, 0x4f, 0x9b, 0x17, 0xf6, 0x9f, 0x24, 0x45, 0xdf, 0x4f, 0x9b, 0x17,
0xad, 0x2b, 0x41, 0x7b, 0xe6, 0x6c, 0x37, 0x10 0xad, 0x2b, 0x41, 0x7b, 0xe6, 0x6c, 0x37, 0x10
}; };
unsigned char key[16] = { unsigned char key[16] = {
0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6, 0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6,
0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c 0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c
}; };
printf("--------------------------------------------------\n");
printf("--------------------------------------------------\n");
printf("K "); print128(key); printf("\n"); printf("K "); print128(key); printf("\n");
printf("\nSubkey Generation\n"); printf("\nSubkey Generation\n");
AES_128(key,const_Zero,L); AES_128(key,const_Zero,L);
printf("AES_128(key,0) "); print128(L); printf("\n"); printf("AES_128(key,0) "); print128(L); printf("\n");
generate_subkey(key,K1,K2); generate_subkey(key,K1,K2);
printf("K1 "); print128(K1); printf("\n"); printf("K1 "); print128(K1); printf("\n");
printf("K2 "); print128(K2); printf("\n"); printf("K2 "); print128(K2); printf("\n");
printf("\nExample 1: len = 0\n"); printf("\nExample 1: len = 0\n");
 End of changes. 91 change blocks. 
262 lines changed or deleted 364 lines changed or added

This html diff was produced by rfcdiff 1.48. The latest version is available from http://tools.ietf.org/tools/rfcdiff/