Re: Can we kill single DES? #2

[Adam Back <aba@dcs.ex.ac.uk>]

Peter Trei <trei@process.com> writes:
> One offer was made of a $1000 reward in return for a crack, if the
> offerer could make publicity hay of the offer (no, I don't have a problem
> with that, but I'd like it set up so that others could add to the reward as
> well). If the reward got big enough ($10k?) I think it would be a 
> major incentive for otherwise uninterested people to run the screen
> saver. On the other hand, it might get into legal hassles - I don't know.

Perhaps the companies which have maintained anti-GAK stances could be
persuaded to have a whip-around?

I've seen mentioned as crypto friendlies in list discussion recently:
Netscape, PGP Inc (obviously:-), Silicon Graphics, others?  (The
internet casino people?)

The SSL challenge had a digicash prize fund, and Pete Wenzel won 
c$ 442.30.

With the advent of a real money backed digicash bank, Mark Twain bank,
perhaps someone with an account could set up a page for donors to give
donations via MT digicash.  This would allow anonymous donations.
Perhaps First Virtual payments too.  Someone who can accept credit
card payments for donations would be real handy too.

Anyone still with contacts at MT (Lucky?) would they be interested in
promoting the idea, perhaps donating prize cash.  Also FV could gain
some positive publicity by supporting.

(For fun, you could take the prize money, in the form payable to
anyone, as MT ecash, and encrypt it with DES.  Publish it as the
challenge.  The winner gets the cash:-)

> [...]

You're probably aware of most of the below, as you were involved with
the Netscape SSL break, so this is really just a suggestion that you
might be able to cut some corners on time to implement by borrowing
some stuff.

> I'm really concerned about the problem of a search failing, or 
> succeeding only after too long a time. Perry's proposal of about
> a month of real time is on the right order, though I could see up
> to 3 months being possible.
> 
> Here's what I'm thinking of doing:
> 
> 1. Writing a prose description of the platform independent speedups.
> 
> 2. Writing a proposal for a client-server protocol for doling out
>    keyspace and returning results. Aside from the direct Internet
>    interface, there will also be a mechanism for i/o via plain text -
>    suitable for cut-and-paste, or simple CLI interfaces.

Take a look at SKSP (Simple Key Search Protocol) before you do, this
was what was used for the 31 hr Netscape SSL brute force.

Piete Brooks <pb@cl.cam.ac.uk> has perl implementations for clients
and servers, and should be able to point you at the draft RFC for
SKSP.  www.brute.cl.cam.ac.uk was a DNS he set up for the purpose.
Some of the software is available starting from:

	http://www.cl.cam.ac.uk/brute/

Andy Brown <a.brown@nexor.co.uk> wrote a win95/NT client for the SKSP
protocol, this would be another reason to use the protocol, few
modifications presumably would be required to the NT client to work
for a DES break.

SKSP was written to make it possible to have a multiple tier system,
with key dolers taking out large chunks from the main server, and
doling it out to clients, or further sub-servers.  Multiple servers
could be also managed by multiple IPs for the same DNS name, with
random selection of the IPs, to share out work for the servers.

The protocol was set up to do multiple targets (bruterc4, brutessl,
all that would be needed would be a brutedes which followed the
template of responses, especially for the unix setup).

The protocol also had some (albeit weak) protection against mistakes,
and uninformed malicious attacks -- the acknowledgements are only
counted with a checksum.  (It is fairly trivial to generate the
checksum without doing the work).

As a way of providing slightly more robust reslience to malicious
attacks, I remember that the approach of the server picking a random
key in the range doled out, and computing the decrypt for that key
itself was discussed in relation to the SSL attack.  The key matching
the decrypt would then form the sanity check.

People can still can abuse the system, but they can't help doing some
work, even if they lie about the outcomes, and this slows them down.

Adam
--
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)