WinMag Voices Column 17-Oct-97

Subdivide and Conquer

By Serdar Yegulalp

Someone once said to me, "The Internet isn't 10 million people all doing the same thing; it's 10 million people doing 10 million things. In unison."

That comment resurfaced when I found out about one of the more novel ways the Internet's being used to tackle a problem that would normally require a monster supercomputer. The answer: Have the Internet emulate a supercomputer, courtesy of tens of thousands of volunteers of spare CPU time. Subdivide and conquer.

The effort underway is a coalition of users and programmers who are pooling their efforts to crack RC5, the 56-bit RSA key-encryption standard. Many people have long theorized RC5 to be extremely vulnerable to systematic crypto attacks, claiming that some of its keys are far weaker than others. What makes distributed.org's crypto-crack effort unique is that it didn't pool its cash to buy a mega-multi-way Cray box to crack the RC5 algorithm. Its members pooled their spare CPU time. And anyone can join the effort.

Distributed.net wrote a key-crack application that's been compiled to run on every conceivable platform: DOS, 16- and 32-bit Windows (they have it as an NT Desktop program or an NT service), Mac, PowerMac, UNIX, LINUX, IRIX, FreeBSD, SCO, AIX, HPUX, OS/2, Amiga--you name it. They've even got source code if you want to compile your own binary. You download the binary that fits your platform, unpack it, connect to the Internet and fire up the application.

The app then gets in touch with one of several distributed.net "key servers." The key servers farm out subdivided pieces of the RC5-cracking effort. The client program downloads one of these pieces and works on it in the background; it uses your computer's idle time to run the key-cracking program. Obviously, the faster your computer and the better your OS is at multithreading, the more transparently the thing runs. Every computer works on a different part of the problem; this is the key to the way it works.

I've got the RC5 crack running in the background as I write this with no visible slowdowns (I'm using NT 4.0 on a 166MHz Pentium). And as I type, this parallel-processing effort--which is running on thousands of computers worldwide--is testing 4,522.16 megakeys per second. That's the equivalent of, say, 37,877 P133s. Not bad for a totally volunteer-based project. To learn more about the program, head over to http://www.distributed.net.

How effective is this kind of work? The first RSA algorithm crack, DES, was done this way in three-and-a-half hours. The next one took a little longer--313 hours--but that's still impressive. After 175 days, they're a little more than a quarter of the way through the RC5 crack. (By the time you read this, it could be up to half.)

What does cracking RC5 and DES accomplish? If your sensitive data is entrusted to the encryption code, it shows how difficult it would be for a someone to break the code and steal your data. Even if you question the ultimate value to society of cracking an encryption code, this is just one example of how the power of Internet users can be harnessed to solve problems.

The Department of Energy supercomputer at Sandia Labs uses more than 9,000 Pentium Pro processors to crunch numbers at teraflop speeds--more than a trillion operations per second. Recently, Sandia simulated the results of a comet smacking into Earth. The simulation covered a month of real-life effects planet-wide. They crunched the whole thing at Sandia in just 48 hours--with only one-half the CPUs in the array.

A press release on the Sandia machine stated, "Civilian research expected to be performed using the new machine includes simulation of disease progression that could help doctors and scientists develop new medicines and drug therapy for debilitating diseases such as cancer and AIDS; severe weather tracking to minimize loss of human life and property; mapping the human genome to facilitate cures for genetic-based diseases or birth defects; car crash and highway safety; and environmental remediation methods to clean up and reclaim polluted land."

The downside to using a supercomputer like Sandia's is that it's costly, immobile, difficult to access and difficult to work with. But the same kind of problem-solving subdivision lends itself naturally to the Internet--to coordinate efforts, allow work to be subdivided, and bring together different minds (and different CPUs) on global tasks.

Maybe that's the Net's ultimate killer app: consolidating CPUs, minds and missions. There's no reason the number-crunching for some of the projects mentioned in the Sandia release couldn't be headed up by academic or civilian researchers and farmed out to volunteers on the Net via secure-socket layers. Obviously, this can't extend to everything, for security's sake, but I bet there are plenty of projects that are publicly workable. With this methodology, ordinary folks could help make history--not scientists in frigid computer labs, but thousands of people like you and me.

There are potential artistic uses as well. Imagine rendering a movie like Toy Story on millions of PCs and Big-Iron machines worldwide--in weeks instead of months or years.

What would you do with the power of 50,000 computers?

In the meantime, those distributed.net guys have got a total of 72,057,594,037,927,936 keys to test. So download a client and pitch in. A CPU is a terrible thing to waste.

Back to Press page | Main page