[RC5] I think we found our next contest...

Bruce Ford ford at aus3.com
Thu Jan 24 00:39:30 EST 2002


> That sounds quite fail to all.. take my example..
> Im stuck with a downed machine (Linux) that did the majority of my calcs,
> my 4 other lan machines are working on it, but in total, at less than half
> the speed of that linux box. I expect to have the Motherboard back from
the
> factory in short order, so I can continue crunching, if I cant get back
> online in the 90 day period, i'd sure rather see someone get it cracked,
> than have the possible key rotting in my HD. (Course we all think we're
> gonna have the right key.. ;)

There is another way to think of this which has not been mentioned.  It is
far more likely that the key blocks sitting on a machine do not have the
key.  You are therefore doing the rest of us a service by not having to wade
through those keys.

Some history on key recycling for those who have come in late to the
contest.

1.  64 bit keys are assigned out of 56 bit key "sub-spaces".  For those slow
on the binary math, there are 256 of these 56 bit "sub-spaces".  This has
its
roots in the RC5-56 contest for which everything was originally designed.

2. We started at "sub-space" 0x64.  This was because there were 3 groups
contesting RC5-56 and that competition was expected to continue.  In the
early days key blocks were assigned randomly out of a "sub-space".  We have
moved upward through the "sub-spaces" cycling to 0x00 after 0xFF.

3. There have been a number of ways random block generation has been done in
the client, but for the most part random blocks are generated out of the
most recently received "sub-space" + 1.  Random blocks are always 2^28 keys
(one work unit) in size.

4. In the early days a few "sub-spaces" were recycled, but as more disk
space became available this has not been done.  It is years since the last
occasion.  It was during that early time that the 90 day policy was put in
place to give some confidence as to when recycling would occur.  Now the
entire 64 bit key space is being recycled and there is no option for that as
all of the original keys have been distributed.

5. About 50% of key blocks distributed are returned.  This means we will
again start distributing keys from "sub-space" 0x64 when 75% of keys have
been tested.  In about another 90 days.

6. Another way of looking at this is that keys appear to currently (20 Jan
2002) be coming from the 0xf4 "sub-space".  There are 112 "sub-spaces"
between this and 0x64, all of which we assume are 50% done.  Thats about
150000 million blocks of 2^28 keys.  As keys are distributed at twice the
key rate reported by stats, due to the 50% return rate, approximately 116
million blocks of 2^28 keys are distributed each day.  This gives about
130 days till 0x64 is distributed again.  No account for growth in
processing rate there or above.  It will probably be somewhere between 90
and 130 days I suspect.

7. Of course the time to the next complete recycle halves each recycle,
so a complete key space recycle will drop from 300 days to 150 to 75 to 40
to 20 to 10 to 5 ...  If we haven't found the key by then we have been
extremely unlucky (99.6% complete).  Based on those rough calcs, the 0xf4
"sub-space" will next be distributed in about 130+150*114/256 = 214 days.

None of the above is "official".  Just the musings of a long running
participant.


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