Index: libsrtp/doc/draft-irtf-cfrg-icm-00.txt |
=================================================================== |
--- libsrtp/doc/draft-irtf-cfrg-icm-00.txt (revision 0) |
+++ libsrtp/doc/draft-irtf-cfrg-icm-00.txt (revision 0) |
@@ -0,0 +1,460 @@ |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
+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] |
+ |
+ |
Property changes on: libsrtp/doc/draft-irtf-cfrg-icm-00.txt |
___________________________________________________________________ |
Added: svn:eol-style |
+ LF |