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

Versions: 00 01                                                         
Network Working Group                           W A Simpson [DayDreamer]
Internet Draft                            S Bradner [Harvard University]
expires in six months                                        August 1998


            DES Applicability Statement for Historic Status
                      draft-simpson-des-as-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 (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 and Scott Bradner (1998).  All
   Rights Reserved.

Abstract

   "The ESP DES-CBC Transform" [RFC-1829] and "The PPP DES Encryption
   Protocol" [RFC-1969] have been re-classified to Historic status, and
   implementation is Not Recommended.  This Applicability Statement pro-
   vides the supporting motivation for that classification.  The primary
   reason is that DES alone provides insufficient strength for the pro-
   tection of moderate value information for any length of time.



Simpson, Bradner          expires in six months                 [Page i]


DRAFT                            DES AS                      August 1998


1.  Introduction

   The US Data Encryption Standard (DES) algorithm [FIPS-46] has had a
   long history of analysis since its adoption in 1977.  At the time of
   RFC-1829 publication in 1995, briefly citing the current analysis and
   describing known limitations, it was suggested that DES was not a
   good algorithm for the protection of moderate value information.
   However, the level of confidentiality provided by the use of DES in
   the Internet environment was considered greater than sending the
   datagrams as cleartext.

   Recently, RSA Data Security has issued a series of challenges to
   demonstrate the current effectiveness of various algorithms and key
   lengths.  Each challenge has a shorter time for completion.

   The first DES challenge of January, 1997, was solved in 140 days on
   June 17, 1997, after searching only 25% of the key space.  On aver-
   age, half of the key space can be expected to be searched.  Much of
   the time was spent organizing competing volunteer efforts.  The hid-
   den message was "Strong cryptography makes the world a safer place."

   The second DES challenge of January 13, 1998, was solved in 40 days
   on February 23, 1998, after searching over 88% of the key space using
   tens of thousands of Internet hosts in their spare time.  The hidden
   message was "Many hands make light work."

   The third DES challenge of July 13, 1998, was solved on July 16,
   1998, after only 2.5 days!  The winner was a single purpose built
   machine sponsored by Electronic Frontier Foundation (EFF) [EFF98].
   The hidden message was "It's time for those 128-, 192-, and 256-bit
   keys."

   This demonstrated that the cost of deploying and maintaining Internet
   firewalls and Virtual Private Networks can easily exceed the cost of
   recovering DES protected confidential data.  For protection against
   governmental or industrial espionage, the use of DES in the Internet
   environment no longer has any cost benefit over sending the datagrams
   as cleartext.













Simpson, Bradner          expires in six months                 [Page 1]


DRAFT                            DES AS                      August 1998


2.  Problems

   DES has a number of problems that restrict its usability in the
   global Internet.


2.1.  Key Length

   Even at the time of DES publication, the analytic community ques-
   tioned the DES 56-bit key length as insufficient for long-term use
   [DH77].  In 1987, the US National Security Administration raised
   objections to re-certifying DES as a US Federal Information Process-
   ing Standard [SB88].  Never-the-less, after much discussion, DES was
   re-certified [FIPS46-1], and again in 1993.

   The DES certification expires in 1998, and the US has begun a public
   process for evaluating replacements with longer key lengths.  This
   successor requires 128-, 192-, and 256-bit key lengths.

   Numerous studies have predicted the work factor of various key
   lengths, and the trade-offs between cost, memory, and time.  See
   [Schneier95, Chapter 7], which recommends a minimum of 112-bit keys,
   and shows that 128-bit keys would be immune to parallel computation
   by conventional computer equipment and recovery of 256-bit keys might
   be limited by the energy available in the solar system.

   The most recent analysis for symmetric keys [BDRSSTW96] empirically
   estimated that a minimum of 75-bit keys would be required in the
   short-term, and strongly recommends a minimum of 90-bit keys for
   future long-term standards.


2.2.  Recovery Time

   Shortly after DES publication, the analytic community predicted a
   purpose-built DES cracking machine could be built for 10 to 20 mil-
   lion US Dollars that would recover a key within 1 to 2 days [DH77,
   Hellman79, Diffie81].  More recently, [Weiner94] sketched the design
   of a DES cracking machine for 1 million US Dollars that would recover
   a key in an average of 3.5 hours.  These costs were within the reach
   of most governments and large organizations.  Anecdotal evidence sug-
   gests that some governments may have built such a machine.

   The progression of the RSA challenges anticipated that the dis-
   tributed software network could finish the third challenge in 10
   days.  A recent paper [BDRSSTW96] estimated that a relatively inex-
   pensive "off-the-shelf technology" 300 thousand US Dollar DES crack-
   ing machine would recover a key in an average of 19 days.



Simpson, Bradner          expires in six months                 [Page 2]


DRAFT                            DES AS                      August 1998


   Instead, the cost of the non-recurrent engineering and first proto-
   type for the EFF DES cracking machine was under 250 thousand US Dol-
   lars [EFF98], and it completed the challenge in 2.5 days.  This is
   well within the reach of even small organizations, and has shown that
   the curve of cost versus time has advanced more rapidly than pre-
   dicted.

   It has been suggested that DES might still be useful for short-lived
   data.  This assumption is unwarranted.  Attackers with relatively
   small budgets will soon have the capability to recover 56-bit keys in
   hours or minutes.  Well-financed attackers have or will soon have the
   capability to recover any DES key within seconds.


2.3.  Value

   The specifications for the EFF DES cracking machine have been pub-
   lished [EFF98].  Additional machines can be built for the same or
   lower cost.  Assuming that a DES cracking machine has a useful ser-
   vice lifetime of 3 or more years, the amortized cost of recovering
   any single key is less than 1,200 US Dollars.  This is significantly
   less than the value of common consumer transactions.

   Morever, the cost of deploying and maintaining Internet firewalls and
   Virtual Private Networks utilizing long-term manually configured DES
   keys is considerably greater than 1,200 US Dollars per key.

   Furthermore, confidential communications and archival data of any
   significant value that was protected by DES have become a ripe target
   for key recovery.  It is frequently impractical to convert the
   archival data to a more robust algorithm.  There can be no assurance
   that all DES copies have been destroyed, and that none have been
   intercepted or compromised.

   There is no comparative advantage, and significant economic disadvan-
   tage, in continuing to use the single-DES algorithm.  A number of
   other algorithms are likely to provide significantly higher protec-
   tion for valuable information, at a cost very close to that of DES.













Simpson, Bradner          expires in six months                 [Page 3]


DRAFT                            DES AS                      August 1998


3.  Conclusions and Recommendations

   Currently deployed equipment using DES should be eliminated, or
   upgraded to a more robust algorithm and key length.

   Existing data depending upon DES for confidentiality should be con-
   sidered potentially compromised.

   Key lengths less than 80 bits are not acceptable for use in future
   standards and not recommended for use in the Internet for protecting
   short-lived Internet data.  Communication protocols with less
   strength will not be advanced on the Internet Standards Track.

   Key lengths less than 128 bits are not recommended for protecting
   long-lived Internet data.  Message and storage protocols with less
   strength should not be advanced on the Internet Standards Track.


Security Considerations

   Security issues are the topic of this entire document.

   Users need to understand that the quality of the security provided
   depends completely on the strength of the 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 correctness of the implementations in
   all of the participating nodes.


Acknowledgements

   John Gilmore provided useful critiques of earlier versions of this
   document.

















Simpson, Bradner          expires in six months                 [Page 4]


DRAFT                            DES AS                      August 1998


References

   [BDRSSTW96] Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimo-
               mura, T., Thompson, E., and Weiner, M., "Minimal Key
               Lengths for Symmetric Ciphers to Provide Adequate Commer-
               cial Security",
               ftp://ftp.research.att.com/dist/mab/keylength, January
               1996.

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

   [DH77]      Diffie, W., and Hellman, M.E., "Exhaustive Cryptanalysis
               of the NBS Data Encryption Standard", Computer, v 10 n 6,
               June 1977.

   [Diffie81]  Diffie, W., "Cryptographic Technology: Fifteen Year Fore-
               cast", BNR Inc., January 1981.

   [EFF98]     Electronic Frontier Foundation, Gilmore, J., Editor,
               "Cracking DES: Secrets of Encryption Research, Wiretap
               Politics, and Chip Design", O'Reilly and Associates, July
               1998.

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

   [Hellman79] Hellman, M.E., "DES Will Be Totally Insecure within Ten
               Years", IEEE Spectrum, v 16 n 7, July 1979.

   [SB88]      Smid, M.E., and Branstad, D.K., "The Data Encryption
               Standard: Past and Future", Proceedings of the IEEE, v 76
               n 5, May 1988.

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

   [Weiner94]  Wiener, M.J., "Efficient DES Key Search", School of Com-
               puter Science, Carleton University, Ottawa, Canada,
               TR-244, May 1994.  Presented at the Rump Session of
               Crypto '93.



Simpson, Bradner          expires in six months                 [Page 5]


DRAFT                            DES AS                      August 1998


Contacts

   Comments about this document should be discussed on the ietf@ietf.org
   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)


      Scott Bradner
      Harvard University
      1350 Mass Ave, Room 876
      Cambridge, Massachusetts  02138

         sob@harvard.edu



Full Copyright Statement

   Copyright (C) William Allen Simpson and Scott Bradner (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, Bradner          expires in six months                 [Page 6]