JunHyuk Song Jicheol Lee INTERNET DRAFT Samsung Electronics Expires: November 30, 2005 May 31 2005 The AES-CMAC Algorithm draft-songlee-aes-cmac-01.txt Status of This Memo By submitting this Internet-Draft, each author represents that any 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 aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Copyright Notice Copyright (C) The Internet Society (2005). Abstract National Institute of Standards and Technology (NIST) has newly specified the Cipher based MAC (CMAC) which is equivalent to the One-Key CBC-MAC1 (OMAC1) algorithm submitted by Iwata and Kurosawa. OMAC1 efficiently reduces the key size of Extended Cipher Block Chaining mode (XCBC). This memo specifies the authentication mechanism based on CMAC mode of operation with 128-bit Advanced Encryption Standard (AES) cipher block. This new authentication algorithm is named AES-CMAC Song and Lee. Expires November 2005 [Page 1]

Internet Draft May 2005 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2 2. Specification of Language . . . . . . . . . . . . . . . . 2 3. AES-CMAC Algorithm . . . . . . . . . . . . . . . . . . . . 3 3.1 Basic Definitions. . . . . . . . . . . . . . . . . . . . . 3 3.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 Input and Output . . . . . . . . . . . . . . . . . . . . . 5 3.3.1 Input . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.3.2 Output . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.4 Padding . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.5 Subkey Generation . . . . .. . . . . . . . . . . . . . . . 6 3.6 AES-CMAC Generation . . . . . . . . . . . . . . . . . . . 7 4. Security Considerations . . . . . . . . . . . . . . . . . . 9 5. Test Vector . . . . . . . . . . . . . . . . . . . . . . . . 9 6. Acknowledgement . . . . . . .. . . . . . . . . . . . . . . 10 7. Authors address . . . . . . . . . . . . . . . . . . . . . . 10 8. References . . . . . . . . . . . . . . . . . . . . . . . . 10 Appendix A. Test Code . .. . . . . . . . . . . . . . . . . . . 11 1. Introduction National Institute of Standards and Technology (NIST) has newly specified the Cipher based MAC (CMAC). CMAC [NIST-CMAC] is a keyed hashed function that is based on a symmetric key block cipher such as Advanced Encryption Standard [AES]. CMAC is equivalent to the One-Key CBC-MAC1 (OMAC1) algorithm submitted by Iwata and Kurosawa [OMAC1]. Although the OMAC1 algorithm is based on the eXtended Cipher Block Chaining mode (XCBC) algorithm submitted by Rogaway and Black [XCBC], OMAC1 efficiently reduces the key size of XCBC. This memo specifies the authentication mechanism based on CMAC mode of operation with 128-bit Advanced Encryption Standard(AES) cipher block. This new authentication algorithm is named AES-CMAC 2. Specification of Language The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [3]. In addition, the following words are used to signify the requirements of the specification. Song and Lee. Expires November 2005 [Page 2]

Internet Draft May 2005 3. AES-CMAC Algorithm 3.1 Basic definitions The following table describes the basic definitions necessary to explain CMAC algorithm and definitions. || 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. 10010001 << 1 is equal to 00100010. x^y y-times repeated x. 0^3 means that 000 in binary format 10^4 means that 10000 in binary format 10^i means that 1 and i-times repeated 0. CBC Cipher Block Chaining mode of operation for message authentication code. MAC Message Authentication Code. A bitstring of a fixed length, computed by MAC generation algorithm, that is used to established the authority and hence, the integrity of a message. CMAC Cipher-based MAC based on an approved symmetric key block cipher, such as the Advanced Encryption Standard. MSB(x) The most-significant bit of x. MSB(10010001) means 1. padding(x) 10^i padded output of input x. It is described in detail in section 3. Key (K) 128-bits (16bytes) long key for AES-128 cipher block. Denoted by K. K1 First subkey, K1 is generated by subkey generation method. Song and Lee. Expires November 2005 [Page 3]

