Internet Engineering Task Force David A. McGrew INTERNET-DRAFT Cisco Systems, Inc. Expires May, 2002 November, 2001 Integer Counter Mode Status of this Memo This document is an Internet Draft and is in full conformance with all provisions of Section 10 of RFC-2026. Internet Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and 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. 1. Abstract This document specifies Integer Counter Mode (ICM), a mode of operation of a block cipher which defines a keystream generator. This mode is efficient, parallelizable, and proven secure given realistic assumptions about the block cipher. Test vectors are provided for RIJNDAEL. Counter Mode admits many variations. The variant specified in this document is secure and flexible, yet it enables a single implementation of a keystream generator to suffice in different application domains. 2. Notational Conventions The key words "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 [B97]. McGrew [Page 1] Internet Draft Integer Counter Mode November, 2001 3. Introduction Counter Mode is a way to define a pseudorandom keystream generator using a block cipher [LRW00,M00]. The keystream can be used for additive encryption, key derivation, or any other application requiring pseudorandom data. In ICM, the keystream is logically broken into segments. Each segment is identified with a segment index, and the segments have equal lengths. This segmentation makes ICM especially appropriate for securing packet-based protocols. 4. ICM In this section, ICM keystream generation and encryption are defined. 4.1. ICM Parameters The following parameters are used in ICM. These parameters MUST remain fixed for any given use of a key. Parameter Meaning ----------------------------------------------------------------- BLOCK_LENGTH the number of octets in the cipher block KEY_LENGTH the number of octets in the cipher key SEGMENT_INDEX_LENGTH the number of octets in the segment index BLOCK_INDEX_LENGTH the number of octets in the block index SEGMENT_LENGTH the maximum number of octets in a segment The index lengths are related to the other parameters, but are defined in order to promote clarity. 4.2. Keystream Segments Conceptually, ICM is a keystream generator that takes a secret key and a segment index as an input and then outputs a keystream segment. The segmentation lends itself to packet encryption, as each keystream segment can be used to encrypt a distinct packet. A counter is a value containing BLOCK_LENGTH octets which is incremented using integer addition modulo 256^BLOCK_LENGTH, to produce a sequence of distinct values which are used as inputs to the block cipher. (In the context of this specification, an integer is an octet string BLOCK_LENGTH octets in length, the most significant of which is the first.) The output blocks of the cipher are concatenated to form the keystream segment. The first octet of the segment is the first octet of the first output block, and so on. McGrew [Page 2] Internet Draft Integer Counter Mode November, 2001 A schematic of this process is shown in Figure 1. Figure 1. The generation of a keystream segment given a segment index and a block cipher key K. Here C[i] and S[i] denote the ith counter and keystream block, respectively, and (++) denotes integer addition modulo 256^BLOCK_LENGTH. segment index | v C[0] ->(++)-> C[1] ->(++)-> C[2] ->(++)-> ... | | | v v v +---+ +---+ +---+ K->| E | K->| E | K->| E | ... +---+ +---+ +---+ | | | v v v S[0] S[1] S[2] ... The initial counter of the keystream segment with segment index s is defined as C[0] = (s * (256^BLOCK_INDEX_LENGTH) + r) modulo (256^BLOCK_LENGTH) where r denotes the Offset. The ith counter of that keystream segment is defined as C[i] = (C[0] + i) modulo (256^BLOCK_LENGTH). The number of blocks in any segment MUST NOT exceed 256^BLOCK_INDEX_LENGTH. The number of segments MUST NOT exceed 256^SEGMENT_INDEX_LENGTH. These restrictions ensure the uniqueness of each block cipher input. Each segment contains SEGMENT_LENGTH octets; this value MUST NOT exceed the value (256^BLOCK_INDEX_LENGTH)*BLOCK_LENGTH. The sum of SEGMENT_INDEX_LENGTH and BLOCK_INDEX_LENGTH MUST NOT exceed BLOCK_LENGTH / 2. This requirement protects the ICM keystream generator from potentially failing to be pseudorandom (see the rationale). McGrew [Page 3] Internet Draft Integer Counter Mode November, 2001 Figure 2. An illustration of the structure of a counter with BLOCK_LENGTH = 8, SEGMENT_INDEX_LENGTH = 2, and BLOCK_INDEX_LENGTH = 2. The field marked `null' is not part of either the block or segment indices. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | null | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | segment index | block index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 4.3. ICM Encryption Unless otherwise specified, ICM encryption consists of bitwise exclusive-oring the keystream into the plaintext to produce the ciphertext. 4.4 ICM KEY An ICM key consists of the block cipher key and an Offset. The Offset is an integer with BLOCK_LENGTH octets, which is used to `randomize' the logical starting point of keystream. The Offset is crucial to providing security; see the rationale. For the purposes of transporting an ICM key, e.g. in a signaling protocol, that key SHOULD be considered a sequence of octets in which the block cipher key precedes the Offset. 5. Implementation Considerations Implementation of the `add one modulo 2^m' operation is simple. For example, with BLOCK_LENGTH = 8 (m=64), it can be implemented in C as if (!++x) ++y; where x and y are 32-bit unsigned integers in network byte order. The implementation of general purpose addition modulo 2^m is slightly more complicated. 6. Parameters and Test Vectors for RIJNDAEL This section provides ICM parameters and test vectors for RIJNDAEL with a 128 bit block size and 128 bit key (that is, with a BLOCK_LENGTH and KEY_LENGTH of 16). McGrew [Page 4] Internet Draft Integer Counter Mode November, 2001 Although a BLOCK_INDEX_LENGTH, SEGMENT_INDEX_LENGTH, and Segment Index are given for each test vector, it is easy to generalize these cases to other values of those parameters. Notation: all integers are expressed in hexadecimal. Each consecutive pair of hex digits corresponds to an octet, so that the integer 000102030405060708090A0B0C0D0E0F corresponds to the octet sequence { 00, 01, 02, 02 ... }. The counter values corresponding to the output blocks are shown for clarity. Test Vector One ICM Key: 000102030405060708090A0B0C0D0E0F000102030405060708090A0B0C0D0E0F Block Cipher Key: 000102030405060708090A0B0C0D0E0F Offset: 000102030405060708090A0B0C0D0E0F BLOCK_INDEX_LENGTH: 4 SEGMENT_INDEX_LENGTH: 4 Segment Index: 00000000 Counter Keystream 000102030405060708090A0B0C0D0E0F 0A940BB5416EF045F1C39458C653EA5A 000102030405060708090A0B0C0D0E10 0263EC94661872969ADAFD0F4BA40FDC 000102030405060708090A0B0C0D0E11 1A2D94B3111CA5F8BDC2C84DCC29EC47 000102030405060708090A0B0C0D0E12 4D0BABD2995F9F076223246847B5D30E 000102030405060708090A0B0C0D0E13 8D33F128463B88EFD3F8A52505020379 Keystream Segment (final output) 0A940BB5416EF045F1C39458C653EA5A0263EC94661872969ADAFD0F4BA40FDC 1A2D94B3111CA5F8BDC2C84DCC29EC474D0BABD2995F9F076223246847B5D30E 8D33F128463B88EFD3F8A52505020379... Test Vector Two ICM Key: 75387824D1F1F3815641B65D78D51EDB96C9781981053CBBCB36927844F1932C Block Cipher Key: 75387824D1F1F3815641B65D78D51EDB Offset: 96C9781981053CBBCB36927844F1932C BLOCK_INDEX_LENGTH: 2 SEGMENT_INDEX_LENGTH: 6 Segment Index: 12345678 McGrew [Page 5] Internet Draft Integer Counter Mode November, 2001 Counter Keystream 96C9781981053CBBCB36A4AC9B69932C EA0AA027BA6D56E44B28F43A7E3E5F58 96C9781981053CBBCB36A4AC9B69932D CBDB3107EDA8D420D3EF7AB7FF290166 96C9781981053CBBCB36A4AC9B69932E AED6F7CB14ED49174336CC010AEB8780 96C9781981053CBBCB36A4AC9B69932F 4C3A754AF027A5C8CCB40E0FE20AF246 96C9781981053CBBCB36A4AC9B699330 01A6D1CE983EF993E980CC9568587E3D Keystream Segment (final output) EA0AA027BA6D56E44B28F43A7E3E5F58CBDB3107EDA8D420D3EF7AB7FF290166 AED6F7CB14ED49174336CC010AEB87804C3A754AF027A5C8CCB40E0FE20AF246 01A6D1CE983EF993E980CC9568587E3D... 7. Security Considerations Each block cipher input is distinct for any segment and any block index. To see this fact, subtract any two counter values with distinct segment or block indices; the result is non-zero. The limitation on the number of segments which can be generated ensures that the probability with which an adversary can distinguish the keystream generator from random is negligible. For a theoretical justification of this fact, see Bellare et. al. [BR98]. Their analysis shows that if the block cipher cannot be distinguished from a random permutation, then the keystream generated by ICM cannot be distinguished from keystream generated by a truly random process, as long as the length of keystream which is generated is kept below some threshold. The threshold defined in Section 4.2 is sufficient for most uses of ICM for encryption. This specification refrains from dictating a lower threshold in order to refrain from dictating a particular policy, and to avoid a complicated digression. The use of the Offset, a key-dependent value which randomizes the starting position of the keystream, is essential for security. The omission of this mechanism leaves the door open for practical attacks, such as the key collision attack and Hellman's time-memory tradeoff attack; see McGrew and Fluhrer [MF00] for a description of these attacks which is applicable to ICM. Several counter mode proposals do not include an offset, and are thus vulnerable to these attacks. McGrew [Page 6] Internet Draft Integer Counter Mode November, 2001 8. Rationale This specification includes input from implementation experience with several counter mode variants. The goals of ICM are to provide: o a secure keystream generator and cipher, and o a definition flexible enough that a single implementation can be used for a variety of applications (e.g., Secure RTP [SRTP], IPsec ESP [KA96]). The Offset slightly increases the key management overhead, but this minor disadvantage is well outweighed by other savings. The Offset is exactly as large as an IV, and ICM enables the use of an explicit IV (as is commonly used with CBC [MD98]) to be avoided. 9. Acknowledgments Thanks are due to Helger Lipmaa, Jerome Etienne, Steve Kent, and Mats Naslund for their helpful discussion and comments. 10. Contact Information Questions and comments on this draft SHOULD be sent to: David A. McGrew Cisco Systems, Inc. mcgrew@cisco.com and copied to the Security Area Advisory Group at saag@mit.edu. 11. References [BR98] M. Bellare, A. Desai, E. Lokipii and P. Rogaway, A Concrete Security Treatment of Symmetric Encryption: Analysis of DES Modes of Operation, Proceedings of the 38th Symposium on Foundations of Computer Science, IEEE, 1997. [B97] S. Bradner, Key words for use in RFCs to Indicate Requirement Levels, RFC 2119, March 1997. [AES] The Advanced Encryption Standard, United States National Institute for Standards and Technology (NIST), McGrew [Page 7] Internet Draft Integer Counter Mode November, 2001 http://www.nist.gov/aes/. [LRW00] H. Lipmaa, P. Rogaway, and D. Wagner, Comments to NIST Concerning AES Modes of Operation: CTR-Mode Encryption, NIST Workshop on AES Modes of Operation, http://csrc.nist.gov/encryption/aes/modes/lipmaa-ctr.pdf [MD98] Madson, C., and Doraswamy, N., "The ESP DES-CBC Cipher Algorithm With Explicit IV", RFC 2405, November 1998. [M00] McGrew, D., "Segmented Integer Counter Mode: Specification and Rationale", comment to NIST Workshop on AES Modes of Operation, http://www.mindspring.com/~dmcgrew/sic-mode.pdf [MF00] D. McGrew and S. Fluhrer, Attacks on Additive Encryption and Implications on Internet Security, Selected Areas in Cryptography 2000. [SRTP] The Secure Real-time Transport Protocol, Blohm et. al., Internet Draft, draft-ietf-avt-srtp-02.txt. McGrew [Page 8]