[RC5] Gaining A Statistical Advantage
eladv at bigfoot.com
Thu Dec 3 10:47:37 EST 1998
Unless, and this is pretty likely, someone in EFF is subscribed to this
list and checking up on d.net. Then when they see you're starting from the
middle they'll start from the middle too and still beat the crap out of us.
I think the best thing to do would be to assign random blocks.
>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
> 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.
>sjschroder at worldnet.att.net
>To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
>rc5-digest subscribers replace rc5 with rc5-digest
Elad Verbin eladv at bigfoot.com
eladv ICQ # : 779784
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest
More information about the rc5