Internet Draft May 2005 K2 Second subkey, K2 is generated by subkey generation method. Message (M) Message to be authenticated. Denoted by M. The total message M is denoted by sequence of M_i where M_i is the i'th block with size 128-bit. Message can be null message which means that the length of M is 0. Length (len) The length of message M in bytes. Denoted by len. Minimum value of the length can be 0. The maximum value of the length is not specified in this document. AES-128(K,M) 128-bit ciphertext, output of performing AES-128 cipher block of 128-bit plaintext M with 128-bit 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. Song and Lee. Expires November 2005 [Page 4]

Internet Draft May 2005 +-----+ +-----+ +-----+ +-----+ +-----+ +---+----+ | 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, E is the AES-128 cipher block and k is input key namely K. M_i means the message block with length 128-bit where i = 1...n. K1 is the key for the case (a). K2 is the key for the case (b). K1 and K2 is generated by subkey generation method described in section 3.4.2. 3.3 Input and Output 3.3.1 Input A given block cipher and key typically fixed across most CMAC invocations are called prerequisites. A given block cipher in this memo is AES-128 and length of key is 128-bits (16bytes). Other input parameters defined in this memo are 'M' denoting 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 output of AES-CMAC can validate the input message. Validating the message provide assurance of the integrity and 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 bits first order. Song and Lee. Expires November 2005 [Page 5]

