Network Working Group P Metzger Internet Draft Piermont W A Simpson Daydreamer D A Wagner Berkeley expires in six months February 1996 The ESP DES-CBC plus MD5 Transform draft-simpson-esp-des1md5-01.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) M, S & W expires in six months [Page i] DRAFT ESP DES-CBC-MD5 February 1996 Abstract This document describes use of DES-CBC for privacy, plus MD5 for integrity, in the IP Encapsulating Security Payload (ESP). M, S & W expires in six months [Page ii] DRAFT ESP DES-CBC-MD5 February 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. 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. The two keys MUST appear to be unrelated. Knowing the value of one key SHOULD NOT give an adversary an opportunity to calculate the other key. M, S & W expires in six months [Page 1] DRAFT ESP DES-CBC-MD5 February 1996 Implementation Notes: Using the same key(s) (or overlapping portion of the same overall key) allows an attack exploiting mathematical relationships between the different algorithms that might reveal some portion of the session-key(s). Never-the-less, there is no known interaction between the MD5 and DES-CBC algorithms. Some implementors might adopt a strategy of systematically reveal- ing some bits of the transform keys (to satisfy US export require- ments for at most 40-bit secrecy algorithms). This is not recom- mended; but if it is necessary, implementors MUST reveal only DES key bits and not MD5 key bits. The independence of the two keys is necessary for security. 1.2. Replay Protection This transform provides replay protection: cryptographically secure at-most-once best-effort datagram delivery. In other words, when an adversary resends an earlier intercepted IP datagram, the recipient will detect the attempt. Each implementation maintains a counter. This counter serves both to generate a per-message unique IV for DES, and also as a sequence num- ber to provide replay protection. When sending, the counter MUST be initialized to 0 for the first datagram, and MUST be incremented (as a 32-bit unsigned integer) after each datagram is sent. On receipt, the sequence number is checked against a list of previ- ously accepted numbers. There is no requirement that datagrams arrive in order. As each datagram arrives, the sequence number is stored so that it won't be accepted again. Implementation Notes: The exact algorithm is implementation dependent, but it MUST reject datagrams with duplicate sequence numbers, and should make a best effort to accept as many valid (non-duplicate) datagrams as possible. A full 2**32 element array storing the status of each sequence number received is probably impractical. The following simple algorithm is one possible improvement. A low-water mark L is maintained; sequence numbers less than M, S & W expires in six months [Page 2] DRAFT ESP DES-CBC-MD5 February 1996 (earlier than) the low-water mark are automatically rejected. A fixed window size W is chosen, according to storage constraints. An array A[L..L+W-1] of size W is maintained, where each element maintains the state (stale or fresh) of the corresponding sequence number. The following steps are applied to each incoming sequence number S: 1. If S < L drop the datagram. 2. If S < L+W and A[S] == stale drop the datagram. 3. If S < L+W and A[S] == fresh set A[S] = stale and accept the datagram. (note: S > L+W-1) 4. If A[L] == stale Let x = L; While A[x] == stale Do set x = x + 1. Let y = L; Let L = x. (shift the array A[] down by y-L elements in memory if necessary, so now A[] has the new bounds L..L+W-1) Set A[j] = fresh for y+W-1 < j < L+W. Goto Step 1. (note: S > L+W-1 and A[L] == fresh) 5. Let y = L; Let L = S-W+1. (shift the array A[] down by y-L elements in memory if necessary, so now A[] has the new bounds L..L+W-1 i.e. L..S) Set A[j] = fresh for y+W-1 < j < L+W. Set A[S] = stale and accept the datagram. Two invariants are maintained in this algorithm. First, all sequence numbers S < L are stale. Second, all sequence numbers S > L+W-1 are fresh. Note that step 5 forgets some state information, and may cause M, S & W expires in six months [Page 3] DRAFT ESP DES-CBC-MD5 February 1996 out-of-order datagrams which were sent earlier but received later to be (incorrectly) judged stale and dropped. Though this algo- rithm may inadvertenly reject a fresh datagram as stale, the important point is that it will never accept a replayed datagram. An implementation may wish to go through with step 5 only for packets that pass the authentication verification. This is only one possible algorithm; implementators may choose another, so long as it rejects replayed datagrams with duplicate sequence numbers. 1.3. 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 IV is generated from the SPI and Sequence fields. An MD5 hash is calculated over the following concatenated values: + the DES key (8 octets including parity bits), + the SPI (4 octets), + the Sequence (4 octets), + the MD5 key (variable length). The most significant 64-bits of the generated hash are used for the final IV. 1.4. 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. 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 M, S & W expires in six months [Page 4] DRAFT ESP DES-CBC-MD5 February 1996 described in [RFC-1825]. 1.5. 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]. Phil 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]. M, S & W expires in six months [Page 5] DRAFT ESP DES-CBC-MD5 February 1996 2. Payload Format +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Security Parameters Index (SPI) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sequence | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | ~ 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. Sequence 4 octets. Provides replay prevention, and 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 length. M, S & W expires in six months [Page 6] DRAFT ESP DES-CBC-MD5 February 1996 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. M, S & W expires in six months [Page 7] DRAFT ESP DES-CBC-MD5 February 1996 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 Sequence in front of the Payload Data. Append the Authentication Data, calculated over the SPI, Sequence, 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, Sequence, padding, Pad Length, Payload Type, and Authentication Data. M, S & W expires in six months [Page 8] DRAFT ESP DES-CBC-MD5 February 1996 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 Sequence 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, Sequence, 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. M, S & W expires in six months [Page 9] DRAFT ESP DES-CBC-MD5 February 1996 Third, the filled key is again concatenated with (immediately fol- lowed 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. M, S & W expires in six months [Page 10] DRAFT ESP DES-CBC-MD5 February 1996 A. Deriving Independent Keys This algorithm is suggested for those implementors that desire to configure only one master key, and derive two apparently indepen- dent keys. The master key shall be considered the key of this transform. The master key length MUST be between 56 and 128 bits; larger values are recommended. DES key: PK = most significant 64-bits of MD5("DES", master key). The 3-byte ASCII string "DES" is followed by (concatenated with) the master key. That is hashed with the MD5 cryptographic hash, and PK is the first 8 bytes (64-bits) of the hash output. The least significant bits of DK are discarded, and replaced by the appropriate DES parity check bits. The result is the DES privacy key. MKL = length of the master key in bits. MD5 key: AK = most significant MKL bits of MD5("MD5", master key). The 3-byte ASCII string "MD5" is followed by (concatenated with) the master key. That is hashed with the MD5 cryptographic hash, and AK is the first MKL bits of the hash output. This ensures that the length of the authentication key accurately reflects its entropy. The result is the MD5 authentication key. Design Notes: Any appropriate pair of strings may be used in place of "DES" and "MD5". This transform does not provide more than 56 bits of confiden- tiality, regardless of the size of the master key. This derivation provides only as many bits of message authentication as the minimum of {master key length, 128-bits}. This simple key scheduling algorithm will not work with a hard- ware token that must generate the DES key itself (a la Clip- per). M, S & W expires in six months [Page 11] DRAFT ESP DES-CBC-MD5 February 1996 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 imple- mentation, the security of the key management mechanism and its implementation, the strength of the key [CN94], and upon the cor- rectness of the implementations in all of the participating nodes. MD5 At the time of writing of this document, it is known to be pos- sible to produce collisions in the compression function of MD5 [dBB93]. There is not yet a known method to exploit these col- lisions to attack MD5 in practice, but this fact is disturbing to some authors [Schneier95]. It has also recently been determined [vOW94] that it is possi- ble to build a machine for $10 Million that could find two cho- sen text variants with a common MD5 hash value. However, it is unclear whether this attack is applicable to a keyed MD5 trans- form. 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. 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. Appli- cations 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]. 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 M, S & W expires in six months [Page 12] DRAFT ESP DES-CBC-MD5 February 1996 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. Acknowledgements Some of the text of this specification was derived from work by Randall Atkinson for the SIP, SIPP, and IPv6 Working Groups. This basic concept and use of DES and MD5 were derived in large part from the work done for SNMPv2 [RFC-1446]. Much of the implementation details were derived from work by Phil Karn. Bart Preneel suggested the hash protection of the IV, to render it impossible to correlate with subsequent IVs. David Wagner was responsible for the description of replay preven- tion. The message authentication mechanism is based on one of the vari- ants discussed in [KR95]. M, S & W expires in six months [Page 13] DRAFT ESP DES-CBC-MD5 February 1996 References [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 Compression function of MD5", Advances in Cryptology -- Eurocrypt '93 Proceedings, Berlin: Springer-Verlag 1994 [FIPS-46] US National Bureau of Standards, "Data Encryption Stan- dard", Federal Information Processing Standard (FIPS) Publication 46, January 1977. [FIPS-46-1] US National Bureau of Standards, "Data Encryption Stan- dard", Federal Information Processing Standard (FIPS) Publication 46-1, January 1988. [FIPS-74] US National Bureau of Standards, "Guidelines for Imple- menting and Using the Data Encryption Standard", Federal Information Processing Standard (FIPS) Publication 74, April 1981. [FIPS-81] US National Bureau of Standards, "DES Modes of Operation" Federal Information Processing Standard (FIPS) Publica- tion 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. [RFC-1321] Rivest, R., "The MD5 Message-Digest Algorithm", RFC-1321, DDN Network Information Center, April 1992. M, S & W expires in six months [Page 14] DRAFT ESP DES-CBC-MD5 February 1996 [RFC-1446] Galvin, J., and McCloghrie, K., "Security Protocols for Version 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 Sciences Institute, June 1995. [RFC-1825] Atkinson, R., "Security Architecture for the Internet Protocol", 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 Com- puter 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 Colli- sion Search with Applications to Hash Functions and Dis- crete Logarithms", Proceedings of the 2nd ACM Conf. Com- puter and Communications Security, Fairfax, VA, November 1994. M, S & W expires in six months [Page 15] DRAFT ESP DES-CBC-MD5 February 1996 Author's Address Questions about this memo can also be directed to: 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)