Network Working Group P Karn Internet Draft [Qualcomm] P Metzger [Piermont] W A Simpson [DayDreamer] expires in six months May 1997 The ESP DES-CBC Transform draft-simpson-esp-des1-v2-00.txt Status of this Memo This document is an Internet-Draft. Internet Drafts are working doc- uments of the Internet Engineering Task Force (IETF), its Areas, and its Working Groups. Note that other groups may also distribute work- ing 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 not appropriate to use Internet Drafts as refer- ence material, or to cite them other than as a ``working draft'' or ``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) ds.internic.net (US East Coast) ftp.isi.edu (US West Coast) munnari.oz.au (Pacific Rim) Distribution of this memo is unlimited. Abstract This document describes the DES-CBC security transform for the IP Encapsulating Security Payload (ESP). Karn, Metzger & Simpson expires in six months [Page i] DRAFT ESP DES-CBC May 1997 1. Introduction The Encapsulating Security Payload (ESP) [RFC-1827] provides confi- dentiality for IP datagrams by encrypting the payload data to be pro- tected. This specification describes the ESP use of the Cipher Block Chaining (CBC) mode of the US Data Encryption Standard (DES) algo- rithm [FIPS-46, FIPS-46-1, FIPS-74, FIPS-81]. All implementations that claim conformance or compliance with the Encapsulating Security Payload specification MUST implement this DES- CBC transform. This document assumes that the reader is familiar with the related document "Security Architecture for the Internet Protocol" [RFC-1825], that defines the overall security plan for IP, and pro- vides important background for this specification. In this document, the key words "MUST, "MUST NOT", "optional", "rec- ommended", "SHOULD", and "SHOULD NOT", are to be interpreted as described in [RFC-2119]. 1.1. Algorithm and Mode P1 P2 Pi | | | IV->->(X) +>->->->(X) +>->->->(X) v ^ v ^ v +-----+ | +-----+ | +-----+ k->| Ek | ^ k->| Ek | ^ k->| Ek | +-----+ | +-----+ | +-----+ | ^ | ^ | +>->->+ +>->->+ +>->-> | | | C1 C2 Ci In DES-CBC, an Initialization Vector (IV) is XOR'd with the first 64-bit (8 octet) plaintext block (P1). The keyed DES encryption function (Ek) generates the ciphertext (C1) for the block. For successive blocks, the previous ciphertext block is XOR'd with the current plaintext (Pi). The keyed DES encryption function (Ek) generates the ciphertext (Ci) for that block. The Cipher Block Chaining (CBC) method provides for re- synchronization when datagrams are lost. For more explanation and implementation information for DES, see [Schneier95]. Karn, Metzger & Simpson expires in six months [Page 1] DRAFT ESP DES-CBC May 1997 1.2. Keys The secret DES key shared between the communicating parties is 56-bits in length. The 56-bit key is stored as a 64-bit (8 octet) quantity, with the least significant bit of each octet used as a par- ity bit. 1.2.1. Weak Keys DES has 64 known weak keys, including so-called semi-weak keys and possibly weak keys [Schneier95, pp 280-282]. Implementations SHOULD take care not to select weak keys [CN94], although the odds of pick- ing one at random are low. When manually configured, these 64 keys SHOULD be be rejected. When dynamically configured via a key management protocol, any of these 64 keys MUST be rejected, and a replacement key requested. 1.2.2. Key Management When manually configured, 64-bits (8 octets) are configured. Keys with incorrect parity SHOULD be be rejected. When dynamically configured via a key management protocol, 64-bits (8 octets) are returned for each key. The least significant bit of each key octet is ignored (or set to parity when the implementation requires). 1.3. Initialization Vector This mode of DES requires an Initialization Vector (IV) that is 64-bits (8 octets) in length. Each datagram contains its own IV. This IV is intended to be unique for the lifetime of the secret DES session-key. When manually configured, the 64-bit IV is generated from the 32-bit Sequence Number field followed by (concatenated with) the bit-wise complement of the same 32-bit value. When dynamically configured via a key management protocol, the 64-bit IV is generated from the 32-bit SPI field followed by (concatenated with) the 32-bit Sequence Number field. The bit-wise complement of the 32-bit Sequence Number value is XOR'd with the first 32-bits Karn, Metzger & Simpson expires in six months [Page 2] DRAFT ESP DES-CBC May 1997 (SPI). Security Notes: Including the IV in each datagram ensures that decryption of each received datagram can be performed, even when some datagrams are dropped, or datagrams are re-ordered in transit. The manually configured variant is required for backward compati- bility. It is appropriate when the associated SPI is unchanging. However, in a dynamic environment, the same data stream might be sent with more than one SPI. Including the changed SPI in the IV generation prevents analysis based on common leading blocks. Using the Sequence Number provides an easy method for preventing IV repetition, and is sufficiently robust for practical use with the DES algorithm. But, when used alone, cryptanalysis might be aided by the rare serendipitous occurrence where a corresponding bit position in the first DES block increments in exactly the same fashion as the Sequence Number. No commonly used IP Protocol/Payloads exhibit this property. Never-the-less, inclusion of the bit-wise complement ensures that Sequence Number bit changes are reflected twice in the IV. 1.4. Block Size The DES algorithm operates on blocks of 64-bits (8 octets). This often requires padding after the end of the unencrypted payload data. Both input and output result in the same number of octets. This facilitates in-place encryption and decryption. 1.5. Performance Phil Karn has tuned DES software to achieve 10.45 Mbps with a 90 MHz Pentium, scaling to 15.9 Mbps with a 133 MHz Pentium. Other DES speed estimates may be found at [Schneier95, page 279]. Karn, Metzger & Simpson expires in six months [Page 3] DRAFT ESP DES-CBC May 1997 2. Payload Format +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security Parameters Index (SPI) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Payload Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Padding | Pad Length | Payload Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Authenticator (optional) ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Security Parameters Index (SPI) 4 octets. Identifies the Security Parameters for this datagram. The value MUST NOT be zero. Sequence Number 4 octets. Provides replay prevention [RFC-yyyy], and is used for calculating the IV, as described earlier. The value begins at one, unless another value is specified by the key management mechanism. The value SHOULD NOT repeat during the lifetime of the encryption session-key. This means that the session-key SHOULD be changed at least as frequently as 2**32 datagrams. Payload Data one or more octets. Prior to encryption and after decryption, this field begins with the IP Protocol/Payload header specified in the Payload Type field. Note that in the case of IP-in-IP encapsulation (Payload Type 4), this will be another IP header. Padding zero or more octets. Prior to encryption, this field is filled with a series of integer values (beginning with zero), to align the Pad Length and Payload Type fields at the Karn, Metzger & Simpson expires in six months [Page 4] DRAFT ESP DES-CBC May 1997 end of an eight octet boundary (counted from the beginning of the Payload Data). After decryption, it is examined for a valid series of integer values. This field is opaque. That is, the value is set prior to encryption, and is examined only after decryption. Pad Length 1 octet. Indicates the size of the Padding field. It does not include the Pad Length and Payload Type fields. The value typically ranges from 0 to 7, but may be up to 255 to permit hiding of the actual data length. This field is opaque. That is, the value is set prior to encryption, and is examined only after decryption. Payload Type 1 octet. Indicates the contents of the Payload Data field, using the IP Protocol/Payload value. Up-to- date values of the IP Protocol/Payload are specified in the most recent "Assigned Numbers" [RFC-1700]. This field is opaque. That is, the value is set prior to encryption, and is examined only after decryption. For example, when encrypting an entire IP datagram (Tunnel-Mode), this field will contain the value 4, indicating IP-in-IP encapsulation. Authenticator zero or more octets. This optional variable-length field contains an Integrity Check Value (ICV) computed over the ESP data after encryption, beginning with the SPI and ending with the Payload Type. The length of the field depends upon the authentication function selected. DES-CBC does not provide integrity. When the ESP data is not otherwise verified (externally using AH or internally by the payload itself), it is recom- mended (but not required) that an ICV be provided here. The details of such functions are outside the scope of this document. Karn, Metzger & Simpson expires in six months [Page 5] DRAFT ESP DES-CBC May 1997 2.1. Encryption Perform compression of the plaintext (when configured). Append zero or more octets of padding to the plaintext, to make its modulo 8 length equal to 6. The padding values begin with the value 0, and count up to the number of padding octets (zero relative). Append a Pad Length octet containing the number of padding octets just added. For example, if the plaintext length is 41, the padding values are 0, 1, 2, 3, 4, and the following Pad Length is 5. Append a Payload Type octet containing the IP Protocol/Payload value which identifies the protocol header that begins the payload. Provide an Initialization Vector (IV) of the form indicated by the SPI. Encrypt the payload with DES in CBC mode, producing a ciphertext of the same length. Octets are mapped to DES blocks in network order (most significant octet first) [RFC-1700]. Octet 0 (modulo 8) of the payload corre- sponds to bits 1-8 of the 64-bit DES input block, while octet 7 (modulo 8) corresponds to bits 57-64 of the DES input block. When configured, calculate and append the optional Authenticator. Construct an appropriate IP datagram for the target Destination, with the indicated SPI, Sequence Number, and payload. The Total/Payload Length in the encapsulating IP Header reflects the length of the encrypted data, plus the SPI, Sequence Number, padding, Pad Length, Payload Type, and optional Authenticator octets. 2.2. Decryption The SPI field is removed and examined. This is used as an index into the local Security Parameter table to find the negotiated parameters and decryption key. If the SPI is invalid, then the payload is dis- carded, and the "Bad SPI" error is indicated [RFC-xxxx]. The Sequence Number field is removed and examined, and an appropriate 64-bit IV value is constructed. Karn, Metzger & Simpson expires in six months [Page 6] DRAFT ESP DES-CBC May 1997 When present, remove and verify the optional Authenticator. If the Authenticator is invalid, then the payload is discarded, and the "Authentication Failed" error is indicated [RFC-xxxx]. If the length of the data to be decrypted is not an integral multiple of eight octets, then the payload is discarded, and the "Decryption Failed" error is indicated [RFC-xxxx]. The encrypted part of the payload is decrypted using DES in the CBC mode. The Payload Type is removed and examined. If it is unrecognized, then the payload is discarded, and the "Decryption Failed" error is indicated [RFC-xxxx]. The Pad Length is removed and examined. If pad checking is config- ured, and the padding octets are not the correct values for the Pad Length, then the payload is discarded, and the "Decryption Failed" error is indicated [RFC-xxxx]. The specified number of pad octets are removed from the end of the decrypted payload, and the IP Total/Payload Length is adjusted accordingly. Perform decompression of the plaintext (when configured). If it is invalid, then the payload is discarded, and the "Decompression Failed" error is indicated [RFC-xxxx]. The IP Header(s) and the remaining portion of the decrypted payload are passed to the protocol processing routine specified by the Pay- load Type field. Operational Considerations When used with manual keying, the specification provides only a few configurable parameters. SPI Configured SPIs are in the range 1 to 255. SPI LifeTime (SPILT) Manually configured LifeTimes are generally measured in days, while dynamic LifeTimes are specified in seconds. Default: 2,764,800 seconds (32 days). Maximum: implementation dependent. Karn, Metzger & Simpson expires in six months [Page 7] DRAFT ESP DES-CBC May 1997 Pad Check Some earlier implementations used random pad values. Default: Off. Key The 56-bit key is configured as a 64-bit quantity, with appropri- ate parity included. Each party configures a list of known SPIs and symmetric secret-keys. In addition, each party configures local policy that determines what access (if any) is granted to the holder of a particular SPI. For example, a party might allow FTP, but prohibit Telnet. Such consid- erations are outside the scope of this document. Security Considerations Users need to understand that the quality of the security provided by this specification depends completely on the strength of the DES algorithm, the correctness of that algorithm's implementation, the security of the key management mechanism and its implementation, the strength of the key [CN94], and upon the correctness of the implemen- tations in all of the participating nodes. The cut and paste splicing attack described by [Bell95, Bell96] exploits the nature of all Cipher Block Chaining algorithms. When a block is damaged in transmission, on decryption both it and the fol- lowing block will be garbled by the decryption process, but all sub- sequent blocks will be decrypted correctly. If an attacker has legitimate access to the same key, this feature can be used to insert or replay previously encrypted data of other users of the same engine, revealing the plaintext. The usual (ICMP, TCP, UDP) trans- port checksum can detect this attack, but on its own is not consid- ered cryptographically strong. In this situation, user or connection oriented integrity checking is needed [RFC-1826]. The padding bytes have a predictable value. They provide a small measure of tamper detection on their own block and the previous block in CBC mode. This makes it somewhat harder to perform splicing attacks, and avoids a possible covert channel. This small amount of known plaintext does not create any problems for modern ciphers. At the time of writing of this document, [BS93] demonstrated a dif- ferential cryptanalysis based chosen-plaintext attack requiring 2^47 plaintext-ciphertext pairs, and [Matsui94] demonstrated a linear Karn, Metzger & Simpson expires in six months [Page 8] DRAFT ESP DES-CBC May 1997 cryptanalysis based known-plaintext attack requiring only 2^43 plain- text-ciphertext pairs. Although these attacks are not considered practical, they must be taken into account. More disturbingly, [Weiner94] has shown the design of a DES cracking machine costing $1 Million that can crack one key every 3.5 hours. This is an extremely practical attack. One or two blocks of known plaintext suffice to recover a DES key. Because IP datagrams typically begin with a block of known and/or guessable header text, frequent key changes will not protect against this attack. It is suggested that DES is not a good encryption algorithm for the protection of even moderate value information in the face of such equipment. Triple DES is probably a better choice for such purposes. However, despite these potential risks, the level of privacy provided by use of ESP DES-CBC in the Internet environment is far greater than sending the datagram as cleartext. Change History Changes from RFC-1829: Additional explanation of IV calculation. Inclusion of SPI in IV calculation improves IV uniqueness over multiple sessions. Updated performance estimates. IV field renamed to Sequence. Only one size is supported. Padding is a known series of integers, and is checked upon receipt. Added compression steps. Added authentication steps. Added operational parameters section. Updated references. Updated contacts. Minor editorial changes. Karn, Metzger & Simpson expires in six months [Page 9] DRAFT ESP DES-CBC May 1997 Acknowledgements The basic field naming and layout is based on "swIPe" [IBK93, IB93]. Participants in the IP Security Working Group modified this to a variable number of variable length fields. After a digression span- ning 4 years, actual implementors mandated a return to these fewer well-known fields. Some of the text of this specification was derived from work by Ran- dall Atkinson for the SIP, SIPP, and IPv6 Working Groups. Phil Karn provided the original Encryption and Decryption text, and was the motivator and founding member of the IP Security Working Group. Perry Metzger provided the original Security Considerations text, some of which is distributed throughout the document. William Allen Simpson was responsible for the name and semantics of the SPI, the IV calculation technique(s), editing and formatting. The use of known padding values was suggested in various forms by Robert Baldwin, Phil Karn, and David Wagner. This specification uses Self-Describing-Padding [RFC-1570]. Steve Bellovin, Steve Deering, Karl Fox, Charles Lynn, Craig Metz, Dave Mihelcic and Jeffrey Schiller provided useful critiques of ear- lier versions of this draft. References [Bell95] Bellovin, S., "An Issue With DES-CBC When Used Without Strong Integrity", Presentation at the 32nd Internet Engi- neering Task Force, Danvers Massachusetts, April 1995. [Bell96] Bellovin, S., "Problem Areas for the IP Security Protocols", Proceedings of the Sixth Usenix Security Symposium, July 1996. [BS93] Biham, E., and Shamir, A., "Differential Cryptanalysis of the Data Encryption Standard", Berlin: Springer-Verlag, 1993. [CN94] Carroll, J.M., and Nudiati, S., "On Weak Keys and Weak Data: Foiling the Two Nemeses", Cryptologia, Vol. 18 No. 23 pp. 253-280, July 1994. Karn, Metzger & Simpson expires in six months [Page 10] DRAFT ESP DES-CBC May 1997 [FIPS-46] US National Bureau of Standards, "Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 46, January 1977. [FIPS-46-1] US National Bureau of Standards, "Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 46-1, January 1988. [FIPS-74] US National Bureau of Standards, "Guidelines for Implement- ing and Using the Data Encryption Standard", Federal Infor- mation Processing Standard (FIPS) Publication 74, April 1981. [FIPS-81] US National Bureau of Standards, "DES Modes of Operation" Federal Information Processing Standard (FIPS) Publication 81, December 1980. [IB93] Ioannidis, J., and Blaze, M., "The Architecture and Imple- mentation of Network-Layer Security Under Unix", Proceedings of the Fourth Usenix Security Symposium, Santa Clara Cali- fornia, October 1993. [IBK93] Ioannidis, J., Blaze, M., and Karn, P., "swIPe: Network- Layer Security for IP", Presentation at the 26th Internet Engineering Task Force, Columbus Ohio, March 1993. [Matsui94] Matsui, M., "Linear Cryptanalysis method dor DES Cipher," Advances in Cryptology -- Eurocrypt '93 Proceedings, Berlin: Springer-Verlag, 1994. [RFC-1570] Simpson, W., "PPP LCP Extensions", DayDreamer, January 1994. [RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers", STD 2, RFC 1700, USC/Information Sciences Institute, October 1994. [RFC-1825] Atkinson, R., "Security Architecture for the Internet Proto- col", RFC-1825, Naval Research Laboratory, July 1995. [RFC-1826] Atkinson, R., "IP Authentication Header", RFC-1826, Naval Karn, Metzger & Simpson expires in six months [Page 11] DRAFT ESP DES-CBC May 1997 Research Laboratory, July 1995. [RFC-1827] Atkinson, R., "IP Encapsulating Security Protocol (ESP)", RFC-1827, Naval Research Laboratory, July 1995. [RFC-2119] Bradner, S., "Key words for use in RFCs to Indicate Require- ment Levels", BCP 14, Harvard University, March 1997. [RFC-xxxx] Karn, P., and Simpson, W., "ICMP Security Failures Mes- sages", draft-simpson-icmp-ipsec-fail-02.txt, work in progress. [RFC-yyyy] Simpson, W., and Wagner, D., "Internet Security Transform Enhancements", draft-simpson-ipsec-enhancement-01.txt, work in progress. [Schneier95] Schneier, B., "Applied Cryptography Second Edition", John Wiley & Sons, New York, NY, 1995. ISBN 0-471-12845-7. [Weiner94] Wiener, M.J., "Efficient DES Key Search", School of Computer Science, Carleton University, Ottawa, Canada, TR-244, May 1994. Presented at the Rump Session of Crypto '93. Karn, Metzger & Simpson expires in six months [Page 12] DRAFT ESP DES-CBC May 1997 Contacts Comments about this document should be discussed on the ipsec@tis.com mailing list. Questions about this document can also be directed to: Phil Karn Qualcomm, Inc. 6455 Lusk Blvd. San Diego, California 92121-2779 karn@qualcomm.com karn@unix.ka9q.ampr.org (preferred) Perry Metzger Piermont Information Systems Inc. 160 Cabrini Blvd., Suite #2 New York, NY 10033 perry@piermont.com William Allen Simpson DayDreamer Computer Systems Consulting Services 1384 Fontaine Madison Heights, Michigan 48071 wsimpson@UMich.edu wsimpson@GreenDragon.com (preferred) bsimpson@MorningStar.com Karn, Metzger & Simpson expires in six months [Page 13]