[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Internet Draft                         October 1996 (Expires April 1997)

                                                    M. Sabin, Consultant
                                                  R. Monsour, Hi/fn Inc.


    Combined 3DES-CBC, LZS Compression, HMAC, and Replay Prevention
                             ESP Transform
                 <draft-sabin-esp-des3-lzs-md5-00.txt>


Status of this Memo

   This document is an Internet-Draft.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working 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 inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "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),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).


Abstract

   This document proposes the "3DES-CBC-LZS-HMAC-Replay" security
   transform for the IP Encapsulating Security Payload (ESP).  The
   proposed transform combines triple-DES encryption, LZS compression,
   HMAC authentication, and replay prevention into a single packet
   format.  The transform is compatible with implementations that do not
   support compression and with implementations that support only
   single-DES encryption.  Compression is performed prior to encryption,
   which has the side benefit of reducing the amount of data that must
   be encrypted.

   This document is based on the IPsec Working Group's proposed
   "Combined DES-CBC, HMAC, and Replay Prevention Security Transform,"
   cited later in this document.


Acknowledgments

   This memo is based on the document "Combined DES-CBC, HMAC, and
   Replay Prevention Security Transform," by the IPsec Working Group, J.



Sabin, et al                                                   [Page  1]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


   Hughes, editor [Hughes96].  Much of the text of that document is
   repeated here, with details specific to LZS and triple-DES added.
   The LZS details are similar to those in "PPP Stac LZS Compression
   Protocol," by R.  Friend and W.  A.  Simpson [RFC-1974].


Table of Contents

   1.  Introduction
   2.  Packet Format
   3.  Encode Procedure
   4.  Decode Procedure
   5.  Generating Key Material
   6.  Security Considerations
   7.  References
   8.  Author's Addresses
   9.  Appendix:  Guidelines for Resetting Compression History


1.  Introduction

   Encrypted data is random in nature and not compressible.  When an IP
   packet is encrypted, the usual techniques for compressing it -- e.g.,
   PPP compression -- do not work.  If both compression and encryption
   are desired, compression must be performed first.


   1.1  Compression with ESP

      ESP is well suited to combining compression with encryption, for a
      variety of reasons:

         -  ESP is the place were encryption is applied to an IP packet.
         It is straightforward to precede the encryption step by a
         compression step.  A side benefit of compressing the data first
         is that the amount of data which must be encrypted is reduced.
         In some implementations, compression is done in hardware and
         encryption in software, and this represents a significant
         reduction in software processing.

         -  ESP supports routing of opaque data.  When a packet is
         encrypted, intermediate nodes along a route are not able to
         decrypt it.  Nevertheless, the encrypted packet can be routed,
         because ESP has been designed with this in mind.  When a packet
         is compressed within ESP, the situation is similar:
         intermediate nodes are not able to decompress it (at least
         without additional expense), but ESP ensures that the
         compressed packet can be routed.

         -  ESP provides a security parameters index (SPI) that links a
         packet to security parameters negotiated elsewhere.  A



Sabin, et al                                                   [Page  2]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


         destination node uses the SPI to look up the ESP transform
         needed to decode an incoming packet.  If compression details
         are included in ESP transform specifications, a destination
         node can also use the SPI to determine if a packet needs to be
         decompressed, and if so, by what algorithm.  Source and
         destination nodes can maintain multiple compression histories
         (described in a later section), one history for each SPI.


   1.2  Background of LZS Compression

      The LZS algorithm is a lossless compression method that uses a
      sliding window of 2,048 bytes.  During compression, redundant
      sequences of data are replaced with tokens that represent those
      sequences.  During decompression, the original sequences are
      substituted for the tokens, in such a way that the original data
      is exactly recovered.  LZS differs from lossy schemes, such as
      those often used for video compression, that do not exactly
      reproduce the original data.

      Details of LZS formatting can be found in [ANSI94].

      The efficiency of the LZS algorithm depends on the degree of
      redundancy in the original data.  A typical compression ratio for
      disk files is 2:1.  LZS achieves a compression ratio of 2.34:1 on
      the University of Calgary Text Compression Corpus [Calgary].

      The LZS algorithm is stateful.  It maintains a "history" in which
      compression information is stored.  The compression operation
      requires a "compression history" and the decompression operation a
      "decompression history." Each of these histories is initialized to
      a start state before any data is processed.  Thereafter, as data
      is compressed and decompressed, the two histories remain
      synchronized, provided that the decompressor processes all the
      data generated by the compressor, in the order in which it is
      generated.

      An LZS compression/decompression history pair can be reset to the
      start state at any time.  This can be used to restore
      synchronization between compressor and decompressor when data
      received by the decompressor has been lost or corrupted.  This is
      particularly important in IP, where the delivery of individual
      packets is not guaranteed.

      When LZS compression is applied to a block of data, it sometimes
      happens that the "compressed" block is actually larger than the
      original, uncompressed block.  In IP, it would be undesirable to
      transmit a block that has expanded in this way.  Accordingly, when
      LZS results in expansion, this specification calls for the
      transmitter to send the uncompressed data instead of the
      compressed data.  The packet format includes a bit to signal the



Sabin, et al                                                   [Page  3]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      receiver that the packet contents are not compressed.

      When the transmitter sends uncompressed data, it still updates its
      compression history as if it had actually compressed the data.
      This enhances its ability to compress future data.  When the
      receiver receives uncompressed data, it updates its decompression
      history using the uncompressed data.  This keeps the decompression
      history in sync with the compression history.

      An application can maintain multiple compression and/or
      decompression processes by maintaining multiple histories, one
      history for each process.  Each process operates independently of
      the others.  This is useful in IPsec, since it allows each
      security association (as indexed by the SPI) to have its own
      history.


   1.3  Licensing

      Source and object licenses for LZS are available on a
      non-discriminatory basis.  Hardware implementations are also
      available.  For more information, contact Hi/fn at the address
      listed with the authors' addresses.


   1.4  3DES-CBC-LZS-HMAC-Replay ESP Transform

      The transform proposed in this memo combines triple-DES in CBC
      mode (3DES-CBC), LZS compression, HMAC authentication, and replay
      prevention.  The proposed transform is based heavily on the
      transform presented in [Hughes96].  Much of the text from that
      document has been repeated here.

      The goals of the transform are: privacy; compression;
      authenticity; integrity; and defense against replay.

         - Privacy is provided by 3DES-CBC [RFC-1851], which is a
         variant of conventional DES-CBC [FIPS-46] [FIPS-46-1] [FIPS-74]
         [FIPS-81].

         - Compression is provided by the LZS algorithm [ANSI94].

         - Integrity is provided by HMAC [Krawczyk96].

         - Authentication is provided since only the source and
         destination know the HMAC key.  If the HMAC is correct, it
         proves that it must have been added by the source.

         - Replay prevention is provided by the combination of a
         constantly increasing count, the SPI and the HMAC key.
         Integrity of the count is provided by the HMAC.



Sabin, et al                                                   [Page  4]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996



   3DES-CBC encryption uses a double-length key (112 bits) or a
   triple-length key (168 bits).  Triple-length is usually preferred for
   security reasons, but some hardware devices only support
   double-length.  Accordingly, this transform supports both
   double-length and triple-length keys as a negotiated parameter.

   The transform also supports single-length keys (56 bits) as a
   negotiated parameter.  This makes it compatible with implementations
   that only support conventional (i.e., single) DES-CBC.


   1.5  Requirements Terminology

      In this document, the words that are used to define the
      significance of each particular requirement are usually
      capitalized.  These words are:

         - MUST:  This word, or the adjective "REQUIRED," means that the
         item is an absolute requirement of the specification.

         - SHOULD:  This word, or the adjective "RECOMMENDED," means
         that there might exist valid reasons in particular
         circumstances to ignore this item, but the full implications
         should be understood and the case carefully weighed before
         taking a different course.

         - MAY:  This word, or the adjective "OPTIONAL," means that the
         item is truly optional.  One vendor might choose to include the
         item because of a particular marketplace requirement or because
         it enhances the product, while another vendor might omit the
         item.






















Sabin, et al                                                   [Page  5]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


2. Packet Format


+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---
|                Security Parameters Index (SPI)                | ^
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |
|                                                               | |
|                Initialization Vector (optional)               | |
|                                                               | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |  ---
|                 Replay Prevention Field (count)               | |   ^
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |   |
|                                                               |HMAC |
|              Payload Data (compressed or uncompressed)        | |   |
|                                                               | |   |
|                                               +-+-+-+-+-+-+-+-| |   |
|                                               |               | |   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+               | | 3DES
|                         Padding (0-7 bytes)                   | |  CBC
|               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |   |
|               |  Pad Length   |      CC       | Payload Type  | v   |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+---  |
|                                                               |     |
|                        HMAC digest                            |     |
|                                                               |     v
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+    ---


   2.1  Security Parameters Index

      This field contains a 32-bit value identifying the security
      association for this packet.  The value is negotiated at key setup
      and MUST NOT be 0.


   2.2  Initialization Vector

      The use of an explicit initialization vector (IV) MAY be
      negotiated.  The purpose of this mode is to support devices that
      automatically generate IV's and cannot operate using a constant
      IV_key_.

      This field is optional and is only used when an explicit IV is
      negotiated during key exchange.  This field contains random data
      or the last ciphertext block of the previous packet.


   2.3  Replay Prevention

      This field contains an unsigned, 32-bit, incrementing counter.
      The counter is initialized to a mutually agreed upon value (see



Sabin, et al                                                   [Page  6]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      the section on Generating Key Material).


      2.3.1  Security Issues

         To defend against replay attacks, the receiver verifies that
         received packets have non-repeating counter values.  The
         simplest approach is for the receiver to reject any packet
         whose counter has a value less than or equal to that of any
         previously received packet.  A consequence of this simple
         approach is that out-of-order packets will be rejected.
         Alternatively, the receiver MAY choose to operate with a window
         of acceptable counter values:  a packet will not be rejected if
         its counter value is within some value M of the highest counter
         value received so far, provided that the counter value has not
         been seen before.  For an example implementation of such a
         strategy, see [Hughes96].

         The counter is not allowed to cycle back to its starting value.
         This requires that the key be changed before 2^32 packets have
         been transmitted.  The receiver rejects any packet whose
         counter value indicates cycling back through the starting
         value.


      2.3.2  Compression Issues

         In addition to defending against replay attacks, the counter
         plays a role in the decompression of packets.  When a packet is
         received out of order, the receiver detects the misordering
         because of the counter value.  Because LZS is stateful, the
         receiver may or may not be able to decompress the out-of-order
         packet.  If the history was reset by the transmitter
         immediately prior to compressing the packet, the receiver can
         decompress it, because decompression does not depend on any
         previous packets.  (The packet includes a flag in the CC field
         that indicates whether or not the history was reset.)  But if
         the history was not reset by the transmitter immediately prior
         to compressing the packet, the receiver cannot decompress it.

         When a receiver is unable to decompress an out-of-order packet,
         the simplest strategy for the receiver is to discard it.
         Alternatively, a receiver MAY elect to use a windowing scheme
         similar to that described in Section 2.3.1, in order to
         accommodate a reasonable spread of out-of-order packets.  Note
         that if the windowing scheme is used, the receiver must queue
         all packets that fall within the window but are not yet
         decompressible.  This makes it more expensive than the scheme
         previously described, which only had to queue counter values.

         Decompressing out-of-order packets is only an issue for the



Sabin, et al                                                   [Page  7]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


         final destination of a packet.  Intermediate nodes along a
         route do not decompress packets and thus can handle packets in
         any order.


   2.4  Payload Data

      The payload data is either compressed or uncompressed.  The value
      of the COMPRESSED bit of the CC field is set accordingly.  The
      payload field is an integral number of bytes in length.


   2.5  Padding

      The padding is used to align the subsequent "payload type" field
      to end on a double-word boundary, counting from the start of the
      replay field.  Padding bytes SHOULD contain random data.

      At a minimum, the number of padding bytes added must be enough to
      align the payload type field on the next appropriate boundary.
      However, the sender may choose to include additional padding, in
      order to hide the actual length of the data.  In general, the
      sender can use any number of padding bytes in the range of 0-255,
      provided that the required alignment is achieved.


   2.6  Pad Length

      This field indicates the number of padding bytes immediately
      preceding it.  The range of valid values is 0-255, where a value
      of zero indicates the byte immediately preceding the pad length
      field is the last byte of payload.


   2.7  Compression Control

      The Compression Control (CC) field is a single, bit-mapped byte.
      The bits are numbered 7 (most significant) to 0 (least
      significant).  The following bits are defined:


      2.7.1  COMPRESSED (bit 7)

         This bit is set to 1 to indicate the payload is compressed.  It
         is cleared to 0 to indicate the payload is not compressed.

         In implementations that do not support compression, this bit
         is always cleard to 0.






Sabin, et al                                                   [Page  8]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      2.7.2  HIST_RESET (bit 6)

         This bit is set to 1 to indicate that the compression history
         associated with this packet's SPI was reset prior to processing
         this packet's payload.  In such a case, the receiver must reset
         the corresponding decompression history prior to processing the
         payload.  If the payload is compressed, it can always be
         decompressed, because compression is not based on any previous
         history.

         This bit is cleared to 0 to indicate that the compression
         history associated with this packet's SPI was not reset prior
         to transmitting the payload.  If the payload is compressed, it
         can only be decompressed if there have been no missed packets
         since the last packet that had the bit set to 1.  A packet that
         cannot be decompressed because of missing packets is either
         rejected or, if the implementation supports it, queued in the
         hope that it can be decompressed when the missing packets
         arrive.

         The transmitter SHOULD adopt a policy of periodically resetting
         the compression history and setting the HIST_RESET bit.  This
         allows a receiver that has missed packets to resynchronize its
         decompressor.  The details of such a policy are up to the
         transmitter implementation.  An attached appendix gives
         guidelines.

         The transmitter MUST flush the compressor each time it
         transmits a compressed packet, regardless of whether or not it
         resets the compression history.  Flushing means that all data
         going into the compressor is included in the output, i.e., no
         data is held back in the hope of achieving better compression.
         Flushing is necessary to prevent a packet's data from spilling
         over into a later packet.


   2.8  Payload Type

      This field indicates the type of payload, using the IP
      Protocol/Payload value.  Values are described in [RFC-1700].


   2.9  HMAC Digest

      The HMAC digest is a 128-bit residue, calculated over the SPI,
      replay, payload, padding, pad length, CC, and payload type.
      Details of the calculation can be found in [Krawczyk96].

      HMAC is a keyed algorithm based on MD5.  It uses the HMAC key
      described in the section on keys.




Sabin, et al                                                   [Page  9]

INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996



3.  Encode Procedure

   For compression, the LZS algorithm is used.

   For encryption, CBC chaining is used.  The initialization vector is
   either the contents of the IV field or the IV_key_:


       IV or
       IV_key_   count|x1             x2                x3
          |         |                 |                 |
          |--------(+)     ----------(+)     ----------(+)
                    |      |          |      |          |
                ---------  |      ---------  |      ---------
            k1--|  DES  |  |  k1--|  DES  |  |  k1--|  DES  |
                |encrypt|  |      |encrypt|  |      |encrypt|
                ---------  |      ---------  |      ---------
                    |      |          |      |          |
                ---------  |      ---------  |      ---------
            k2--|  DES  |  |  k2--|  DES  |  |  k2--|  DES  |
                |decrypt|  |      |decrypt|  |      |decrypt|
                ---------  |      ---------  |      ---------
                    |      |          |      |          |
                ---------  |      ---------  |      ---------
            k3--|  DES  |  |  k3--|  DES  |  |  k3--|  DES  |
                |encrypt|  |      |encrypt|  |      |encrypt|
                ---------  |      ---------  |      ---------
                    |------|          |------|          |----...
                    |                 |                 |
                   y1                 y2                y3


   In the figure:  count is the value in the replay prevention field;
   x1, x2, x3 are the plaintext (x1 is 32 bits, all others are 64 bits);
   y1, y2, y3 are the ciphertext; k1, k2, k3 are the 56-bit portions of
   the triple-length key.  (When a double-length key is used, k3 = k1.
   When a single-length key is used, k3 = k2 = k1.)

   The transform is carried out in the following steps:

      i)  If the transmitter chooses to reset the compression history,
      it does so, and it sets the HIST_RESET bit of the CC field to 1.
      Otherwise, it clears the HIST_RESET bit to 0.

      ii)  The transmitter decides whether or not to compress the
      payload.

         - If the transmitter chooses to compress the payload, the LZS
         algorithm is applied.  The resulting compressed data is
         formatted according to [ANSI94].  The COMPRESSED bit of the CC



