[Search] [pdf|bibtex] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01                                                         
Network Working Group                                          P Metzger
Internet Draft                                                  Piermont
                                                             W A Simpson
                                                              D A Wagner
expires in six months                                      February 1996

                   The ESP DES-CBC plus MD5 Transform

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


   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

   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

   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

      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

      The following steps are applied to each incoming sequence number

         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

   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-

   MD5 software speeds are adequate for commonly deployed LAN and WAN
   links, but reportedly are too slow for newer link technologies

   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

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

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

   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

                    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-

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

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-

   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

   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

   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

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

      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

         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-

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.


         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-

         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.


         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.


      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

      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-

      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


      [BS93]   Biham, E., and Shamir, A., "Differential Cryptanalysis of
               the Data Encryption Standard", Berlin: Springer-Verlag,

      [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

               US National Bureau of Standards, "Data Encryption Stan-
               dard", Federal Information Processing Standard (FIPS)
               Publication 46, January 1977.

               US National Bureau of Standards, "Data Encryption Stan-
               dard", Federal Information Processing Standard (FIPS)
               Publication 46-1, January 1988.

               US National Bureau of Standards, "Guidelines for Imple-
               menting and Using the Data Encryption Standard", Federal
               Information Processing Standard (FIPS) Publication 74,
               April 1981.

               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.

               Matsui, M., "Linear Cryptanalysis method dor DES Cipher,"
               Advances in Cryptology -- Eurocrypt '93 Proceedings,
               Berlin: Springer-Verlag, 1994.

               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

               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.

               Reynolds, J., and Postel, J., "Assigned Numbers", STD 2,
               RFC-1700, USC/Information Sciences Institute, October

               Postel, J., "Internet Official Protocol Standards", STD
               1, RFC-1800, USC/Information Sciences Institute, July

               Touch, J., "Report on MD5 Performance", USC/Information
               Sciences Institute, June 1995.

               Atkinson, R., "Security Architecture for the Internet
               Protocol", RFC-1825, Naval Research Laboratory, July

               Atkinson, R., "IP Authentication Header", RFC-1826, Naval
               Research Laboratory, July 1995.

               Atkinson, R., "IP Encapsulating Security Protocol (ESP)",
               RFC-1827, Naval Research Laboratory, July 1995.

               Schneier, B., "Applied Cryptography Second Edition", John
               Wiley & Sons, New York, NY, 1995.  ISBN 0-471-12845-7

               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

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


         William Allen Simpson
         Computer Systems Consulting Services
         1384 Fontaine
         Madison Heights, Michigan  48071

             bsimpson@MorningStar.com (prefered)