Re: RSA DES challenge

Rocke Verser (rcv@dopey.verser.frii.com)
Wed, 16 Apr 1997 05:13:59 -0600


> From davidz@educom.com.au Wed Apr 16 02:00:21 1997
> From: David Zverina <davidz@educom.com.au>
> To: "'rcv@dopey.verser.frii.com'" <rcv@dopey.verser.frii.com>,
> "'dvgroup@des.violaton.net'" <dvgroup@des.violaton.net>,
> "'des@des.sollentuna.se'" <des@des.sollentuna.se>
> Subject: RSA DES challenge
> Date: Wed, 16 Apr 1997 18:04:16 +1000
>
> As far as I can see there are three coordinated group efforts:
> DES violation group, DES Challenge, and DES coordinated effort.
> All three groups seem to be searching the space independent of each
> other. I would like to propose a way to eliminate the wastage of
> searching
> duplicate spaces by creating loosely knit coalition.
>
> 1) Reserve 6 bits of the key and let them be allocated by central
> entity. This would partitioan the keyspace into 64 subspaces.
>
> 2) Considering any of the group will take several months to search
> even 1/64 of the space this process could easily be done manually
> by one person. This would eliminate need to write key superserver
> and also avoid any software export restrictions.
>
> 3) The mechanism for keyspace allocation would as follows:
> 1. Central party allocates a keyspace on demand from
> any party participating in the colation.
> 2. Central party notifies all parties of the allocation so
> each party can keep track of which sections
> of key space were searched and by whom.
>
> IMPLEMENTATION:
> 1) Fix the number of reserved bits to 6.
> 2) All groups would have to provide info on how they have been
> generating keys so far so that the best choice for the 6 reserved bits
> can be made.
> 3) Appoint central moderator to allocate the subspaces. I would be
> happy to fulfill this role unless someone objects or believes that they
> would be more suitable.
>
> PROS
> 1) The common goal of compromising DES should be achieved faster.
> 2) Unless two groups using same algorithm to generate keys, the
> likelihood of any one group breaking the key corresponds directly
> to how much of space it can search. This likelihood would be preserved
> under the new system.
> 3) As you preserve control over results obtained from the search, the
> rewards (fame, fortune, etc....) are still yours.
> 4) If any party of the coalition is found to produce incorrect results
> all
> parties will know which subspaces are affected.
> 5) You get to participate in a truly global effort to show the stupidity
> of
> US (and other) government's cryptographic policy.
>
> CONS
> 1) It may be difficult to find common 6 bits to reserve. Considering DES
> Challenge only can have at most 7 invariant bits, while the other groups
> should still have 8 invariants.
> 2) Some (small) modifications may be required to the key servers.
>
> Discussion and comments are most welcome,
>
> Cheers,
>
> Dave
> ---
> David Zverina
> Software Engineer
> (davidz@educom.com.au)

Hi David:

Thank you for the suggestion and for the offer be the coordinator.

At this time, the DESCHALL team is far too busy with essential
matters, such as porting clients, creating gateways, improving Web
pages and statistics, and a thousand other things.

With less than 1% of the keyspace searched by each team, the possible
savings are insignificant. Frankly, our time is far better spent
adding new clients and speeding up existing clients, where we expect
to achieve much much more than a 1% growth in rates of keyspace
search. We simply don't have the time to deal with a <1% issue
right now.

I can't speak for the other teams, but it's hard to believe that
they don't also have ideas that will increase their keysearch
rates by more than 1% over the short term.

I will state that the DESCHALL server is capable of simultaneously
searching several discontiguous areas of keyspace, and it has been
doing so from the beginning. There are *no* invariant bits in the
unsearched DESCHALL keyspace. I suspect changes to the keyserver
and clients would not be trivial.

As the total amount of searched keyspace grows, and as the project
matures, we may reconsider your suggestion.

Thanks again.

-- Rocke Verser, rcv@dopey.verser.frii.com