Sabin, et al                                                   [Page 10]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


         field is set to 1.

         - If the transmitter chooses not to compress the payload, the
         COMPRESSED bit of the CC field is set to 0.  The compression
         history is updated with the uncompressed payload.

      iii)  The payload is encapsulated with the SPI, IV (if used),
      replay, padding, pad length, CC, and payload type.  The padding
      and pad length are appropriately adjusted.  The replay is
      incremented by one from its previous value.

      iv)  The HMAC is calculated.  The calculation uses the HMAC_key_
      and spans the SPI, IV (if used), replay, payload, padding, pad
      length, CC, and payload type.  The result is placed in the HMAC
      digest field.

      v)  The replay, payload, padding, pad length, CC, payload type,
      and HMAC digest are encrypted using 3DES-CBC with the appropriate
      DES_key_.  The initialization vector is the IV field, if used, or
      the appropriate IV_key_.

   An implementation SHOULD monitor the results of the payload
   compression operation and reject the operation if it results in
   expansion.  In such a case, the uncompressed payload SHOULD be
   transmitted.





























Sabin, et al                                                   [Page 11]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


4.  Decode Procedure

   For decryption, CBC chaining is used:


       IV or
       IV_key_      y1                y2                y3
         |          |                 |                 |
         |          |-------          |-------          |----...
         |          |      |          |      |          |
         |      ---------  |      ---------  |      ---------
         |  k3--|  DES  |  |  k3--|  DES  |  |  k3--|  DES  |
         |      |decrypt|  |      |decrypt|  |      |decrypt|
         |      ---------  |      ---------  |      ---------
         |          |      |          |      |          |
         |      ---------  |      ---------  |      ---------
         |  k2--|  DES  |  |  k2--|  DES  |  |  k2--|  DES  |
         |      |encrypt|  |      |encrypt|  |      |encrypt|
         |      ---------  |      ---------  |      ---------
         |          |      |          |      |          |
         |      ---------  |      ---------  |      ---------
         |  k1--|  DES  |  |  k1--|  DES  |  |  k1--|  DES  |
         |      |decrypt|  |      |decrypt|  |      |decrypt|
         |      ---------  |      ---------  |      ---------
         |          |      |          |      |          |
         |---------(+)     |---------(+)     |---------(+)
                    |                 |                 |
               (count|x1)             x2                x3


   For decompression, the LZS algorithm is used.  The decompression
   maintains a state variable "expected_count," which tracks the value
   of count expected in the next packet.  Expected_count is initialized
   to the starting value of the replay count; this value was mutually
   agreed upon, as described in the section on Generating Key Material.

   In the procedure described here, it is assumed that out-of-order
   packets are not queued for the purposes of decompression.  Compressed
   packets that cannot be immediately decompressed are discarded.
   Implementations MAY choose a scheme that queues packets, allowing
   some spread of out-of-order packets to be decompressed; this was
   discussed in Section 2.3.2.

   The transform is carried out in the following steps:

      i)  The replay, payload, padding, pad length, CC, payload type,
      and HMAC digest are decrypted using 3DES-CBC and the appropriate
      DES_key_.  The initialization vector is the IV field, if used, or
      the appropriate IV_key_.

      ii)  The count is checked for replay attack using the window



