Internet Info 1997 December/Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso/drafts/draft_ietf_i/draft-ietf-ipsec-ciph-desx-00.txt

Text File | 1997-07-03 | 20KB | 607 lines

Network Working Group                                        W A Simpson
Internet Draft                                              [DayDreamer]
                                                               R Baldwin
                                                     [RSA Data Security]
expires in six months                                          July 1997


                     The ESP DES-XEX3-CBC Transform
                    draft-ietf-ipsec-ciph-desx-00.txt


Status of this Memo

   This document is an Internet-Draft.  Internet Drafts are working doc-
   uments of the Internet Engineering Task Force (IETF), its Areas, and
   its Working Groups.  Note that other groups may also distribute work-
   ing documents as Internet Drafts.

   Internet Drafts are draft documents valid for a maximum of six
   months, and may be updated, replaced, or obsoleted by other documents
   at any time.  It is not appropriate to use Internet Drafts as refer-
   ence material, or to cite them other than as a ``working draft'' or
   ``work in progress.''

   To learn the current status of any Internet-Draft, please check the
   ``1id-abstracts.txt'' listing contained in the internet-drafts Shadow
   Directories on:

      ftp.is.co.za (Africa)
      nic.nordu.net (Europe)
      ds.internic.net (US East Coast)
      ftp.isi.edu (US West Coast)
      munnari.oz.au (Pacific Rim)

   Distribution of this memo is unlimited.

Abstract

   This document describes the "DESX" DES-XEX3-CBC block cipher trans-
   form interface used with the IP Encapsulating Security Payload (ESP).











Simpson & Baldwin         expires in six months                 [Page i]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


1.  Introduction

   The Encapsulating Security Payload (ESP) [RFC-1827x] provides confi-
   dentiality for IP datagrams by encrypting the payload data to be pro-
   tected.  This specification describes the ESP use of a variant of the
   Cipher Block Chaining (CBC) mode of the US Data Encryption Standard
   (DES) algorithm [FIPS-46, FIPS-46-1, FIPS-74, FIPS-81].

   This variant, also known as "DESX", processes each block three times,
   each time with a different key [Kaliski96].  The first and last pass
   are a simple and fast XOR.  This was originally proposed by Ron
   Rivest in May of 1984 as a computationally cheap mechanism to protect
   DES against exhaustive key-search attacks.

   Although XOR of a constant value over multiple blocks would not nor-
   mally be considered cryptographically secure, the use of DES-CBC in
   the middle provides a background of highly random internal chaining.
   The XOR values are combined with these random blocks to provide a
   modest improvement in strength.

   For an explanation of the use of CBC mode with this cipher, see [RFC-
   wwww].

   For more explanation and implementation information for DESX, see
   [Schneier95].

   This document assumes that the reader is familiar with the related
   document "Security Architecture for the Internet Protocol"
   [RFC-1825x], that defines the overall security plan for IP, and pro-
   vides important background for this specification.

   In this document, the key words "MAY", "MUST", "recommended",
   "required", and "SHOULD", are to be interpreted as described in
   [RFC-2119].


1.1.  Availability

   The DESX algorithm has been previously described in [Kaliski96,
   Schneier95].  This algorithm is not protected by either patent or
   trade secret laws, though the DESX name is a trademark of RSA Data
   Security, a wholly owned subsidary of Security Dynamics Inc.  Trade-
   mark fair-use laws allow vendors to label a product as being compati-
   ble with DESX.  An implementation of DESX is available in RSA's BSAFE
   cryptography toolkit and interoperable implementations have been cre-
   ated outside of the United States.





Simpson & Baldwin         expires in six months                 [Page 1]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


1.2.  Performance

   The additional computational cost beyond DES is negligible.


2.  Description
2.1.  Block Size

   The US Data Encryption Standard (DES) algorithm operates on blocks of
   64-bits (8 bytes).  This often requires padding before encrypting,
   and subsequent removal of padding after decrypting.

   The output is the same number of bytes that are input.  This facili-
   tates in-place encryption and decryption.


