The DES Hacks and the RSA Challenges --Thomas Jerry Scott

Note: This note reports on the various DES hacks, which were attempts to the "RSA Challenge Prize" started by RSA Data Security Incorporated to explore how weak the current cryptographic standards were.

The first hack worked because a number of computers were linked together and found the decryption key by a brute force attack. As time went on, more sophisticated machinary was used to brute force a DES key in less than one day. This note was grafted together from various web sources by Thomas Jerry Scott for use in his Computer Security classes.

Table of Contents for DES Hacks and the RSA Challenges

RSA Issues their Secret Key Challenges to Improve Cryptograhpy
Rocke Verser's Team Solves the DES Challenge
Distributed.net and EFF Crack DES in Less than One Day
Distributed.net Also Cracks 64 Bit RC5 Challenge 9/26/2002
Return to the Main Menu

Return to the Beginning of This Document

The RSA Secret-Key Challenge

The following is taken directly from the RSA Web site, where the "Secret Key Challenge" was announced.

*RSA Secret Key Challenge Issued -- January, 1997*
RSA Laboratories is pleased to announce the establishment of a series of new cryptographic contests. The goal of the contests described here is to quantify the security offered by the government-endorsed data encryption standard (DES) and other secret-key ciphers with keys of various sizes. The information obtained from these contests is anticipated to be of value to researchers and developers alike as they estimate the strength of an algorithm or application against exhaustive key-search. It is widely agreed that 56-bit keys, such as those offered by the government's DES standard, offer marginal protection against a committed adversary. By inertia as much as anything else, however, DES is still used for many applications. Theoretical studies have been performed showing that it is possible to build for a modest sum a specialized computer "DES cracker" that could crack keys in mere hours by exhaustive search. However, no one is known to have built such a machine in the private sector, and it is generally unknown whether or not one has been built by any government, either. The successful factorizations achieved as part of the RSA Factoring Challenge (launched by RSA Data Security, Inc. in 1991) show that for some types of problems, it is possible to recruit spare cycles on a large number of machines distributed around the Internet. Therefore, by offering a suitable incentive, it might well be possible to recruit sufficient computational power across the Internet to exhaustively search the DES keyspace (or the keyspace of a cipher with a comparable keysize) in a matter of weeks. The RSA Secret-Key Challenge consists of one DES challenge and twelve contests based around the block cipher RC5. DES has a fixed key of length 56 bits, and the ciphertext produced by DES-encrypting some unknown plaintext will be posted as part of the DES challenge. RC5 is a fully parameterized block cipher, and twelve RC5 contests will be posted. As well as having a variable key size, RC5 also has a variable block size and a variable number of rounds; however, all the RC5 contests posted as part of the RSA Secret-Key Challenge will use 12-round RC5 with a 32-bit word size. The different RC5 contests will involve secret keys of different lengths. The first RC5 contest will consist of some unknown plaintext encrypted using a 40-bit key; the second will consist of some unknown plaintext encrypted using a 48-bit key; and so forth to the twelfth contest, which will consist of some unknown plaintext message encrypted using a 128-bit key. For each contest, the unknown plaintext message is preceded by three known blocks of text that contain the 24-character phrase "The unknown message is: ". While the mystery text that follows will clearly be known to a few employees of RSA Security, the secret key itself used for the encryption was generated at random and never revealed to the challenge administrators. The goal of each contest is for participants to recover the secret randomly-generated key that was used in the encryption. In addition to the "real" contests, thirteen "pseudo-contests" will be posted. These pseudo-contests have no prizes attached to them and the solutions to each pseudo-contest is not secret. The pseudo-contests are only supplied so that contest participants can test out their software in a "contest" scenario with a known solution. RSA Security requests that participants not submit solutions to the practice contests, except possibly to test out the formatting of output produced by their software.

The RSA Secret-Key Challenge, announced at the RSA Data Security Conference in January, provided $1,000, $5,000 and $10,000 prizes for breaking various RC5(TM) keys at different sizes and gave a $10,000 prize to break DES, which uses a fixed-size, 56-bit encryption key.

RC5 is RSA's variable key length, parameterized symmetric-key cipher. So far, the 40-bit and 48-bit RC5 key challenges have been solved. There are twelve RC5 challenges in all.

Return to the Beginning of This Document

Breaking DES

Responding to the Challenge, including a prize of $10,000, Rocke Verser, with the help of team leaders Matt Curtin and Justin Dolske decided to tackle DES.

To date, the most effective way to "crack" DES is through an attack known as "brute force." In brute force attacks, a challenger keeps trying new possible DES keys until they find the specific key used to encipher the challenge phrase.

