NIST SP 800-38C 日本語訳

Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality

NIST Special Publication 800-38C

Morris Dworkin

Recommendation for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality

NIST Special Publication 800-38C

Morris Dworkin

Computer Security Division Information Technology Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899-8930

May 2004 (errata update 07-20-2007; corrected value of parameter B on p.19)

U.S. Department of Commerce Donald L. Evans, Secretary

Technology Administration Phillip J. Bond, Under Secretary of Commerce for Technology

National Institute of Standards and Technology Arden L. Bement, Jr., Director

Reports on Information Security Technology

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of technical, physical, administrative, and management standards and guidelines for the cost-effective security and privacy of sensitive unclassified information in Federal computer systems. This Special Publication 800-series reports on ITL’s research, guidance, and outreach efforts in computer security, and its collaborative activities with industry, government, and academic organizations.

Certain commercial entities, equipment, or materials may be identified in this document in order to describe an experimental procedure or concept adequately. Such identification is not intended to imply recommendation or endorsement by the National Institute of Standards and Technology, nor is it intended to imply that the entities, materials, or equipment are necessarily the best available for the purpose.

National Institute of Standards and Technology Special Publication 800-38C Natl. Inst. Stand. Technol. Spec. Publ. 800-38C 25 pages (May 2004)

This Recommendation defines a mode of operation, called CCM, for a symmetric key block cipher algorithm. CCM may be used to provide assurance of the confidentiality and the authenticity of computer data by combining the techniques of the Counter (CTR) mode and the Cipher Block Chaining-Message Authentication Code (CBC-MAC) algorithm.

KEY WORDS: authenticated encryption; authentication; block cipher; confidentiality; cryptography; encryption; information security; message authentication code; mode of operation.

Table of Figures

Table 1: Formatting of the Flags Octet in B₀ — 13

Table 2: Formatting of B₀ — 13

Table 3: Formatting of Ctr_i — 14

Table 4: Formatting of the Flags Field in Ctr_i — 14

This publication is the third Part in a series of Recommendations regarding modes of operation of symmetric key block cipher algorithms.

This document has been developed by the National Institute of Standards and Technology (NIST) in furtherance of its statutory responsibilities under the Federal Information Security Management Act (FISMA) of 2002, Public Law 107-347.

NIST is responsible for developing standards and guidelines, including minimum requirements, for providing adequate information security for all agency operations and assets, but such standards and guidelines shall not apply to national security systems. This guideline is consistent with the requirements of the Office of Management and Budget (OMB) Circular A-130, Section 8b(3), Securing Agency Information Systems, as analyzed in A-130, Appendix IV: Analysis of Key Sections. Supplemental information is provided in A-130, Appendix III.

This guideline has been prepared for use by federal agencies. It may be used by nongovernmental organizations on a voluntary basis and is not subject to copyright. (Attribution would be appreciated by NIST.)

Nothing in this document should be taken to contradict standards and guidelines made mandatory and binding on federal agencies by the Secretary of Commerce under statutory authority. Nor should these guidelines be interpreted as altering or superseding the existing authorities of the Secretary of Commerce, Director of the OMB, or any other federal official.

Conformance testing for implementations of the mode of operation that is specified in this Part of the Recommendation will be conducted within the framework of the Cryptographic Module Validation Program (CMVP), a joint effort of NIST and the Communications Security Establishment of the Government of Canada. An implementation of a mode of operation must adhere to the requirements in this Recommendation in order to be validated under the CMVP. The requirements of this Recommendation are indicated by the word “shall.”

This Recommendation specifies an algorithm, Counter with Cipher Block Chaining-Message Authentication Code [1], abbreviated CCM, that can provide assurance of the confidentiality and authenticity of data. CCM is based on an approved symmetric key block cipher algorithm whose block size is 128 bits, such as the Advanced Encryption Standard (AES) algorithm currently specified in Federal Information Processing Standard (FIPS) Pub. 197 [2]; thus, CCM cannot be used with the Triple Data Encryption Algorithm [3], whose block size is 64 bits. CCM can be considered a mode of operation of the block cipher algorithm. As with other modes of operation, a single key to the block cipher must be established beforehand among the parties to the data; thus, CCM should be implemented within a well-designed key management structure. The security properties of CCM depend, at a minimum, on the secrecy of the key.

