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

Versions: 03                                                            
Network Working Group                           W A Simpson [DayDreamer]
Internet Draft                                      P Metzger [Piermont]
                                                       P Karn [Qualcomm]
                                                Naganand Doraswamy [Bay]
expires in six months                                          July 1998


                      The ESP Triple DES Transform
                    draft-simpson-esp-des3v2-03.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 (Northern Europe)
      ftp.nis.garr.it (Southern Europe)
      ftp.ietf.org (Eastern USA)
      ftp.isi.edu (Western USA)
      munnari.oz.au (Pacific Rim)

   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) William Allen Simpson, Perry Metzger and Philip Karn
   (1994-1995).  Copyright (C) William Allen Simpson, Perry Metzger,
   Philip Karn and Naganand Doraswamy (1997-1998).  All Rights Reserved.









Simpson, Metzger          expires in six months                 [Page i]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


Abstract

   This document describes the 'Triple' DES-EDE3-CBC block cipher trans-
   form interface used with the IP Encapsulating Security Payload (ESP).















































Simpson, Metzger          expires in six months                [Page ii]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


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, colloquially known as "Triple DES", processes each
   block three times, each time with a different key [Tuchman79].

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

   For more explanation and implementation information for Triple DES,
   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

   There were a number of US patents (see [Schneier95] for listing).
   All patents have expired.  Several freely available implementations
   have been published world-wide.


1.2.  Performance

   As this specification requires "outer" chaining, it is not possible
   to provide parallel computation for the same data stream.

   The DES "initial" and "final" permutations are inverses of each
   other, so the permutations effectively cancel between the first and
   second and the second and third steps.  A significant performance
   improvement can be obtained by removing these "inner" permutations
   entirely.  Thus, "triple DES" is approximately 2.5 times slower than
   "single DES".

   Phil Karn has tuned DES-EDE3-CBC software to achieve 6.22 Mbps with a
   133 MHz Pentium, compared with 15.9 Mbps for "single" DES-CBC on the



Simpson, Metzger          expires in six months                 [Page 1]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


   same machine.  This software is freely available on the
   www.cryptography.org site.  Other DES speed estimates may be found at
   [Schneier95, page 279].  Your mileage may vary.


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

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

   In DES-EDE3-CBC, the algorithms are an encryption (Ek1), followed by
   a decryption (Dk2), followed by an encryption (Ek3).  Each step uses
   an independant key: k1, k2 and k3.

   To decrypt, the order of the functions is reversed: decrypt with k3,
   encrypt with k2, decrypt with k1.

   Note that when a pair of keys (k1 and k2 or k2 and k3) are the same,
   DES-EDE3-CBC is equivalent to DES-CBC.  This property allows the DES-
   EDE3 hardware implementations to operate in DES mode without modifi-
   cation.


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-EDE3-CBC requires an Initialization Vector (IV) that is 64-bits
   (8 bytes) in length.  By default, the IV is carried immediately fol-
   lowing the ESP Sequence Number.





Simpson, Metzger          expires in six months                 [Page 2]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


4.  Keys

   The secret DES-EDE3 keys shared between the communicating parties are
   effectively 168-bits long, but are represented as a 192-bit (24 byte)
   quantity.

   The keys consist of three independent 56-bit quantities used by the
   DES algorithm.  Each of the three 56-bit keys is stored as a 64-bit
   (8 byte) quantity, with the least significant bit of each byte used
   as a parity bit.


4.1.  Weak Keys

   DES has 64 known weak keys, including so-called semi-weak keys and
   possibly-weak keys [Schneier95, pp 280-282].  The likelihood of pick-
   ing one at random is negligible.

   For DES-EDE3, there is no known need to reject weak or complementa-
   tion keys.  Any weakness is likely to be obviated by the other keys.

   However, since checking for weak keys is quite easy, conformant
   implementations MUST test for weak DES keys.

   Moreover, when operating as DES-EDE3, each key MUST NOT be the same
   as the preceding key.


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 SHOULD be rejected.  In either case, a warning
   SHOULD be displayed.










Simpson, Metzger          expires in six months                 [Page 3]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


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
   each 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 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 keys.  Depending on the average size of the datagrams, the
   keys SHOULD be changed at least as frequently as 2**30 datagrams.


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)
      Although automated LifeTimes are internally maintained in seconds,
      manually configured LifeTimes are generally measured in days to
      promote ease of configuration.

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

   Key
      Three 56-bit keys, with parity included as appropriate, are con-
      figured in order as a 192-bit quantity.




Simpson, Metzger          expires in six months                 [Page 4]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


   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.


Security Considerations

   Users need to understand that the quality of the security provided by
   this specification depends completely on the strength of the Triple
   DES 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 biggest practical vulnerability of any software security system
   is protecting the memory containing the keys.  No system can remain
   secure when its key storage is insecure.  If this key storage is man-
   aged by an operating system, then the combination is no more secure
   than the operating system itself.  Even when the OS is secure against
   external attack, there is always the possibility of physical compro-
   mise.

   It was originally thought that DES might be a group, but it has been
   demonstrated that it is not [CW92].  Since DES is not a group, compo-
   sition of multiple rounds of DES is not equivalent to simply using
   DES with a different key.

   Triple DES with independent keys is not, as naively might be
   expected, as difficult to break by brute force as a cryptosystem with
   three times the keylength.  A space/time tradeoff has been shown
   which can brute-force break triple block encryptions in the time
   naively expected for double encryption [MH81].

   However, "double" DES (DES-EE2) can be broken with a meet-in-the-
   middle attack, without significantly more complexity than breaking
   DES requires [ibid].  DES-EDE3 with three independant keys is actu-
   ally needed to provide significantly more security than "single" DES.

   An attack has been shown on DES-EDE2 (using only two independent
   keys) [Tuchman79] that is somewhat (sixteen times) faster than
   exhaustive search [OW91].  Again, DES-EDE3 with three independant
   keys is actually needed to provide the expected level of security.

   Although it is widely believed that DES-EDE3 is substantially
   stronger than single DES alone, as it is less amenable to brute force



