[3044] in cryptography@c2.net mail archive
DES Applicability Statement for Historic Status
daemon@ATHENA.MIT.EDU (William Allen Simpson)
Wed Jul 22 16:32:55 1998
Date: Wed, 22 Jul 1998 13:29:07 -0400
To: cryptography@c2.net
From: William Allen Simpson <wsimpson@greendragon.com>
I'm looking for additional references and comments for this prospective draft,
although it must be kept as blunt and concise as possible. Any ideas?
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.
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 issued a series of challenges to demon-
strate the current effectiveness of various key lengths. Each chal-
lenge has a shorter time for completion.
The first DES challenge of January, 1997, was solved in 140 days on
June 17, 1997, but only searching 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 `OStrong cryptography makes the world a safer place.'O
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
thousands of Internet hosts in their spare time. The hidden message
was "Many hands make light work."
The third DES challenge of June 13, 1998, was solved by June 16,
1998, after only 2.5 days, rather than the anticipated 10 days. The
winner was a single purpose built machine sponsored by Electronic
Frontier Foundation (EFF). The hidden message was "It's time for
those 128-, 192-, and 256-bit keys."
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 for long-term use [DH77]. Since
that time, numerous studies have predicted the work factors of vari-
ous key lengths, and the trade-offs between cost, memory, and time
[Schneier95, which newer papers should we cite?]
2.2. Time
Since 1977, the analytic community has 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 every 3.5
hours. This amount is within the reach of most governments and large
organizations. Anecdotal evidence suggests that some governments
have built such a machine.
It has been suggested that DES might still be useful for short-lived
data. The DES challenge has shown that the cost versus time for
recovery curve has advanced more rapidly than predicted. A deter-
mined attacker has or will soon have the capability to recover any
DES key within seconds.
2.3. Value
The reported cost of non-recurrent engineering and first prototype
for the EFF machine was 250 thousand US Dollars, and can recover any
key in under 7 days. Additional machines can be built for 50 thou-
sand US Dollars [???]. This amount is well within the reach of most
small organizations.
Assuming that a 50 thousand US Dollar DES cracking machine has a use-
ful service lifetime of 3 or more years, the amortized cost of recov-
ering any single key is less than 320 US Dollars. This is signifi-
cantly less than the value of common consumer transactions.
Moveover, the cost of deploying and maintaining Internet firewalls
and Virtual Private Networks exceeds the cost of recovering the DES
confidential data. There is no longer any cost benefit over sending
the datagrams as cleartext.
Furthermore, DES confidential data of any significant value in the
past 20 years has become a ripe target for key recovery.
3. Recommendations
Key lengths less than 80 bits are not acceptable for protecting
short-lived Internet data.
Key lengths less than 128 bits are not acceptable for protecting
long-lived Internet data.
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 compromised.
Security Considerations
Specific security limitations are described in the relevant sections.
Acknowledgements
References
[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., "Cryptogrpahic Technology: Fifteen Year For-
cast", BNR Inc., January 1981.
[FIPS-46] US National Bureau of Standards, "Data Encryption Stan-
dard", Federal Information Processing Standard (FIPS)
Publication 46, January 1977.
[Hellman79] Hellman, M.E., "DES Will Be Totally Insecure within Ten
Years", IEEE Spectrum, v 16 n 7, July 1979.
[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.