2.2.  Mode

                      P1             P2             Pi
                      |              |              |
               IV->->(X)    +>->->->(X)    +>->->->(X)
                      |     ^        |     ^        |
                      v     ^        v     ^        v
               k1->->(X)    ^ k1->->(X)    ^ k1->->(X)
                      |     ^        |     ^        |
                      v     ^        v     ^        v
                   +-----+  ^     +-----+  ^     +-----+
               k2->|  E  |  ^ k2->|  E  |  ^ k2->|  E  |
                   +-----+  ^     +-----+  ^     +-----+
                      |     ^        |     ^        |
                      v     ^        v     ^        v
               k3->->(X)    ^ k3->->(X)    ^ k3->->(X)
                      |     ^        |     ^        |
                      +>->->+        +>->->+        +>->->
                      |              |              |
                      C1             C2             Ci

   The DES-XEX3-CBC algorithm is a simple variant of the DES-CBC algo-
   rithm [RFC-wwww, RFC-1829x].

   In DES-XEX3-CBC, an Initialization Vector (IV) is XOR'd with the
   first 64-bit (8 byte) plaintext block (P1), and with a block-sized
   key (Xk1).  A keyed DES encryption (Ek2) is followed by another XOR
   (Xk3), and generates the ciphertext (C1) for the block.  Each itera-
   tion uses an independant key: k1, k2 and k3.

   For successive blocks, the previous ciphertext block is XOR'd with
   the current plaintext (Pi).  The keyed DES-XEX3 encryption function



Simpson & Baldwin         expires in six months                 [Page 2]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


   generates the ciphertext (Ci) for that block.

   To decrypt, the order of the functions is reversed: XOR with k3,
   decrypt with k2, XOR with k1, and XOR the previous ciphertext block.


2.3.  Interaction with Authentication

   There is no known interaction of DES with any currently specified
   Authenticator algorithm.  Never-the-less, any Authenticator MUST use
   a separate and independently generated key.


3.  Initialization Vector

   DES-XEX3-CBC requires an Initialization Vector (IV) that is 64-bits
   (8 bytes) in length [RFC-wwww].

   By default, the 64-bit IV is generated from the 32-bit SPI field fol-
   lowed by (concatenated with) the 32-bit Sequence Number field.  Then,
   the bit-wise complement of the 32-bit Sequence Number value is XOR'd
   with the first 32-bits (SPI).

      (SPI ^ -SN) || SN

   Alternative IV generation techniques MAY be specified when dynami-
   cally configured via a key management protocol.

   Security Notes:

      In a dynamic environment, the same data stream might be sent with
      more than one key.  Including the changed SPI in the IV generation
      prevents analysis based on common leading blocks.

      Using the Sequence Number provides an easy method for preventing
      IV repetition, and is sufficiently robust for practical use with
      the DES algorithm.  Inclusion of the bit-wise complement ensures
      that Sequence Number bit changes are reflected twice in the IV.


4.  Keys

   The secret DES-XEX3 key shared between the communicating parties is
   effectively 184-bits long.  This key consists of three independent
   quantities: a 64-bit sub-key used by an XOR, a 56-bit sub-key used by
   the DES algorithm, and another 64-bit sub-key used by an XOR.  The
   middle 56-bit sub-key is stored as a 64-bit (8 byte) quantity, with
   the least significant bit of each byte used as a parity bit.



Simpson & Baldwin         expires in six months                 [Page 3]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


4.1.  Weak Keys

   DES has 64 known weak keys, including so-called semi-weak keys and
   possibly-weak keys [Schneier95, pp 280-282].  Implementations SHOULD
   take care not to select weak keys [CN94], although the likelihood of
   picking one at random is negligible.


4.2.  Manual Key Management

   When configured manually, three independently generated keys are
   required, in the order used for encryption, and 64-bits (8 bytes) are
   configured for each individual key.

   Keys with incorrect parity SHOULD be rejected by the configuration
   utility, ensuring that the keys have been correctly configured.

   Each key is examined sequentially, in the order used for encryption.
   A key that is identical to a previous key MAY be rejected.  The 64
   known weak DES keys [RFC-1829x] SHOULD be rejected.