Sabin, et al                                                   [Page 12]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      algorithm discussed in Section 2.3.1.  If the packet is duplicate
      or too old, the packet is discarded.

      iii)  The HMAC is calculated.  The calculation uses the HMAC_key_
      and spans the SPI, IV (if used), replay, payload, padding, pad
      length, CC, and payload type.  The calculated digest is compared
      against the decrypted digest at the end of the packet.  If the two
      do not match, the packet is discarded.

      iv)  The HIST_RESET bit of the CC is checked.

         - If HIST_RESET = 1, the decompression history is reset, and
         expected_count is set to (count + 1).

         - If HIST_RESET = 0, the value of count is compared to
         expected_count.  If the two match, expected_count is set to
         (count + 1).  If the two do not match, expected_count is
         unchanged; and if COMPRESSED = 1, the packet is discarded.
         (Queuing out-of-order packets is not considered here, but an
         implementation MAY choose to implement queuing instead of
         immediate discard, as discussed in Section 2.3.2.)

      v)  The COMPRESSED bit of the CC is checked.  If COMPRESSED = 1,
      decompression is applied to the payload data.  If COMPRESSED = 0,
      decompression is not applied, and the decompression history is
      updated with the uncompressed data.

   An implementation MAY choose to perform a "sanity check" prior to the
   above procedure.  In the sanity check, the first block of data is
   decrypted using the appropriate DES_key_ and IV_key_, and the
   decrypted value of the replay count is checked.  If the count is way
   out of range -- e.g., more than 2^16 away from the expected value --
   the packet is discarded as non-authentic.  This helps defend against
   clogging attacks, in which an attacker tries to tie up the receiver's
   resources by having it decrypt meaningless packets.  Note that if the
   sanity check passes, the above procedure MUST still be performed.


