| |
| |
| |
| |
| |
| |
| |
| |
| Crypto Forum Research Group David A. McGrew |
| Internet Draft Cisco Systems, Inc. |
| Expires April, 2003 October, 2002 |
| |
| |
| |
| Integer Counter Mode |
| <draft-irtf-cfrg-icm-00.txt> |
| |
| |
| 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 an indexed keystream |
| generator (which generates a keystream segment given an index). |
| This mode is efficient, parallelizable, and has been proven secure |
| given realistic assumptions about the block cipher. Test vectors |
| are provided for AES. |
| |
| 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. |
| |
| |
| |
| |
| |
| |
| McGrew [Page 1] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| 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]. |
| |
| |
| 3. Introduction |
| |
| Counter Mode is a way to define a pseudorandom keystream generator |
| using a block cipher [CTR]. 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 |
| OFFSET_LENGTH the number of octets in the offset |
| SEGMENT_INDEX_LENGTH the number of octets in the segment index |
| BLOCK_INDEX_LENGTH the number of octets in the block index |
| |
| |
| 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 |
| |
| |
| |
| McGrew [Page 2] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| incremented using an increment function based on integer addition, |
| 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, 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. 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. |
| |
| 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 ith counter C[i] of the keystream segment with segment index s |
| is defined as |
| |
| C[i] = (i + s * (256^BLOCK_INDEX_LENGTH)) (+) r |
| |
| where r denotes the shifted Offset, which is defined as the Offset |
| times 256^(BLOCK_LENGTH - OFFSET_LENGTH). (This multiplication |
| left-shifts the Offset so that it is aligned with the leftmost |
| edge of the block.) Here ^ denotes exponentiation and (+) denotes |
| the bitwise exclusive-or operation. |
| |
| 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. They also imply that each segment |
| contains no more than (256^BLOCK_INDEX_LENGTH)*BLOCK_LENGTH octets. |
| |
| 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 |
| |
| |
| |
| McGrew [Page 3] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| the rationale). |
| |
| 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 OFFSET_LENGTH octets, which is used to |
| `randomize' the logical starting point of keystream. The Offset is |
| crucial to providing security; see the rationale. The value of |
| OFFSET_LENGTH SHOULD be at least half that of BLOCK_LENGTH. |
| |
| 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. |
| |
| The fact that the Offset is left-aligned enables an implementation |
| |
| |
| |
| McGrew [Page 4] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| to avoid propagating carry values outside of the block index and/or |
| the segment index. Choosing an OFFSET_LENGTH value equal to half |
| that of BLOCK_LENGTH avoids all of these carries, since the Offset |
| is then shifted so that it occupies the most significant octets of |
| the block, while the block and segment indices occupy the least |
| significant ones. |
| |
| |
| 6. Parameters and Test Vectors for AES |
| |
| This section provides ICM parameters and test vectors for AES |
| with a 128 bit block size and 128 bit key (that is, with a |
| BLOCK_LENGTH and KEY_LENGTH of 16). |
| |
| 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 ... }. |
| |
| BLOCK_LENGTH 16 |
| KEY_LENGTH 16 |
| OFFSET_LENGTH 14 |
| SEGMENT_INDEX_LENGTH 6 |
| BLOCK_INDEX_LENGTH 2 |
| |
| Block Cipher Key: 2b7e151628aed2a6abf7158809cf4f3c |
| Offset: f0f1f2f3f4f5f6f7f8f9fafbfcfd |
| Segment Index: 000000000000 |
| Keystream: e03ead0935c95e80e166b16dd92b4eb4 |
| d23513162b02d0f72a43a2fe4a5f97ab |
| ... |
| |
| The counter values that correspond to the keystream blocks are |
| outlined below. |
| |
| Counter Keystream |
| |
| f0f1f2f3f4f5f6f7f8f9fafbfcfd0000 e03ead0935c95e80e166b16dd92b4eb4 |
| f0f1f2f3f4f5f6f7f8f9fafbfcfd0001 d23513162b02d0f72a43a2fe4a5f97ab |
| f0f1f2f3f4f5f6f7f8f9fafbfcfd0002 41e95b3bb0a2e8dd477901e4fca894c0 |
| ... ... |
| |
| |
| 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. |
| |
| |
| |
| McGrew [Page 5] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| 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. |
| |
| |
| 8. Rationale |
| |
| This speficiation 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 no larger than a CBC mode IV, and ICM enables the use of an |
| explicit IV (as is commonly used with CBC [MD98]) to be avoided. |
| |
| |
| 9. History |
| |
| This draft is based on draft-mcgrew-saag-icm-00.txt, which was |
| submitted to SAAG on November, 2001 and which expired in May, 2002. |
| |
| The current definition of ICM has changed from the earlier one; the |
| counter formation is different and the specifications are |
| |
| |
| |
| McGrew [Page 6] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| unfortunately not interoperable. This change was motivated by a |
| considerable amount of feedback on the desirability of admitting |
| optimizations of the sort described in Section 5, in which the carry |
| operations of counter addition need not be propagated across a large |
| register. |
| |
| The current definition of ICM is interoperable with that defined in |
| Secure RTP [SRTP]. |
| |
| |
| 10. Acknowledgements |
| |
| Thanks are due to Helger Lipmaa, Jerome Etienne, Scott Fluhrer and |
| Mats Naslund for their helpful discussion and comments. |
| |
| |
| 11. 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 Crypto Forum Research Group at: |
| |
| cfrg@ietf.org. |
| |
| |
| 12. 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), |
| http://www.nist.gov/aes/. |
| |
| [CTR] M. Dworkin, NIST Special Publication 800-38A, |
| "Recommendation for Block Cipher Modes of Operation: Methods |
| and Techniques", 2001. Online at |
| |
| |
| |
| McGrew [Page 7] |
| |
| |
| Internet Draft Integer Counter Mode October, 2002 |
| |
| |
| http://csrc.nist.gov/publications/nistpubs/800-38a/sp800- |
| 38a.pdf. |
| |
| [MD98] Madson, C., and Doraswamy, N., "The ESP DES-CBC Cipher |
| Algorithm With Explicit IV", RFC 2405, November 1998. |
| |
| [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, Baugher et. al., |
| Internet Draft, draft-ietf-avt-srtp-05.txt. |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| McGrew [Page 8] |
| |
| |