Internet Draft May 2005 3.4 Padding AES-CMAC uses cipher block with fixed length (128-bit). There 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]. Padding(x) means 10^i padded output with 128-bit length. If the input x has length r-bytes, padding(x) is defined as follows: - padding(x) = x || 10^i where i is 128-8*r-1 3.5 Subkey Generation AES-CMAC algorithm requires the subkeys K1 and K2. K1 is used for the case that the size of last block is equal to cipher block 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 which is the input key described 3.3. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + Algorithm Generate_Subkey + +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + + + Input : K (128-bit Key described in section 4.1) + + Output : K1 (128-bit subkey) + + K2 (128-bit 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 3.2 Generate_Subkey Algorithm Song and Lee. Expires November 2005 [Page 6]

Internet Draft May 2005 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: If the most significant bit of L is equal to 0, left-shift L by 1 bit. Otherwise, exclusive-OR const_Rb with the result of 1-bit left-shift of L. In step 3. K2 is derived through following operation: If the most significant bit of K1 is equal to 0, left-shift K1 by 1 bit. Otherwise, exclusive-OR const_Rb with the result of 1-bit left-shift of K1. In step 4. return K1 and K2. The mathematical meaning of procedure in step 2 and step 3 including const_Rb can be found in [OMAC1]. 3.6 AES-CMAC Generation To perform the algorithm, we should have Generate_Subkey algorithm which is described in section 3.4.2 and padding function which is 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. Output of AES-CMAC is T which is the authentication code described in section 3.3. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + Algorithm AES-CMAC + +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + + + Input : K ( 128-bit Symmetric Key ) + + : M ( message to be authenticated ) + + : len ( length of message in bytes ) + + Output : T ( message authenticated code ) + + + +-------------------------------------------------------------------+ Song and Lee. Expires November 2005 [Page 7]

Internet Draft May 2005 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + Constants: const_Zero is 0x00000000000000000000000000000000 + + const_Rb is 0x00000000000000000000000000000087 + + const_Bsize is 16 in bytes for 128-bit block + + + + Variables: K1, K2 for 128-bit subkeys + + M_i means i'th 128-bit block (i=1..[M/const_Bsize]) + + M_last for last block xor-ed with K1 or K2 + + n for number of block to be processed + + r for number of bytes of last block + + flag for denoting if last block is complete or not + + + + Step 1. (K1,K2) := Generate_Subkey(K); + + Step 2. n := [ 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; + + X := AES-128(K,Y); + + Step 7. return T; + +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Figure 3.3 AES-CMAC Algorithm Figure 3.3 describes the AES-CMAC authentication code generation algorithm In step 1, Derive subkeys, K1 and K2 with K In step 2, Calculate the number of blocks. The number of blocks is a smallest integer value greater than or equal to quotient by dividing length parameter by 128-bit (16 bytes). Song and Lee. Expires November 2005 [Page 8]

Internet Draft May 2005 In step 3, Check if the last block is complete block. If the input length is less than 128-bit (16 bytes), the number of blocks to be processed shall be 1 and mark the flag as not-complete -block (false). Otherwise, if the last block size is 128-bit, mark 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 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. Perform AES-CBC mode of operation with the input 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 The security provided by AES-CMAC is based upon the strength of AES. At the time of this writing there are no practical cryptographic attacks against AES or AES-CMAC. As is true with any cryptographic algorithm, part of its strength lies in the correctness of the algorithm implementation, the security of the key management mechanism and its implementation, the strength of the associated secret key, and upon the correctness of the implementation in all of the participating systems. This document contains test vectors to assist in verifying the correctness of AES-CMAC code. 5. Test Vectors Following test vectors are same as those of [NIST-CMAC]. The following vectors are also output of the test program in appendix A. -------------------------------------------------- Subkey Generation K 2b7e1516 28aed2a6 abf71588 09cf4f3c AES_128(key,0) 7df76b0c 1ab899b3 3e42f047 b91b546f K1 fbeed618 35713366 7c85e08f 7236a8de K2 f7ddac30 6ae266cc f90bc11e e46d513b -------------------------------------------------- Song and Lee. Expires November 2005 [Page 9]

Internet Draft May 2005 -------------------------------------------------- Example 1: len = 0 M <empty string> AES_CMAC bb1d6929 e9593728 7fa37d12 9b756746 -------------------------------------------------- Example 2: len = 16 M 6bc1bee2 2e409f96 e93d7e11 7393172a AES_CMAC 070a16b4 6b4d4144 f79bdd9d d04a287c -------------------------------------------------- Example 3: len = 40 M 6bc1bee2 2e409f96 e93d7e11 7393172a ae2d8a57 1e03ac9c 9eb76fac 45af8e51 30c81c46 a35ce411 AES_CMAC dfa66747 de9ae630 30ca3261 1497c827 -------------------------------------------------- Example 4: len = 64 M 6bc1bee2 2e409f96 e93d7e11 7393172a ae2d8a57 1e03ac9c 9eb76fac 45af8e51 30c81c46 a35ce411 e5fbc119 1a0a52ef f69f2445 df4f9b17 ad2b417b e66c3710 AES_CMAC 51f0bebf 7e3b9d92 fc497417 79363cfe -------------------------------------------------- 6. Acknowledgement Portions of this text were borrowed from [NIST-CMAC]. We would like to thank to OMAC1 author Tetsu Iwata and Kaoru Kurosawa, and CMAC author Morris Dworkin, and special thanks to David Johnston for providing AES cipher block test code. 7. Author's Address Junhyuk Song Samsung Electronics +82-31-279-3639 santajunman@hanafos.com Jicheol Lee Samsung Electronics +82-31-279-3605 jicheol.lee@samsung.com Song and Lee. Expires November 2005 [Page 10]

Internet Draft May 2005 8. References [NIST-CMAC] NIST, Special Publication 800-38B Draft,"Recommendation for Block Cipher Modes of Operation: The CMAC Method for Authentication," March 9, 2005 [AES] NIST, FIPS 197, "Advanced Encryption Standard (AES)," November 2001. http://csrc.nist.gov/publications/fips/ fips197/fips-197.pdf [OMAC1] "OMAC: One-Key CBC MAC," Tetsu Iwata and Kaoru Kurosawa, Department of Computer and Information Sciences, Ilbaraki University, March 10, 2003. [XCBC] Black, J. and P. Rogaway, "A Suggestion for Handling Arbitrary-Length Messages with the CBC MAC," NIST Second Modes of Operation Workshop, August 2001. http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/ xcbc-mac/xcbc-mac-spec.pdf Appendix A. Test Code /****************************************************************/ /* AES-CMAC with AES-128 bit */ /* AES-128 from David Johnston (802.16) */ /* CMAC Algorithm described in SP800-38B draft */ /* Author: Junhyuk Song (junhyuk.song@samsung.com) */ /* Jicheol Lee (jicheol.lee@samsung.com) */ /****************************************************************/ #include <stdio.h> /******** SBOX Table *********/ unsigned char sbox_table[256] = { 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76, 0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf, Song and Lee. Expires November 2005 [Page 11]

Internet Draft May 2005 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16 }; /* For CMAC Calculation */ unsigned char const_Rb[16] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x87 }; unsigned char const_Zero[16] = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }; /*****************************/ /**** Function Prototypes ****/ /*****************************/ void xor_128(unsigned char *a, unsigned char *b, unsigned char *out); void xor_32(unsigned char *a, unsigned char *b, unsigned char *out); unsigned char sbox(unsigned char a); void next_key(unsigned char *key, int round); void byte_sub(unsigned char *in, unsigned char *out); void shift_row(unsigned char *in, unsigned char *out); void mix_column(unsigned char *in, unsigned char *out); void add_round_key( unsigned char *shiftrow_in, unsigned char *mcol_in, unsigned char *block_in, int round, unsigned char *out); Song and Lee. Expires November 2005 [Page 12]