Simpson, Metzger          expires in six months                 [Page 5]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


   attack, it should be noted that real cryptanalysis of DES-EDE3 might
   not use brute force methods at all.  Instead, it might be performed
   using variants on differential [BS93] or linear [Matsui94] cryptanal-
   ysis.

   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-EDE3 prove weak.


Changes from RFC-1851:

   Updated performance estimates.  Replaced erroneous text about paral-
   lel computation.

   Details of CBC are moved to an informational document, to be used by
   multiple algorithms.

   The explicit 64-bit version of the IV is specified as a default.
   Compatibility and enhancement options are moved to an informational
   document.

   Implementation details by Karn were found to be common to many ESP
   Ciphers, and are awaiting consolidation in the ESP specification.

   Updated security considerations.

   Added an operational section.

   Updated acknowledgements, references, and contacts.

   Reorganized according to the "road map" document.














Simpson, Metzger          expires in six months                 [Page 6]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


Acknowledgements

   The basic field naming and layout is based on "swIPe" [IBK93, IB93].

   Some of the text of this specification was derived from work by Ran-
   dall Atkinson for the SIP, SIPP, and IPv6 Working Groups.

   Perry Metzger provided the original Security Considerations text,
   some of which is distributed throughout the document.

   William Allen Simpson was responsible for the name and semantics of
   the SPI, editing and formatting.

   Steve Bellovin, Angelos Keromytis, Holger Kummert, and Rodney Thayer
   provided useful critiques of earlier versions of this document.


References

   [Bellovin96]
               Bellovin, S., "Problem Areas for the IP Security Proto-
               cols", Proceedings of the Sixth Usenix Security Sympo-
               sium, July 1996.

   [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.

   [CW92]      Campbell, K.W., and Wiener, M.J., "Proof that DES Is Not
               a Group", Advances in Cryptology -- Crypto '92 Proceed-
               ings, Berlin: Springer-Verlag, 1993, pp 518-526.

   [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.



Simpson, Metzger          expires in six months                 [Page 7]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


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

   [IB93]      Ioannidis, J., and Blaze, M., "The Architecture and
               Implementation of Network-Layer Security Under Unix",
               Proceedings of the Fourth Usenix Security Symposium,
               Santa Clara California, October 1993.

   [IBK93]     Ioannidis, J., Blaze, M., and Karn, P., "swIPe: Network-
               Layer Security for IP", Presentation at the 26th Internet
               Engineering Task Force, Columbus Ohio, March 1993.

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

   [MH81]      Merkle, R.C., and Hellman, M., "On the Security of Multi-
               ple Encryption", Communications of the ACM, v. 24 n. 7,
               1981, pp. 465-467.

   [OW91]      van Oorschot, P.C., and Weiner, M.J.  "A Known-Plaintext
               Attack on Two-Key Triple Encryption", Advances in Cryp-
               tology -- Eurocrypt '90 Proceedings, Berlin: Springer-
               Verlag, 1991, pp. 318-325.

   [RFC-1570]  Simpson, W., "PPP LCP Extensions", DayDreamer, January
               1994.

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

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

   [RFC-1829]  Karn, P., Metzger, P., Simpson, W.A., "The ESP DES-CBC
               Transform", August 1995.

   [RFC-2119]  Bradner, S., "Key words for use in RFCs to Indicate
               Requirement 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, Metzger          expires in six months                 [Page 8]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


   [Tuchman79] Tuchman, W, "Hellman Presents No Shortcut Solutions to
               DES", IEEE Spectrum, v. 16 n. 7, July 1979, pp. 40-41.



Contacts

   Comments about this document should be discussed on the ipsec@tis.com
   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

          wsimpson@UMich.edu
          wsimpson@GreenDragon.com (preferred)


      Perry Metzger
      Piermont Information Systems Inc.
      160 Cabrini Blvd., Suite #2
      New York, NY  10033

          perry@piermont.com


      Phil Karn
      Qualcomm, Inc.
      6455 Lusk Blvd.
      San Diego, California  92121-2779

          karn@qualcomm.com
          karn@unix.ka9q.ampr.org (preferred)


      Naganand Doraswamy
      Bay Networks
      3 Federal Street  #BL3-04
      Billerica, Massachusetts  01821

          naganand@BayNetworks.Com






Simpson, Metzger          expires in six months                 [Page 9]


DRAFT                       ESP DES-EDE3-CBC                   July 1998


Full Copyright Statement

   Copyright (C) William Allen Simpson, Perry Metzger and Philip Karn
   (1994-1995).  Copyright (C) William Allen Simpson, Perry Metzger,
   Philip Karn and Naganand Doraswamy (1997-1998).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this doc-
   ument itself may not be modified in any way, except as required to
   translate it into languages other than English.

   This document and the information contained herein is provided on an
   "AS IS" basis and the author(s) DISCLAIM ALL WARRANTIES, EXPRESS OR
   IMPLIED, INCLUDING (BUT NOT LIMITED TO) ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.































Simpson, Metzger          expires in six months                [Page 10]