Network Working Group G. Caronni Internet Draft M. Waldvogel TIK, ETHZ, Switzerland Expires in six months April 1996 The ESP Stream Transform draft-caronni-esp-stream-00.txt Status of this Memo ------------------- This document is an Internet-Draft. Internet Drafts are working docu- ments of the Internet Engineering Task Force (IETF), its areas, and its working Groups. Note that other groups may also distribute working docu- ments as Internet Drafts. Internet-Drafts draft documents are 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." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast). Distribution of this memo is unlimited. The authors intend to publish this draft as an Experimental RFC after it has been reviewed within the IPsec Working Group. Abstract -------- This document describes a security transform providing privacy and (optional) replay protection through Encapsulating Secure Payload (ESP). The transform defines how to use ESP in conjunction with byte-oriented stream ciphers, such as RC4 or SEAL. These stream ciphers offer strong encryption with comperatively low computational demands, and are thus favorable for multimedia bulk data or environments where the computing power needed per packet should be low. Caronni, Waldvogel [Page 1] INTERNET-DRAFT ESP Stream Transform March 1996 Table of Contents ----------------- 1. Introduction 1.1. Conventions 1.2. Cipher Overview 2. Payload Format 2.1. Stream Offset 2.2. Replay Protection Using the Stream Offset 2.3. Authentication Issues 3. Encryption 4. Decryption 5. Security Considerations 6. Implementation Details 6.1. Summary of Limits 6.2. Technical Notes 7. Acknowledgements 8. References 9. Author addresses 1. Introduction ---------------- The mechanisms presented in this document provide confidentiality and optional replay protection for IP datagrams, using the Encapsulating Security Payload (ESP) [RFC1827] format. Altough ESP may also provide data integrity and authenticity, 'esp-stream' only offers encryption. This document assumes that the reader is familiar with the related docu- ment "Security Architecture for the Internet Protocol" [RFC1825], which defines the overall security plan for IP and provides important back- ground. Additionally, familiarity with "IP Encapsulating Security Pay- load (ESP)" [RFC1827] is required, as some of the mechanisms employed here are described in greater depth in that document. 1.1. Conventions ----------------- There are a few conventions we followed in this document what the reader should be aware of: a) Whenever it is said that something is ``LIMITED'', the appropriate maximum and minimum values plus a set of recommended values are given in section 6.1. b) The meanings of capitalized ``MUST'', ``MUST NOT'', ``SHOULD'', and ``MAY'' apply as declared in [RFC1825]. c) Variables and constants in pseudo code are in ALL CAPITALS, to clearly distinguish actual code symbols from the description of the action. Caronni, Waldvogel [Page 2] INTERNET-DRAFT ESP Stream Transform March 1996 1.2. Cipher Overview --------------------- Fast algorithms, such as RC4 (devised by Ron Rivest) or SEAL (by Phil Rogaway and Don Coppersmith) are very efficient and easily understand- able symmetric additive stream ciphers with a large internal state. The efficiency with which they operate make them ideal candidates for encrypting/decrypting high-throughput, low-latency data streams in software with relatively low CPU usage or just whenever low CPU overhead for security is needed. Such data streams are very common in modern multi-media applications who transmit video data and/or high quality audio data. RC4 has been used (together with SKIP prototypes) to encrypt interactive video connections over IP. Resulting quality was adequate and acceptable. For all stream ciphers, key lengths of up to and including 128 bits MUST be supported by the implementation, although any particular key may be shorter. Longer keys are strongly recommended. RC4 allows for key sizes of up to 256 bytes. The key is used to permute the values of 0 to 255 in an array of 256 entries, thus creating the internal state for the pseudo random generator, whose output is used as a one time pad for encryption/decryption. The initial state after keying can thus be one out of 256! states, being equivalent to about 1676 bits key state. SEAL supports position-dependent key setup, expects 160 bits of key material and allows initializing at any 32 bit offset into the stream. SEAL mayin certain environments be even faster than RC4. Key setup in SEAL is much more expensive, as SHA is employed to generate the internal state. For more details about RC4, SEAL, and about using other stream ciphers, refer to [Schn96]. Please note that SEAL is being patented by IBM, and RC4, altough interoperable code is available, is a proprietary algorithm of RSA Data Security Inc. RC4 is trademarked by RSA DSI, anybody contem- plating its use should contact them. 2. Payload Format ------------------ The following diagram describes the basic format of IP packets contain- ing the 'esp-stream' header and data. The selection of the actual stream cipher and the key to be used has to take place on a upper layer. |<---- Unencrypted ---->|<---- Encrypted ---->| +-----------+-----------------+------------+----------------+------+ | IP Header | IP Ext. Headers | ESP Header | Encrypted Data | Type | +-----------+-----------------+------------+----------------+------+ Caronni, Waldvogel [Page 3] INTERNET-DRAFT ESP Stream Transform March 1996 A more detailed diagram of the format of the particular ESP Header (labelled ``E'' in the left column shown in diagram below) to be used with stream ciphers and the data following it (Data labelled ``D'', Type labelled ``T'') is given below, together with a short description of every field. |1 2 3 4 5 6 7 8|1 2 3 4 5 6 7 8|1 2 3 4 5 6 7 8|1 2 3 4 5 6 7 8| - +---------------+---------------+---------------+---------------+ E | Security Parameters Index (SPI) | E +---------------------------------------------------------------+ E | | E | Stream Offset (64 bits) | E | | - +---------------------------------------------------------------+ D | | D : Encrypted Payload Data (arbitrary number of bytes) : D | | D | +---------------+---------------+ T | | Payload Type | - +-------------------------------+---------------+ Notes ----- Security Parameters Index (SPI) A 32-bit value identifying the Security Parameters for this datagram (network order). The value MUST NOT be zero. Stream Offset (64 bits) Indicates the number of data bytes already encrypted under the current key for this cipher before this packet was encrypted. This value is stored in network order (most significant octet first) [RFC1700]. For details, see section 2.1. Encrypted Payload Data (arbitrary number of bytes) Encapsulated IP or other protocol data, encrypted. No padding is required. Payload Type (8 bits) Contains the encrypted type of the next protocol header in the encrypted payload data. Up-to-date values of the IP Protocol/Payload are specified in the most recent "Assigned Numbers" [RFC1700]. This value is encrypted together with the pay- load, and may only be examined after decryption. 2.1. Stream Offset ------------------- Current stream ciphers were not designed for integration in IP. There- fore, provisions for detecting and handling out of order delivery, Caronni, Waldvogel [Page 4] INTERNET-DRAFT ESP Stream Transform March 1996 duplicate or missing packets must be taken additionally. The Stream Offset field is used at the receiving end to prepare the ciphers inter- nal state such that decrypting is possible even in case of abovemen- tioned events. To make this possible, the receiver MUST be able to accept packets with Stream Offset being a LIMITED number of bytes ahead or before the previ- ously received Stream Offset. The sender MUST count all bytes encrypted before the first byte in this packet is encrypted and send this value as this packet's Stream Offset. The counter MUST be initialized with zero when the encryption key is used the first time. It MUST be reset to zero if and only if the encrypting key changes. It MUST NOT be reset at any other time. Espe- cially, it MUST NOT be allowed to wrap around to zero, the encryption key MUST be changed instead. It is most important (see security con- siderations in section 5), that no encrypting key is used with the same Stream Offset twice. Thus, after the encrypting key has been changed, the probability for its reuse MUST be as small as practically feasible. Ideally, an old encryption key SHOULD NOT be reused ever. The sender MAY encrypt a LIMITED number of dummy bytes between packets, although this is discouraged, because it would use more cache space at the receiver. 2.2. Replay Protection Using the Stream Offset ----------------------------------------------- Since the sender creates Stream Offsets so that for any two packets encrypted with the same key their ranges [Stream Offset .. (Stream Offset + Encrypted Bytes in Packet - 1)] are free of intersections, the receiver may optionally check this range independence to protect against replay attacks. The receiving end may independently decide whether replay protection is to be performed or not, it is not mandatory that the sender be involved in this decision. To achieve Replay Protection, the receiver has to remember the ``holes'' in the Stream where incoming packets may still be accepted. For each currently employed key, a LIMITED list of valid Stream Offset ranges has to be stored. They cover the range starting from the end of the 'highest' received packet up to the maximum offset, and ranges where packets have not yet been delivered (e.g. were lost in transit or will be delivered out of order). In section 4 we will give pseudo code that implements replay protection for the receiving end, at the same time allowing for reception of out of order packets. 2.3. Authentication Issues --------------------------- Authentication is not included into the 'esp-stream' transform, mainly Caronni, Waldvogel [Page 5] INTERNET-DRAFT ESP Stream Transform March 1996 because of the following points: a) The main reason to employ stream ciphers such as RC4 or SEAL is the remarkable speed of these alogorithms. MD5 software speeds are ade- quate for commonly deployed LAN and WAN links, but reportedly are too slow for newer link technologies [RFC1810]. If faster implementations emerge, their use is strongly recommended, as encryption without authentication offers only a very limited amount of security. b) Authentication may be chosen as an orthogonal transform in addition to this transform, so users have the ability to choose the authenti- cation that best fits necessities in speed and security at runtime. 3. Encryption -------------- Procedural description of the encryption process: Encrypt packet: Prepare sufficient space before and after the payload; Append a Payload Type byte describing the type of encapsulated data; Store the SPI in the SPI field; Get the current internal state associated with this security association; Store the number of data bytes already encrypted with the current key into the Stream Offset field; Encrypt the payload and the Payload Type byte, updating the internal state; Generate outer headers such as AH or IP; Send packet; 4. Decryption -------------- Pseudo code to allow efficient handling of out of order packet reception and packet loss including replay protection is given below. To remember the range of Stream Offsets already used by the received packets, a set of 3-tuples for each packet key is stored. It contains start of used range, end of used range (=start+length, effectively being start of next expected packet), and cipher internal state associated with the Stream Offset of the packet that would immediately follow. If no protection against replay attacks is required, the following pseudo code may be simplified. We strongly recommend using replay pro- tection, as the additional cost is low and the benefits are large. FORWARD_SEEK_LIMIT and STATE_CACHE_ENTRIES are defined in section 6.1, DATA_SIZE includes the actual Payload size and the one byte Payload Type field. Key initialization (input: KEY): Set INTERNAL_STATE to the result of prepare_key(KEY); Caronni, Waldvogel [Page 6] INTERNET-DRAFT ESP Stream Transform March 1996 Store tuple (0, 0, INTERNAL_STATE); Return; Decrypt packet (input: ESP_HEADER, ESP_DATA, DATA_LENGTH): Process all outer headers; Set START to Stream Offset found in ESP_HEADER; Set END to START + DATA_LENGTH; If intersection between [START..END] and any stored range { Drop packet and return; // Replay, garbage, or duplicate packet } Set PREDECESSOR to tuple with biggest end <= START; If no PREDECESSOR was found { Drop packet and return; // Packet too old } If START minus PREDECESSOR.END is greater than FORWARD_SEEK_LIMIT { Drop packet and return; // Too far out in ``future'' key stream } If START equals PREDECESSOR.END { Set WORK to PREDECESSOR; } else { // Seek forward to a new IV Duplicate of PREDECESSOR.IV, call it TEMP_IV; Run rc4 on PREDECESSOR.END-START dummy bytes with TEMP_IV, updating it; Store new tuple WORK = (START, START, TEMP_IV); } // We have a tuple just preceeding ours, // extend it by our newly received range decrypt with WORK.IV, updating the IV; Set WORK.END to END; If there is a tuple NEIGHBOUR whose start == END { // join the two ranges into one Set NEIGHBOUR.START to WORK.START; Delete WORK; } If more than STATE_CACHE_ENTRIES tuples are stored { // delete the first (oldest) hole. Set START of the first remaining tuple to 0; } Get Payload Type; If Payload Type is valid { Process packet according to payload type and return; } else { Drop the packet and return; } It is suggested that a new tuple (with extended range) is only stored if Caronni, Waldvogel [Page 7] INTERNET-DRAFT ESP Stream Transform March 1996 the incoming packet is correctly authenticated. Alternatively, if no authentication is required, it may also be stored if the packet decrypts correctly (i.e. passes some integrity tests, such as a valid TCP or UDP checksum in inner headers). This is to prevent denial of service attacks involving excessive seeking in the key stream. In the case a packet fails the verification the packet MUST be dropped. 5. Security Considerations --------------------------- One goal of this document is to allow different implementors of the stream cipher RC4 to interoperate securely. Some of the security con- siderations discussed here hold true for other ciphers. Do NOT re-use key material. Do not use previous keys to generate new keys, but use a reliable and well-initialized random number generator to generate new keys. See [RFC1750] for additional information. If you do re-use key material, the security of a stream cipher is instantly lost. Remove all information belonging to old keys whenever they become invalid, including information held in caches, especially the ``hole'' cache. The key management protocol in the upper layer has to decide when a key becomes invalid. As pointed out in [Roos95], there are classes of weak keys (especially those whose first two bytes are two's complements of each other), which SHOULD be avoided in RC4. Since the first few bytes generated after the initial setup of the RC4 are those easiest cryptanalized and broken (see [Roos95]), we recommend that the sender SHOULD encrypt a LIMITED number of dummy bytes (updating the internal state and the Stream Offset accordingly) before starting to send packets. Receivers must be prepared to accept a first packet with a Stream Offset that is equal to a LIMITED number of bytes above zero. We strongly recommend using authentication if your security requirements are high and you want to protect against active attacks, such as those described in [Bell96]. This paper also gives a good overview over the risks and open security problems that need to be taken into considera- tion. 6. Implementation Details -------------------------- 6.1. Summary of Limits ----------------------- In the following table we show up to three values or ranges for every variable: the minimum supported number (what each implementation MUST support), some recommended values (what implementatios SHOULD use), and a maximum that MUST NOT be exceeded. The column ``Who'' indicates Caronni, Waldvogel [Page 8] INTERNET-DRAFT ESP Stream Transform March 1996 whether the sender (S) or the recipient (R) or both need to support these limits. Values are given in bytes, except where otherwise noted. Name Who Minimum Recommended Maximum (MUST) (SHOULD) Key length (bits) SR 128 128 .. 2048 2048 Initial forward seek S 0 16 .. 1024 64K Initial forward seek R 64K Forward seek per packet R 32K .. 200K 512K Backward history R 16K .. 100K State cache entries per key R 4 .. 16 Notes ----- Key length indicates the number of bits that an implementation must support, altough the use of shorter keys may be required in certain cir- cumstances. Initial forward seek indicates the number of bytes the sender should seek forward before encrypting the first packet. The receiver must accept a packet encrypted with a new key with Stream Offsets going up to the value of ``initial forward seek''. Be aware that the first packet encrypted with the new key can get lost, so that senders can not exploit the full limit on ``initial forward seek'' that receivers have. Forward seek per packet indicates the amount of bytes that the receivers allows the Stream Offset of two succeeding packets to be apart, thus restricting the amount of forward or backward seeking that may be performed. Oth- erwise, a denial of service attack could be easily mounted by forc- ing the receiver to do exhaustive seeking in the cipher key stream. Backward history indicates the amount of past bytes for which the receiver should be able to reconstruct the internal state of any ``hole'' (needed for out of order delivery). State cache entries per key is the recommended number of previous internal states a receiver should keep. Under normal circumstances this is enough to provide good coverage of swapped and delayed packets. Caronni, Waldvogel [Page 9] INTERNET-DRAFT ESP Stream Transform March 1996 6.2. Technical Notes --------------------- To prevent getting a blocked channel whenever packets are received out of order, receivers SHOULD maintain multiple internal states for the stream cipher, and handle these conditions gracefully. It is also suggested, that the stream cipher is rekeyed frequently (after short amounts of elapsed time) so that connections can easily recover after excessive blocks of data have been lost. Otherwise the limit on forward seeking at the receiving end might block the connec- tion. Seeking forward by n bytes in the cipher keystream is identical to encrypting that many dummy bytes. Forward seeks may be optimized by creating a dedicated procedure which only implements the relevant parts of the algorithm. Sophisticated solutions may want to add the capability for backward seeking in algorithms where this is possible (such as RC4), and can then use the nearest stored state to seek to the needed posi- tion. When algorithms (such as SEAL) are used, where the current posi- tion in the stream can be set, use of this functionality is stronlgy encouraged. 7. Acknowledgements -------------------- The authors would like to thank Ran Atkinson for his helpful comments and the authors of RFCs 1826, 1828, and 1851, from which many ideas were used. Special thanks go to Christian Schneider and Michael Hauber for incorporating stream cipher support into ENskip and the extensive evaluation of replay protection. The SKIP team at SUN-ICG (Ashar Aziz, Tom Markson, Martin Patterson and Josef Reveane) originally suggested the use of RC4 in the early SKIP drafts, and proved to be an extremly valuable partner in interoperabil- ity tests during public forums. We express our gratitude to Ron Rivest for pointing out legal aspects relating to our original 'alleged RC4' draft, and, nevertheless, for devising such a simple and elegant cipher such as RC4. 8. References -------------- Bell96 S. Bellovin, "Problem Areas for the IP Security Protocols", sub- mitted to the Sixth USENIX Unix Security Conference, draft available from ftp://ftp.research.att.com/dist/smb/badesp.ps. Caronni, Waldvogel [Page 10] INTERNET-DRAFT ESP Stream Transform March 1996 RFC1700 J. Reynolds, J. Postel, "ASSIGNED NUMBERS", 10/20/1994, RFC 1700. RFC1750 D. Eastlake, S. Crocker, J. Schiller, "Randomness Recommenda- tions for Security", 12/29/1994, RFC 1750. RFC1810 J. Touch, "Report on MD5 Performance", 06/21/1995, RFC 1810. RFC1825 R. Atkinson, "Security Architecture for the Internet Protocol", 08/09/1995, RFC 1825. RFC1826 R. Atkinson, "IP Authentication Header", 08/09/1995, RFC 1826. RFC1827 R. Atkinson, "IP Encapsulating Security Payload (ESP)", 08/09/1995, RFC 1827. RFC1828 P. Metzger, W. Simpson, "IP Authentication using Keyed MD5", 08/09/1995, RFC 1828. RFC1851 P. Metzger, P. Karn, W. Simpson, "The ESP Triple DES-CBC Transform", 10/02/1995, RFC 1851. Roos95 A. Roos , "Weak Keys in RC4", Posted to sci.crypt on Sep 22, 1995, archived in e.g. http://www.tik.ee.ethz.ch/~mwa/RC4/WeakKeys.txt Schn96 B. Schneier, "Applied Cryptography: Protcols, Algorithms, and Source Code in C (second edition)", John Wiley & Sons, New York, 1996. 9. Author addresses -------------------- Questions and comments about this memo can be directed to: Germano Caronni Computer Engineering and Networks Laboratory Swiss Federal Institute of Technology (ETH) ETH Zentrum CH-8092 Zurich caronni@tik.ee.ethz.ch, OR gec@acm.org Marcel Waldvogel Computer Engineering and Networks Laboratory Swiss Federal Institute of Technology (ETH) ETH Zentrum CH-8092 Zurich Caronni, Waldvogel [Page 11] INTERNET-DRAFT ESP Stream Transform March 1996 waldvogel@tik.ee.ethz.ch Caronni, Waldvogel [Page 12]