Network Working Group P Karn Internet Draft Qualcomm P Metzger Piermont W A Simpson Daydreamer expires in six months April 1996 The ESP Triple DES Transform draft-simpson-esp-des3-x-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 Triple DES-CBC security transform for the IP Encapsulating Security Payload (ESP). Karn, Metzger & Simpson expires in six months [Page i] DRAFT ESP 3DES-CBC April 1996 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 a variant of of the Cipher Block Chaining (CBC) mode of the US Data Encryption Stan- dard (DES) algorithm [FIPS-46, FIPS-46-1, FIPS-74, FIPS-81]. This variant, known as Triple DES (3DES), processes each block of the plaintext three times, each time with a different key [Tuchman79]. 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. 1.1. Keys The secret 3DES key shared between the communicating parties is effectively 168-bits long. This key consists of three independent 56-bit quantities used by the DES algorithm. Each of the three 56-bit subkeys is stored as a 64-bit (8 octet) quantity, with the least significant bit of each octet used as a parity bit. In addition, when "whitening" is indicated by the key management mechanism, some additional 64-bit (8 octet) keys are needed. See [RFC-yyyy] for details. 1.2. Initialization Vector This mode of 3DES requires an Initialization Vector (IV) that is 64-bits (8 octets) in length. Each datagram contains its own IV. Including the IV in each datagram ensures that decryption of each received datagram can be performed, even when other datagrams are dropped, or datagrams are re-ordered in transit. This IV is intended to be unique for the lifetime of the secret 3DES session-key. The 64-bit IV is generated from the 32-bit SPI field followed by (concatenated with) the 32-bit Sequence field. The bit-wise comple- ment of the 32-bit Sequence value is XOR'd with the first 32-bits (SPI). Implementation Notes: Karn, Metzger & Simpson expires in six months [Page 1] DRAFT ESP 3DES-CBC April 1996 The method for selection of Sequence values is implementation dependent. A common acceptable technique is simply a counter, beginning with either the value one or a randomly chosen value. While this pro- vides an easy method for preventing repetition, and is suffi- ciently robust for practical use, cryptanalysis might use the rare serendipitous occurrence when a corresponding bit position in the first DES block increments in exactly the same fashion. No commonly used IP Protocol/Payloads exhibit this property. Never-the-less, the bit-wise complement and XOR ensure that any bit changes are reflected twice in the resulting IV. Other implementations exhibit unpredictability, usually through a pseudo-random number generator. Care should be taken that the periodicity of the number generator is long enough to prevent rep- etition during the lifetime of the session key. 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. 1.3. Data Size The 3DES 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.4. Performance As this specification requires "outer" chaining, it is not possible to provide parallel computation for the same data stream. Phil Karn has tuned "single" DES software to achieve 10.45 Mbps with a 90 MHz Pentium. Triple DES is approximately 2.5 times slower. Other DES speed estimates may be found at [Schneier95, page 279]. Karn, Metzger & Simpson expires in six months [Page 2] DRAFT ESP 3DES-CBC April 1996 2. Payload Format +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security Parameters Index (SPI) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Payload Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Padding | Pad Length | Payload Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Security Parameters Index (SPI) 4 octets. Identifies the Security Parameters for this datagram. The value MUST NOT be zero. Sequence 4 octets. Provides replay prevention [RFC-yyyy], and is used for calculating the IV, as described earlier. 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 an eight octet boundary. 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 Karn, Metzger & Simpson expires in six months [Page 3] DRAFT ESP 3DES-CBC April 1996 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. Karn, Metzger & Simpson expires in six months [Page 4] DRAFT ESP 3DES-CBC April 1996 3. Algorithm The 3DES-CBC algorithm is a simple variant on the DES-CBC algorithm. The DES function is interated three times, an encryption followed by a decryption followed by an encryption. Each iteration uses an inde- pendant key, k1, k2 and k3. The "outer" CBC method is used to chain to the next block. Note that when all three keys (k1, k2 and k3) are the same, 3DES-CBC is equivalent to DES-CBC. This property allows the 3DES hardware implementations to operate in DES mode without modification. For more explanation and implementation information for Triple DES, see [Schneier95]. 3.1. Encryption 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 Triple DES (EDE mode), producing a cipher- text 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. Construct an appropriate IP datagram for the target Destination, with the indicated SPI, IV, and payload. The Total/Payload Length in the encapsulating IP Header reflects the length of the encrypted data, plus the SPI, IV, padding, Pad Length, and Payload Type octets. Karn, Metzger & Simpson expires in six months [Page 5] DRAFT ESP 3DES-CBC April 1996 3.2. Decryption First, 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. The negotiated form of the IV determines the size of the IV field. These octets are removed, and an appropriate 64-bit IV value is con- structed. If the length of the data to be decrypted is not an integral multiple of eight octets, then the payload is discarded, and a "Decryption Failed" error is indicated, as described in [RFC-xxxx]. The encrypted part of the payload is decrypted using Triple DES (DED mode). The Payload Type is removed and examined. If it is unrecognized, then the payload is discarded, and a "Decryption Failed" error is indicated, as described in [RFC-xxxx]. The Pad Length is removed and examined. If the padding octets are not the correct values for the Pad Length, then the payload is dis- carded, and a "Decryption Failed" error is indicated, as described in [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. 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. A. Changes Changes from RFC-1851: IV calculation inclusion of SPI eliminates complementation, and improves IV uniqueness over multiple sessions. Additional explana- tion of IV calculation. Replaced erroneous text about parallel computation. Updated performance estimates. IV field renamed to Sequence. Only one size is supported. Karn, Metzger & Simpson expires in six months [Page 6] DRAFT ESP 3DES-CBC April 1996 Clarified to use "outer" CBC, as originally intended. Padding is a known series of integers, and is checked upon receipt. Updated references. Updated contacts. Minor editorial changes. Security Considerations Users need to understand that the quality of the security provided by this specification depends completely on the strength of the Triple 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 implementations in all of the participating nodes. Among other considerations, applications may wish to take care not to select weak keys for any of the three DES rounds, although the odds of picking one at random are low [Schneier95, page 281]. It was originally thought that DES might be a group, but it has been demonstrated that it is not [CW92]. Since DES is not a group, compo- sition of multiple rounds of DES is not equivalent to simply using DES with a different key. Triple DES with independent keys is not, as naively might be expected, as difficult to break by brute force as a cryptosystem with three times the keylength. A space/time tradeoff has been shown which can brute-force break triple block encryptions in the time naively expected for double encryption [MH81]. However, 2DES can be broken with a meet-in-the-middle attack, without significantly more complexity than breaking DES requires [ibid], so 3DES with independant keys is actually needed to provide this level of security. An attack on 3DES using two independent keys that is somewhat (sixteen times) faster than any known for independent keys has been shown [OW91]. The cut and paste splicing attack described by [Bell95] exploits the nature of all Cipher Block Chaining algorithms. When a block is dam- aged in transmission, on decryption both it and the following block will be garbled by the decryption process, but all subsequent 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 Karn, Metzger & Simpson expires in six months [Page 7] DRAFT ESP 3DES-CBC April 1996 encrypted data of other users of the same engine, revealing the plaintext. The usual (ICMP, TCP, UDP) transport checksum can detect this attack, but on its own is not considered 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. Although it is widely believed that 3DES is substantially stronger than DES, as it is less amenable to brute force attack, it should be noted that real cryptanalysis of 3DES might not use brute force meth- ods at all. Instead, it might be performed using variants on differ- ential [BS93] or linear [Matsui94] cryptanalysis. It should also be noted that no encryption algorithm is permanently safe from brute force attack, because of the increasing speed of modern computers. As with all cryptosystems, those responsible for applications with substantial risk when security is breeched should pay close attention to developments in cryptography, and especially cryptanalysis, and switch to other transforms should 3DES prove weak. Acknowledgements Some of the text of this specification was derived from work by Ran- dall Atkinson for the SIP, SIPP, and IPv6 Working Groups. The use of known padding values was suggested in various forms by Robert Baldwin, Phil Karn, and David Wagner. References [Bell95] Bellovin, S., "An Issue With DES-CBC When Used Without Strong Integrity", Proceedings of the 32nd IETF, Danvers, MA, April 1995. [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 8] DRAFT ESP 3DES-CBC April 1996 [CW92] Campbell, K.W., and Wiener, M.J., "Proof that DES Is Not a Group", Advances in Cryptology -- Crypto '92 Proceedings, Berlin: Springer-Verlag, 1993, pp 518-526. [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. [Matsui94] Matsui, M., "Linear Cryptanalysis method dor DES Cipher," Advances in Cryptology -- Eurocrypt '93 Proceedings, Berlin: Springer-Verlag, 1994. [MH81] Merkle, R.C., and Hellman, M., "On the Security of Multiple Encryption", Communications of the ACM, v. 24 n. 7, 1981, pp. 465-467. [OW91] van Oorschot, P.C., and Weiner, M.J. "A Known-Plaintext Attack on Two-Key Triple Encryption", Advances in Cryptology -- Eurocrypt '90 Proceedings, Berlin: Springer-Verlag, 1991, pp. 318-325. [RFC-1610] Postel, J., "Internet Official Protocol Standards", STD 1, RFC 1610, USC/Information Sciences Institute, July 1994. [RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers", STD 2, RFC 1700, USC/Information Sciences Institute, October 1994. Karn, Metzger & Simpson expires in six months [Page 9] DRAFT ESP 3DES-CBC April 1996 [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 Research Laboratory, July 1995. [RFC-1827] Atkinson, R., "IP Encapsulating Security Protocol (ESP)", RFC-1827, Naval Research Laboratory, July 1995. [RFC-xxxx] Karn, P., and Simpson, W., "ICMP Security Failures Messages", 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-00.txt, work in progress. [Schneier95] Schneier, B., "Applied Cryptography Second Edition", John Wiley & Sons, New York, NY, 1995. ISBN 0-471-12845-7. [Tuchman79] Tuchman, W, "Hellman Presents No Shortcut Solutions to DES", IEEE Spectrum, v. 16 n. 7, July 1979, pp. 40-41. Contacts Comments about this document should be discussed on the ipsec- dev@terisa.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@unix.ka9q.ampr.org Karn, Metzger & Simpson expires in six months [Page 10] DRAFT ESP 3DES-CBC April 1996 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 11]