Add current version of libSRTP from CVS.

libsrtp/doc/draft-irtf-cfrg-icm-00.txt

+
+
+
+
+
+
+
+
+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]
+
+