CCM is intended for use in a packet environment, i.e., when all of the data is available in storage before CCM is applied; CCM is not designed to support partial processing or stream processing. The input to CCM includes three elements: 1) data that will be both authenticated and encrypted, called the payload; 2) associated data, e.g., a header, that will be authenticated but not encrypted; and 3) a unique value, called a nonce, that is assigned to the payload and the associated data.

CCM consists of two related processes: generation-encryption and decryption-verification, which combine two cryptographic primitives: counter mode encryption and cipher block chaining-based authentication. Only the forward cipher function of the block cipher algorithm is used within these primitives.

In generation-encryption, cipher block chaining is applied to the payload, the associated data, and the nonce to generate a message authentication code (MAC); then, counter mode encryption is applied to the MAC and the payload to transform them into an unreadable form, called the ciphertext. Thus, CCM generation-encryption expands the size of the payload by the size of the MAC. In decryption-verification, counter mode decryption is applied to the purported ciphertext to recover the MAC and the corresponding payload; then, cipher block chaining is applied to the payload, the received associated data, and the received nonce to verify the correctness of the MAC. Successful verification provides assurance that the payload and the associated data originated from a source with access to the key.

A MAC provides stronger assurance of authenticity than a checksum or an error detecting code. The verification of a (non-cryptographic) checksum or an error detecting code is designed to detect only accidental modifications of the data, while the verification of a MAC, as occurs in CCM, is designed to detect intentional, unauthorized modifications of the data, as well as accidental modifications.

This specification of CCM is intended to be compatible with the use of CCM within the draft amendment [4] to the IEEE Standard 802.11 for wireless local area networks [5].

a — The octet length of the associated data.

A — The associated data string.

Alen — The bit length of the associated data.

\(B_i\) — The ith block of the formatted input.

C — The ciphertext.

Clen — The bit length of the ciphertext.

\(Ctr_i\) — The ith counter block.

K — The block cipher key.

Klen — The bit length of the block cipher key.

m — The number of blocks in the formatted payload.

n — The octet length of the nonce.

N — The nonce.

Nlen — The bit length of the nonce.

P — The payload.

Plen — The bit length of the payload.

q — The octet length of the binary representation of the octet length of the payload.

Q — A bit string representation of the octet length of P.

r — The number of blocks in the formatted input data (N, A, P).

Risk — The highest acceptable probability for an inauthentic message to pass the decryption-verification process.

t — The octet length of the MAC.

T — The MAC that is generated as an internal variable in the CCM processes.

Tlen — The bit length of the MAC.

0x — The prefix to a bit string that is represented in hexadecimal characters.

\([x]_s\) — The binary representation of the non-negative integer x, in s bits, where \(x<2^s\).

\(\mathrm{MSB}_s(X)\) — The bit string consisting of the s left-most bits of the bit string X.

lg(x) — The base 2 logarithm of the positive real number x.

The selection of a block cipher algorithm and secret key are discussed in Section 5.1. The two cryptographic primitives that CCM requires for its operation are discussed in Section 5.2. The data elements of CCM are discussed in Section 5.3. The formatting of valid data elements is discussed in Section 5.4. Examples of operations and functions are given in Section 5.5.

For any given key, the underlying block cipher algorithm of the mode consists of two functions that are inverses of each other. As part of the choice of the block cipher algorithm, one of the two functions of the block cipher algorithm is designated as the forward cipher function. ∗ The inverse of this process is called the inverse cipher function; however, the CCM mode does not require the inverse cipher function.

The forward cipher function is a function on bit strings of a fixed bit length; the strings are called blocks, and their length is called the block size. For CCM, the block size of the block cipher algorithm shall be 128 bits; currently, the AES algorithm is the only approved block cipher algorithm with this block size.

The CCM specification essentially combines two cryptographic mechanisms that are based on the forward cipher function. One mechanism is the Counter (CTR) mode for confidentiality, which is specified for general use in the first Part of this Recommendation [6]. The CTR mode requires the generation of a sufficiently long sequence of blocks called the counter blocks. The counter blocks must be distinct within a single invocation and across all other invocations of the CTR mode under any given key, but they need not be secret. This requirement on the counter blocks extends to the CCM mode. See [6] for further discussion of the generation of counter blocks; see Section 5.4 below for an additional requirement on the counter blocks in CCM.

