Network Working Group W A Simpson Internet Draft [DayDreamer] S Bradner [Harvard University] expires in six months June 1999 Internet Security Algorithms Applicability Statement draft-simpson-des-as-01.txt Status of this Memo This document is an Internet Draft, and is in full conformance with all provisions of Section 10 of RFC2026, except that the right to produce derivative works is not granted. 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 not appropriate to use Internet Drafts as reference material, or to cite them other than as "Work In Progress." The list of current Internet Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. To view the list of Internet Draft Shadow Directories, see http://www.ietf.org/shadow.html. Distribution of this memo is unlimited. Copyright Notice Copyright (C) William Allen Simpson (1998-1999). All Rights Reserved. Abstract "The PPP DES Encryption Protocol" [RFC-2419], "The ESP DES-CBC Cipher Algorithm With Explicit IV" [RFC-2405], and "The ESP DES-CBC Transform" [RFC-1829] have been re-classified to Historic status, and implementation is Not Recommended. Simpson, Bradner expires in six months [Page i] DRAFT Security Algorithms Applicability June 1999 "The PPP Triple-DES Encryption Protocol (3DESE)" [RFC-2420] and "The ESP Triple-DES Transform" [RFC-xxxx] are now classified as mandatory to implement for Standards Track interoperability. This Applicability Statement provides the supporting motivation for that classification. The primary reason is that DES alone provides insufficient strength for the protection of moderate value information for any length of time. Simpson, Bradner expires in six months [Page ii] DRAFT Security Algorithms Applicability June 1999 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 average, half of the key space can be expected to be searched. Much of the time was spent organizing competing volunteer efforts. The hidden message was "Strong cryptography makes the world a safer place." The DES challenge of January, 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 DES challenge of July 13, 1998, was solved on July 16, 1998, after only 2.5 days (56 hours)! The winner was a single purpose built machine, "Deep Crack", 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. The DES challenge of January 19, 1999, was solved in only 22 hours and 15 minutes! The winner was the EFF "Deep Crack" working together with the distributed volunteer network. The hidden message was "See you in Rome (second AES Conference, March 22-23, 1999)." The Advanced Encryption Standard (AES) initiative proposes replacing the obsolete 56-bit DES with one or more algorithms using encryption keys of at least 128-bits. Simpson, Bradner expires in six months [Page 1] DRAFT Security Algorithms Applicability June 1999 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 questioned 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 Processing 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, the Advanced Encryption Standard (AES) initiative, 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. Correspondence with some of those authors has indicated that these estimates should rise a few bits to reflect subsequent increases in computational power. Taking these recommendations together yields a range of 80-bit keys for short term use, 128-bit keys for longer term use, and 256-bit keys as standards evolve. Simpson, Bradner expires in six months [Page 2] DRAFT Security Algorithms Applicability June 1999 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 million 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 suggests that some governments may have built such a machine. The progression of the RSA challenges anticipated that the distributed software network could finish the third challenge in 10 days. A recent paper [BDRSSTW96] estimated that a relatively inexpensive "off-the-shelf technology" 300 thousand US Dollar DES cracking machine would recover a key in an average of 19 days. It turns out that these estimates were too high. The EFF was able to build an operating DES cracking machine for under 250 thousand US Dollars [EFF98]. The device, known as "Deep Crack", completed the DES challenge in only 2.5 days. This level of expenditure is well within the reach of even small organizations, and the EFF effort has shown that the curve of cost versus time has advanced more rapidly than had been predicted. It has been suggested that DES might still be useful for short-lived data. This assumption is unwarranted. Adversaries with relatively small budgets will soon have the capability to recover 56-bit keys in hours or minutes. Well-financed adversaries 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 published [EFF98]. Additional machines can be built for the same or lower cost. Assuming that a DES cracking machine has a useful service 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 Simpson, Bradner expires in six months [Page 3] DRAFT Security Algorithms Applicability June 1999 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 disadvantage, in continuing to use the single-DES algorithm. A number of other algorithms are likely to provide significantly higher protection for valuable information, at a cost very close to that of DES. 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 considered 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 must 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. "The PPP DES Encryption Protocol" [RFC-2419], "The ESP DES-CBC Cipher Algorithm With Explicit IV" [RFC-2405], and "The ESP DES-CBC Transform" [RFC-1829] have been re-classified to Historic status, and implementation is Not Recommended. "The PPP Triple-DES Encryption Protocol (3DESE)" [RFC-2420] and "The ESP Triple-DES Transform" [RFC-xxxx] are now classified as mandatory to implement for Standards Track interoperability. Simpson, Bradner expires in six months [Page 4] DRAFT Security Algorithms Applicability June 1999 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. History On July 20, 1998, William Allen Simpson, with the concurrance of Perry Metzger and Phil Karn, asked that their DES encryption Proposed Standard [RFC-1829], and the related PPP DES encryption Proposed Standard [RFC-1619], be declared Historic (removed from the Standards Track), and recommended DESX and Triple-DES as interim Proposed Standards until the selection of AES. With the assistance of Scott Bradner, this Applicability Statement was written to reflect the recommendation. Instead, the IESG approved RFC-2405 and RFC-2419 for publication as Proposed Standards in November and September, 1998, respectively. On March 18, 1999, the Security Area Advisory Group overwhelmingly approved removal of DES from the Standards Track, and recommended Triple-DES as mandatory to implement. This Applicability Statement was updated to reflect the recommendation. Acknowledgements John Gilmore provided useful critiques of earlier versions of this document. Simpson, Bradner expires in six months [Page 5] DRAFT Security Algorithms Applicability June 1999 References [BDRSSTW96] Blaze, M., Diffie, W., Rivest, R., Schneier, B., Shimomura, T., Thompson, E., and Weiner, M., "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial 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 Forecast", 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 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. [Hellman79] Hellman, M.E., "DES Will Be Totally Insecure within Ten Years", IEEE Spectrum, v 16 n 7, July 1979. [RFC-1829] Karn, P., Metzger, P., Simpson, W., "The ESP DES-CBC Transform", July 1995. [RFC-2405] Madson, C., Doraswamy, N., "The ESP DES-CBC Cipher Algorithm With Explicit IV", November 1998. [RFC-2419] Sklower, K., Meyer, G., "The PPP DES Encryption Protocol, Version 2 (DESE-bis)", September 1998. [RFC-2420] Kummert, H., "The PPP Triple-DES Encryption Protocol (3DESE)", September 1998. Simpson, Bradner expires in six months [Page 6] DRAFT Security Algorithms Applicability June 1999 [RFC-xxxx] Simpson, W., Metzger, P., Karn, P., Doraswamy, N., "The ESP Triple-DES Transform", Work In Progress, July 1998. [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 Computer Science, Carleton University, Ottawa, Canada, TR-244, May 1994. Presented at the Rump Session of Crypto '93. 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 Simpson, Bradner expires in six months [Page 7] DRAFT Security Algorithms Applicability June 1999 Full Copyright Statement Copyright (C) William Allen Simpson (1998-1999). 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 document 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 8]