5.  Generating Key Material

   The key management layer provides several negotiated parameters:

      - The master secret K.

      - The length of the DES symmetric keys:  triple length (168 bits),
      double length (112 bits), or single length (56 bits).

      - Compression support: yes or no.

   The master secret K is used to derive the following symmetric keys:




Sabin, et al                                                   [Page 13]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      DES_Key_I1, DES_Key_I2, and DES_Key_I3 are the three parts of the
      triple-length DES key for traffic from the initiator -> responder.
      When a double-length key is used, DES_Key_I3 = DES_Key_I1.
         When a single-length key is used, DES_Key_I3 = DES_KEY_I2 =
         DES_Key_I1.

      DES_Key_R1, DES_Key_R2, and DES_Key_R3 are the three parts of the
      triple-length DES key for traffic from the responder -> initiator.
      When a double-length key is used, DES_Key_R3 = DES_Key_R1.
         When a single-length key is used, DES_Key_R3 = DES_KEY_R2 =
         DES_Key_R1.

      HMAC_Key_I is the key for the HMAC Algorithm for traffic from the
      initiator -> responder.

      HMAC_Key_R is the key for the HMAC Algorithm for traffic from the
      responder -> initiator.

      IV_key_I is used to stop code book attacks on the first block for
      traffic from the initiator -> responder.

      IV_key_R is used to stop code book attacks on the first block for
      traffic from the responder -> initiator.

      RP_key_I is the initial value and wrap point for the replay
      prevention field for traffic from the initiator -> responder.

      RP_key_R is the initial value and wrap point for the replay
      prevention field for traffic from the responder -> initiator.

   The vertical bar symbol "|" is used to denote concatenation of bit
   strings.

   MD5(x|y) denotes the result of applying the MD5 function to the
   concatenated bit strings x and y.

   Truncate(x,n) denotes the result of truncating x to its first n bits.

      IV_Key_I    = Truncate(MD5( I_Pad_I  | K ),64)
      IV_Key_R    = Truncate(MD5( I_Pad_R  | K ),64)
      HMAC_Key_I  =          MD5( H_Pad_I  | K )
      HMAC_Key_R  =          MD5( H_Pad_R  | K )
      RP_Key_I    = Truncate(MD5( R_Pad_I  | K ),32)
      RP_Key_R    = Truncate(MD5( R_Pad_R  | K ),32)

   For triple-length DES keys:

      DES_Key_I1  = Truncate(MD5( D_Pad_I1 | K ),64)
      DES_Key_I2  = Truncate(MD5( D_Pad_I2 | K ),64)
      DES_Key_I3  = Truncate(MD5( D_Pad_I3 | K ),64)
      DES_Key_R1  = Truncate(MD5( D_Pad_R1 | K ),64)



