[DES] DES Key Recovery Project, Progress Report #5

["Peter Trei" <trei@process.com>]

DES Key Recovery Project, Progress Report #5
6 January 1997

Well, the New Year brings changes....

1. I'm astonished at the low level of reaction RSA's 
announcement that they will be sponsoring a DES Challenge, 
with a $10,000 cash prize.

I've been working with people at RSA to get this set up. It looks like
there'll be an ascii-plaintext challenge (we won't know the full
plaintext - just that it's ascii, and long enough to be unambigious),
and the full prize will go the first person who emails them the key. 

This is pretty much what we need to recruit a large number of 
otherwise dis-interested people, and their machines. The code
will be a tad slower than for an attack where we know the full
plaintext of the block sought, but not much.

2. As for my code for WinTel machines - it's very close 
to an initial alpha release (squashing a few last bugs). I 
intend this to be used only for identifying porting issues. 
The first 'real' version is a couple weeks away. 

Once the alpha is out, I'll be looking at the new assembly
language code from Eric Young and Svend Mikkelsen to see
how it compares with mine. Since Eric independently matched
my speed in the DES round, I want to see if he is using any
different tricks than I.

When it's released, my code will be able to:

1. Run a validity and speed test.
2. Accept a specified 32 bit 'chunk' of the keyspace to test. When it
   finishes a chunk, it appends information about whether it found the
   key to a results file, and also any half-matches it found along
   with a checksum. The latter two items help make cheating and
   sabotage more difficult. 
3. Read it's input (plaintext, IV, etc) from a file. After the actual
   DES Challenge is announced, I'll hardwire that challenge into the
   program.
4. Periodically checkpoint it's status to a file. This is so that the
   program can be stopped at any time neccesary, without losing more
   than a few minutes work. At startup, it looks in this file for
   where to continue searching, unless instructed otherwise.  

It will NOT run as a screen saver. It's actually more efficient to run
as a low-priority task in the background - that way it soaks up unused
cycles even when a screen saver is not in operation. If someone else
want's to incorporate it into an SS, go ahead.

The alpha will run in a DOS box under Win95 and WinNT. A GUI
interface may come along later.

It will NOT talk to a keyspace server, though the format of the 
input and output should make it possible to add this in the 
future. I don't have time to develop both myself, and while 
people on the lists have proposed any number of complex schemes 
for setting up and managing a server, no one in the US seems
willing to do the work (I'm worried about violating ITAR/EAR).
I have a pretty good idea what needed in a server. At very least, I'd
like to have people register the fact that they are taking part, so we
get some idea of the level of effort being expended.

The very first time it is started up on a given machine, if 
it is not given a specific chunk at which to start, it will 
pick one at random. The checkpointing scheme means that on 
later runs, it will pick up where it left off, advancing to 
the next chunk as it completes each one.

For this purpose, we don't need cryptographically strong PRNG,
just one that provides a fairly smooth distribution of results.

This means that the search *will* complete, but the time is not
as good as a carefully doled-out keyspace would provide. If you
want to do the math, go ahead, but I think it will average about
twice as long as a purely doled-out search to search the whole
keyspace, and somewhat less to search half the keyspace.

Peter Trei
trei@process.com