This article to appear in the special May 1998 issue of ;login:.
The Data Encryption Standard (DES) has been the workhorse of cryptography for some 20 years. Its wide deployment and small (by today's standards) key size make it an interesting target for attackers. This paper discusses the first public ``crack'' of a DES-encrypted message using brute force, and shows how the sort of power necessary to reproduce this can be mustered by individuals and very small organizations with little or no funding.
We originally suggested that this work is repeatable, and have been proven correct, as DES has fallen again, and RC5-32/12/7 has been defeated by brute force. We strongly advise systems based on DES to be replaced with systems that use longer keys.
Led by Rocke Verser, Matt Curtin, and Justin Dolske, the DESCHALL effort  sought to crack RSA's DES Challenge  by means of a large-scale, distributed computing project on the Internet. We simply endeavored to try each of the 256 (over 72 quadrillion) keys that might have been used to encrypt the secret message--a brute force attack. Brute force attacks like this are naturally suited to distributed or parallel computing efforts, since they essentially consist of a large number of independent problems--the testing of each key.
Although not a new attack by any means, brute force key search has been a metric by which the security of cryptosystems are judged. If an algorithm is believed to be ``safe'', that typically means that the best known attack against the system is infeasible. Often, a ``safe'' algorithm's security is measured in terms of the cost of a brute force attack. The number of possible keys determines the feasibility of this attack.
While there has been relatively widespread belief that government intelligence agencies have had the technology and resources available to efficiently perform brute force attacks against DES, no one had ever accomplished the feat in public before this project's success. DES is still widely deployed in a variety of environments, including financial circles. DES is, therefore, a real target, and because of its relatively small key size (by today's standards), it's an attractive one.
Clients would automatically increase the size of the key blocks they requested so that they would gradually reach the point where a block of keys took about 30 minutes to test. Blocks were always 2N keys in size, where N was generally between 22 and 30.
Additionally, all messages dealing with key blocks included checksums for message integrity, since UDP (as a low-overhead protocol) does not make any such checks itself. To help prevent sabotage, the client's ``Not found'' message contained additional data, calculated during its search, to allow the server to verify that the client had actually searched the assigned keyspace.
The clients that used this protocol were designed to run on a wide variety of systems. By the end of the contest, we had 40 different clients available for a variety of different hardware and operating system combinations. All of the clients running on Intel (or compatible) and Macintosh PowerPC hardware contained hand-optimized assembly code, while the remainder of the clients were entirely done in C. Java was briefly considered, but it was quickly dropped--we already had clients for a large variety of systems, and it was generally agreed that the speed of a generic Java version would be unacceptable.
The clients were highly optimized for decrypting DES messages, using a variety of methods to optimize the DES process and detect non-winning keys as early as possible. Using these methods, a 200 MHz Pentium system was able to test approximately 1 million keys/second, and a 250 MHz PowerPC 604e based system reached 1.5 million keys/second. Towards the end of the contest, we introduced a ``bitslice'' client inspired by Biham  which was extremely fast on 64-bit systems, as well as slightly faster on most other systems.
With this new client, a 500 MHz Alpha was able to test 5.3 million keys/second, and a 167 MHz UltraSPARC was able to test 2.4 million keys/second. In the end, Intel-compatible systems accounted for 53.8% of the keys searched, SPARC based systems for 21.3 %, PowerPC systems for 8.1%, and a mix of other systems for the remaining 16.8% of the keys.
All of the clients would, by default, run with low priority, so that only ``idle cycles'' would be used, rather than interfering with the work that the host would normally perform. An interesting side-effect of the ``only use idle cycles'' approach of DESCHALL, shown in Figure 2, is that weekends would show significant peaks in average host speed, as there were more idle cycles generally available. Also, performance improvements in the clients contributed toward a steady increase in average host speed.
The DESCHALL gateways allowed a large number of people to participate, who would have been otherwise unable. For example, the entirety of Sun Microsystems' contribution (ranked 5th in total keys tested) was conducted through the gateways.
With the increasing amount of computing power available at lower and lower costs, today's cryptosystems must be able to withstand brute-force attacks that would have been unthinkable in the relatively recent past. Simply put, DES and other small-key cryptosystems are weak, and vulnerable to attack by groups with even minimal funding.
What we have done is something that the security community has known to be possible for some time. To our knowledge, however, this is the first time that a 56-bit key for DES (or any cryptosystem) has been successfully found in a brute force search.
At the same time that the cost of computing is going down, the availability of massive computational power is increasing. Given the ubiquity of the Internet and the fact that key search is easily parallelizable, it's relatively easy to harness the power of many thousands of computers of all types.
During the course of the DESCHALL project, more than 78,000 unique IP addresses were recorded by the keyserver as having participated to some extent. We had a peak of about 14,000 unique hosts within a single 24-hour period. All participants were volunteers; a one-time prize of US$4,000 was awarded to the person whose machine found the winning key.
While we did get a relatively large number of hosts to participate, it's very easy to imagine getting a much larger number of hosts involved. Three major considerations influenced the number of hosts available:
Often, when performing risk analysis, one will consider a threat model in terms of varying degrees of an attacker's resources (``rogue individual'', ``moderate'', ``well-equipped'', etc.)
The dropping cost of computing technology and the easy access to large numbers of machines tends to blur the distinctions among the classifications. Now, individuals and small groups can muster the resources equivilant to several large organizations. Data that was once considered to be be vulnerable only to an attack by a ``large, well-equipped organization'' may now be vulnerable to a just few people with friends on the Internet and no budget. This ability may especially affect policies that have assumed a feasable attack on DES would require an investment in specialized hardware.
The ease of development and deployment of a software-based system has its tradeoff in the amount of computational power necessary to accomplish a given task. Hardware implementations are always much faster and more efficient than their software counterparts.
Rocke Verser estimates  that a 10,000 cell FPGA should be able to process nearly 100 million keys per second.
Michael Wiener presented a design for a DES key search machine . A $1,000,000 version of the machine would be capable of finding DES keys in 3.5 hours, on average. A late-1997 version of this machine  would be capable of finding DES keys in 35 minutes, on average. A $10,000 version of this machine would be capable of finding DES keys in 2.5 days, on average.
A dedicated, funded attacker is going to use more efficient methods of key search than idle cycles of general purpose computers. However, a hardware-based attack requires a substantial investment in the hardware. Even though a software-based attack like DESCHALL is inefficient in comparasion, we were able to take advantage of the huge numbers of general-purpose computers already deployed, as essentially no cost.
DESCHALL's relatively simple architecture was able to accomplish a tremendous amount of work. On our peak day, we sustained a search rate of just under seven billion (109) keys per second. On that day alone, more than 600 trillion (1012) keys were searched. Figure 4 shows our search rate, in keys per day, from mid-March until we found the key in mid-June.
Much of the amount of work accomplished was due to the number of hosts participating. As shown in Figure 5, fewer than 1,000 hosts per day were involved in early April, and nearly 14,000 per day ran the client at peak.
Figure 6 shows that our progress over the course of the project was steady, and that the architecture we had in place was adequate to meet the demands made of it.
Although we had additional keyserver capacity available should a need suddenly arise, it turned out to be unnecessary. Elaborate systems, including such things as hierarchical keyservers, turned out to end up either unimplemented or problematic in starting and maintaining. We found it best to plan to scale the system as high as it could go without requiring additional components, but have those additional components ready, just in case of an unexpected increase in system load.
While using this type of effort to do a brute force attack on a 64-bit key would be difficult today, it will certainly be possible in the not so distant future, as more people become involved in these efforts, and as CPU speeds increase according to Moore's Law. At the same time, attacks on smaller key lengths will become easier and easier. Although current distributed projects, like DESCHALL, have not been a direct threat to computer security (i.e., we didn't decipher actual, sensitive data), there is no reason that a DESCHALL-type project could not be assembled by the ``underworld'' of computer crackers for their own use.
It is our hope that those responsible for deployment and management of cryptosystems take heed to the warnings here, and demand strong cryptography with large keys.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -no_navigation -split 0 des-key-crack.tex.
The translation was initiated by Matt Curtin on 4/11/1998