The other cryptographic mechanism within CCM is an adaptation of the cipher block chaining (CBC) technique from [6] to provide assurance of authenticity. Specifically, the CBC technique with an initialization vector of zero is applied to the data to be authenticated; the final block of the resulting CBC output, possibly truncated, serves as a message authentication code (MAC) of the data. The algorithm for generating a MAC in this fashion is commonly called CBC-MAC. This Recommendation does not approve CBC-MAC as an authentication mode outside of the context of the CCM specification; however, a variation of CBC-MAC is proposed for general use in the second Part of this Recommendation [7].

A bit string called the nonce, denoted N, is assigned to the data pair to be protected, i.e., the payload and its associated data. The nonce shall be non-repeating in the sense that any two distinct data pairs to be protected by CCM during the lifetime of the key shall be assigned distinct nonces. In effect, the nonce determines an invocation of CCM. The nonce is not required to be random.

The CCM data elements N, P, and A shall be formatted into a non-empty sequence of complete data blocks, denoted B₀, B₁, …, B_r for some non-negative integer r, in accordance with a function called the formatting function (in [8], the formatting function is called the encoding function, β). The value of r depends on the formatting function and the input elements. For any given key, the following three properties shall hold for the formatting function:

The third property suggests that the formatting function and the counter generation function should not be selected or constructed independently of each other.

An example of a formatting function and counter generation function that together satisfy these requirements is given in Appendix A. Alternative formatting functions may be developed in the future.

Given a positive integer s and a non-negative integer x that is less than 2^s, the binary representation of x in s bits is denoted [x]_s. For example, for the (base 10) integer 45, the binary representation (base 2) is 101101, so [45]₈ = 00101101.

∗ This property deals with the case that a nonce is repeated within two distinct input triples. Although the legitimate source/sender of the data is already required to assign distinct nonces to different input triples, the security model in [8] takes into account that the recipient of purported ciphertexts might not monitor whether a nonce is repeated.

The two CCM processes are called generation-encryption and decryption-verification. The prerequisites, inputs, outputs, steps, and summaries for the execution of the two CCM processes are specified in Sections 6.1 and 6.2 below. The prerequisites are inputs that are typically fixed across many invocations of CCM. The prerequisites and inputs shall meet the requirements in Section 5.

There is some flexibility in the order of the steps of the two processes. For example, the generation of the counter blocks can occur at any time before they are used; in fact, the counter blocks may be generated in advance and be considered as inputs to the processes.

The following is a specification of the generation-encryption process of CCM:

Steps:

Steps:

The input to the decryption-verification process is a purported ciphertext, an associated data string, and the nonce that was purportedly used in the generation of the purported ciphertext. Counter mode decryption is applied to the purported ciphertext to produce the corresponding MAC and payload. If the nonce, the associated data string, and the payload are valid, as discussed in Section 5.4, then these strings are formatted into blocks according to the formatting function, and the CBC-MAC mechanism is applied to verify the MAC. If verification succeeds, the decryption-verification process returns the payload as output; otherwise, only the error message INVALID is returned.

In this appendix, a formatting function for the input data and a counter generation function are specified that together satisfy the requirements of Section 5.4. With these functions, this specification of CCM is essentially equivalent to the specification of CCM in the draft amendment [4] to the IEEE Standard 802.11 for wireless local area networks [5].

The requirements that this particular formatting function imposes on the lengths of the variables in CCM are given in Section A.1; the formatting of the input data is specified in Section A.2; the counter generation function is specified in Section A.3.

A.1 Length Requirements

The formatting in this appendix imposes the following length conditions:

A.2 Formatting of the Input Data

The formatting of the input data (N, A, P) into a sequence of blocks B₀, B₁, …, B_r is presented in the following three sections: in Section A.2.1, the formatting of the nonce and control information such as length indicators is specified; in Section A.2.2, the formatting of A is specified; in Section A.2.3, the formatting of P is specified.

A.2.1 Formatting of the Control Information and the Nonce

Table 1: Formatting of the Flags Octet in B₀

Table 2: Formatting of B₀

For example, if B₀ is

01101110 00010011 11010100 10100011 01011101 01110001 10100101 00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000100 00000001:

A.2.2 Formatting of the Associated Data

A.2.3 Formatting of the Payload

A.3 Formatting of the Counter Blocks