Sabin, et al                                                   [Page 14]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      DES_Key_R2  = Truncate(MD5( D_Pad_R2 | K ),64)
      DES_Key_R3  = Truncate(MD5( D_Pad_R3 | K ),64)

   For double-length DES keys:

      DES_Key_I1  = Truncate(MD5( D_Pad_I1 | K ),64)
      DES_Key_I2  = Truncate(MD5( D_Pad_I2 | K ),64)
      DES_Key_I3  = DES_Key_I1
      DES_Key_R1  = Truncate(MD5( D_Pad_R1 | K ),64)
      DES_Key_R2  = Truncate(MD5( D_Pad_R2 | K ),64)
      DES_Key_R3  = DES_Key_R1

   For single-length DES keys:

      DES_Key_I1  = Truncate(MD5( D_Pad_I1 | K ),64)
      DES_Key_I3  = DES_Key_I2 = DES_Key_I1
      DES_Key_R1  = Truncate(MD5( D_Pad_R1 | K ),64)
      DES_Key_R3  = DES_Key_R2 = DES_Key_R1

   Note:  Each DES_Key_ is in the usual "7 bits plus parity" format,
   which is why the above procedure generates 64 bits instead of 56
   bits.  The values of the parity bits in each DES_Key_ should either
   be corrected or ignored.

   Each _Pad_is a 512 bit string, as follows:

      D_Pad_I1 = 0x5C repeated 64 times
      D_Pad_I2 = 0xA3 repeated 64 times
      D_Pad_I3 = 0xCA repeated 64 times
      D_Pad_R1 = 0x3A repeated 64 times
      D_Pad_R2 = 0xA5 repeated 64 times
      D_Pad_R3 = 0xC3 repeated 64 times
      I_Pad_I  = 0xAC repeated 64 times
      I_Pad_R  = 0x55 repeated 64 times
      H_Pad_I  = 0x53 repeated 64 times
      H_Pad_R  = 0x3C repeated 64 times
      R_Pad_I  = 0x35 repeated 64 times
      R_Pad_R  = 0xCC repeated 64 times

   (Implementation note: The 16 byte intermediate residuals can be
   precalculated from these constants and stored to reduce processing
   overhead.)


