Internet Engineering Task Force David A. McGrew IP Security Working Group Scott R. Fluhrer INTERNET-DRAFT Cheryl Madson Expires in May, 2001 Cisco Systems, Inc. November, 2000 The Stream Cipher Encapsulating Security Payload 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.....................4 6. Counter Mode...............................................5 7. Security Considerations....................................7 7.1 Security of Counter Mode.................................8 8. Summary and Rationale......................................9 9. Acknowledgements..........................................10 10. Contact Information.......................................10 11. References................................................10 McGrew, Fluhrer, Madson [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) [KA98b]. This transform fits into and extends the framework of ESP CBC-Mode Cipher Algorithms [PA98]. Further, this draft describes the use of the Counter Mode of a block cipher as an ESP encryption transform. 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 has been 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]. 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 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 McGrew, Fluhrer, Madson [Page 2] Internet Draft The Stream Cipher ESP July, 2000 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 include SEAL [RC98] and LEVIATHAN [MF00b] . 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 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 McGrew, Fluhrer, Madson [Page 3] Internet Draft The Stream Cipher ESP July, 2000 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. 5. Cipher Specifications and Requirements McGrew, Fluhrer, Madson [Page 4] Internet Draft The Stream Cipher ESP July, 2000 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 Sequence Number 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. Counter Mode Counter Mode is an encryption mode of a block cipher that acts as an additive stream cipher [S96]. This mode can be used in SC/ESP, providing a way to use a block cipher that has the advantages of less packet expansion and parallelizable keystream generation. Counter Mode has been well studied, has proven security properties, and has been submitted to NIST [LRW00,M00] for inclusion in the standard modes of use of the Advanced Encryption Standard (AES) [NIST00]. Our definition of Counter Mode follows that of the Segemented Integer Counter Mode (SICM) [M00], with a 32 bit block index and a 32 bit segment index. This section defines how to compute the keystream segment for a given ESP sequence number. The number of bits in each block of the cipher is denoted as N. The keystream is the concatination of the output blocks of the cipher in encrypt mode, with the inputs specified below. The inputs have the following format: McGrew, Fluhrer, Madson [Page 5] Internet Draft The Stream Cipher ESP July, 2000 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Block Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Segment Index | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + Salt + | .... | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The block index is 32 bits in length, and its value increments by one for every block generated by the keystream: the block index for the ith input block is equal to i plus the initial block index, modulo 2^32. Increments are computed modulo 2^32, so that the value `wraps around' to zero after reaching its maximum value. The block index is initially set to a secret, random 32 bit value. The block index is the only field that varies during the keystream generation for a particular packet. The same initial value of the block index is used for every keystream segment (i.e., it is constant for the duration of an SA. The segment index is 32 bits in length, and its value is the ESP Sequence Number of the packet to which the keystream segment corresponds, plus a 32 bit offset. The offset is a secret, random value that is the same for all keystream segments (i.e., it is constant for the duration of a SA). The salt is an N-64 bit value that is secret and random, and which remains constant for the duration of the SA. For example, for sequence number s, the inputs to the block cipher are as follows: Block Index Segment Index Salt ------------- ------------- ---- A B+s mod 2^32 C A+1 mod 2^32 B+s mod 2^32 C A+2 mod 2^32 B+s mod 2^32 C A+3 mod 2^32 B+s mod 2^32 C ... ... ... where A is the initial value of the block index, B is the offset of the segment index, and C is the salt. To compute the initial value of the block index, the offset of the segment index, and the salt, N random bits are generated and those McGrew, Fluhrer, Madson [Page 6] Internet Draft The Stream Cipher ESP July, 2000 N bits are assigned to the above values, with the first 32 bits being assigned to the block index, the next 32 bits being assigned to the segment index and the rest being assigned to the salt. These N bits should be considered part of the key of the cipher. When IKE is used to establish Counter Mode SC/ESP SAs, the IKE PRF is used to generate N + N_K bits, where N_K is the number of bits in the key of the underlying block cipher. The first N bits of PRF output are used to initialize the structure and the following N_K of bits are used as the key of the underlying block cipher. See section 7.1 for a discussion of the security provided by this keystream generation method. 7. 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 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 McGrew, Fluhrer, Madson [Page 7] Internet Draft The Stream Cipher ESP July, 2000 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 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.1. Security of Counter Mode McGrew, Fluhrer, Madson [Page 8] Internet Draft The Stream Cipher ESP July, 2000 This specification defines Counter Mode to have random, secret values for the initial block index, segment index offset and salt. This strengthens the transform against key collision and time-memory tradeoff attacks [MF00]. By using N bits for these values, these attacks have no advantage over exhaustive search with a key of up to N bits, where N is the block size of the cipher. The AES cipher [NIST00] can be used with a 128 bit block size and a 128 bit key; using these parameters in SC/ESP provides 128 bits of security against all known attacks. The security of the defined counter mode against exhaustive key search is no greater than the strength of the underlying block cipher; the random initial block index, segment index and salt do not add any benefit against this attack. 8. Summary and Rationale SC/ESP enables the use of fast stream ciphers and parallelized implementations, has smaller packet sizes than other currently defined ESP encryption mechanisms, and fits 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 McGrew, Fluhrer, Madson [Page 9] Internet Draft The Stream Cipher ESP July, 2000 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 [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. 9. Acknowledgements We would like to thank Brian Weis and Scott Fanning for their critical review and useful comments. In addition, thanks are due to Phil Rogaway for discussion and encouragement. 10. Contact Information Questions and comments about this memo can be directed to: David A. McGrew, Ph.D. Scott R. Fluhrer Cheryl Madson Cisco Systems, Inc. San Jose, CA 95134-1706 USA {mcgrew, sfluhrer, cmadson}@cisco.com 11. 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. McGrew, Fluhrer, Madson [Page 10] Internet Draft The Stream Cipher ESP July, 2000 [FGK00] Frankel, S., Glenn, R., Kelley, S., "The Candidate AES 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. [LRW00] Lipmaa, H., Rogaway, P., and Wagner, D., "Comments to NIST concerning AES Modes of Operation: CTR-Mode Encryption", NIST AES Modes of Operation Workshop, October, 2000. [MD98] Madson, C., and Doraswamy, N., "The ESP DES-CBC Cipher Algorithm With Explicit IV", RFC 2405, November 1998. [M00] McGrew, D., "Segmented Integer Counter Mode: Specification and Rationale", NIST AES Modes of Operation Workshop, October, 2000. [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). [MF00b] McGrew, D., and Fluhrer, S., "The Stream Cipher LEVIATHAN: Specification and Supporting Documentation", Proceedings of the First NESSIE Open Workshop, https://www.cosic.esat.kuleuven.ac.be/nessie/workshop/. [NIST00] "The Advanced Encryption Standard", http://www.nist.gov/aes, The United States National Institute for Standards and Technology, October, 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 McGrew, Fluhrer, Madson [Page 11] Internet Draft The Stream Cipher ESP July, 2000 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, Madson [Page 12]