Rocke created a "cracking" program that would keep trying new keys until it solved the DES challenge phrase. He designed the program so that it could be distributed and downloaded over the Internet. They even created a web site, www.distributed.net, which has clients for developing and testing keys for many algorithms on many different kinds of computers, from Apple 2's to current Pentiums.

"Distributed.net" often has many different clients distributed to people all over the world. Using this technique, distributed.net can coordinate "brute force" cracking efforts, such as the Rocke Verser group that used brute force and many clients to find the secret key in the RSA DES challenge.

The project, code-named DESCHALL, linked together hundreds, and eventually tens of thousands of volunteer computers. As each new computer volunteer signed on, the DESCHALL team created new portions of the DES key space for each of these machines to test. Wrong DES keys could be eliminated, and the correct key, somewhere, would be rooted out.

The Power of The Internet

The attack team included an amazing array of Internet volunteers and computing resources from industry, universities, and government. With a possible 72 quadrillion keys to test, this distributed attack would require an incredibly large amount of computing power.

And compute the DESCHALL team did, at some points testing almost seven billion keys per second. And by writing different crackers for Unix, Windows, Macintosh, and OS/2 operating systems, the DESCHALL team could utilize the computing power of the largest workstations, as well as more modest personal home computers.

In 1998, when this challenge was solved, the US Government maintained a strategy that only allowed "40-bit" encryption products to be legally exported. This governmental policy underscored a problem then faced by the U.S. software industry.

Because of this policy, the DESCHALL team could not export the cracking program outside the U.S. and Canada. SolNet, a competitive effort based in Sweden was able to take advantage of this restriction. Even though they started much later than the DESCHALL team, by marketing their cracker worldwide, they had searched nearly 10 quadrillion keys when the DESCHALL team hit on the winning key.

Lots of Help and a Little Luck

In the end, the DESCHALL effort solved the DES challenge after only searching 24.6% of the key space. (about 18 quadrillion keys!) The winning key was determined by Michael Sanders, using a Pentium 90 MHz desktop PC with 16 megs of RAM. As promised, Rocke Verser split his $10,000 winnings 60/40 with the actual winning computer, and as such, will give $4,000 of his prize to Mr. Sanders.

Mr. Sanders knew he had the right key when his machine successfully decrypted the DES challenge phrase. "Strong cryptography makes the world a safer place."

Return to the Beginning of This Document

DES Challenge III Broken in Record 22 Hours 1/19/1999

On January 19, 1999, RSA Data Security announced that the DES III challenge had been solved by a team from www.distributed.net and the Electronic Frontier Foundation. Their note is italicized below.

Breaking the previous record of 56 hours, Distributed.Net, a worldwide coalition of computer enthusiasts, worked with the Electronic Frontier Foundation's (EFF) "Deep Crack," a specially designed supercomputer, and a worldwide network of nearly 100,000 PCs on the Internet, to win RSA Data Security's DES Challenge III in a record-breaking 22 hours and 15 minutes.

The worldwide computing team deciphered a secret message encrypted with the United States government's Data Encryption Standard (DES) algorithm using commonly available technology. From the floor of the RSA Data Security Conference & Expo, a major data security and cryptography conference being held in San Jose, Calif., EFF's "Deep Crack" and the Distributed.Net computers were testing 245 billion keys per second when the key was found.

First adopted by the federal government in 1977, the 56-bit DES algorithm is still widely used by financial services and other industries worldwide to protect sensitive on-line applications, despite growing concerns about its vulnerability. RSA has been sponsoring a series of DES-cracking contests to highlight the need for encryption stronger than the current 56-bit standard widely used to secure both U.S. and international commerce.

"As today's demonstration shows, we are quickly reaching the time when anyone with a standard desktop PC can potentially pose a real threat to systems relying on such vulnerable security," said Jim Bidzos, president of RSA Data Security, Inc. "It has been widely known that 56-bit keys, such as those offered by the government's DES standard, offer only marginal protection against a committed adversary. We congratulate Distributed.Net and the EFF for their achievement in breaking DES in record-breaking time."

As part of the contest, RSA awarded a $10,000 prize to the winners at a special ceremony held during the RSA Conference. The goal of this DES Challenge contest was not only to recover the secret key used to DES-encrypt a plain-text message, but to do so faster than previous winners in the series. As before, a cash prize was awarded for the first correct entry received. The amount of the prize was based on how quickly the key was recovered.

