[RC5] Gaining A Statistical Advantage

Stephen Schroder sjschroder at worldnet.att.net
Tue Dec 1 19:41:44 EST 1998


There has been much discussion lately re possible ways of gaining a
statistical advantage over other networks (such as EFF)
during the next DES contest.  I am not a statistician, but with all due
respect to those who have more service with d.net than I, I
humbly wish to make what I believe are valid observations.  I refer
first to some of the history of the discussion:

Date: Tue, 24 Nov 1998 00:21:30 +0100
From: "Lothar Kimmeringer" <kimmerin at online.de>
Subject: Re: [RC5] DES coming...

On Mon, 23 Nov 1998 12:50:34 +0100, Andreas Kunz wrote:

>What about starting at the end, in the middle or distributing keys
>randomly? So the chances to win correspond to the computing-power not
>to "who's a tick faster".

It doesn't matter, where you start.


Lothar

- --
Lothar Kimmeringer                          E-Mail: kimmerin at online.de


________________________________________________________________________________________________

Date: Tue, 24 Nov 1998 14:40:55 -0500 (EST)
From: John Campbell <jcampbel at lynn.ci-n.com>
Subject: Re: [RC5] DES coming...

On Tue, 24 Nov 1998, Lothar Kimmeringer wrote:

> On Mon, 23 Nov 1998 12:50:34 +0100, Andreas Kunz wrote:
>
> >What about starting at the end, in the middle or distributing keys
> >randomly? So the chances to win correspond to the computing-power not

> >to "who's a tick faster".
>
> It doesn't matter, where you start.
>
        I think the point is not the particular starting point, but
assuring
that we're not just cracking the same keys EFF already cracked. For
minimum
duplication of effort, if they start at the beginning, we want to start
at
the end. If they start at the end, we want to start at the beginning. If

they start with the middle, we want to start with the ends. If they do
random keys, there isn't any real advantage of any particular starting
point, so we might as well start with the beginning, that being what the

clients are already set up to do.

- ---
John Campbell
jcampbel at lynn.ci-n.com


________________________________________________________________________________________________

It seems to me that Lothar would be quite correct that it doesn't matter

where we start if we were only competing against ourselves in a timed
event.  Since the solution could be anywhere in keyspace, in 50% of such

contests we would find the
correct key more quickly by starting at the beginning, and in 50% of
such contests we would find the correct key more quickly
by starting at the end.  However, since we are competing against other
networks, and since EFF presumably won the last time
because of slightly greater speed, I believe the outcome is changed.  If

we both start at the beginning and exam keyspace in the
same way, and if EFF is always slightly faster than us, then we will
always lose, because EFF will always get to the correct key
before we do.

The suggestion was made that we start in the middle and work toward both

ends simultaneously.  If EFF continues to start at
the beginning and use the brute force method (as we are doing), and if
our computing power was divided nearly equally in half,
with Group A working toward the beginning of keyspace and Group B
working toward the end of keyspace, several points
seem obvious to me:

     1.    The time required to cover the total keyspace will be the
same as if we all started at the beginning.  The computing power of
Group A and Group B will each be 50% of the total, but each group will
have only half as many keys to check.

     2.    If EFF is just slightly faster than us, we will each cover
1/3 of the keyspace in the same amount of time.  We will cover the
middle 1/3, while they will cover the first 1/3.  If the solution is
generated randomly, then given enough contests, the solution will be in
the first 1/3 of keyspace 33.33% of the time.  EFF will always win those

contests.

     3.    If the solution is generated randomly, then given enough
contests, the solution will be in the middle 1/3 of keyspace 33.33% of
the time.  We will always win those contests.

     4.    Since it is assumed EFF is just slightly faster than us, both

we and they will require the same length of time to cover the total
keyspace.  Therefore, while they were testing the first 1/3 of keyspace,

we will have tested the middle 1/3 of keyspace.  While Group B is
testing the final 1/6 of keyspace, EFF will be testing the final 1/3 of
keyspace at twice the rate as Group B.  While EFF would continually gain

on Group B, they would not converge until just before reaching the end.

     5.    Given the above assumptions, by conceding 1/3 of all contests

to EFF, we would win the other 2/3 of contests.

Additionally, given the above assumptions, the same result would be
obtained if we process the latter 2/3 of keyspace first.  In either case

this would also require that there is a unique way of 'looking' at
keyspace, so everyone agrees what constitutes the beginning and end.
But if this is not universally agreed upon, or if EFF does not proceed
as assumed above, the conclusions do not follow.  Jim Nasby has pointed
out that we don't know what EFF will do.  It is also possible the
principle idea is to demonstrate the speed of networked parallel
processing, rather than testing statistical theory.

I apologize for the screwy formatting.  I composed this in HTML first,
then had to convert it to text.

Steve
sjschroder at worldnet.att.net








--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list