Distributed Internet Crack
Information Page

This page tells what the Distributed Internet Crack is and why it is important.
The page was last updated 11 February 1997, 12:45AM CST.
This page is also available en français.

The 48-bit RC5 challenge has been solved!

Key: 74 a3 53 cc 0b 19
Time: from start of contest until Mon Feb 10 18:52:23 1997 (a little over 13 days)
Method: massive distributed coordinated keysearch
Secret Message: The magic words are Security Dynamics and RSA.


What is the Distributed Internet Crack all about?

The Distributed Internet Crack (DIC) is a loosely organized group of individuals from around the world working together to harness the power of thousands of internet-connected computers to crack encryption challenges.

The group has no formal leader or leaders and has never met together in person. Its activities are coordinated through an internet mailing list hosted by the Swiss Federal Institute of Technology in Zurich. Members of the group from all over the world have volunteered their time to write and maintain software, create world-wide web pages and other documentation, and of course, run the software they have created to crack the challenge codes.

The group first attacked the RSA Data Security's 40-bit RC5 Challenge, cracking it in about 3.5 hours (unfortunately a few minutes after a Ian Goldberg, a college student, broke the key using a group of workstations). The group then took on the RSA's 48-bit RC5 challenge and completed it in a total time of about 13 days.

A world-wide web page for the Distributed Internet Crack can be found at http://www.ee.ethz.ch/~rsa_clng/. Distributed Internet Crack's latest statistics are available at http://www.42.org/challenge/.

In what way is this project the biggest, fastest, coolest, bestest or what-the-hell-ever-est such thing that has ever been done?

The Distributed Internet Crack successful attack on 48-bit RC5 broke new ground in several areas:

In addition, the crack brought together thousands of ordinary computer users from all over the world. This group had never met or worked together before. Within days, code was written, tested, and put into action on over ten thousand different of machines. Then, as problems arose or suggestions for improvement were given, several improved versions of the software were written, tested, and put into operation, sometimes within hours. Code was optimized and ported to over a dozen different operating systems. Documentation was written, statistics generated, World-wide Web pages written, translated into at least four different languages, and mirrored on WWW sites throughout the world. Internet mailing lists were set up and hundreds of messages exchanged as users offered suggestions and helped each other overcome difficulties.

The project grew rapidly as word of it spread throughout the internet. The peak computing power achieved near the end of the crack was around ten times the amount at the start of the project. As a result, the challenge was cracked much faster than even the project's participants initially had expected.

The incredible response to the Distributed Internet Crack shows, if nothing else, that thousands of internet users across the world care a lot about achieving real security and privacy online. This concern about internet security is not just the concern of a fringe group, but is shared by a solid core of internet users.

Why did we undertake the project?

Governments, particularly U.S. government, wish to limit the strength of encryption available to the public. Right now, 40-bit encryption may be exported from the U.S. without much problem, and permission to export encryption stronger than 40 bits may be given after companies complete a lengthy process to receive a special export license. Companies wishing export software using longer keys must also agree to implement Government Access to Keys (GAK) within two years.