"The diversity, volume and growth in participation that we have seen at Distributed.Net not only demonstrates the incredible power of distributed computing as a tool, but also underlines the fact that concern over cryptography controls is widespread," said David McNett, co-founder of Distributed.Net.

"EFF believes strongly in providing the public and industry with reliable and honest evaluations of the security offered by DES. We hope the result of today's DES Cracker demonstration delivers a wake-up call to those who still believe DES offers adequate security," said John Gilmore, EFF co-founder and project leader. "The government's current encryption policies favoring DES risk the security of the national and world infrastructure."

The Electronic Frontier Foundation began its investigation into DES cracking in 1997 to determine just how easily and cheaply a hardware-based DES Cracker (i.e., a code-breaking machine to crack the DES code) could be constructed.

Less than one year later and for well under U.S. $250,000, the EFF, using its DES Cracker, entered and won the RSA DES Challenge II-2 competition in less than 3 days, proving that DES is not very secure and that such a machine is inexpensive to design and build.

"Our combined worldwide team searched more than 240 billion keys every second for nearly 23 hours before we found the right 56-bit key to decrypt the answer to the RSA Challenge, which was 'See you in Rome (second AES Conference, March 22-23, 1999)'," said Gilmore. The reason this message was chosen is that the Advanced Encryption Standard (AES) initiative proposes replacing DES using encryption keys of at least 128 bits.

RSA's original DES Challenge was launched in January 1997 with the aim of demonstrating that DES offers only marginal protection against a committed adversary. This was confirmed when a team led by Rocke Verser of Loveland, Colorado recovered the secret key in 96 days, winning DES Challenge I.

Since that time, improved technology has made much faster exhaustive search efforts possible. In February 1998, Distributed.Net won RSA's DES Challenge II-1 with a 41-day effort, and in July, the Electronic Frontier Foundation (EFF) won RSA's DES Challenge II-2 when it cracked the DES message in 56 hours.

Return to the Beginning of This Document

Distributed.net Solves RC-5 Secret-Key Challenge -- 9/26/2002

RSA Data Security announced on September 9, 2002 that the distributed.net team had solved another of its secret key challenges. Their press release is shown in the table below. RSA designed these contests to keep the cryptographic community updated on new achievements and help organizations maintain highest levels of security.

*Table 2: RSA Announces RC5 Contest Solved*
Bedford, MA, Thursday, September 26, 2002 — RSA Laboratories, the research center of RSA Security Inc. (Nasdaq: RSAS), the most trusted name in e-security®, today announced that a coordinated team of computer programmers and enthusiasts, known as distributed.net, has solved the RC5-64 Secret-Key Challenge. The distributed.net team solved the challenge in approximately four years, using 331,252 volunteers and their machines. Distributed.net receives a cash prize of $10,000 for solving the challenge. Established in 1997, RSA Laboratories’ Secret-Key Challenge is offered to quantify the strength of symmetric encryption algorithms such as DES and the RC5® algorithm with various key sizes. By sponsoring an actual contest, RSA Laboratories helps the industry confirm theoretical estimates, and through this constant evaluation, vendors are motivated to continue to improve their security solutions. The distributed.net consortium utilized the idle time of computers throughout the world to search through the list of all possible 64-bit keys for RSA Security’s RC5 algorithm to find the one secret key selected at random by RSA Laboratories that decrypts a given message correctly. RSA Laboratories sponsors a series of cryptographic challenges that allow individuals or groups to attempt to solve various encryption “puzzles” for cash prizes. The RC5-64 Challenge is one of a series of contests held to determine the difficulty of finding a symmetric encryption key by exhaustive search (trial-and-error). Previous contests include the DES Challenge, the RC5-40 Challenge and the RC5-56 Challenge. “We’re very appreciative of all the volunteers who offered their time and computer’s idle processing time to help solve this challenge,” said David McNett, distributed.net co-founder and president. “We have once again shown how collective computing power can be applied to security technology with ordinary PC’s. We look forward to future RSA Laboratories-sponsored challenges that will assist in helping the cryptographic community gauge the strength of an algorithm or application against exhaustive key search.” “RSA Security congratulates the distributed.net team in solving the RC5-64 Secret-Key Challenge,” said Burt Kaliski, chief scientist at RSA Laboratories. “We appreciate the persistence of distributed.net and the many individuals involved in completing the search for this one key. Their work helps the industry confirm how much work is involved to search exhaustively for a key — and how a huge volume of computing time can be harnessed. The various challenges we sponsor are very useful for tracking the state of cryptographic achievements and helping ensure that organizations are maintaining the highest levels of security to protect their most critical data assets.”

Return to the Beginning of This Document