6.  Security Considerations

   The transform described in this draft is immune to the [Bellovin96]
   attacks.

   The implications of the size of K can be found in [Blaze96].




Sabin, et al                                                   [Page 15]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996



7.  References

   [ANSI94] American National Standards Institute, Inc., "Data
      Compression Method for Information Systems," ANSI X3.241-1994,
      August 1994.

   [Blaze96] Blaze, M., Diffie, W., Rivest, R., Schneir, B., Shimomura,
      T., Thompson, E., Wiener, M., "Minimal Key Lengths for Symmetric
      Ciphers to Provide Adequate Commercial Security,"
      http://theory.lcs.mit.edu/~rivest/bsa-final-report.ascii, January
      1996.

   [Calgary]  Text Compression Corpus, University of Calgary, available
      at
      ftp://ftp.cpsc.ucalgary.ca/pub/projects/text.compression.corpus.

   [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
      Implementing 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) Publication 81,
      December 1980.

   [Hughes96] Hughes, J.  editor, "Combined DES-CBC, HMAC, and Replay
      Prevention Security Transform," work-in-progress, available from
      ftp://ds.internic.net/internet-drafts
      /draft-ietf-ipsec-esp-des-md5-03.txt.

   [Krawczyk96]  Krawczyk, H., Bellare, M., Canetti, R., "HMAC-MD5:
      Keyed-MD5 for Message Authentication," work-in-progress, available
      from
      ftp://ds.internic.net/internet-drafts
      /draft-ietf-ipsec-hmac-md5-00.txt.

   [RFC-1700] Reynolds, J., and Postel, J., "Assigned Numbers," STD 2,
      RFC-1700, UCS/Information Sciences Institute, October 1994.

   [RFC-1974] Friend, R., and Simpson, W.A., "PPP Stac LZS Compression
      Protocol," RFC-1974, Stac Electronics, August 1996.

   [RFC-1851] Karn, P., Metzger, P., and Simpson, W., "The ESP Triple



