Internet Engineering Task Force                          David A. McGrew
IP Security Working Group                               Scott R. Fluhrer
INTERNET-DRAFT                                       Cisco Systems, Inc.
Expires in January, 2001                              Mohammad Peyravian
                                                                     IBM
                                                              July, 2000


            The Stream Cipher Encapsulating Security Payload
                   <draft-mcgrew-ipsec-scesp-01.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.

Table of Contents

   1.  Abstract...................................................2
   2.  Notational Conventions.....................................2
   3.  Stream Ciphers.............................................2
   4.  The Stream Cipher ESP (SC/ESP).............................3
     4.1  The SC/ESP Packet Format................................4
     4.2  Key Usage in SC/ESP.....................................4
   5.  Cipher Specifications and Requirements.....................5
   6.  Security Considerations....................................5
   7.  Summary and Rationale......................................7
   8.  Acknowledgements...........................................8
   9.  Contact Information........................................8
   10. References.................................................8






McGrew, Fluhrer, Peyravian                                      [Page 1]


Internet Draft            The Stream Cipher ESP               July, 2000


1. Abstract

   This document specifies the use of an additive stream cipher as a
   confidentiality mechanism within the context of the IPSec
   Encapsulating Security Payload (ESP) defined by Kent and Atkinson
   [KA98b].  This transform fits into and extends the
   framework of ESP CBC-Mode Cipher Algorithms of Pereira and Adams
   [PA98], and can be used in conjunction with any ESP Authentication
   Algorithm.  The advantages of the Stream Cipher ESP (SC/ESP)
   transform are twofold: it enables the use of faster ciphers, and
   the expansion of stream cipher ESP protected packets is less than
   that of CBC-Mode ESP protected packets.  A detailed security
   analysis of additive encryption of Internet traffic and SC/ESP is
   being published separately [MF00].

   The stream ciphers that can be used by the Stream Cipher ESP must
   be able to efficiently seek to arbitrary locations in their
   keystream.  This requirement ensures that Stream Cipher ESP packets
   can be efficiently decrypted even when they are received out of
   order, and protects against denial of service attacks described
   against earlier IPSEC stream cipher proposals by Bellovin [B96].

   This rest of this document describes additive stream ciphers,
   defines the Stream Cipher ESP, reviews security considerations, and
   provides a rationale and a summary.

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. Stream Ciphers

   An additive stream cipher is a cipher that generates a
   pseudo-random string of bits called a keystream, and encrypts by
   bitwise adding this string into the plaintext, modulo two (recall
   that addition modulo two is the same as exclusive-or).  To decrypt,
   the keystream is bitwise added into the ciphertext modulo two.
   Stream ciphers and their terminology are well described by Ruppel
   [R92] and Schneier [S96].  In the rest of this document, we will
   use the term "stream cipher" to refer to additive stream ciphers.

   Secure stream ciphers with high encryption rates may be more
   realizable than block ciphers with similar qualities.  There is
   both practical and theoretical support for this statement.  On the
   practical side, a C implementation of the SEAL cipher [RC98]
   encrypted 256 byte blocks of data at 16.9 times the rate as did an



McGrew, Fluhrer, Peyravian                                      [Page 2]


