Bovine RC5 Effort

DESCHALL

GIMPS

iNetZ Corp.

Infinite Monkeys

International PGP

PGP, Inc.

RSA Data Security

As fascinating as finding very large prime numbers is for those interested in mathematics, encryption may have a more direct impact on many people's e-lives in the near future. Last month, networked personal computers cracked  a message encrypted using RSA's 56-bit RC5 algorithm. And this wasn't the first 56-bit algorithm to fall either: earlier this summer DES was cracked in a similar manner.

In January the data security firm RSA announced the Secret Key Challenge. There are thirteen challenges: one to crack 56-bit DES and 12 to crack various key length versions of RSA's RC5. DES (Data Encryption Standard) is a symmetric-key encryption block cipher defined by the U.S. government in 1977. DES has been extensively studied since its publication and remains the most common method used by the majority of financial institutions worldwide to protect monetary transactions. RC5 is RSA's variable key size, parameterized, symmetric-key cipher.

RSA offered $1000, $5000, and $10000 prizes for breaking 40-bit, 48-bit, and 56-bit key sizes of RC5, and $10000 for breaking DES, which uses a fixed-size 56-bit encryption key. RSA started the challenge to investigate the power of distributed computing attacks over the Internet and to publicize the relative strengths and weaknesses of different secret-key ciphers. The first four prizes have now been awarded. The fifth challenge is a version of RC5 using 64-bit key; it has not been cracked---so far. The final challenge uses a 128-bit key and is unlikely to be cracked using currently known techniques.

All  samples in the challenge are encrypted plaintext containing an unknown message and the 24-character string “The unknown message is: ”. The encrypted message was only known to few RSA employees; the key used was randomly generated. All RC5 samples use a 12-round RC5 with a 32-bit word size. The DES sample uses the fixed 56-bit key size. The 40-bit version of RC5 was cracked in 3 hours. The 48-bit key version of RC5 was cracked in 13 days. And then the government-endorsed DES was cracked.

On June 17th, Michael Sanders, a employee of iNetZ Corp. in Salt Lake City, cracked the message “Strong cryptography makes the world a safer place.”, which was encrypted using DES. The computer that cracked the message was a Pentium 90 with 16M of RAM running FreeBSD, but it was operating as part of a much larger project called DESCHALL. Over a four month period the DESCHALL team checked nearly 18 quadrillion keys (about a quarter of the possible 72 quadrillion keys), finally finding the right one that revealed the encrypted message. For those of you keeping score, the secret key was 0x8558891AB0C851B6. To give you an idea of how large 72 quadrillion is, if you manually checked one DES key per second it would take over 9 billion years to check the key space!

DESCHALL was organized by Rocke Verser, a contract programmer in Colorado. With two other people he developed a program to crack DES using brute force: an exhaustive search technique where new keys are tried until the correct one is found. In symmetric cipher systems like DES the same key used to encode the plaintext is used to decode it. When DES was designed over twenty years ago it was thought that the computational power needed for a brute-force attack would be prohibitively expensive. It is now felt that a dedicated special-purpose computer could crack as 56-bit DES message in a few hours. Verser's program was designed to be distributed over the Internet and run on many different types of computers and operating systems.

Each participant in the project was assigned a portion of the DES key space to search. Results were coordinated over the Internet by Verser's team. At its peak, the DESCHALL project had approximately 14,000 computers working in parallel on the DES challenge, processing about 7 billion keys per second. Over 78000 different computers took part in the challenge. If the project had of started with the same number of computer participants that it ended with (over 550 trillion keys were checked in the last day alone), DES would have been cracked in just 32 days rather than the 96 days that it took. The $10000 prize was split between Verser ($6000) and Sanders ($4000).

Even though DES has now been cracked, it received federal approval for renewal through 1998. DES has a known weakness, exposed in 1990, called differential cryptanalysis. This type of attack can be used on block ciphers like DES by analyzing the evolution of the differences between two related plaintexts as they are encrypted using the same key. However, this method is more difficult than a brute-force attack based on trial and error. Only Moore's law of doubled computing power every 18 months, the plunging cost of powerful personal computers, and the Internet made this brute-force approach possible. Its success was recently duplicated in the cracking of RC5.

The RC5 cipher is an even stronger encryption algorithm than DES. In fact, with its 56-bit key it is the strongest encryption allowed by U.S. law for export without the use of key escrow or key recovery schemes that provide a “back door” for government agencies to enable them to decode encrypted messages. Nevertheless, in October RSA paid $10000 to a group called the Bovine RC5 Effort for cracking a message encrypted using the RC5 algorithm. The group was made up of over 4000 teams using tens of thousands of computers linked over the Internet. It took Bovine 250 days to decode the message “It is time to move to a longer key length.”

