In This chapter:
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.+
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
_______________________
Michael J. Wiener, Entrust Technologies, 750 Heron Road, Suite E08, Ottawa, Ontario, Canada K1V 1A7
This article first appeared in RSA Laboratories' Autumn 1997 Cryptobytes newsletter; it is reprinted with permission from the author and RSA Data Security, Inc.
* R. Rivest, "The RC5 Encryption Algorithm", Fast Software Encryption--Lecture Notes in Computer Science (1008), pp. 86-96. Springer, 1995.
+ 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.
11-1
11-2
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.
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.
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.
| Key Search Machine Cost | Expected Search Time |
$10,000 |
2.5 days |
$100,000 |
6 hours |
$1,000,000 |
35 minutes |
$10,000,000 |
3.5 minutes |
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.
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
_____________________
* 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 ftp://ripem.msu.edu/pub/crypt/docs/des-keysearch.ps.
11-3
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.
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.
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.
Avoiding Known Plaintext
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.
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
_____________________
* 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 http://www.bsa.org/policy/encryption/cryptographers.html.
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.
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.
Frequent Key Changes
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.
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.