The counter generation function in this section is equivalent to formatting the counter index i into a complete data block. The counter blocks Ctr_i are formatted as shown in Table 3 below.

Within each block Ctr_i, the Flags field is formatted as shown in Table 4 below.

Table 4: Formatting of the Flags Field in Ctr_i

The Reserved bits are reserved for future expansions and shall be set to 0. Bits 3, 4, and 5 shall also be set to 0, to ensure that all the counter blocks are distinct from B₀ (as specified in A.2.1 above). Bits 0, 1, and 2 contain the same encoding of q as in B₀.

B.1 Authentication Assurance

The decryption-verification process determines whether a purported ciphertext input is, in fact, a ciphertext, i.e., the output of the generation-encryption process with the given key, associated data string, and nonce. The basis of the CCM authentication assurance is the scarcity of ciphertexts, which suggests that an attacker, i.e., a party without access to the key or to the generation-encryption process, cannot easily generate a ciphertext. Therefore, any purported ciphertext that passes the decryption-verification process was probably generated legitimately.

Moreover, an attacker may be able to choose the purported ciphertext in such a way as to control every bit of the corresponding payload, as described in [9].* Therefore, if the output of the decryption-verification process is a payload, the contents of the payload do not constitute evidence for its authenticity beyond the assurance that the mode already provides.

Also, an attacker may be able to intercept a legitimate ciphertext and “replay” it for verification at a later time. To defend against such an event, the controlling protocol or application should typically provide the receiver with a means to detect replayed messages, out-of-sequence messages, and missing messages, for example, by numbering legitimate messages sequentially.

B.2 Selection of the MAC Length

In this appendix, four examples are provided for the encryption-generation process of CCM with the formatting and counter generation functions that are specified in Appendix A. The underlying block cipher algorithm is the AES algorithm [2] under a key of 128 bits. The MACs, the nonces, the associated data strings, and the payload strings have different lengths in each example, including a very long, repetitive string of associated data in Example 4. The bit strings are represented in hexadecimal notation.

From each example, a corresponding example of the decryption-verification process of CCM is straightforward to construct.

C.1 Example 1

40414243 44454647 48494a4b 4c4d4e4f

10111213 141516

00010203 04050607

20212223

4f101112 13141516 00000000 00000004 00080001 02030405 06070000 00000000 20212223 00000000 00000000 00000000

6084341b

Ctr₀:

07101112 13141516 00000000 00000000

2d281146 10676c26 32bad748 559a679a

Ctr₁:

07101112 13141516 00000000 00000001

51432378 e474b339 71318484 103cddfb

7162015b 4dac255d

C.2 Example 2

40414243 44454647 48494a4b 4c4d4e4f

10111213 14151617

00010203 04050607 08090a0b 0c0d0e0f

20212223 24252627 28292a2b 2c2d2e2f

B: 56101112 13141516 17000000 00000010 00100001 02030405 06070809 0a0b0c0d 0e0f0000 00000000 00000000 00000000 20212223 24252627 28292a2b 2c2d2e2f

T: 7f479ffc a464

\(Ctr_0\): 06101112 13141516 17000000 00000000

\(S_0\): 6081d043 08a97dcc 20cdcc60 bf947b78

\(Ctr_1\): 06101112 13141516 17000000 00000001

\(S_1\): f280d2c3 75cf7945 20335db9 2b107712

C: d2a1f0e0 51ea5f62 081a7792 073d593d 1fc64fbf accd

K: 40414243 44454647 48494a4b 4c4d4e4f

N: 10111213 14151617 18191a1b

A: 00010203 04050607 08090a0b 0c0d0e0f 10111213

P: 20212223 24252627 28292a2b 2c2d2e2f 30313233 34353637

B: 5a101112 13141516 1718191a 1b000018 00140001 02030405 06070809 0a0b0c0d 0e0f1011 12130000 00000000 00000000 20212223 24252627 28292a2b 2c2d2e2f 30313233 34353637 00000000 00000000

T: 67c99240 c7d51048

\(Ctr_0\): 02101112 13141516 1718191a 1b000000

\(S_0\): 2f8a00bb 06658919 c3a040a6 eaed1a7f

\(Ctr_1\): 02101112 13141516 1718191a 1b000001

\(S_1\): c393238a d1923c5d b335c0c7 e1bac924