The Bovine team took the same brute-force approach to the RC5 problem that the DESCHALL team had taken to the DES challenge. Three Bovine members, Adam Beberg, Jeff Lawson, and David McNett, wrote a program that simply parceled out blocks of keys to all participants. Each block contained over 250 million keys. Since the key length for RC5 was the same as for DES, there were over 72 quadrillion total keys (2⁵⁶). Multiple proxy servers were used to coordinate the effort, ensuring that no work was duplicated.

The correct key (0x532B744CC20999) was found by Peter Stuer, a researcher in a Belgian computer science lab. The actual machine used (starpc14.vub.ac.be) was a a Pentium Pro 200 with 128M of RAM running Windows NT 4.0. But as with Sanders and DESCHALL, Stuer was working as part of a team. In this case, a group led by Jo Hermans, the systems manager at the Computer Science Department of the Vrije University in Brussels. He was able to get about 40 people in the lab to run the program on their machines, processing about 10000 blocks a day. The collaborative effort of all computers in the Bovine group was the equivalent of 14000 Pentium Pro's working simultaneously.

Because they cracked the message, Hermans' lab won $1000 of the $10000 award. The Bovine group kept $1000 and gave the rest ($8000) to the Gutenburg Project. The Bovine group is already at work on  Version 3 of their software in preparation for attacking the next RSA challenge: the 64-bit key version of RC5. And they are joining the GIMPS project as well.

Projects such as these demonstrate the kind of supercomputing power that previously was available only to large research labs. Distributed personal computers networked together over the Internet can now provide what is in effect a virtual parallel supercomputer. And these projects made use of nothing but spare CPU cycles made available by thousands of users who never even met one another.

It is very possible that the same techniques used to find large prime numbers and crack encryption may find their way into other domains. This could have a significant impact on future software engineering approaches to attacking problems that lend themselves to this type of distributed computing. Of course, not all problems are amenable to a brute-force solution. Witness the chess challenges between Deep Blue and Kasparov. But some problems that are inherently parallel could be attacked in this manner.

It is even conceivable that a smaller company, one that could not afford a  proper supercomputer costing millions of dollars, might instead opt for a “research lottery”. They could offer a small reward to the first group, like the Infinite Monkeys, to come up with a solution to their computationally-intensive problem. Putting the terms “research” and “lottery” together in this way may seem a bit odd, but think of it as the free market at work. Or at play.

One final tidbit of information related to this musing. The encryption program “Pretty Good Privacy” (PGP) is one of the better known examples of private industry running into government regulations of cipher techniques. It is becoming increasingly difficult for governments to legislate rapidly-evolving technology. In fact, 56-bit DES was cracked just one day after a new bill was introduced in Congress that advocated the use of 56-bit key encryption. PGP is capable of much stronger encryption, using up to 128-bit keys. In a turn of events so extraordinary it could only happen in real life, the source code of PGP Version 5 was recently made publicly available---even though exporting this type of strong encryption technology is generally against the law. (There are exemptions for financial transactions. Both Microsoft and Netscape were permitted to export 128-bit encryption technology in their Web browsers and serves to support SSL (Secure Socket Layer) for protecting Internet commerce.)

How was this PGP exported? By throwing the government a curve ball and doing it the old-fashioned way: the source code was copied from a book. In particular, it was scanned by people in Norway from the 12-volume, 6,000-page series published by Warthman Associates in June. After two months of checking to make sure everything was correct the program was on a Web site at the University of Olso for anyone in the world to download. The loophole was that there are no export restrictions on books!

Perhaps the old adage “The pen is mightier than the sword” should be updated to read “The scanner is mightier than the disk”.

Related information:

• Yahoo's Computer and Internet Security section on the RSA challenge
• A Presentation on RC5 by Parag Shantu Shah, Oregon State U.
• An excellent FAQ on crypto by RSA Laboratories at http://www.rsa.com/rsalabs/newfaq/. It is over 200 pages but you can download a PDF version for offline viewing.
• The Encryption Policy Resource Page (http://www.crypto.com/)
• The Parallel Virtual Machine (PVM) (http://www.epm.ornl.gov/pvm/)

Sources: C|Net, Linux Journal, Microsoft, Microsoft Developer Network, Netscape, New York Times, RSA, Wall Street Journal, Wired, ZDNet and private communications.

Copyright © 1997 Scott Tilley

www.srtilley.com