Internet Engineering Task Force David A. McGrew
IP Security Working Group Scott R. Fluhrer
INTERNET-DRAFT Cisco Systems, Inc.
Expires in six months Mohammad Peyravian
IBM
July, 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................................3
4.2 Key Usage in SC/ESP.....................................4
5. Cipher Specifications and Requirements.....................4
6. Security Considerations....................................5
7. 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 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].
The rest of this document is organized as follows: stream ciphers
are described in Section 3. The Stream Cipher ESP is defined in
Section 4. Security considerations with the use of stream ciphers
are discussed in Section 5, in which their implementation
imperatives are made explicit and recommendations are made for
their proper usage. Acknowledgements and contact information for
the authors of this paper are in Sections 6 and 7, respectively,
and references are provided in Section 8.
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 ciphertext is added with the keystream 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
McGrew, Fluhrer, Peyravian [Page 2]
Internet Draft The Stream Cipher ESP July, 2000
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
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 [KA98b]. The ESP packet format and
associated semantics are unchanged, but are specialized for SC/ESP.
In the SC/ESP, the ESP Sequence Number as defined in Section 2.2 of
[KA98a] 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 is used to encrypt a single
packet. The Sequence Number with value zero corresponds to the
first keystream segment, that with value one corresponds to the the
second keystream segment, and so on. The first keystream segment
is not used to encrypt any packet, because ESP packets never use
the Sequence Number with value zero.
4.1 The SC/ESP Packet Format
Each field of an ESP packet is described below, with a
McGrew, Fluhrer, Peyravian [Page 3]
Internet Draft The Stream Cipher ESP July, 2000
specification of its use within SC/ESP.
The Sequence Number of an SC/ESP packet is used as an index to the
keystream segment that will be used to encrypt and decrypt that
packet. The Sequence Number is 32 bits long, and is monotonically
increasing, starting with a value of 1 for the first packet.
Sequence Number values are not reused; it is mandated in [KA98a]
that an SA be deleted after 2^32 - 1 packets have been sent. This
ensures that, for a given SA, each SC/ESP packet will be encrypted
with a keystream segment that corresponds to a unique index.
The Payload Data, as defined in Section 2.3 of [KA98a], 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 can be used to conceal the length of the message,
as described in Section 2.4 of [KA98a]. However, padding is not
needed for any other reason, as there is no requirement to
byte-align the payload data to any value, as is done for CBC mode
block ciphers. Therefore, implementations that do not attempt to
conceal the length of the payload will have a Padding Length of
zero.
The Payload Data, Next Header, Padding, and Padding Length fields
are encrypted by bitwise adding those fields, modulo two, with the
segment of keystream indexed by the Sequence Number.
The Authentication Data field and its use have no specialization
for 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 as described in [KA98a]. All
encryption or decryption associated with a given Security
Association (SA) will use 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
Ciphers used in SC/ESP must be able to seek to 2^32 distinct
locations in its keystream, where each location is separated by 64
McGrew, Fluhrer, Peyravian [Page 4]
Internet Draft The Stream Cipher ESP July, 2000
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 stream cipher could be called a (keyed)
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). If
message integrity is required, it can be provided through the use
of an authentication transform. Such a transform SHOULD be used.
An adversary who knows (or correctly guesses) one of the plaintext
bits can manipulate the value of the corresponding ciphertext bit
so that it will decrypt to whatever value the adversary chooses.
Due to the additive nature of the cipher, flipping a bit of
ciphertext will cause the decryption of that ciphertext to have
that bit flipped (relative to the original plaintext). A good
summary of ciphertext manipulation attacks on stream ciphers can be
found in Section 3.4 of [B96]. Note that the Sequence Number
attacks described in that section do not apply to this
specification.
No bit of keystream in an additive stream cipher should ever be
used to encrypt multiple distinct plaintext bits. Such keystream
reuse, disparagingly 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.
McGrew, Fluhrer, Peyravian [Page 5]
Internet Draft The Stream Cipher ESP July, 2000
In the Stream Cipher ESP, a `two-time pad' is avoided by requiring
that both keys and Sequence Numbers 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.
Replay detection SHOULD be used with a Stream Cipher ESP if an
authentication transform is not used. This is because a ciphertext
manipulation attack could take advantage of the lack of
authentication by replaying a message several times, each time
guessing a different value of the plaintext.
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.
We encourage the use of keys that are as large as possible, and
note that in many cases increasing the key size of a cipher does
not affect the throughput of a cipher. In particular, we recommend
that the increase in key size be 32 bits for networks with 50,000
connections (fully meshed networks with up to 200 devices), and 64
bits for networks with 49e+12 connections (fully meshed networks
with up to 7,000,000 devices). This choice of key size ensures
that common plaintext 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. 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].
It is an important point that the extra key provided to thwart
McGrew, Fluhrer, Peyravian [Page 6]
Internet Draft The Stream Cipher ESP July, 2000
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 for
dictionary attacks.
Note that other security protocols which use additive ciphers for
the encryption of Internet traffic (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. 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]