Sabin, et al                                                   [Page 16]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


      DES Transform," RFC-1851, Qualcomm, September 1995.


8.  Authors' Addresses

   Michael Sabin
   883 Mango Avenue
   Sunnyvale, CA  94087
   Email:  mike.sabin@worldnet.att.net

   Robert Monsour
   Hi/fn Inc.
   12636 High Bluff Drive
   San Diego, CA  92130
   Email: rmonsour@hifn.com


9.  Appendix:  Guidelines for Resetting Compression Histories

   The following table offers some guidance on how frequently an LZS
   compression history can be reset.  The table considers two
   parameters: "payload_bytes," the number of bytes in each payload; and
   "reset_bytes," the number of bytes between history resets.
   Reset_bytes is a multiple of payload_bytes, since an integer number
   of payloads is processed between resets.  Each entry in the table
   shows the compression ratio that was achieved when compressing a test
   file with the corresponding values of payload_bytes and reset_bytes.

   The test file was the University of Calgary Text Compression Corpus
   [Calgary].  The length of the file prior to compression was 3,278,000
   bytes.  When the entire file was compressed as a single payload, a
   compression ratio of 2.34 resulted.


               |                    reset_bytes
               |   64   128   256   512  1024  2048  4096  8192 16384
   ------------+-----------------------------------------------------
   packet_bytes|
          64   | 1.18  1.26  1.37  1.48  1.61  1.74  1.84  1.89  1.92
         128   |       1.28  1.40  1.53  1.67  1.82  1.93  1.99  2.03
         256   |             1.43  1.56  1.71  1.86  1.98  2.05  2.08
         512   |                   1.58  1.73  1.89  2.01  2.08  2.11
        1024   |                         1.74  1.90  2.02  2.09  2.13
        2048   |                               1.91  2.03  2.10  2.14
        4096   |                                     2.04  2.10  2.14
        8192   |                                           2.11  2.14
       16384   |                                                 2.14


   The table suggests that not there is not much degradation in
   compression ratio if the compression history is reset after several



Sabin, et al                                                   [Page 17]


INTERNET DRAFT        3DES-CBC-LZS-HMAC-Replay ESP          October 1996


   thousand bytes have been processed.  Resetting after less than 1,000
   bytes is probably too soon -- the compression ratio degrades
   significantly.  But waiting longer than about 8,000 bytes gains
   little -- the compression ratio does not increase much.


















































Sabin, et al                                                   [Page 18]