

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]