Update libsrtp to upstream commit be95365fbb4788b688cab7af61c65b7989055fb4

srtp/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]
-
-