\(Ctr_2\): 02101112 13141516 1718191a 1b000002

\(S_2\): 514798ea 9077bc92 6c22ebef 2ac732dc

C: e3b201a9 f5b71a7a 9b1ceaec cd97e70b 6176aad9 a4428aa5 484392fb c1b09951

C.4 Example 4

40414243 44454647 48494a4b 4c4d4e4f

10111213 14151617 18191a1b 1c

00010203 04050607 08090a0b 0c0d0e0f 10111213 14151617 18191a1b 1c1d1e1f 20212223 24252627 28292a2b 2c2d2e2f 30313233 34353637 38393a3b 3c3d3e3f 40414243 44454647 48494a4b 4c4d4e4f 50515253 54555657 58595a5b 5c5d5e5f 60616263 64656667 68696a6b 6c6d6e6f 70717273 74757677 78797a7b 7c7d7e7f 80818283 84858687 88898a8b 8c8d8e8f 90919293 94959697 98999a9b 9c9d9e9f a0a1a2a3 a4a5a6a7 a8a9aaab acadaeaf b0b1b2b3 b4b5b6b7 b8b9babb bcbdbebf c0c1c2c3 c4c5c6c7 c8c9cacb cccdcecf d0d1d2d3 d4d5d6d7 d8d9dadb dcdddedf e0e1e2e3 e4e5e6e7 e8e9eaeb ecedeeef f0f1f2f3 f4f5f6f7 f8f9fafb fcfdfeff ...

20212223 24252627 28292a2b 2c2d2e2f 30313233 34353637 38393a3b 3c3d3e3f

T: f4dd5d0e e4046172 25ffe34f ce91

\(Ctr_0\): 01101112 13141516 1718191a 1b1c0000

\(S_0\): 407136e2 77ec38fc 5af24ef3 24ca1178

\(Ctr_1\): 01101112 13141516 1718191a 1b1c0001

\(S_1\): 49b07f8e 3aa1e010 4241e8bd 5260854e

\(Ctr_2\): 01101112 13141516 1718191a 1b1c0002

\(S_2\): 6ad1cf2c 9af17af3 bcbbbf12 7a01f14d

C: 69915dad 1e84c637 6a68c296 7e4dab61 5ae0fd1f aec44cc4 84828529 463ccf72 b4ac6bec 93e8598e 7f0dadbc ea5b

[1] D. Whiting, R. Housley, N. Ferguson, Counter with CBC-MAC (CCM). Available at http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/.

[2] FIPS Publication 197, Advanced Encryption Standard (AES). U.S. DoC/NIST, November 26, 2001. Available at http://csrc.nist.gov/publications/.

[3] FIPS Publication 46-3, Data Encryption Standard (DES). U.S. DoC/NIST, October 25, 1999. Available at http://csrc.nist.gov/publications/.

[4] Institute of Electrical and Electronics Engineers, Inc., IEEE Std. 802.11i/D7.0, Draft Amendment to Standard for Telecommunications and Information Exchange Between Systems – LAN/MAN Specific Requirements – Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Medium Access Control (MAC) Security Enhancements, October 2003.

[5] Institute of Electrical and Electronics Engineers, Inc., IEEE Std. 802.11-1999, IEEE Standard for Telecommunications and Information Exchange Between Systems – LAN/MAN Specific Requirements – Part 11: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications, New York: IEEE Press, 1999.

[6] NIST Special Publication 800-38A, Recommendation for Block Cipher Modes of Operation – Methods and Techniques. U.S. DoC/NIST, December 2001. Available at http://csrc.nist.gov/publications/.

[7] Draft NIST Special Publication 800-38B, Recommendation for Block Cipher Modes of Operation: the CMAC Authentication Mode. U.S. DoC/NIST, October 2003. Available at http://csrc.nist.gov/CryptoToolkit/modes.

[8] J. Jonsson, On the Security of CTR + CBC-MAC, in Proceedings of Selected Areas in Cryptography – SAC, 2002, K. Nyberg, H. Heys, Eds., Lecture Notes in Computer Science, Vol. 2595, pp. 76–93, Berlin: Springer, 2002.

[9] P. Rogaway and D. Wagner, A Critique of CCM. Cryptology ePrint Archive: Report 2003/070, April 2003. Available at http://eprint.iacr.org/2003/070/.