Internet Draft            The Stream Cipher ESP               July, 2000


   optimized C implementation of the Data Encryption Standard
   [FIPS46], in the authors' experiments on a 32 bit RISC processor.
   On the theoretical side, there are attacks that a block cipher must
   be designed to resist (e.g., chosen plaintext attacks) that are not
   effective against a stream cipher.  Additionally, many stream
   ciphers can be implemented with parallelism.

   The Internet Protocol is an unreliable transport mechanism, and ESP
   packets may arrive out of order, and may not arrive at all.  The
   unreliable nature of IP requires that stream ciphers used to
   encrypt IP packets be able to efficiently generate keystream out of
   order.  We say that a cipher that can do this has the `seek'
   capability.  Such stream ciphers exist; SEAL is one example [RC98].

   Many stream ciphers are intended only to produce keystream in
   order, and cannot efficiently produce unordered segments of
   keystream.  RC4 [S96] and the Output Feedback (OFB) mode [FIPS81]
   are ciphers with this restriction.  It is possible to define a
   state-caching mechanism that enables the decryption of out-of-order
   packets with such a cipher.  However, such methods are complicated,
   are expensive in terms of memory and/or processor time, and may be
   vulnerable to the denial of service attacks described by Bellovin
   [B96].  Therefore, this specification excludes ciphers with that
   limitation.

4. The Stream Cipher ESP (SC/ESP)

   The Stream Cipher Encapsulating Security Payload defines an
   encryption mechanism for ESP.  The ESP packet format and associated
   semantics as defined in Section 2 of [KA98b] are unchanged, but are
   specialized for SC/ESP in order to meet the unique requirements of
   stream ciphers.

   In the SC/ESP, the ESP Sequence Number as defined in Section 2.2 of
   [KA98b] is used as an index into the keystream.  The keystream is
   viewed as 2^32 segments of length 64 kilobytes (the maximum length
   of an IP packet), each segment of which corresponds to a single
   packet.  The segments are indexed from zero to 2^32 - 1.  The
   keystream segment with index zero is not used to encrypt any
   packet, because ESP packets never use the Sequence Number with
   value zero.

   Encryption of a particular packet consists of generating as many
   bytes of the keystream segment as are needed to encrypt that
   packet, then bitwise adding that keystream into the fields of the
   ESP packet that are confidentiality protected.  The keystream
   segment is aligned with the Payload Data; that is, the initial bit
   of the keystream segment is used to encrypt the initial bit of the



McGrew, Fluhrer, Peyravian                                      [Page 3]


Internet Draft            The Stream Cipher ESP               July, 2000


   Payload Data, and so on.  The number of bytes of the keystream
   segment that are used to encrypt a particular packet is equal to the
   length of the Payload Data plus the length of the Padding plus two
   (for the Pad Length and Next Header fields).

   An ESP Authentication Algorithm MUST be used with SC/ESP.  This
   provides authentication of the Sequence Number, thus preventing
   attacks which could manipulate the Sequence Number.

4.1 The SC/ESP Packet Format

   Each field of an ESP packet is described below, with a
   specification of its use within SC/ESP.

   The Payload Data contains only the data described by the Next
   Header field, i.e., the ciphertext message.  There is no
   Initialization Vector (IV) as described in that section, as a
   stream cipher does not need an IV.

   Plaintext Padding must be used to align the Authentication Data
   field to a four-byte boundary, if needed, and may be used to
   conceal the length of the message, as described in Section 2.4 of
   [KA98b].  However, there is no need to pad the plaintext out to a
   length that is a multiple of a block size, as is done for CBC mode
   block ciphers.  The bitwise nature of additive encryption obviates
   the need for such padding.

   The Payload Data, Next Header, Padding, and Padding Length fields
   are encrypted by bitwise adding those fields, modulo two, with the
   corresponding length of the segment of keystream indexed by the
   Sequence Number.

   The Authentication Data field MUST be present, because an
   Authentication Algorithm MUST be used with SC/ESP.

4.2  Key Usage in SC/ESP

   The key used by the stream cipher is shared between the sender and
   the receiver, and MUST be generated by a uniformly random process
   [KA98a].  All encryption or decryption associated with a given
   Security Association (SA) uses the same key.

   Additive stream ciphers must be protected against key collision and
   time-memory tradeoff attacks, both of which are possible when the
   the plaintext source is redundant [MF00].  The SC/ESP can achieve
   this protection through the use of large keys, as described in
   Section 5.




McGrew, Fluhrer, Peyravian                                      [Page 4]


Internet Draft            The Stream Cipher ESP               July, 2000


5. Cipher Specifications and Requirements

   A cipher used in SC/ESP must be able to seek to 2^32 distinct
   locations in its keystream, where each location is separated by 64
   Kilobytes (or 2^19 bits).

   The security requirement on ciphers used in SC/ESP is that a secret
   key used to generate 2^48 bytes of keystream (the maximum length of
   the keystream used in SC/ESP) cannot be found by a computationally
   limited adversary who has been given that keystream.  At present,
   `computationally limited' implies an adversary that cannot perform
   more than about 2^80 trial encryptions nor store more than about
   2^54 ciphertexts, though a precise definition of this term is
   beyond the scope of this standard.  This requirement ensures that
   SC/ESP will provide privacy even in the case that the vast majority
   of its plaintext is known to an adversary.

   In order to specify an instantiation of the SC/ESP transform with a
   particular cipher, a description of how to produce a 64 Kilobyte
   segment of keystream given a 32 bit index in network byte order
   MUST be provided.

   While this specification refers to stream ciphers, it is worth
   noting that a seekable keystream generator could be called a keyed
   pseudorandom function, or a pseudorandom function family in the
   cryptographic literature [GGM86, RC98].