4.3.  Automated Key Management

   When configured via a Security Association management protocol, three
   independently generated keys are required, in the order used for
   encryption, and 64-bits (8 bytes) are returned for each individual
   key.

   The key manager MAY be required to generate the correct parity for
   the DES key.  Alternatively, the least significant bit of each key
   byte is ignored, or locally set to parity by the DES implementation.

   Each key is examined sequentially, in the order used for encryption.
   A key that is identical to a previous key MUST be rejected.  The 64
   known weak DES keys [RFC-1829x] (for the DES key) MUST be rejected.


4.4.  Refresh Rate

   To prevent differential and linear cryptanalysis of collisions [RFC-
   wwww], no more than 2**32 plaintext blocks SHOULD be encrypted with
   the same key.  Depending on the average size of the datagrams, the
   key SHOULD be changed at least as frequently as 2**30 datagrams.







Simpson & Baldwin         expires in six months                 [Page 4]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


5.  ESP Alterations
5.1.  ESP Sequence Number

   The Sequence Number is a 32-bit (4 byte) unsigned counter.  This
   field protects against replay attacks, and may also be used for syn-
   chronization by stream or block-chaining ciphers.

   When configured manually, the first value sent SHOULD be a random
   number.  The limited anti-replay security of the sequence of data-
   grams depends upon the unpredictability of the values.

   When configured via an automated Security Association management pro-
   tocol, the first value sent is 1, unless otherwise negotiated.

   Thereafter, the value is monotonically increased for each datagram
   sent.  A replacement SPI SHOULD be established before the value
   repeats.  That is, no more than 2**32 datagrams SHOULD be sent with
   any single key.


5.2.  ESP Padding

   The Padding field may be zero or more bytes in length.

   Prior to encryption, this field is filled with a series of integer
   values to align the Pad Length and Payload Type fields at the end of
   a 64-bit (8 byte) block boundary (measured from the beginning of the
   Transform Data).

   By default, each byte contains the index of the byte.  For example,
   three pad bytes would contain the values 1, 2, 3.

   After decryption, this field MAY be examined for a valid series of
   integer values.  Verification of the sequence of values is at the
   discretion of the receiver.
















Simpson & Baldwin         expires in six months                 [Page 5]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


Operational Considerations

   The specification provides only a few manually configurable parame-
   ters:

   SPI
      Manually configured SPIs are limited in range to aid operations.
      Automated SPIs are pseudo-randomly distributed throughout the
      remaining 2**32 values.

      Default: 0 (none).  Range: 256 to 65,535.

   SPI LifeTime (SPILT)
      Manually configured LifeTimes are generally measured in days.
      Automated LifeTimes are specified in seconds.

      Default: 32 days (2,764,800 seconds).  Maximum: 182 days
      (15,724,800 seconds).

   Replay Window
      Long term replay prevention requires automated configuration.
      This check must only be used with those peers that have imple-
      mented this feature.

      Default: 0 (checking off).  Range: 32 to 256.

   Pad Values
      All implementations use verifiable values.

      Also, some operations desire additional padding to inhibit traffic
      analysis.

      Default: 7 (checking on).  Range: 7 to 255.

   Key
      A 64-bit key, a 56-bit key with parity included as appropriate,
      and another 64-bit key, are configured in order as a 192-bit quan-
      tity.

   Each party configures a list of known SPIs and symmetric secret-keys.

   In addition, each party configures local policy that determines what
   access (if any) is granted to the holder of a particular SPI.  For
   example, a party might allow FTP, but prohibit Telnet.  Such consid-
   erations are outside the scope of this document.






Simpson & Baldwin         expires in six months                 [Page 6]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


