This document describes the DESCHALL Project, what we're doing, why, how you can help, and everything else that one might be inclined to ask.
This FAQ may be electronically reproduced in its entirety.
Inclusion of this document on a CD-ROM or in a printed
publication may not be done without the express written
permission of the maintainers. For updates, questions, or
comments about the FAQ, please email Matt Curtin.
Copyright © 1997 Rocke Verser
Copyright © 1997 Justin Dolske
Copyright © 1997 Matt Curtin
The current version of this document is available from http://www.research.megasoft.com/deschall/deschall-faq.html.
RSA Data Security, Inc issued the Secret Key Challenge in early 1997. This is a series of 13 contests where an encrypted message is posted on their web site. The first person to tell RSA the contents of encrypted message and key used to encrypt it is awarded some prize money.
Among 12 contests for different-key-length versions of the RC5 algorithm is a contest using the Data Encryption Standard (DES), which is sometimes known as the Data Encryption Algorithm (DEA). DESCHALL is an attempt to find the solution to RSA's DES Secret-Key Challenge.
Different participants have different answers. Some of these include...
For most of us, it's a combination of some of these, and probably some other reasons.
We're a group of Internet users, from different backgrounds and occupations, all working together for a common goal: to find the secret key. Some of us are security experts, some are programmers, others are system administrators, and still others are hobbyists.
Assuming that DESCHALL is the project that finds the right key, Rocke, who designed and implemented the server, client, and protocol, intends to submit a request to RSA for 60% of the prize money. The person whose computer found the key will be able to request the remaining 40%. That person will be responsible for submitting their own claim.
To quote Rocke:
I will never touch your share of the prize money! Your share of the money can be used any way you and/or your employer and/or your school see fit. [They may let you keep it. They may ask you to donate it to a worthy cause. They may want it for themselves. They may want it to go to their general scholarship fund.]
I am not prepared to make any promises as to what I will do with my share of the prize money. If your share goes to a worthy cause, I may be inclined to send a portion of my share to a worthy cause. But again, this is not intended to be a guarantee.
Yes. After some other efforts folded, there are three efforts that are major contenders for finding the key. These are...
There are a few good resources available that should be able to help you better understand cryptography, regardless of your level of experience.
No! (However, such traits as weird hair, wearing sandals and socks, and being generally nocturnal are worth bonus points.) Seriously, though, you don't need any programming or cryptography expertise in order to run the client, or tell other people about what you're doing. These are the two things we need most now.
This is an easy one...
Several methods are possible. First, you can tune into the mailing lists. You can either do this by subscribing, or by looking through the archives. Alternatively, you can keep watching the Project Status page.
This is an extremely low-volume moderated list. Reserved only for special announcements, like the release of new clients, or for when someone (hopefully one of us!) finds the key.
To subscribe, send email to majordomo@gatekeeper.megasoft.com with only the text "subscribe deschall-announce" (without quotes) in the body of the message (the Subject: header is ignored). You will then be mailed instructions on how to confirm your subscription. (Replace "subscribe" with "unsubscribe" to get off of the list.)
This is a pretty high-volume unmoderated mailing list. It's a catch-all for the project participants to discuss essentially anything relevant to the project. (Before posting, please consider whether you're contributing toward the "signal" or the "noise." This should help us keep a high-quality list going, despite its size.)
To subscribe, send an email to majordomo@gatekeeper.megasoft.com with only the text "subscribe deschall" (without quotes) in the body of the message (the Subject: header is ignored). You will then be mailed instructions on how to confirm your subscription. (Replace "subscribe" with "unsubscribe" to get off of the list.) Alternatively, you may wish to browse the mailing list archive.
Yes. There are a few simple guidelines that will help.
Point your browser to http://www.research.megasoft.com/deschall/des-dist/ fill out the form, and submit it. If you're within the US or Canada, you should be presented with a list of clients you can download.
We can't give you the client. We're uninterested in becoming the first people to be prosecuted under the new Export Administration Regulations (EAR). Sorry.
To create a version for a new platform, we need to have access to that platform. So, if you'd like a new client for your FooBarBaz system, we need to be able to get an account on your system to do so. Because of buggy compilers and other subtle errors, be need to have access in order to make sure the client is functioning properly.
You can't, for three reasons.
This is sometimes a concern of security conscious people. It's a valid concern, but consider the following:
None of these people have repoted any sneaky or unsafe things going on in the code.
Running the DESCHALL software places you at no greater risk than running any other piece of software on the net. How many of you have the source code to Netscape or Microsoft Internet Explorer? Finally, none of the other efforts have made working source code available.
Nonfunctioning command-line arguments to confuse you. :-) -d stands for "debug" but this is turned off in the released clients. -e stands for "exclusive" which also doesn't work.
Yes, you can. Every time the client gets a new block of keys, it reports its work on the previous block to the server. However, when you stop the client in the middle of a block of keys, all work on that block is lost, unless you're using a Mac client, which will ask you if you want to finish the current block before it quits. If you finish the current block, no work is lost. If you go ahead and quit immediately, work on that current block is lost. The server will reallocate the lost block to another client later on, so even if someone quits on a block that has the right key, the key will be found, albeit a little later than originally expected.
To reduce the load on the server and statistics scripts, it would be nice if you can avoid stopping and starting the client repeatedly.
First, make sure you're running the correct client if you're using an Intel system. Each Intel platform has a client optimized for a specific CPU -- if you're using the wrong optimized version, the client will run slower. If you're using a Cyrix or other Intel "clone," you should try each client to see which runs best. Use the "-m" option to benchmark the client.
Next, make sure you're doing the math right. The client reports pairs of keys, not total keys. Suppose you run the client and see:
2^21 complementary pairs of keys tested: 16 seconds
This means that you have tested 2^22 (2 * 2^21) keys in 16 seconds -- that's 262,144 keys per second.
That said, there are a number of reasons why you may be incorrect in assuming that a system should be faster. DESCHALL basically only uses raw CPU power, and very little else. Having a large amount of RAM, disk space, or a fast disk drive will not make the client faster. When comparing non-Intel platforms with the Intel versions, do not be mislead by the clock speed (Mhz) of the various systems. In other words, don't expect a 100Mhz RISC system to perform the same as a 100Mhz Pentium. RISC systems tend to require more instructions to do the same amount of work (which is why RISC systems tend to have a higher clock speed than CISC systems). Also, different chips in a family can run at vastly different speeds, for a number of reasons. See any good book on computer architecture for the reasons why. Finally, "high-end" systems may only be high-end because of expensive add-on hardware. Expensive graphics hardware and lots of memory, are of no value to DESCHALL.
Think of it this way... DES was standardized in 1977. It was designed to be implemented on a single 1977-era chip. In 1997, there's no inherent reason why a $200 chip shouldn't be faster than a $2000 desktop computer, which shouldn't be faster than a $20,000 enterprise computer, which shouldn't be faster than a $200,000 mainframe. The DESCHALL clients are probably using only a few hundred dollars of the hardware in your computer, anyway.
Some 586 CPUs are actually 486-class processors. You should only expect it to perform like a 486 at that clock speed. Other 586 and 686 CPUs have a different internal architecture than Intel processors. The optimizations that were tuned for the Intel processors may be ineffective, or even slow down other brands. Be sure to use the -m flag with clients for different processors if in doubt. Use the fastest of them.
No.
Most have been compiled with -O3.
This is a technique introduced by Eli Biham. Biham implements DES by representing S boxes by their logical gate circuits. This view is taken of the entire cipher. The circuit is then computed 64 times in parallel. The entire "circuit" has around 16,000 gates. So in 16,000 instructions, DES can be computed 64 times on 64-bit processors. Using this method, the number of instructions needed to perform DES encryption is about 300, versus 600+ in other fast DES implementations.
Processors of other sizes: 32, 16, 8 bits, etc. can use the same approach. However, in 16,000 instructions, they'll perform only as many encryptions as the host architecture's word size. So, although 64-bit processors will be able to perform 64 encryptions in 16,000 instructions, 32-bit processors will perform 32 encryptions, 16-bit will do 16, 8-bit will do 8, etc.
You should have exactly one process per processor running to make optimal use of your machine. The MacOS client has built-in MP capability, so don't run more than one copy, even on MP systems. For the other clients, you'll need to run one process per processor. While Unix clients can do this more automatically, by specifying the number of processors on the command line, the Windows clients need to have the proper number of clients started by hand.
Almost certainly yes.
There are two ways to participate through a firewall. The first way is to have your firewall administrators allow you to pass UDP traffic on port 8669 to keymaster.verser.frii.com. The second way is to use the nifty DESCHALL U2T GatewayTM.
The U2T gateway is a Perl script that runs on some system behind your firewall. When you start clients on your network, start them, and give them the name of the host running the U2T gateway as the keyserver. The U2T gateway will convert the UDP datagram into an HTTP GET request to one of our HTTP servers known as deschall-gateway.verser.frii.com. The request will be submitted to a keyserver, and an answer returned through the client as a response to the GET. Despite all that is going on, it's actually quite fast in most cases.
Because in NT lacks an important call (specifically, fork()) the U2T gateway will not work on that platform. It should work on any (other) platform that can run Perl 5.003. You can get the U2T gateway from http://www.research.megasoft.com/deschall/deschall-u2t.
A C++-based U2T gateway is being tested right now for NT. We're hoping for a release soon.
Another gateway is being written in Java, which should add NT to the list of possible deschall gateways. This is currently functional at its core, but requires more work to bring it up to par with the features offered by the Perl gateway.
There are several advantages to using the U2T gateways. Two big advantages for a lot of folks are: no firewall configuration changes are needed, and it allows you to participate somewhat anonymously. Because of the way statistics are reported from the server, everyone using a particular gateway will contribute toward the statistics of whichever gateway they're using. Someone who wants to see how he's going in a situation like this can simply collect the log data from each of the clients, compile it, and compare it.
If you do not want to participate anonymously, simply flip the "anonymous" bit in the u2t gateway script.
Yes. The section above describes how to use the U2T gateway to turn DESCHALL protocol traffic into web traffic, which easily traverses almost all gateways.
Sure! You can get the Perl U2T gateway at http://www.research.megasoft.com/deschall/deschall-u2t and use it to talk to http://deschall-gateway.verser.frii.com:8080
If port 80 is the only one you're allowed to use, you might be stuck. Mail Matt and see if something can be worked out for you. It's possible that, unless you're a fairly large site, you're stuck at this point. But it's worth looking into anyway.
This is a complex answer because different management groups will have different concerns. Some things that might give you some ideas for making a good case to your management might be...
Windows Users
(From Randy Weems <rweems@hotmail.com>)
If you don't have access to a full time Internet connection and are running a flavor of Windows (95, NT3.51, or NT4.0) check out the Windows GUI Front-End at http://www.concentric.net/~Mithran/. This front-end uses your Windows Dial-Up Networking to only dial your service provider when needed and for only as long as needed. It's called a front-end because it relies on the DOS DES challenge client executable to do the actual work; it starts the client as a background child process, captures output from the client, and displays the results in a graphical format. Many Windows users with a full-time Internet connection still prefer to run this front-end because of its slick Windows interface and the additional features it provides.
OS/2 Users
(From Phillip Catt <prcatt@netrover.com>)
In the section on automating a dialup connection in OS/2 check out my page at http://www.netrover.com/~prcatt/autoppp/
It is the scripts I use to automate connecting at midnight and staying up for 6 hours. It can easily be adapted to any time frame needed.
On my system it is started by exiting my BBS mailer and calling the REXX script. But on other systems, there are various CRON programs available to start tasks at scheduled times.
In addition, if the deschos2 client were modified to maintain a QUEUE, and write something like CONNECTION_REQUEST to it. A REXX script could be written to check the queue every few minutes and if It finds one, to make a connection, and keep it up till the QUEUE read CONNECTION_NOT_NEEDED. So the Deschall Client could say when it needed a connection and when it didn't and under connection_request, wait for the connection to be up, and then after returning a keynotfound and getting a new key to work on, it could tell when to down the connection. This would allow dialup connections to conserver connection time, and connect only when a connection is needed. Once up, the connection would only be needed for a few seconds. But as I said, this would require changes to the client so it would maintain the QUEUE for REXX to see.
But the above page should be of assistance to others.
MacOS Users
(From Michael Kiaer <mikkel@echonyc.com>)
FreePPP, OT/PPP and MacPPP are the most common PPP clients for Mac. I know for a fact that FreePPP has an option that "Allow Application to Open Connection." I am pretty sure that other do as well.
An option that some folks are using is having their email client check for email with enough frequency to keep the connection established. A more optimal solution would be to find out how to allow the connection to be dropped, and then establish a new one right about the time the client needs more keyspace. Anyone with details on how to do this is free to share 'em with us for inclusion in this FAQ. :-)
Unix Users
Many people solve this problem by setting up automated timer
programs such that their computer dials up every thirty
minutes, connects for 5 minutes, then hangs up. The hope
is, in this five minute time your computer will report "Key
not found" and get a new key.
The TCP/IP protocols provide the IP address of your computer, but not its hostname to the keyserver. To get the hostname, the scripts that generate the statistics and rankings must do a "reverse" DNS lookup. Most likely, your network administrator does not have reverse DNS lookup configured properly.
Here's an example of a reverse lookup failing -- we can't get the hostname from the IP address, but we can get the IP address from the hostname:
[D:\]nslookup 198.95.251.36 *** can't find 198.95.251.36: Non-existent domain [D:\]nslookup www81.netscape.com Name: www81.netscape.com Address: 198.95.251.36
(In case netscape.com people are reading this, this is a contrived example. Your DNS is working fine. :-)
You may be able to get your hostname from a reverse lookup with nslookup, but this doesn't always mean that others will be able to.
Use the U2T gateway, described in the section on firewalls. This will allow you to participate anonymously, by default. (It can be configured to allow anyone using it to have their stats published.)
Because we don't know where in the keyspace of 72,000,000,000,000,000 the right answer is. On the average, only 50% of the keyspace needs to be searched before a solution is found.