6. Security Considerations

   Additive ciphers do not provide any security service other than
   privacy.  In particular, they do not provide message integrity (see
   [RK99] or [S96] for a discussion of this security service).  A good
   summary of ciphertext manipulation attacks on stream ciphers can be
   found in Section 3.4 of [B96] (though the denial of service attacks
   described in that section do not work against this specification).

   In SC/ESP, message integrity is provided through the use of an ESP
   Authentication Algorithm.  Such a transform MUST be used with
   SC/ESP.

   No bit of keystream in an additive stream cipher should ever be
   used to encrypt multiple distinct plaintext bits.  Such keystream
   reuse (jokingly called a `two-time pad' system by cryptographers),
   can seriously compromise security.  The NSA's VENONA project [C99]
   provides a historical example of such a compromise.

   In the Stream Cipher ESP, a `two-time pad' is avoided by requiring
   that both keys and Sequence Numbers (and thus the indices to the



McGrew, Fluhrer, Peyravian                                      [Page 5]


Internet Draft            The Stream Cipher ESP               July, 2000


   keystream segments) be unique.  The uniqueness of the Sequence
   Numbers (for a given SA) is already part of the ESP specification,
   and is mandated by [KA98b].  Uniqueness of the keys follows from
   proper key management.  To help enforce good key management, manual
   keying SHOULD NOT be used with a Stream Cipher ESP.  If manual
   keying is used, two different SAs might accidentally use the same
   SC/ESP key with non-negligible probability, through manual error or
   procedural inadequacies.  The Internet Key Exchange [HC98], or some
   other automated mechanism, SHOULD be used to establish keys for the
   Stream Cipher ESP.

   An additive stream cipher is vulnerable to attacks that use
   statistical knowledge about the plaintext source to enable key
   collision and time-memory tradeoff attacks [MF00,H80,Bi96].  These
   attacks take advantage of commonalities among plaintexts, and
   provide a way for a cryptanalyst to amortize the computational
   effort of decryption over many keys, thus reducing the effective
   key size of the cipher.  A detailed analysis of these attacks and
   their applicability to the encryption of Internet traffic is
   provided in [MF00].  In summary, the effective key size of SC/ESP,
   when used in a security system in which m distinct keys are used,
   is equal to the key size of the cipher less the logarithm (base
   two) of m.  Protection against such attacks can be provided simply by
   increasing the size of the keys used.

   In order to provide an effective key size of n bits in a deployment
   in which SC/ESP 2^m SAs will be created, the true key size will
   need to be n+m bits.  The value of m SHOULD be 32 bits for networks
   with 50,000 connections (fully meshed networks with up to 200
   devices), and SHOULD be 64 bits for networks with 49e+12
   connections (fully meshed networks with up to 7,000,000 devices).
   These choices of m ensures that key collision attacks amortized
   over a ten year period offer no advantage over exhaustive search,
   when new SC/ESP keys are established for every connection every
   hour (note that such an attack requires the storage of all network
   traffic over the ten year period).  These choices will suffice for
   many networks, though SC/ESP deployments with more stringent
   security requirements will need to make a detailed assessment of
   those requirements with respect to the attacks described in [MF00].

   Implementations SHOULD use keys that are as large as possible.
   Please note that in many cases increasing the key size of a cipher
   does not affect the throughput of that cipher.

   It is an important point that the m bits of `extra' key provided to
   thwart these attacks need not be private.  In jurisdictions with
   mandated limits on the length of a secret key, the additional key
   bits could be made public.  This is because those bits are



McGrew, Fluhrer, Peyravian                                      [Page 6]


Internet Draft            The Stream Cipher ESP               July, 2000


   functionally equivalent to the `salt' that is used to protect
   passwords from dictionary attacks.  The fact that the `extra' key
   bits are distinct for many different keys defeats the key collision
   and time-memory tradeoff attacks by reducing the number of keys
   over which cryptanalytic computation can be amortized.

   Note that other security protocols which use additive ciphers for
   the encryption of Internet traffic (e.g., SSL, TLS, SSH) are also
   vulnerable to the attacks described in [MF00].  Those attacks are
   generic to additive encryption of redundant plaintext, and are not
   particular to SC/ESP, ESP, nor IPSEC.

7.  Summary and Rationale

   SC/ESP enables the use of fast stream ciphers, has smaller packet
   sizes than other currently defined encryption mechanisms, and fits
   completely into the frameworks defined by [KA98a] and [PA98].

   SC/ESP achieves small packet sizes by merging cryptographic
   synchronization information with a replay protection counter.  The
   use of the ESP Sequence Number as an index, rather than using a
   field dedicated to this purpose, achieves cryptographic
   synchronization while reducing the size of an SC/ESP packet.  For
   example, an SC/ESP packet is between eight and fifteen bytes
   shorter than a comparable ESP DES-CBC packet [MD98], and between
   sixteen and thirty one bytes shorter than a comparable ESP AES CBC
   packet [FGK00].  There are no adverse security implications of this
   dual use of the ESP Sequence Number.  This follows from the fact
   that the only security property that we expect from the stream
   cipher is privacy, and the security of the cipher is independent of
   how its keystream is indexed.

   The foremost motivation for SC/ESP is to enable the use of fast
   stream ciphers within ESP.  However, no ciphers are specified in
   this document, in order that this document may provide a basis for
   the standardization of the use of any cipher that meets the
   criteria outlined in Section 4.  SEAL [RC98] satisfies these
   criteria, as does any block cipher in counter mode [S96].  It has
   been widely recognized that implementations of counter mode
   encryption can take advantage of parallelization, while CBC mode
   encryption is necessarily serialized.

   CBC mode encryption has the advantage that it is not as vulnerable
   to typical plaintext attacks as is encryption with an additive
   stream cipher.  This is because CBC is `randomized' through the use
   of an unpredictable IV.  However, additive encryption can achieve
   the same level of security as CBC mode encryption through an
   increase in key size as described at the end of Section 5 and in



McGrew, Fluhrer, Peyravian                                      [Page 7]


Internet Draft            The Stream Cipher ESP               July, 2000


   [MF00].  This strategy of "putting all of the randomization in the
   key" provides an encryption method that can be as secure as CBC,
   while providing the advantages outlined above.

8. Acknowledgements

   We would like to thank Cheryl Madson, Brian Weis, and Scott Fanning
   for their critical review and useful comments.  In addition, thanks
   are due to Phil Rogaway for discussion and encouragement.

9. Contact Information

   Questions and comments about this memo can be directed to:

   David A. McGrew, Ph.D.
   Scott R. Fluhrer
   Cisco Systems, Inc.
   San Jose, CA 95134-1706 USA
   mcgrew@cisco.com, sfluhrer@cisco.com

   Mohammad Peravian
   IBM
   peyravn@us.ibm.com

10. References

   [B97]   Bradner, S., "Key words for use in RFCs to Indicate
           Requirement Levels", RFC 2119, March 1997.

   [KA98a] Kent, S., and R. Atkinson, "Security Architecture for IP",
           RFC 2401, November 1998.

   [KA98b] Kent, S., and R. Atkinson, "IP Encapsulating Security
           Payload (ESP)", RFC 2406, November 1998.

   [B96]   S. Bellovin, "Problem Areas for the IP Security Protocols",
           Sixth USENIX Unix Security Conference,
           ftp://ftp.research.att.com/dist/smb/badesp.ps.

   [C99]   Crowell, W. P., "Introduction to the VENONA Project",
           http://www.nsa.gov:8080/docs/venona/index.html.

   [FIPS46] "Data Encryption Standard", Federal Information Processing
           Standard (FIPS) Publication 46-2, US National Institute of
           Standards and Technology,
           http://www.itl.nist.gov/fipspubs/fip46-2.htm.

   [FGK00] Frankel, S., Glenn, R., Kelley, S., "The Candidate AES



McGrew, Fluhrer, Peyravian                                      [Page 8]


Internet Draft            The Stream Cipher ESP               July, 2000


           Cipher Algorithms and Their Use With IPsec", Internet Draft
           draft-ietf-ipsec-ciph-aes-cbc-00.txt, March, 2000.

   [GGM86] Goldreich, O., Goldwasser, S. and Micali, S., "How to
           construct random functions", Journal of the ACM, Volume 33,
           Number 4, 1986, pp. 210-217.

   [HC98]  Harkins, D. and Carrel, D., The Internet Key Exchange (RFC
           2409).  November, 1998.

   [H80]   Hellman, M. E., "A cryptanalytic time-memory trade-off", IEEE
           Transactions on Information Theory, July 1980, pp. 401-406.

   [MD98]  Madson, C., and Doraswamy, N., "The ESP DES-CBC Cipher
           Algorithm With Explicit IV", RFC 2405, November 1998.

   [MF00]  McGrew, D., and Fluhrer, S., "Attacks on Encryption of
           Redundant Plaintext and Implications on Internet Security",
           to be presented at the Seventh Annual Workshop on Selected
           Areas in Cryptography (SAC 2000).

   [PA98]  Pereira, R. and Adams, R., "The ESP CBC-Mode Cipher
           Algorithms", RFC 2451.

   [R92]   Rueppel, R., "Stream Ciphers", Chapter 2 of Simmons, G.,
           "Contemporary Cryptology: the Science of Information
           Integrity," 1992, IEEE Press.

   [RC94]  Rogaway, P. and Coppersmith, D., "A Software-Optimized
           Encryption Algorithm", Proceedings of the 1994 Fast
           Software Encryption Workshop, Lecture Notes In Computer
           Science, Volume 809, Springer-Verlag, 1994, pp. 56-63.

   [RC98]  Rogaway, P. and Coppersmith, D., "A Software-Optimized
           Encryption Algorithm", Journal of Cryptology, Volume 11,
           Number 4, Springer-Verlag, 1998, Pages 273-287.  Also
           available on the Internet at
           http://www.cs.ucdavis.edu/~rogaway/papers/seal-abstract.html.

   [RK99]  Rescorla, E., and Korver, B., "Guidelines for Writing RFC
           Text on Security Considerations,"
           draft-rescorla-sec-cons-00.txt

   [S96]   Schneier, B. "Applied Cryptography: Protocols, Algorithms,
           and Source Code in C", Wiley, 1996.






McGrew, Fluhrer, Peyravian                                      [Page 9]