The Upcoming DES Challenge

Peter Trei (trei@process.com) writes:

 > 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'm certainly jumping up and down and cheering.  I said a while
back that the life expectancy of DES would be about two weeks if
anyone forked over serious cash.

I'm also pleased to see they will be offering prizes for trying
to break Ron Rivest's new RC5 cipher, which scrambles using data
dependent rotates as its only non-linear operation.  This is very
speedy, and if it turns out to be robust, will be a nice fast
efficient drop-in replacement for most other popular block
ciphers.

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

Ick.  Why overly complexify things?  A known plaintext attack
would be far more straightforward.  After all, the goal is to
recover the key, not the message.  Having to find a key which
decrypts to something having all high bits clear will discourage
people who might want to take a crack at this independent of the
canned program you are going to distribute.

[snip]

 > It will NOT run as a screen saver.

Too bad.  The screensaver paradigm is something the unwashed
masses can easily understand.

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

This is VERY IMPORTANT.  Unlike factoring problems, where the
data supplied by people can be checked in a small fraction of the
CPU time used to generate it, searching a keyspace is very
vulnerable to sabotage or stupidity on the part of the people
doing the searching.  It is well worth the extra factor of 2-3 to
guarantee that the exercise will eventually terminate.

Sounds good, but I would prefer matching plaintext and ciphertext
with the goal of recovering the key.  This is really the
situation that would exist for someone tapping financial data on
a line, and knowing the plaintext of a transaction he
deliberately generated for testing purposes.

K.I.S.S.

--
     Mike Duvos         $    PGP 2.6 Public Key available     $
     mpd@netcom.com     $    via Finger.                      $

> > 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)
> 
> Ick.  Why overly complexify things?  A known plaintext attack would be
> far more straightforward.  After all, the goal is to recover the key,
> not the message.

I think a completely known-plaintext attack would not impress the
masses. Consider how often crypto illiterate programmers implement
ciphers (such as Vigenere variants) which are obviously vulnerable to
known-plaintext attacks. The idea seems to be that if you know the
plaintext, what do you need the key for? _We_ may know better, but I
think we are in the minority.

For a slight increase in the computational requirements, we could end up
with a break that the "DES is good enough" people would have a _much_
harder time downplaying.

> I think a completely known-plaintext attack would not impress the
> masses. Consider how often crypto illiterate programmers implement
> ciphers (such as Vigenere variants) which are obviously vulnerable to
> known-plaintext attacks. The idea seems to be that if you know the
> plaintext, what do you need the key for? _We_ may know better, but I
> think we are in the minority.

You have got to be kidding!
Where are you getting this "idea" from? Since when is recovering the
plaintext following and preceeding the known plaintext not of
_any_ interest?

In regards to known ciphertext. Can't you just calculate the time
required to successfuly perform known ciphertext only attack from the time
to successfuly break known plaintext?

I agree with earlier posters. I am glad RSA putting up some real money for
this and as such I respect their design of the contest. 

What I am curious about is wether the chaining mode will be "given" as
part of the contest, but I'll gladly wait till AFTER Peter is done with
his program to get an answer.

Regards,

Bernie Doehner