Network Working Group P Karn Internet Draft Qualcomm P Metzger Piermont W A Simpson Daydreamer expires in six months December 1995 The ESP DES-CBC plus MD5 Transform draft-simpson-esp-des1md5-00.txt Status of this Memo This document is a submission to the IP Security Working Group of the Internet Engineering Task Force (IETF). Comments should be submitted to the ipsec@ans.net mailing list. Distribution of this memo is unlimited. 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) Karn, Metzger & Simpson expires in six months [Page i] DRAFT ESP DES-CBC-MD5 December 1995 Abstract This document describes use of DES-CBC for privacy, plus MD5 for integrity, in the IP Encapsulating Security Payload (ESP). Karn, Metzger & Simpson expires in six months [Page ii] DRAFT ESP DES-CBC-MD5 December 1995 1. Introduction The Encapsulating Security Payload (ESP) [RFC-1827] provides confi- dentiality for IP datagrams by encrypting the payload data to be pro- tected. Some transforms may also provide integrity. This specification describes the ESP use of the Cipher Block Chaining (CBC) mode of the US Data Encryption Standard (DES) algorithm [FIPS-46, FIPS-46-1, FIPS-74, FIPS-81], together with Message Digest 5 (MD5) [RFC-1321]. The usual combination of ESP and AH [RFC-1826] can do this task just as well. The primary benefit of this transform is that it saves 4 octets. 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 There are two keys used by this transform. The secret DES key shared between the communicating parties is eight octets (64-bits) in length. This key consists of a 56-bit quantity used by the DES algorithm. The 56-bit key is stored as a 64-bit quantity, with the least significant bit of each octet used as a par- ity bit. The secret MD5 key shared between the communicating parties SHOULD be a cryptographically strong random number, not a guessable string of any sort. The MD5 key is not constrained by this transform to any particular size. Lengths of up to 128-bits MUST be supported by the implementa- tion, although any particular key may be shorter. Longer keys are encouraged. Implementation Notes: It is recommended that the two keys be unrelated, to prevent attacks exploiting mathematical relationships between the differ- ent algorithms that might reveal some portion of the session- key(s). Never-the-less, there is no known interaction between MD5 and DES-CBC. Karn, Metzger & Simpson expires in six months [Page 1] DRAFT ESP DES-CBC-MD5 December 1995 1.2. Initialization Vector This mode of DES requires an Initialization Vector (IV) that is eight octets (64-bits) 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. The SPI is used for the most significant four octets of the IV. The method for selection of the least significant four octets of the IV is implementation dependent. Then, this IV is hashed before use. The MD5 hash is calculated over the following concatenated values: + the DES key (8 octets including parity bits), + the SPI (4 octets), + the IV (4 octets), + the MD5 key (variable length). The most significant 64-bits of the generated hash are used for the final IV. Implementation Notes: A common technique for the least significant four octets of the IV is simply a counter, beginning with a randomly chosen value. This provides an easy method for preventing repetition, and is suffi- ciently robust for practical use. 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. 1.3. Data Size The DES algorithm operates on blocks of eight octets (64-bits). 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. MD5's 128-bit output is naturally 64-bit aligned. There is no fur- ther padding of the Authentication Data field. Karn, Metzger & Simpson expires in six months [Page 2] DRAFT ESP DES-CBC-MD5 December 1995 On receipt, if the length of the data to be decrypted is not an inte- gral multiple of eight octets, then an error is indicated, as described in [RFC-1825]. 1.4. Performance In general, DES software speeds are considerably slower than MD5 software, while DES hardware is considerably faster than MD5 hard- ware. MD5 software speeds are adequate for commonly deployed LAN and WAN links, but reportedly are too slow for newer link technologies [RFC-1810]. One of the authors (Karn) has tuned DES software to achieve 10.45 Mbps with a 90 MHz Pentium. Other DES speed estimates may be found at [Schneier95, p 279]. Karn, Metzger & Simpson expires in six months [Page 3] DRAFT ESP DES-CBC-MD5 December 1995 2. Payload Format +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security Parameters Index (SPI) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Initialization Vector (IV) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Payload Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... Padding | Pad Length | Payload Type | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ Authentication Data ~ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Security Parameters Index (SPI) 4 octets. Identifies the Security Parameters for this datagram. The value MUST NOT be zero. Initialization Vector (IV) 4 octets. Provides a seed for calculating the final IV, as described earlier. Payload Data variable. 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 variable. Prior to encryption, it is filled with unspecified implementation dependent (preferably random) values, to align the Pad Length and Payload Type fields at an eight octet boundary. After decryption, it MUST be ignored. 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 Karn, Metzger & Simpson expires in six months [Page 4] DRAFT ESP DES-CBC-MD5 December 1995 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. Authentication Data 16 octets. Filled with the result of the MD5 calcu- lation. Karn, Metzger & Simpson expires in six months [Page 5] DRAFT ESP DES-CBC-MD5 December 1995 3. Algorithm In DES-CBC, each plaintext block is XOR'd with the previous cipher- text block, and the DES encryption function is applied to yield the ciphertext for the current block. This provides for re- synchronization when datagrams are lost. For more explanation and implementation information for DES, see [Schneier95]. 3.1. Encryption Append zero or more octets of (preferably random) padding to the plaintext, to make its modulo 8 length equal to 6. For example, if the plaintext length is 41, 5 octets of padding are added. Append a Pad Length octet containing the number of padding octets just added. Append a Payload Type octet containing the IP Protocol/Payload value identifying the protocol header that begins the payload. Provide an appropriate Initialization Vector (IV), as described ear- lier. 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 (mod- ulo 8) corresponds to bits 57-64 of the DES input block. Add the indicated SPI and IV seed in front of the Payload Data. Append the Authentication Data, calculated over the SPI, IV, Payload Data, padding, Pad Length, and Payload Type. Construct an appropriate IP datagram for the target Destination. The Total/Payload Length in the encapsulating IP Header reflects the length of the encrypted data, plus the SPI, IV, padding, Pad Length, Payload Type, and Authentication Data. Karn, Metzger & Simpson expires in six months [Page 6] DRAFT ESP DES-CBC-MD5 December 1995 3.2. Decryption First, the SPI field is examined. This is used as an index into the local Security Parameter table to find the negotiated parameters and decryption key. The Authentication Data is verified and removed. The SPI and IV fields are removed, and an appropriate 64-bit IV value is constructed. 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, the payload is discarded with an appropriate ICMP message. The Pad Length is removed and examined. 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 receive routine specified by the Payload Type field. 3.3. Authentication The 128-bit digest is calculated as described in [RFC-1321]. The specification of MD5 includes a portable 'C' programming language description of the MD5 algorithm. The form of the authenticated message is MD5( key, keyfill, MD5( key, keyfill, data, MD5fill), MD5fill ) First, the variable length secret authentication key is filled to the next 512-bit boundary, using the same pad with length technique defined for MD5. Second, the filled key is concatenated with (immediately followed by) the SPI, IV, Payload Data, padding, Pad Length, and Payload Type. A trailing pad with length to the next 512-bit boundary for the entire message is added by MD5 itself. The 128-bit MD5 digest is calculated. Third, the filled key is again concatenated with (immediately Karn, Metzger & Simpson expires in six months [Page 7] DRAFT ESP DES-CBC-MD5 December 1995 followed by) the previous digest. A trailing pad with length to the next 512-bit boundary for the entire message is added by MD5 itself. The 128-bit MD5 digest is calculated, and the result is inserted into the Authentication Data field. Discussion: The leading copy of the key is padded in order to facilitate copy- ing of the key at machine boundaries without requiring re- alignment of the following datagram. The padding technique includes a length that protects arbitrary length keys. Filling to the MD5 block size also allows the key to be prehashed to avoid the physical copy in some implementations. It is further sug- gested that this might protect against some forms of cryptanaly- sis, although no such weakness is yet known in keyed MD5 [KR95]. When the implementation adds the keys and padding in place before and after the IP datagram, care must be taken that the keys and/or padding are not sent over the link by the link driver. Security Considerations Users need to understand that the quality of the security provided by this specification depends completely on the strength of the DES and MD5 algorithms, the correctness of the 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. MD5 At the time of writing of this document, it is known to be possi- ble to produce collisions in the compression function of MD5 [dBB93]. There is not yet a known method to exploit these colli- sions to attack MD5 in practice, but this fact is disturbing to some authors [Schneier95]. It has also recently been determined [vOW94] that it is possible to build a machine for $10 Million that could find two chosen text variants with a common MD5 hash value. However, it is unclear whether this attack is applicable to a keyed MD5 transform. This attack requires approximately 24 days. The same form of attack is useful on any iterated n-bit hash function, and the time is entirely due to the 128-bit length of the MD5 hash. Karn, Metzger & Simpson expires in six months [Page 8] DRAFT ESP DES-CBC-MD5 December 1995 Although there is no substantial weakness for most IP security applications, it should be recognized that current technology is catching up to the 128-bit hash length used by MD5. Applications requiring extremely high levels of security may wish to move in the near future to algorithms with longer hash lengths. DES Among other considerations, applications may wish to take care not to select weak keys, although the odds of picking one at random are low [Schneier95, p 280]. The cut and paste attack described by [Bell95] exploits the nature of all Cipher Block Chaining algorithms. When a block is damaged 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 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]. At the time of writing of this document, [BS93] demonstrated a differential cryptanalysis based chosen-plaintext attack requiring 2^47 plaintext-ciphertext pairs, and [Matsui94] demonstrated a linear cryptanalysis based known-plaintext attack requiring only 2^43 plaintext-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 crack- ing 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 pro- vided by use of ESP DES-CBC in the Internet environment is far greater than sending the datagram as cleartext. Karn, Metzger & Simpson expires in six months [Page 9] DRAFT ESP DES-CBC-MD5 December 1995 Acknowledgements Some of the text of this specification was derived from work by Ran- dall Atkinson for the SIP, SIPP, and IPv6 Working Groups. This basic concept and use of DES and MD5 are derived in large part from the work done for SNMPv2 [RFC-1446]. Bart Preneel suggested the hash protection of the IV, to render it impossible to correlate with subsequent IVs. The message authentication mechanism is based on one of the variants discussed in [KR95]. Karn, Metzger & Simpson expires in six months [Page 10] DRAFT ESP DES-CBC-MD5 December 1995 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. [dBB93] den Boer, B., and Bosselaers, A., "Collisions for the Com- pression function of MD5", Advances in Cryptology -- Euro- crypt '93 Proceedings, Berlin: Springer-Verlag 1994 [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. [KR95] Kaliski, B., and Robshaw, M., "Message authentication with MD5", CryptoBytes (RSA Labs Technical Newsletter), vol.1 no.1, Spring 1995. [Matsui94] Matsui, M., "Linear Cryptanalysis method dor DES Cipher," Advances in Cryptology -- Eurocrypt '93 Proceedings, Berlin: Springer-Verlag, 1994. Karn, Metzger & Simpson expires in six months [Page 11] DRAFT ESP DES-CBC-MD5 December 1995 [RFC-1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC-1321, DDN Network Information Center, April 1992. [RFC-1446] Galvin, J., and McCloghrie, K., "Security Protocols for Ver- sion 2 of the Simple Network Management Protocol (SNMPv2)", RFC-1446, DDN Network Information Center, April 1993. [RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers", STD 2, RFC-1700, USC/Information Sciences Institute, October 1994. [RFC-1800] Postel, J., "Internet Official Protocol Standards", STD 1, RFC-1800, USC/Information Sciences Institute, July 1995. [RFC-1810] Touch, J., "Report on MD5 Performance", USC/Information Sci- ences Institute, June 1995. [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. [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. [vOW94] van Oorschot, P. C., and Wiener, M. J., "Parallel Collision Search with Applications to Hash Functions and Discrete Log- arithms", Proceedings of the 2nd ACM Conf. Computer and Com- munications Security, Fairfax, VA, November 1994. Karn, Metzger & Simpson expires in six months [Page 12] DRAFT ESP DES-CBC-MD5 December 1995 Author's Address Questions about this memo 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 (prefered) 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 Bill.Simpson@um.cc.umich.edu bsimpson@MorningStar.com (prefered)