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.
Solved by: ESCHER.UNI-MUENSTER.DE
Contents
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:
- The most machines ever working together on a single, public, project: over 5000 at once, probably over 10,000 altogether
(machines often dropped in and out over the course of the crack).
- The most keys per second ever solved in a public project: 440 million keys per second at peak, 140 million keys per second over
the course of the project.
- The longest and most difficult key ever broken by a public group: 48 bits.
A 48-bit key means there are 2^48, or 281474976710656, keys to check. This number is roughly seven times the age of the earth
in hours.
- The most computing power ever brought together in an internet-based project.
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:
- financial information (credit card numbers, bank account information, etc.)
- personal information
- information about competitors
- anything of value or interest that moves across the internet
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:
- Encrypted email: Here the protocols are public, easy to identify
from information in the email itself, and there is plenty of known
plaintext in the form of headers.
- Secure Netscape Connections: Again the protocols are public, easy to
identify, and known plaintext in the form of headers.
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:
- Computer software firms may find it profitable to decrypt
competitor's email and thus discover trade secrets, especially
if they can do it for free by using spare cycles on machines they
already have. (This might be more believable if you imagine the two
companies being in different countries, which are, say, highly
competitive with each other or known to spy on each other already
in more conventional ways.)
- Governments are well known to spy on each other, and with the winding
down of the cold war, much of this spying is turning economic. For
instance, the US was recently caught red-handed, spying on the
Japanese in trade negotiations. Insecure encryption makes such
spying easy; secure encryption makes it very difficult (of course,
this may be good or bad depending which end of the spying you're on).
- Tabloids may be willing to pay thousands of dollars for decrypts of
the email of famous people. The tabloids may not have the computing
power themselves, but it probably wouldn't take much money to
convince a few enterprising college students to undertake some
decrypts over, say, Christmas break, when a lot of computing power
is sitting idle.
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.
- Many informed internet users believe that the National Security Agency (NSA) routinely sifts through
internet communication. The NSA naturally decrypts anything it finds interesting, if it can. The Distributed
Internet Crack has proven that the power to routinely crack 40-bit and 48-bit encrypted messages is well
within the NSA's grasp. Other national security agencies throughout the world have similar interests
and capabilities; if they aren't sifting through data such as that provided by the internet, they have
little reason to exist. Of course, such agencies aren't exactly broadcasting their exact
interests and capabilities, so precisely what they may intercept and decrypt is unknown. Intelligence
officials have fought long and hard against the wide deployment of strong encryption on the internet--this gives
a pretty good clue as to their interest in this data.
Situations where encryption would have saved the day, if only it had been used:
- In a widely publicized event recently, Kevin Mitnick broke into Netcom, one of the U.S.'s largest internet providers,
and grabbed a list of 30,000 or so credit card numbers of Netcom subscribers.
If the credit card file had been encrypted with strong encryption,
the file would have been useless.
- Copies of some of Newt Gingrich's cellular phone conversations were
recently made public. They were quite embarrassing to Newt. If
the phone had been using strong encryption, they wouldn't have
been intercepted. In this same vein, it is easy to imagine political
parties of various countries spying on each other, and spending
considerable time and money decrypting opponents' messages,
particularly if they believe the information obtained would turn
an election. The press, too, may have considerable interest in
politician's email. With present weak or non-existent encryption, any electronic communication by a politician
or other public figure is subject to interception and can be easily read.
- A hacker has admitted reading email of famous people, including Billy Idol, when he hacked into The WELL,
a California-based internet provider. See http://www.gti.net/grayarea/well.htm.
This sort of thing may not happen every day, but it probably happens a lot more often than most internet users realize.
If strong encryption were implemented in the correct way, hacking into systems would be harder and reading personal files or email
would be difficult or impossible.
- Reprogramming of cellular phones is a major problem. All it takes
is a little knowledge about how they work, and a person can get
unlimited free air time. If strong encryption were implemented
it could be impossible for unauthorized people to reprogram them.
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 ;)
