[RC5] Wheres the blocks?

Eric Gindrup gindrup at okway.okstate.edu
Fri Jan 8 15:56:58 EST 1999


     Recycling is not a bad thing.  Suppose there were one block and a 
     bunch of clients.  The fastest way to get that block done is to 
     assign it to all the clients.  The first client to report it back 
     "wins".  The same is true if there are more than one block.
     
     The trouble is reassigning blocks when there are unassigned blocks 
     left.  Then duplicated work is definitely wasted.  The dupe work 
     would have been more profitably used to crack untouched blocks.
     
     95Gkey ~= 2^37 keys = 64 of 2^28 blocks.  It's closer to 48 blocks.  
     We're doing that every second in the DES test.  Assume 25000 clients 
     download 40 blocks (a "nice round days-worth of work") = 1MBlock.  
     That takes 5.8 hours to crack.  Now, in reality, some of the blocks 
     haven't been done and some are done quickly and more are requested.
        So after 6 hours, "half" of 1MBlock are in somebody's buffer.  
     I.e. 2^29 blocks (2^28-sized) are in somebody's buffer.
     
     But wait!  *How* many blocks are there in a DES keyspace?  2^28.  
     (Actually 2^27th due to a neat pairing property of DES keys.)  What 
     does this mean?  If everyone converted to DES-III immediately after 
     the contest started, the entire keyspace would be handed out to the 
     clients.  Fast machines will reconnect early and download reissues.  
     Some of those will be returned before the machine that first grabbed 
     them does.  This way, the average latency is reduced by recycling 
     already-assigned keys.
        If there were unassigned keys, this would not help.  The latency 
     of those keys would be increased by such a process.  However, the 
     DES technique is to assign *all* the keys before recycling.  (Our 
     RC5-64 technique isn't quite so great, but who cares -- we wouldn't 
     significantly decrease our expected completion time and the cost of 
     the master keyserver would increase dramatically if we were to do 
     so.)
     
     For RC5-56, the completion percentage was around 35% behind the 
     assigned percentage when the key was found.  A keyspace recycle had 
     already started (twice, I think).  But think.  The RC5-56 contest 
     was long enough that the fetch/flush operations were poorly 
     correlated.  For DES-III the times of fetches and flushes will be 
     highly correlated.  Pretty much everyone will fetch at contest start 
     and then for every *very few* blocks afterwards.  (Remember, set 
     your DES buffers *very small*.)  This means that the portion of the 
     keyspace in client buffers immediately after their first DES-III 
     fetch will be higher than at any subsequent point in the process.  
     (Expect exponentially decaying sinusoidal behaviour for the "blocks 
     in buffers" statistic.  It's the sum of several thousand components 
     of the shape /----\ (fetch, then chew, then return -- the sloped 
     parts are *very* steep) with a rather clumpy distribution of 
     periods.  It's best to think of this as "all the buffers are full 
     all the time and occasionally they quickly empty and refill."  Low 
     amplitude portions occur when many clients have similar buffer 
     latencies (same time to completely crunch a buffer).  But this 
     analysis isn't particularly helpful.)  Essentially, all the keyspace 
     is in client buffers for DES-III.
            -- Eric Gindrup ! gindrup at okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: [RC5] Wheres the blocks? 
Author:  <rc5 at lists.distributed.net> at SMTP
Date:    1/7/99 3:00 PM


hello,
     
So I'm looking at the stats and I see 102% send, 16% checked.  With only 
16% turned in it is a bit early to start recycling; assuming that the 
other 84% has not been lost, but is out being processed.
     
I am sure the actual number for the contest will be allot different, 
with less people loosing interest, and more people joining. But if those 
numbers are an indication of what is to come it looks a little
hopeless.  We could end up w/ several clients doing the same blocks.
     
I appreciate the open approach of d.net not to stop RC5 while DES is on, 
and obviously not for the test.  But a solution may be needed to see 
that recycling is not started so early.
     
An easy way to do this I am not sure.  But perhaps n blocks could be 
sent to everyone, and then when you turn one in, you get one more? Or no 
more until the buffer is processed.
     
Does anyone know where the hell those blocks are? Do some people have 
buffers set to 10 000 blocks on there home P166?  I would even expect 
people who went back to RC5 to have the courtesy to complete what 
remains in there buffer before switching back.
     
And I guess we get to see what happens when the key space is exhausted 
after all :)
     
--
     
     
,,+°'°+,,,,+°'°+,,*
....Jason C. Leach
..."Many Hands Make Light Work."
..- Unknown
. Distributed.Net - Team Canada
     
-- PGP key on server: pgpkeys.mit.edu 
-- ICQ @ 14398878
     
     
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net 
rc5-digest subscribers replace rc5 with rc5-digest
     
     

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