Security Considerations

   Users need to understand that the quality of the security provided by
   this specification depends completely on the strength of the DESX
   algorithm, the correctness of that algorithm's implementation, the
   security of the Security Association management mechanism and its
   implementation, the strength of the key [CN94], and upon the correct-
   ness of the implementations in all of the participating nodes.

   The padding bytes have a predictable value.  They provide a small
   measure of tamper detection on their own block and the previous block
   in CBC mode.  This makes it somewhat harder to perform splicing
   attacks, and avoids a possible covert channel.  This small amount of
   known plaintext does not create any problems for modern ciphers.

   It has been shown that DES-XEX3 is substantially stronger than DES
   alone, as it is less amenable to brute force attack with an exhaus-
   tive key search.  When the number of plaintext blocks are limited to
   2**32 as recommended, the time complexity of the idealized random
   permutation block cipher model is increased from an order 2**86 (for
   DES) to 2**134 (for DES-EXE3) [Kilian96, Rogaway96].

   It should be noted that real cryptanalysis of DES-XEX3 might not use
   brute force methods at all.  Instead, it might be performed using
   variants on differential [BS93] or linear [Matsui94] cryptanalysis.
   It has been estimated that differential cryptanalysis is increased
   from 2**47 (for DES) to 2**61 chosen-plaintext blocks, and linear
   cryptanalysis is increased from 2**43 (for DES) to 2**60 known-
   plaintext blocks [Kaliski96].  Although these attacks are not consid-
   ered practical, this offers only a small improvement over DES alone.

   It should also be noted that no encryption algorithm is permanently
   safe from brute force attack, because of the increasing speed of mod-
   ern computers.

   As with all cryptosystems, those responsible for applications with
   substantial risk when security is breeched should pay close attention
   to developments in cryptology, and especially cryptanalysis, and
   switch to other transforms should DES-XEX3 prove weak.












Simpson & Baldwin         expires in six months                 [Page 7]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


Acknowledgements

   Most of the text of this specification was derived from earlier work
   by Perry Metzger and William Allen Simpson in multiple Request for
   Comments.

   Use of DES-XEX3 was proposed by William Allen Simpson and various
   other participants in the IETF IP Security Working Group in 1995 and
   1996, but was prevented from publication through disregard of the
   IETF Standards Process.


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.

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

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

   [FIPS-74]
            US National Bureau of Standards, "Guidelines for Implement-
            ing and Using the Data Encryption Standard", Federal Infor-
            mation Processing Standard (FIPS) Publication 74, April
            1981.

   [FIPS-81]
            US National Bureau of Standards, "DES Modes of Operation"
            Federal Information Processing Standard (FIPS) Publication
            81, December 1980.

   [Kaliski96]
            Kaliski, B., and Robshaw, M., "Multiple Encryption: Weighing
            Security and Performance", Dr. Dobbs Journal, January 1996.





Simpson & Baldwin         expires in six months                 [Page 8]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


   [Kilian96]
            Kilian J., and Rogaway, P., "How to protect DES against
            exhaustive key search", Advances in Cryptology -- Crypto '96
            Proceedings, Berlin: Springer-Verlag, 1996,
            http://wwwcsif.cs.ucdavis.edu/~rogaway.

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

   [Rogaway96]
            Rogaway, P., "The Security of DESX", CryptoBytes, v 2 n 2,
            RSA Laboratories, Redwood City, CA, USA, Summer 1996.

   [RFC-1825x]
            Atkinson, R., "Security Architecture for the Internet Proto-
            col", Naval Research Laboratory, July 1995.

   [RFC-1827x]
            Simpson, W., "IP Encapsulating Security Protocol (ESP) for
            implementors",

   [RFC-1829x]
            Karn, P., Metzger, P., Simpson, W.A., "The ESP DES-CBC
            Transform", work in progress.

   [RFC-2119]
            Bradner, S., "Key words for use in RFCs to Indicate Require-
            ment Levels", BCP 14, Harvard University, March 1997.

   [RFC-wwww]
            Simpson, W.A, "ESP with Cipher Block Chaining (CBC)", work
            in progress.

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













Simpson & Baldwin         expires in six months                 [Page 9]
DRAFT                       ESP DES-XEX3-CBC                   July 1997


Contacts

   Comments about this document should be discussed on the [e-mail]
   mailing list.

   Questions about this document can also be directed to:

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

          [e-mail]
          [e-mail] (preferred)
          [e-mail]


      Robert Baldwin
      RSA Data Security Inc.
      100 Marine Parkway
      Redwood City, California  94065

          [e-mail]



























Simpson & Baldwin         expires in six months                [Page 10]