OS/2 e-Zine! - OS/2 and RSA's Contests

RSA's Contests and OS/2 - by Colin L. Hildinger

If you read the OS/2 news groups or spend time in #OS/2 on IRC, you might have seen people talking about DES and RC5. They mostly talk about things like various client versions, keyrates, and what team is "ahead." For anyone not involved in the projects I'm sure these discussions seem not only arcane, but completely irrelevant to the vast majority of OS/2 users.

Hopefully I can clear some of this up with you and maybe get you involved in the largest distributed computing project that I've ever heard of.

RSA Data Security's Contests

RSA Data Security is a company that writes and sells encryption systems. They have issued a series of contests, each with a $10,000 prize for anyone who can crack a message encoded with a specific cryptography system. The contests included a DES encrypted message and a variety of RC5 encrypted messages, encrypted with different length keys. DES is an encryption standard which uses a 56-bit key length and was developed by IBM for the government in the 1970's. RC5 is a newer standard with a variable key length developed by RSA.

Several of the prizes have already been claimed. The 40-bit RC5 message was cracked 3 hours after the contest was issued. The 48-bit message took 13 days, and DES fell 140 days after the contest was issued. The 48-bit RC5 and the DES messages were cracked by distributed efforts on the Internet; both were cracked by Pentium class machines using their spare cycles and a client that coordinated with other machines all over the world.

Cryptography? Who Cares?

Many of you may be wondering why you should have the slightest interest in these contests. Well, you should if you do any electronic transactions at all. Many are protected by the same cryptography standards which these groups have shown to be unbelievably weak. I'm not just talking about Internet transactions, I'm talking about any sensitive data that is passed by computer from one place to another. If a bunch of people on the Internet can crack DES in a few months with their spare CPU cycles, a dedicated government, company, or other organization could build (and probably already have built) machines that specialize in cracking encoded data that could do the same thing in a few seconds. I'm not an expert on the subject, but it has been shown that specialized DES chips could be built quite cheaply.

Unfortunately, the US government, in its infinite wisdom, has regulated the export of all "large key" encryption. They consider 56-bit encoding to be large key. This means that international companies either use small key encryption or have to buy their encryption software outside of the US. Hopefully these efforts will show how weak this encryption is and put pressure on the government to open up their export standards.

In fact, this appears to be working, as Netscape and Microsoft have recently gotten permission to export the 128-bit SSL versions of their web browsers.

Distributed Computing is Cool

The method being used by the various teams to crack the messages is what's known as brute force. This means that they basically try every key until they find one that works (part of the message is provided by RSA so you know when you've found the key). For the 40-bit encryption, this is about 1.1 trillion keys, for 56-bit encryption, about 72 quadrillion keys, and for 128-bit it's about 3.4E38 keys.

To put it in perspective, a P166 trying 200,000 keys per second could try all the keys in a 40-bit RC5 message in about 64 days. 56-bit would take about 11,500 years, and 128-bit would take about 54,000,000,000,000,000,000,000,000 years. Of course since the key could be anywhere within the keyspace, you could get lucky and find the key for the 128-bit message in only 1,000,000 years or so. <g>

As you can see, a single computer working on its own would take a lifetime to finish. The solution to this is what's called a coordinated effort using distributed computing. In other words, the work is broken down and distributed to computers through a network (the Internet) so that each computer can work on a piece of it.

The clients for all the efforts so far work at "idle" priority or very high "nice" levels on Unix systems. These programs only get CPU time when more important programs aren't actively using it. OSes with good schedulers like OS/2 will notice little to no performance hit whatsoever while running the clients, since they only use a few hundred kilobytes of memory when they're running. I run the RC5 client minimized from my Startup folder and don't even realize it's running unless I take the time to look and see how it's doing.

Team Warped and the distributed.net Effort

The group who has taken up the effort to crack the 56-bit RC5 is called the "Bovine" effort, but no one but the organizer really understands his fascination with cattle. I usually refer to it as distributed.net effort as that's the domain name they've registered for it.

Distributed.net has not only committed to the 56-bit RC5 effort, but to furthering distributed computing. Their upcoming version 3 client/server model will allow them to host multiple projects simultaneously and allow users to "hot swap" projects easily. At press time they're over 5% of the way through the 56-bit RC5 keyspace and progressing at a rate of 1% every 5 days. Of course, they could find the key any day, so they plan to begin implementing other projects as soon as possible. They plan to keep $1,000 of the prize money for themselves (they would earn more if they were paid 50 cents an hour for the time they've already put in), give $1,000 to the person who finds the winning key, and give the other $8,000 to a charity called Project Gutenberg.

After promoting the DES effort, I had the names of quite a few OS/2 users who were participating in the group that won it, called DESCHALL. I had recruited people to get involved because they had a breakdown by OS in their statistics and I wanted to see OS/2 high in that list. Also, though, because I thought it would be good publicity if an OS/2 machine found the "magic key."

Distributed.net not only keeps platform stats, but also allows people to form "teams" under an e-mail address. I created a team called "Team Warped" using my warped@ionet.net e-mail address and started getting people to join. If we find the key, we plan to use the $1,000 to promote OS/2 (the exact method hasn't been decided yet, but it will be through supporting nonprofit OS/2 groups or events like Warpstock). After only a few weeks, we are checking more keys every day than any other group, we are in the top 10 in total keys checked, and we hope to continue growing.

Of course, we don't limit ourselves to OS/2 machines, any machines you can use to help Team Warped would be appreciated. One of our members is even porting the client to the AS/400 platform.

Another group has started up and is offering more of the $10,000 for the person who finds the key, but they don't currently have an OS/2 client, and since we have developed an installed base with the distributed.net effort, we don't intend to splinter our effort by attempting to switch. Since distributed.net has already checked almost 6% of the keyspace, 6% of the keys that this group checks have already been checked by distributed.net. As distributed.net continues to grow and progress, this will continue to reduce the effectiveness of the slower, new effort. Also, since this group is keeping a larger chunk of the $10,000 instead of donating it to a nonprofit organization, distributed.net seems like the best place to be as a socially responsible person.

Colin Hildinger is an Aerospace Engineering senior at Oklahoma State University and has been using OS/2 for the last 3 years. In addition to being the Games Editor for OS/2 e-Zine!, he maintains The Ultimate OS/2 Gaming Page and the AWE32 and OS/2 Page in his "spare" time.

[Our Sponsor: MR/2 ICE Internet Email Client - Delivering the Email features of the future, today.]

This page is maintained by Falcon Networking. We welcome your suggestions.