DESCHALL Project Frequently Asked Questions

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.


1. What is DESCHALL?

  1. What is this project all about?

    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.

  2. Why are you doing this?

    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.

  3. Who are you?

    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.

  4. Who gets the prize money?

    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.

  5. What are some web sites related to DESCHALL?
    http://www.frii.com/~rcv/deschall.htm
    The Project Home Page. Progress statistics, current status of the effort, and all sorts of information about the project is available here.
    http://www.research.megasoft.com/deschall/
    The mailing list archives, primary client distribution center, and FAQ all live here.
    http://www.cis.ohio-state.edu/~dolske/des97/
    Home of Graph-O-Matic, Banner Mania, and the secondary client distribution center, as well as some Ohio State-specific statistical information.
    http://www.frii.com/~rcv/krstat/
    The statistics page, in rankings by domain, has links to sites with their own DESCHALL pages. (There are too many to include them all here!)
  6. Are there other efforts to find RSA's Secret DES Key?

    Yes. After some other efforts folded, there are three efforts that are major contenders for finding the key. These are...

    1. DESCHALL
      It's noteworthy that we've got the fastest key search rate by far. Despite the fact that we seem to have fewer clients than another, the ones we have are extremely fast. As a result, we've nearly moved into first place for amount of keyspace searched, and we have been holding on to first place for keyspace search rate for quite some time.
    2. SolNET
      The largest effort to find the secret DES key outside of the United States. If you're outside of North America and want to help find the key, this is probably the best place to go. If you're inside of North America, however, DESCHALL is probably a better option for you.
    3. Silicon Graphics
      An effort to find the key is underway inside of SGI. While this effort holds the most keyspace searched as of this writing, it's soon to be overtaken by DESCHALL, as its rate for key searches is much lower. Also, no one outside of SGI can participate in this effort.
  7. Where can I learn more about cryptography?

    There are a few good resources available that should be able to help you better understand cryptography, regardless of your level of experience.

2. Joining DESCHALL

  1. Do I need to be a cryptographer, a scientist, a programmer, or have weird hair to participate?

    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.

  2. How can I help?

    This is an easy one...

  3. How can I keep in touch with the project?

    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.

  4. What mailing lists are available?
  5. Are there any special etiquette guidelines I should know about?

    Yes. There are a few simple guidelines that will help.

  6. Where are the mailing list archives?

    http://www.research.megasoft.com/deschall/archive/

3. The Client Software

  1. How do I get the software?

    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.

  2. What if I don't live in the US or Canada?

    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.

  3. How can I get the software for a platform that isn't currently supported?

    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.

  4. How do I get the source code?

    You can't, for three reasons.

    1. The US Government has restrictions on the export of cryptography. The author (Rocke) does not want to risk the problems that may arise if someone were to export the source code.
    2. Even though DES may be on its last legs, the author (Rocke) believes their may be some commercial value in very fast DES software. He hopes to recover some of his investment in this project through licensing of the software.
    3. Previous efforts have been disrupted by bogus clients based on the authentic source code.
  5. How do I know the program isn't doing something naughty?

    This is sometimes a concern of security conscious people. It's a valid concern, but consider the following:

    1. The source code has been seen and examined by a number of people, including:
      • Rocke Verser (original author) in Colorado
      • Guy Albertelli and Justin Dolske, graduate students at OSU in Ohio.
      • Darrell Kindered, a graduate student at CMU.
      • Andrew Meggs, an indepentant programmer in Virginia.

      None of these people have repoted any sneaky or unsafe things going on in the code.

    2. A few people on the mailing list have traced the program as it ran, and have not reported any suspicious behavior.
    3. The project has grown to 10,000+ computers. If the client is secretly doing something malicious, we could be placing ourselves at a HUGE risk. Someone would eventually notice something weird was happening.

    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.

  6. What are the -d and -e options?

    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.

  7. Can I stop the client at any time?

    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.

  8. Why does my client seem slower than that one?

    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.

  9. Why does my non-Intel x86 not perform like a Pentium?

    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.

  10. Does DESCHALL use floating point arithmetic?

    No.

  11. What flags were used for compilation?

    Most have been compiled with -O3.

  12. What is "bitslicing," and why are the bitslice clients so fast?

    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.

  13. Can I speed things up by running more than one copy of DESCHALL?

    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.

4. Gateways, Firewalls, and other Obstacles

  1. I am behind a firewall. Can I still participate?

    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.

  2. I'm behind a router that blocks UDP packets. Can I still participate?

    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.

  3. My proxy won't allow HTTP connections to any ports besides 80 and 8080. Can I still participate?

    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.

  4. How can I convince my management that my organization should participate in DESCHALL?

    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...

  5. How can I participate if I don't have dedicated Internet access?

    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.

5. Statistics

  1. I'm running the client, but my domain name isn't showing up in the statistics, but my IP address seems to be. Why?

    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.

  2. How can my organization participate without having our domain name show up in the stats?

    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.)

  3. Why do the statistics measure estimate time to having 50% of the keyspace searched?

    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.


C Matthew Curtin
Last modified: Wed Jun 11 09:06:03 EDT 1997