chap-11.html
b4941533b428cade3092178d589e62870344a33a74a40e14ff66fba231f718ca<!DOCTYPE HTML PUBLIC "html.dtd">
<HTML>
<HEAD>
<TITLE>Cracking DES: Secrets of Encryption Research, Wiretap Politics, and
Chip Design </TITLE>
</HEAD>
<BODY BGCOLOR="#ffffff">
<H1>
<A NAME="11">11</A>
</H1>
<H2>
<I>Efficient DES Key Search An Update by Michael J. Wiener </I>
</H2>
<P>
<P>
<I>In This chapter: </I>
<P>
<UL>
<LI>
<I>Advancing Technology </I>
</UL>
<UL>
<LI>
<I>Programmable Hardware </I>
</UL>
<UL>
<LI>
<I>Conclusion </I>
</UL>
<P>
<P>
An exciting moment in the history of DES was reached in June 1997 when a
group coordinated by Rocke Verser solved RSA Data Security's DES challenge
by exhaustive key search on a large number of computers. This result was
useful because it served to underscore in a public way how vulnerable DES
has become. However, it may also have left the false impression that one
cannot do much better than attacking DES in software with a large distributed
effort. The design of DES is such that it is fairly slow in software, but
is compact and fast when implemented in hardware. As a result, using software
to attack DES gives poor performance compared to what can be achieved in
hardware. This applies not only to DES, but also to most other block ciphers,
attacks on hash functions, and attacks on elliptic curve cryptosystems. Avoiding
efficient hardware- based attacks requires the use of algorithms with
sufficiently long keys, such as triple-DES, 128-bit RC5,* and
CAST-128.<SUP>+</SUP>
<P>
In this article we assess the cost of DES key search using hardware methods
and examine the effectiveness of some proposed methods for thwarting attacks
on
<P>
_______________________
<P>
<SMALL>Michael J. Wiener, Entrust Technologies, 750 Heron Road, Suite E08,
Ottawa, Ontario, Canada K1V 1A7 </SMALL>
<P>
<SMALL>This article first appeared in RSA Laboratories' Autumn 1997 Cryptobytes
newsletter; it is reprinted with permission from the author and RSA Data
Security, Inc. </SMALL>
<P>
<SMALL>* R. Rivest, "The RC5 Encryption Algorithm", Fast Software
Encryption--Lecture Notes in Computer Science (1008), pp. 86-96. Springer,
1995. </SMALL>
<P>
<SMALL>+ C. Adams, "Constructing Symmetric Ciphers Using the CAST Design
Procedure", Designs, Codes and Cryptography, vol. 12, no. 3, pp. 283-316,
Nov. 1997. Also available as "The CAST-128 Encryption Algorithm", RFC 2144,
May 1997.</SMALL>
<P>
<I>11-1</I>
<P>
<HR>
<P>
<I>11-2</I>
<H3>
<I>Advancing Technology </I>
</H3>
<P>
The best known way to attack DES is to simply try all of the possible 56-bit
keys until the correct key is found. On average, one expects to go through
about half of the key space. In 1993, a design for an exhaustive DES key
search machine including a detailed chip design was published.* A $1 million
version of this machine used 57600 key search chips, each capable of testing
50 million keys per second. Overall, the machine could find a DES key in,
on average, three and a half hours.
<P>
About four and a half years have passed since this design was completed,
and according to Moore's Law, processing speeds should have doubled three
times in that period. Of course, estimating in this fashion is a poor substitute
for the careful analysis and design effort that went into the earlier design.
The original chip design was done in a 0.8 micron CMOS process, and with
the geometries available today, it is possible to fit four instances of the
original design into the same silicon area. In keeping with the conservative
approach to estimates in the 1993 paper, we assume here that the updated
key search chip's clock speed would increase to only 75 MHz from the original
50 MHz, making the modern version of the chip six times faster for the same
cost. It is interesting to note that just 21 of these chips would give the
same key searching power as the entire set of computers used by the team
who solved the DES challenge.
<P>
Today's version of the $1 million machine could find a DES key in, on average,
about 35 minutes (one-sixth of 3.5 hours). This time scales linearly with
the amount of money spent as shown in the following table.
<P>
<TABLE BORDER CELLPADDING="12">
<TR>
<TD><B>Key Search Machine Cost </B></TD>
<TD><B>Expected Search Time </B></TD>
</TR>
<TR>
<TD><P ALIGN="Right">
$10,000 </TD>
<TD>2.5 days</TD>
</TR>
<TR>
<TD><P ALIGN="Right">
$100,000 </TD>
<TD>6 hours</TD>
</TR>
<TR>
<TD><P ALIGN="Right">
$1,000,000 </TD>
<TD>35 minutes</TD>
</TR>
<TR>
<TD><P ALIGN="Right">
$10,000,000 </TD>
<TD>3.5 minutes</TD>
</TR>
</TABLE>
<P>
<P>
Note that the costs listed in the table do not include the cost to design
the chip and boards for the machine. Because the one-time costs could be
as high as half a million dollars, it does not make much sense to build the
cheaper versions of the machine, unless several are built for different
customers.
<P>
This key search engine is designed to recover a DES key given a
plaintext-ciphertext pair for the standard electronic-codebook (ECB) mode
of DES. However, the machine can also handle the following modes without
modification: cipher-block
<P>
_____________________
<P>
<SMALL>* Wiener, "Efficient DES Key Search", presented at the Rump session
of Crypto '93. Reprinted in Practical Cryptography for Data Internetworks,
W. Stallings, editor, IEEE Computer Society Press, pp. 31-79 (1996). Currently
available at
<A HREF="ftp://ripem.msu.edu/pub/crypt/docs/des-keysearch.ps">ftp://ripem.msu.edu/pub/crypt/docs/des-keysearch.ps</A>.</SMALL>
<P>
<HR>
<P>
<I>11-3</I>
<P>
chaining (CBC), 64-bit cipher feedback (CFB), and 64- bit output feedback
(OFB). In the case of OFB, two consecutive plaintexts are needed. The chip
design can be modified to handle two other popular modes of DES, 1-bit and
8-bit CFB, at the cost of a slightly more expensive chip. Fewer chips could
be purchased for a $1 million machine causing the expected key search time
to go up to 40 minutes for all modes, except 1-bit CFB, which would take
80 minutes, on average.
<H3>
<I>Programmable Hardware</I>
</H3>
<P>
The costs associated with chip design can present a significant barrier to
smalltime attackers and hobbyists. An alternative which has much lower start-up
costs is the use of programmable hardware. One such type of technology is
the Field Programmable Gate Array (FPGA). One can design a circuit on a PC
and download it to a board holding FPGAs for execution. In a report in early
1996,* it was estimated that $50000 worth of FPGAs could recover a DES key
in, on average, four months. This is considerably slower than what can be
achieved with a chip design, but is much more accessible to those who are
not well funded.
<P>
Another promising form of programmable hardware is the Complex Programmable
Logic Device (CPLD). CPLDs offer less design freedom and tend to be cheaper
than FPGAs, but the nature of key search designs seems to make them suitable
for CPLDs. Further research is needed to assess whether CPLDs are useful
for DES key search.
<P>
<B><I>Avoiding Known Plaintext</I></B>
<P>
The designs described to this point have relied on the attacker having some
known plaintext. Usually, a single 8-byte block is sufficient. One method
of preventing attacks that has been suggested is to avoid having any known
plaintext. This can be quite difficult to achieve. Frequently, data begins
with fixed headers. For example, each version of Microsoft Word seems to
have a fixed string of bytes that each file begins with.
<P>
For those cases where a full block of known plaintext is not available, it
is possible to adapt the key search design. Suppose that information about
plaintext is available (e.g., ASCII character coding is used), but no full
block is known. Then instead of repeatedly encrypting a known plaintext and
comparing the result to a ciphertext, we repeatedly decrypt the ciphertext
and test the candidate plaintexts against our expectations. In the example
where we expect 7-bit ASCII plaintext, only about 1 in 256 keys will give
a plaintext which has the correct form. These
<P>
_____________________
<P>
<SMALL>* M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson,
and M. Wiener, "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate
Commercial Security", currently available at
<A HREF="http://www.bsa.org/policy/encryption/cryptographers.html">http://www.bsa.org/policy/encryption/cryptographers.html</A>.</SMALL>
<P>
<HR>
<P>
keys would have to be tried on another ciphertext block. The added logic
to handle this would add just 10 to 20% to the cost of a key search chip.
<P>
Even if we only know a single bit of redundancy in each block of plaintext,
this is enough to cut the number of possible keys in half. About 56 such
blocks are needed to uniquely identify the correct key. This does not mean
that the run-time is 56 times greater than the known-plaintext case. On average,
each key is eliminated with just two decryptions. Taking into account the
cost of the added logic required makes the expected run-time for a $1 million
machine about 2 hours in this case.
<P>
<B><I>Frequent Key Changes</I></B>
<P>
A commonly suggested way to avoid key search attacks is to change the DES
key frequently. The assumption here is that the encrypted information is
no longer useful after the key is changed, which is often an inappropriate
assumption. If it takes 35 minutes to find a DES key, why not change keys
every 5 minutes? The problem with this reasoning is that it does not take
exactly 35 minutes to find a key. The actual time is uniformly distributed
between 0 and 70 minutes. We could get lucky and find the key almost right
away, or we could be unlucky and take nearly 70 minutes. The attacker's
probability of success in the 5-minute window is 5/70 = 1/14. If after each
key change the attacker gives up and starts on the next key, we expect success
after 14 key changes or 70 minutes. In general, frequent key changes cost
the attacker just a factor of two in expected run-time, and are a poor substitute
for simply using a strong encryption algorithm with longer keys.
<H3>
<I>Conclusion</I>
</H3>
<P>
Using current technology, a DES key can be recovered with a custom-designed
$1 million machine in just 35 minutes. For attackers who lack the resources
to design a chip and build such a machine, there are programmable forms of
hardware such as FPGAs and CPLDs which can search the DES key space much
faster than is possible using software on PCs and workstations. Attempts
to thwart key search attacks by avoiding known plaintext and changing keys
frequently are largely ineffective. The best course of action is to use a
strong encryption algorithm with longer keys, such as triple-DES, 128-bit
RC5, or CAST-128.
<P>
</BODY></HTML>
© 2022 Packet Storm. All rights reserved.
%7Cutmcsr%3D(direct)%7Cutmcmd%3D(none)){kind=small}
Follow us on Twitter
Follow us on Facebook
Subscribe to an RSS Feed