This was written for a cryptography class (Math 485) at Sonoma State University after finding that other students had not heard of distributed.net or the crypto politics of the 1990s.
David Turover
Math 485 Cryptography
Fall 2009
From the late 1970s through the 1990s, the Data Encryption Standard or DES algorithm was the encryption standard promoted by the United States National Bureau of Standards, a part of the Department of Commerce now known as the National Institute of Standards and Technology, as a secure way of encrypting data.
The viability of brute-force attacks on the DES had been suggested almost immediately after its adoption. A paper by Whitfield Diffie and Martin Hellman of Stanford University, titled "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" and published in Computer magazine in June 1977, says that "if one key could be tried each microsecond, it would take 10^11 seconds, or about 10^6 days, to do an exhaustive search. A million devices searching in parallel ... would take only one day for an exhaustive search and one-half day for the average search" (Diffie-Hellman, 3). Diffie and Hellman themselves cite an earlier report by Bell Labs which calls for increasing the key size.
To prove that stronger encryption was needed, activists in the 1990s began to implement brute-force attacks on DES by using highly parallel systems. One form of attack was done by the DESCHALL and distributed.net projects which used the processing power of tens of thousands of ordinary desktop computers across the Internet. Another attack was done by the Electronic Frontier Foundation which designed and built a custom machine dedicated to cracking DES. The DES cracker proved that DES was no longer a secure encryption method, and so the standard was soon replaced by 3DES and, later, AES.
A brute force attack tries every possible key for an encryption scheme until it finds a key that works. Such attacks may be mathematically viable, but they are not realistic if the key range is large enough. A brute force attack against a large key range could require, for instance, more bits of memory than the number of atoms in the universe and more time to complete than until the heat death of the universe.
So the key to a brute force attack is viability. Does the attack run in a short enough time to be viable? Is the financial cost in the needed equipment and electricity low enough to be viable?
DES has a key length of 56 bits. This was long enough to make brute force attacks unlikely with the computing power of the 1970s and 1980s, but brute force attacks against this key length began to become viable with the increased computing power of the 1990s and the development of algorithms to quickly test DES keys.
A major disadvantage of brute force attacks is that it is far easier to increase the difficulty of finding a key than it is to increase the attacker's computing power. For every bit that the defender adds to the key length, the attacker will need to double his computing power.
Since DES is a standard with a fixed key length that had been in service for twenty years, it is more difficult to change than the example of a single generic algorithm. The implementations of DES in hardware and software throughout the computing world were all based on DES having a 56-bit key length, and changing the key length would require the work and expense of replacing old hardware and software.
The DESCHALL and distributed.net projects sought to use the power of the thousands of ordinary personal computers connected to the Internet to work on projects requiring large amounts of processing. DESCHALL, the DES Challenge, was dedicated to cracking DES. While distibuted.net imagined a more general-purpose use of distributed computing power, two of the first distributed.net projects were brute-force attacks against the RC5 and DES encryption methods.
The way these projects work is to have a client program that Internet users can install on their computers. The client program is portable so it can be installed on different operating systems and CPU models. A centralized server divides the problem into small segments of work which are requested by clients. The clients then perform the work at a low priority using the computer's spare CPU cycles. When the clients are finished, they report their results to the server and request more work.
In 1997, DESCHALL broke DES in 81 days with the network's computing power peaking at about seven billion keys per second (Curtin-Dolske). In early 1998, the distributed.net network broke DES in 39 days by testing up to 34 billion keys per second (McNett).
U.S. government officials, in particular Federal Bureau of Investigation director Louis Freeh, did not consider the DESCHALL project's success to be much of a threat to the security of DES (EFF 1.2 citing Members Briefing). The government's unalarmed response led some activists to build a DES cracker to prove that DES was totally insecure.
The EFF's DES cracker works on the principle that it is faster to tell if a potential key is bad than to tell if a key is good. From the book Cracking DES: "The job of the hardware isn't to find the answer, but to eliminate the vast majority of the non-answers" (EFF, 1.10).
The result of decrypting ciphertext with random keys is going to be random numbers, but we can assume that the plain text is not random. If it is known that the plain text is made of ASCII code, perhaps with punctuation, the system can be told that ASCII letters, numbers, and punctuation are acceptable. Decryption results falling outside of this set of acceptable results can be ignored as non-answers. This sharply reduces the key space that needs to be directly tested by a less efficient process. (EFF 1.12)
This process of eliminating potential keys can done independent of any other potential key. This allows several potential keys to be processed simultaneously, so the machine was designed to take advantage of this fact. The DES Cracker has 1,536 chips to work through the key space and send potentially valid keys to a controlling computer which tests the potential key through a conventional software program. Each of the 1,536 chips contains 24 hardware search units that each test a potential key against eight bytes of cyphertext to see if the results fall within the acceptable range (EFF 1.13).
Each search unit can test 2.5 million keys per second, so given that the chips operate at 40MHz, the process of testing a single DES key takes 16 cycles. For comparison, the DESCHALL FAQ states that 64-bit computers can test a single key in 300 instructions, with other computers requiring 600 or more instructions (Curtin). This shows the performance advantage to implementing the DES solver in hardware, in addition to the advantage that many small and individually low-power chips can be built to operate in parallel.
For a quick note of the DES Cracker's power, consider that each search unit can test more than 2^21 keys per second. The number of search units in the DES Cracker is more than 2^15. The number of keys that can be tested per second is therefore more than 2^21 * 2^15 = 2^36. Dividing this from the key length of 56 bits, it takes the DES Cracker less than 2^20 seconds to exhaust the keyspace. That is only twelve days, and this understates the performance of the machine since we rounded down its performance numbers to get nearby powers of two.
According to the EFF's documentation, the machine's time to exhaust the key space is about nine days (EFF 1.14). Had the the DES key length been only ten bits longer, the same machine would take 25 years to exhaust the key space.
One of the politically persuasive aspects of the DES cracker is the fact that it was built for a fairly low price of $200,000. This is an amount easily available to a government or large business. Such an organization could invest more to build a bigger and more powerful machine using the same technology, one that could crack DES in a day or less.
The EFF considered it fair to assume that such devices already existed. From section 1-16 of Cracking DES: "Given the budget and mission of the US National Security Agency, they must have started building DES Crackers many years ago. We would guess that they are now on their fourth or fifth generation of such devices [...] It would be safe to assume that any large country has DES Cracking machines."
In 1999, the DES cracker and distributed.net worked together to crack a DES key in less than a day. Shortly afterwards, federal standards began to recommend that DES be replaced with Triple DES (3DES) which allows a longer key length and runs the DES encryption algorithm three times.
DES has since been replaced by the Advanced Encryption Standard (AES) using the Rijndael algorithm.
Distributed computing technology has been used to address problems outside the realm of computing, such as protein folding, searching for mersenne primes, and the SETI@home project.
The distributed.net project has also attempted to defeat the RC5 encryption scheme through brute force. 56-bit RC5 was defeated in 1997 after 250 days. 64-bit RC5 was defeated in 2002 after 1,757 days. An attempt to defeat 72-bit RC5 was begun shortly afterward and is still ongoing as of 2009 with less than 1% of the key space tested.
In 2006, a team of German and Czech students developed a DES cracker called COPACOBANA which is built with field-programmable gate arrays [FPGAs], allowing the machine to be reprogrammed to address other tasks. The COPACOBANA performs at about the same rate as the EFF DES cracker in a smaller space and with a hardware cost of around $10,000.
An article in Computerworld predicts that within ten years we may have supercomputers with 100 million processors (Thibodeau). The utility of such technology in performing massively parallel operations, such as a brute force attack on DES, should be obvious. However, this increase in computing power can be defeated by doubling the key size to exponentially increase the time needed to exhaust the range of potential keys.
All URLs accessed November 2009.