Internet Draft May 2005 void AES_128(unsigned char *key, unsigned char *data, unsigned char *ciphertext); void leftshift_onebit(unsigned char *input,unsigned char *output); /****************************************/ /* AES_128() */ /* Performs a 128 bit AES encrypt with */ /* 128 bit data. */ /****************************************/ void xor_128(unsigned char *a, unsigned char *b, unsigned char *out) { int i; for (i=0;i<16; i++) { out[i] = a[i] ^ b[i]; } } void xor_32(unsigned char *a, unsigned char *b, unsigned char *out) { int i; for (i=0;i<4; i++) { out[i] = a[i] ^ b[i]; } } unsigned char sbox(unsigned char a) { return sbox_table[(int)a]; } void next_key(unsigned char *key, int round) { unsigned char rcon; unsigned char sbox_key[4]; unsigned char rcon_table[12] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x36, 0x36 }; sbox_key[0] = sbox(key[13]); sbox_key[1] = sbox(key[14]); sbox_key[2] = sbox(key[15]); sbox_key[3] = sbox(key[12]); Song and Lee. Expires November 2005 [Page 13]

Internet Draft May 2005 rcon = rcon_table[round]; xor_32(&key[0], sbox_key, &key[0]); key[0] = key[0] ^ rcon; xor_32(&key[4], &key[0], &key[4]); xor_32(&key[8], &key[4], &key[8]); xor_32(&key[12], &key[8], &key[12]); } void byte_sub(unsigned char *in, unsigned char *out) { int i; for (i=0; i< 16; i++) { out[i] = sbox(in[i]); } } void shift_row(unsigned char *in, unsigned char *out) { out[0] = in[0]; out[1] = in[5]; out[2] = in[10]; out[3] = in[15]; out[4] = in[4]; out[5] = in[9]; out[6] = in[14]; out[7] = in[3]; out[8] = in[8]; out[9] = in[13]; out[10] = in[2]; out[11] = in[7]; out[12] = in[12]; out[13] = in[1]; out[14] = in[6]; out[15] = in[11]; } void mix_column(unsigned char *in, unsigned char *out) { int i; unsigned char add1b[4]; unsigned char add1bf7[4]; unsigned char rotl[4]; unsigned char swap_halfs[4]; unsigned char andf7[4]; unsigned char rotr[4]; Song and Lee. Expires November 2005 [Page 14]

Internet Draft May 2005 unsigned char temp[4]; unsigned char tempb[4]; for (i=0 ; i<4; i++) { if ((in[i] & 0x80)== 0x80) add1b[i] = 0x1b; else add1b[i] = 0x00; } swap_halfs[0] = in[2]; /* Swap halfs */ swap_halfs[1] = in[3]; swap_halfs[2] = in[0]; swap_halfs[3] = in[1]; rotl[0] = in[3]; /* Rotate left 8 bits */ rotl[1] = in[0]; rotl[2] = in[1]; rotl[3] = in[2]; andf7[0] = in[0] & 0x7f; andf7[1] = in[1] & 0x7f; andf7[2] = in[2] & 0x7f; andf7[3] = in[3] & 0x7f; for (i = 3; i>0; i--) /* logical shift left 1 bit */ { andf7[i] = andf7[i] << 1; if ((andf7[i-1] & 0x80) == 0x80) { andf7[i] = (andf7[i] | 0x01); } } andf7[0] = andf7[0] << 1; andf7[0] = andf7[0] & 0xfe; xor_32(add1b, andf7, add1bf7); xor_32(in, add1bf7, rotr); temp[0] = rotr[0]; /* Rotate right 8 bits */ rotr[0] = rotr[1]; rotr[1] = rotr[2]; rotr[2] = rotr[3]; rotr[3] = temp[0]; Song and Lee. Expires November 2005 [Page 15]

Internet Draft May 2005 xor_32(add1bf7, rotr, temp); xor_32(swap_halfs, rotl,tempb); xor_32(temp, tempb, out); } void AES_128(unsigned char *key, unsigned char *data, unsigned char *ciphertext) { int round; int i; unsigned char intermediatea[16]; unsigned char intermediateb[16]; unsigned char round_key[16]; for(i=0; i<16; i++) round_key[i] = key[i]; for (round = 0; round < 11; round++) { if (round == 0) { xor_128(round_key, data, ciphertext); next_key(round_key, round); } else if (round == 10) { byte_sub(ciphertext, intermediatea); shift_row(intermediatea, intermediateb); xor_128(intermediateb, round_key, ciphertext); } else /* 1 - 9 */ { byte_sub(ciphertext, intermediatea); shift_row(intermediatea, intermediateb); mix_column(&intermediateb[0], &intermediatea[0]); mix_column(&intermediateb[4], &intermediatea[4]); mix_column(&intermediateb[8], &intermediatea[8]); mix_column(&intermediateb[12], &intermediatea[12]); xor_128(intermediatea, round_key, ciphertext); next_key(round_key, round); } } } Song and Lee. Expires November 2005 [Page 16]