Computer programmers throughout the world know how to create encryption strong to resist every sort of decryption attempt. These encryption systems are simple enough that they can be implemented by virtually any computer science student (although it is a little trickier to make sure your code doesn't have any bugs that may allow the system to be attacked).

These systems can be developed and used by those within the U.S., and also developed and used by those outside the U.S. However, the U.S. export restrictions make difficult or impossible for programmers in the U.S. to make strong encryption systems that can be used both inside and outside the U.S.

This fact is particularly important on the internet, which is international in scope. The U.S. export restrictions have effectively kept encryption on the internet to those levels allowed for export from the U.S.

Large corporations also shy away from including robust encryption in their applications, because they will have to develop different versions of the software for domestic use and for export. They generally just leave encryption out (better that their name is not associated with a weak product), or at best include a weak level of encryption.

When the Distributed Internet Crack easily breaks keys which are as large as the U.S. government allows, it shows that the government regulations are far too restrictive. Most of those who participate in the DIC would argue for the complete abolition of export restrictions on encryption. All would suggest that, at a minimum, regulations should be relaxed by a significant amount.

Government Access to Keys (GAK)

Government Access to Keys (also known as "key escrow") means that software companies will give copies of all keys (or at least enough of the key that the remainder could be cracked very easily) to the government. The government promises that they would hold the keys in a secure way and only use them to crack keys when a court issues a warrant to do so. To the government, this issue is similar to the ability to wiretap phones: they are not going to tap into everyone's phone line, but they certainly want the ability to tap into anyone's phone conversations if they feel the need and can get a court order. Similarly, they want the ability to crack into to anyone's online communication, although they promise they will not break into anyone's communication unless it is legal for them to do so.

The details of Government Access to Keys remain to be worked out, but many in the online community are suspicious of it. If keys were leaked or stolen, online communications throughout the world that were previously thought to be secure would suddenly become insecure. And the United States' National Security Agency (NSA) has a mandate to monitor worldwide communications for security and intelligence purposes. It is known that the NSA routinely eavesdrops on plaintext communications travelling the radio waves (telephone communications transmitted through satellites, for instance), and it seems unlikely that they would restrain themselves from filtering internet communication as well. If the keys to all online encryption were available to the NSA via Government Access to Keys, would the NSA restrain themselves from using them? Many in the online community find it difficult to believe that they would, especially since many (perhaps most) of the keys archived under GAK would be used for communication outside the borders of the U.S. where the NSA has little legal restriction on its activities.

The details of GAK remain to be worked out, and perhaps problems with it will be resolved to the satisfaction of most internet users. But a nagging suspicion remains--someone, with little difficulty, can read communications that are supposed to be secure. Are these communications then really secure?

This feeling of insecurity has significantly restrained the development of internet commerce in the past; with GAK it may continue to do so in the future.

Why is encryption important?

As little as twenty years ago, encryption was a specialized field mostly of use in military communications. With the explosive growth of the internet, much communication now takes place in digital form. A variety of people can intercept this information as it moves from node to node across the internet. If this digital information is not encrypted, all of these people can simply read it. Even more frightening, they can easily program computers to sift through gigabytes of information for that which is of interest: If the information is protected with strong encryption, it simply cannot be read or sifted in this way. If the information is only protected with weak encryption (the sort allowed by the U.S. government), the encryption can simply be cracked, and then the eavesdroppers proceed as usual. Weak encryption slows eavesdroppers down a little, but it certainly doesn't stop them.

When DIC breaks 40-bit or 48-bit bit encryption, it shows that it this level of encryption is indeed too weak to reliably protect the valuable information that is travelling over the internet. With this weak level of encryption, neither consumers nor companies will consider the internet secure enough to conduct business over it.

In fact, it is this very perception of insecurity that has held back the development of commerce over the internet.

The success of the Distributed Internet Crack in breaking 40- and 48-bit keys validates the perception of internet users: This level of encryption is, in fact, insecure.

Exactly what real-life situation does breaking the challenge key emulate?

Some have suggested that the cracks of the RSA challenges are meaningless because RSA gave out information about the key that law enforcement officials don't normally have when trying to decode info-terrorist's messages.

This is technically true and certainly important to law enforcement agencies such as the FBI and intellegence agencies such as the NSA and the CIA. These agencies often deal with messages of unknown origin, encrypted by unknown encryption systems. For our purposes, however, this sort of argument is irrelevant. Situations very similar to those presented by the RSA challenges appear on the internet daily.

Here are some common situations that would easily give data similar to that found in the RSA Challenge:

In what real life sorts of situations could this kind of a crack happen?

Obviously, thousands of computers do not come together in a massive international effort just to crack into some poor soul's credit card number (they could get it much more easily just by looking over his shoulder down at the neighborhood grocery store). So who does have this sort of computing power and what sort of situation would cause them to bring it to bear against someone's encrypted message?

Governments, large corporations, and many universities have enough computing power to make a crack feasible. Some may not be able to do it as fast as we've done it here, but some could do it faster.

Situations that could make cracks profitable:

Examples of weak encryption being broken:

These are hard to come by. Anyone who has found a way to profit from weak encryption is not going to broadcast the fact, and they could be very hard to track down. This is one reason strong encryption is so vital to business and commerce, as well as to regular internet users who wish to protect their privacy.

Situations where encryption would have saved the day, if only it had been used:

What was the cost of the crack?

Usually, the dollar cost of cracking keys is calculated something like this:

The crack took would take X years to accomplish on system Y.

System Y costs so many dollars. To house it, maintain it, pay sysop's salary, etc., for X years costs so many dollars. Adding all these expenses up gives us the cost per crack.

This sort of calculation doesn't really apply to the Distributed Internet Crack. No special computers were bought or paid for to participate in the project; no other projects were set aside or delayed while this project moved forward. The DIC client was designed to use spare CPU cycles on pre-existing machines--cycles that usually just go to waste. For instance, the DIC client can check thousands or even hundreds of thousands of RC5 keys while the computer is waiting for the operator to push the next button (even if the operator is a fast typist!). If a job does come along that requires all of the computer's capacity, the DIC client steps aside and then resumes when the activity level drops again.

Here is an estimate of the cost of doing a 40-bit crack (note that this is 256 times easier than the 48-bit crack most of this document is discussing):

A 486DX2-66 can check 1,000,000 keys in 24 seconds. Thus it crack a 40-bit key in an average time of 153 days. The crack would take maybe 10 hours to set up the first time around (much less for succeeding cracks). Cost of computing time is $0, since the program runs in the background without noticably degrading system performance.

*Total cost of cracking 40-bit RC5 on a 486: 10 manhours, $0 computing time, 153 days to completion.

A dedicated key-cracking machine could be used instead. A simple 486DX-66 system can be bought for $400 and sold at the end of 5 months for $375.

*Total cost of cracking 40-bit RC5 on dedicated 486: 10 manhours, $25 computing time, 153 days to completion.

If a person used, say an office network of computers or several fast networked computers available to students at most any university, the project could easily be accomplished ten times faster at essentially the same cost.

How fast could the crack have been done 2 years ago? How fast will we be able to do it 2 years in the future?

Eighteen months ago, 40-bit RC4 was cracked in 30 hours. Recently 40-bit RC5 was cracked by DIC and another group. Both groups did it in approximately 3.5 hours.

In eighteen months, there was a ten-fold increase in available computing power. The increase in speed is because of faster computers, more computers available to be easily interconnected, and greater interest in the internet community in demonstrating the weakness of encryption methods that are currently allowed.

If this trend continues, within a couple of years, 48-bit keys will be able to be cracked within a few hours; within five years 56-bit keys will be easy pickings, too.

So in five years, any number of college students will be able to decrypt anything that is encrypted today with 56-bit encryption.

What about the technical details?

What is encryption?

Encryption is when computer data is scrambled so that it cannot be read. Encrypted data always has a key; using the key, a computer can unscramble (or decrypt) the data and make it readable again.

Encryption is like a lock that protects your data; the encryption's key is the combination to the lock. If you know the combination, you can open the lock and read the data. If you can't open the lock, you can't read the data.

Some combination locks are very difficult to open--these offer a lot of protection. Other locks aren't well made or have combinations that are easy to figure out. These locks offer very little protection. Imagine a combination lock with a five-number combination: 12-25-32-16-10. This combination would be very difficult to crack. A combinations with three numbers would be somewhat easier to figure out. Combinations with only one or two numbers would be child's play--they offer so little protection that no one even sells such a thing.

In a similar way, encryption can be strong, weak, or somewhere in between.

The strength of encryption is generally measured in bits. DIC's crack have shown that 40-bit encryption is very weak and 48-bit encryption are quite weak. 56-bit encryption would be moderately weak, and encryption with over 100 bits is very strong.

What is RC5?

RC5 is a rather new encryption system developed by RSA Data Security. RC5 is new enough that it is not currently used on the internet as much as other encryption systems.

However, the difficulty in doing a brute force crack (such as that done by the DIC group) is more dependent on the bits in the keyspace than particular characteristics of the enciphering method. For instance, 48-bit RC5 is equivalent in difficulty to 48-bit RC4. Paul Foley estimates that DES would be approximately 70 times more difficult to solve than 48-bit RC5 (DES has a keyspace of 56 bits, but keys can be checked somewhat faster than they can with RC5).

Both RC4 and DES are widely used on the internet today.

How exactly was the RC5 attack done?

A brute force attack . . .

The RC5 crack was a "brute force" attack. In this sort of attack, the computers decrypt the encrypted text with every possible key. They then check to see if the key is correct by seeing if this decrypted text makes sense (in this case, we knew a small part of the original encrypted message, so the computers simply checked for that). If the decrypted text is gibberish, then that was not the right key and the computer moves on to the next key.

In the case of 48-bit RC5, this process is repeated up to 281474976710656 times until the correct key is found.

. . . distributed among many computers . . .

The brute force attack is straightforward, but it can take a very long time. Cracking 48-bit RC5 on a single 486DX-66 could take as long as 214 years. The fastest computers commonly available commercially could crack the key perhaps 100 times faster, but even with such a speedy computer the crack would take over 2 years.

The Distributed Internet Crack solves this problem by splitting up this difficult problem into many small parts. One central computer divides up the work. Using the internet, the central computer sends assignments to worker computers located all over the world. These computers complete the assigned work and report back to the central computer, which then assigns them a new task.

In this way thousands of computers worked simultaneously on the problem, and were able to solve it thousands of times faster than a single computer could have.

. . . and run in the background

Most computers are not run at full capacity all the time. Fifty percent, 80%, or even more of a computer's capacity may go unused, at nights, on weekends, or simply when no one is giving it a particularly difficult task to accomplish. DIC's client program was designed to use these otherwise wasted cycles to solve the challenge. When other programs demanded the computer's full processing power, the DIC client would step aside, and then resume computing when excess computing power was available again.

A stupid analogy

What is a web page without a stupid analogy? So here goes . . .

DIC's distributed attack on RC5 is like searching for a penny in a cake.

Let's say that your sister just got married. A lot of guests forgot to come to the wedding, so you ended up with about 20 giant sheet cakes left over. You happen to know that somewhere in those sheet cakes is exactly one penny. If you can find the penny, you will get a prize and, more important, a happy feeling inside.

Now if you start searching for the penny yourself, it is going to take a long time, especially if you don't want to let any of that good cake go uneaten:

20 sheet cakes x 40 pieces per cake / three desserts per day = 267 days
But if you invite a few hundred friends over, you can make short work of this problem. You divide up the cake and give a piece to each friend. Your friends eat the cake and as soon as they are ready, they ask you for another piece.

Because you don't want your friends getting too fat, you make them eat nutritious food first. Only if they have excess stomach capacity after eating all their peas and potatoes are they allowed a piece of cake.

Even though you are using only excess stomach capacity (which is usually just filled with pretzels and beer anyway), you and your three hundred friends easily find the penny within a day.

This is similar to the way thousands of computers worked together to find the RC5 key in just a few days, when one computer working alone would have taken many years.

How does the RC5 crack compare with the widely publicized cracks of RSA public keys?

To crack RSA public keys requires factoring large numbers. The search method is quite different from the brute force attack DIC mounted on RC5. So the results of the RC5 cracks do not directly apply to cracks of RSA public key systems.

However, the general result--that we can break keys much faster today, because of faster computers and greater interconnectivity, and that the speed of cracks will increase even more in the near future--certainly does apply.

What is the difference between the RSA Challenge and RSA public key encryption systems

RSA Data Security, Inc, holds the patents to RSA public key encryption (at least, the patents to the system in the U.S.). They also invented RC4 and RC5, and write and sell general security-related software.

RSA Data Security offered the RSA Secret Key Challenge, which is actually a series of cryptographic contests. The 40-bit RC5 challenge and the 48-bit RC5 challenge are two of these contests.

Despite the similarity in the name, none of the current contests involve RSA public key encryption.

Where can I find more information the Distributed Internet Crack, the RSA Challenge, and encryption in general?

This page is coordinated by Brent Hugh (bhugh@cstp.umkc.edu). Please write him with any suggestions or corrections. You are welcome to copy, mirror, print, or otherwise make any reasonable non-commercial use of this page.

The following have contributed ideas or text to the page:

Matt Hartley, Robert Rothenburg, Olaf Erb, Jeff Kesner, Craig H. Rowland, Piete Brooks, Wesley Felter, Göran Öberg, Paul Foley and probably others who I accidentally forgot ;)