Internet Draft May 2005 void print_hex(char *str, unsigned char *buf, int len) { int i; for ( i=0; i<len; i++ ) { if ( (i % 16) == 0 && i != 0 ) printf(str); printf("%02x", buf[i]); if ( (i % 4) == 3 ) printf(" "); if ( (i % 16) == 15 ) printf("\n"); } if ( (i % 16) != 0 ) printf("\n"); } void print128(unsigned char *bytes) { int j; for (j=0; j<16;j++) { printf("%02x",bytes[j]); if ( (j%4) == 3 ) printf(" "); } } void print96(unsigned char *bytes) { int j; for (j=0; j<12;j++) { printf("%02x",bytes[j]); if ( (j%4) == 3 ) printf(" "); } } /* CMAC-AES Generation Function */ void leftshift_onebit(unsigned char *input,unsigned char *output) { int i; unsigned char overflow = 0; for ( i=15; i>=0; i-- ) { output[i] = input[i] << 1; output[i] |= overflow; overflow = (input[i] & 0x80)?1:0; } return; } void generate_subkey(unsigned char *key, unsigned char *K1, unsigned char *K2) { unsigned char L[16]; Song and Lee. Expires November 2005 [Page 17]

Internet Draft May 2005 unsigned char Z[16]; unsigned char tmp[16]; int i; for ( i=0; i<16; i++ ) Z[i] = 0; AES_128(key,Z,L); if ( (L[0] & 0x80) == 0 ) { /* If MSB(L) = 0, then K1 = L << 1 */ leftshift_onebit(L,K1); } else { /* Else K1 = ( L << 1 ) (+) Rb */ leftshift_onebit(L,tmp); xor_128(tmp,const_Rb,K1); } if ( (K1[0] & 0x80) == 0 ) { leftshift_onebit(K1,K2); } else { leftshift_onebit(K1,tmp); xor_128(tmp,const_Rb,K2); } return; } void padding ( unsigned char *lastb, unsigned char *pad, int length ) { int j; /* original last block */ for ( j=0; j<16; j++ ) { if ( j < length ) { pad[j] = lastb[j]; } else if ( j == length ) { pad[j] = 0x80; } else { pad[j] = 0x00; } } } void AES_CMAC ( unsigned char *key, unsigned char *input, int length, unsigned char *mac ) { unsigned char X[16],Y[16], M_last[16], padded[16]; unsigned char K1[16], K2[16]; int n, i, flag; generate_subkey(key,K1,K2); n = (length+15) / 16; /* n is number of rounds */ Song and Lee. Expires November 2005 [Page 18]

Internet Draft May 2005 if ( n == 0 ) { n = 1; flag = 0; } else { if ( (length%16) == 0 ) { /* last block is a complete block */ flag = 1; } else { /* last block is not complete block */ flag = 0; } } if ( flag ) { /* last block is complete block */ xor_128(&input[16*(n-1)],K1,M_last); } else { padding(&input[16*(n-1)],padded,length%16); xor_128(padded,K2,M_last); } for ( i=0; i<16; i++ ) X[i] = 0; for ( i=0; i<n-1; i++ ) { xor_128(X,&input[16*i],Y); /* Y := Mi (+) X */ AES_128(key,Y,X); /* X := AES-128(KEY, Y); */ } xor_128(X,M_last,Y); AES_128(key,Y,X); for ( i=0; i<16; i++ ) { mac[i] = X[i]; } } int main() { unsigned char L[16], K1[16], K2[16], T[16], TT[12]; unsigned char M[64] = { 0x6b, 0xc1, 0xbe, 0xe2, 0x2e, 0x40, 0x9f, 0x96, 0xe9, 0x3d, 0x7e, 0x11, 0x73, 0x93, 0x17, 0x2a, 0xae, 0x2d, 0x8a, 0x57, 0x1e, 0x03, 0xac, 0x9c, 0x9e, 0xb7, 0x6f, 0xac, 0x45, 0xaf, 0x8e, 0x51, 0x30, 0xc8, 0x1c, 0x46, 0xa3, 0x5c, 0xe4, 0x11, 0xe5, 0xfb, 0xc1, 0x19, 0x1a, 0x0a, 0x52, 0xef, 0xf6, 0x9f, 0x24, 0x45, 0xdf, 0x4f, 0x9b, 0x17, 0xad, 0x2b, 0x41, 0x7b, 0xe6, 0x6c, 0x37, 0x10 }; unsigned char key[16] = { 0x2b, 0x7e, 0x15, 0x16, 0x28, 0xae, 0xd2, 0xa6, 0xab, 0xf7, 0x15, 0x88, 0x09, 0xcf, 0x4f, 0x3c }; Song and Lee. Expires November 2005 [Page 19]

Internet Draft May 2005 printf("--------------------------------------------------\n"); printf("K "); print128(key); printf("\n"); printf("\nSubkey Generation\n"); AES_128(key,const_Zero,L); printf("AES_128(key,0) "); print128(L); printf("\n"); generate_subkey(key,K1,K2); printf("K1 "); print128(K1); printf("\n"); printf("K2 "); print128(K2); printf("\n"); printf("\nExample 1: len = 0\n"); printf("M "); printf("<empty string>\n"); AES_CMAC(key,M,0,T); printf("AES_CMAC "); print128(T); printf("\n"); printf("\nExample 2: len = 16\n"); printf("M "); print_hex(" ",M,16); AES_CMAC(key,M,16,T); printf("AES_CMAC "); print128(T); printf("\n"); printf("\nExample 3: len = 40\n"); printf("M "); print_hex(" ",M,40); AES_CMAC(key,M,40,T); printf("AES_CMAC "); print128(T); printf("\n"); printf("\nExample 4: len = 64\n"); printf("M "); print_hex(" ",M,64); AES_CMAC(key,M,64,T); printf("AES_CMAC "); print128(T); printf("\n"); printf("--------------------------------------------------\n"); return 0; } Song and Lee. Expires November 2005 [Page 20]

Internet Draft May 2005 Intellectual Property Statement The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Acknowledgment Funding for the RFC Editor function is currently provided by the Internet Society. Song and Lee. Expires November 2005 [Page 21]