[rc5] Random keyblocks

Eric Gindrup gindrup at okway.okstate.edu
Tue Aug 26 14:36:40 EDT 1997


     The advantage to the hashing order is that the blocks could be 
     assigned (roughly) sequentially.  The pre-hashed indices would be 
     (roughly) sequential while the post-hashed blocks would wander over 
     the keyspace.
        The current method is to sequentially assign random hunks of the 
     keyspace.  Rationally, there's no reason to do the random hunk thing 
     since each key is equally likely.
        The advantage of hashing the keyblocks is that the observed 
     behaviour of the search effort would be unchanged, but it would be 
     easier to generate meaningful random blocks.  Just choose a random 
     block from the segment of the pre-hashed blockspace that hasn't 
     (probably) been assigned yet.  This has similar redundant work 
     properties as the current method, but only to the degree of the 
     current effort when a significant portion of the keyspace is completed 
     after the client starts generating random blocks.
        This makes swapping information with the other efforts neither 
     easier nor harder.
     
        Again, I don't consider this an issue of unassigned versus tardy.  
     This is an issue of tardy versus random.  What's at stake is the 
     usefulness of offline work.  Working on random blocks offline is 15.7% 
     worthless now.  Working on a tardy block is, even in the one month 
     vacation example you give, useful as it accelerates the completion of 
     the effort.  It also simplifies the data storage by the proxies since 
     storing a copmlete bitmap of the blockspace would require 32MB.  
     Although realistically it would be stored as an assigned/returned list 
     with extents or something similar.  In any event, completing tardy 
     blocks reduces the storage requirements of the proxies.  This is not a 
     particularly good point and I don't want to suspend my argument from 
     it.
        My basic claim, that the efficacy of working on random blocks is 
     going to be less than the efficacy of working on tardy blocks, does 
     not change.
        The real question is a question of utility.  The most utile thing 
     to do, until the probability of finding the key in a tardy block is 
     larger, is to assign unassigned blocks to clients.  When it is more 
     likely that a tardy block contains the target key, i.e. when the 
     number of tardy blocks is greater than twice the number of unassigned 
     blocks, it is more utile to work on tardy blocks.
        This only becomes an issue when the client is unable to retrieve 
     unassigned blocks in my suggestion.  When it is unable to continue to 
     retrieve unassigned blocks from a proxy, it can work on cached tardy 
     blocks.  In the current scheme more of that work is wasted on 
     redundant random blocks.
        The point of the exercise is to prove that 56bits is not enough.  
     The best way to prove that is to complete the effort quickly.  Wasting 
     work is not an effective way to reach this goal.  Therefore, the goal 
     is to maximize the utility of each block searched.
        Right now, it is more utile to work on unassigned blocks than on 
     tardy or random blocks.  It is also more utile to work on tardy than 
     on random blocks.
     
        You state that it is just as easy to download a guaranteed untested 
     block as a tardy one.  I disagree, especially in the scenario I keep 
     talking about.  In that scenario, it is not possible to download a 
     guaranteed untested block.  In that instance, it would be better to 
     work on a tardy block than on a random block.  Since you can't 
     download a tardy block either, you have to have cached it.  Since for 
     the bulk of clients, they never have a detected proxy interruption, 
     this does not affect them.  What this does do is, for the small 
     population of clients with unreliable connections to proxies, the 
     effort that would be wasted on redundant random blocks is instead used 
     usefully to reduce the untested keyspace.
     
        And ultimately I don't agree that working on a random block is 
     better than just exiting.  When the keyspace is about 80% exhausted, 
     there is essentially no point in generating random blocks.
     
        The best method I can imagine would have the clients "promising" to 
     return blocks at certain future times.  These promises would be based 
     on the results of the self-test on startup.  The proxies would then 
     assign sequential pieces of the keyspace to the clients.  The clients 
     would continue to work on the sequential piece until they missed a 
     deadline.  If they missed a deadline, they would abandon the piece 
     since the proxy has reassigned it.
        A source of sequential numbers would be used for keyblock 
     assignment, but would be hashed so as to spread the blocks assigned to 
     more widely sample the keyspace.
        If a client were unable to report results to a proxy, it would hash 
     its MAC address into a block number and work sequentially through as 
     many blocks as it needed until connection could be re-established.  
     MAC addresses are unique, so a perfect hash would have different 
     clients work on disjoint pieces of the keyspace instead of random 
     pieces.  The client would need to store its "offline status" so that 
     it would restart such work at the end if it becomes offline again.  
     The proxies would need to report extensions of the completed space 
     that overlaps the "offline space" of a client whenever they send it 
     new work.
        This method would eventually exhaust the keyspace even if all the 
     proxies went down.  The worst-case for the current method is that it 
     would never complete.
            -- Eric Gindrup ! gindrup at Okway.okstate.edu


______________________________ Reply Separator _________________________________
Subject: Re: Re[4]: [rc5] Random keyblocks
Author:  <rc5 at llamas.net> at SMTP
Date:    1997/08/26 13:09


On Tue, 26 Aug 1997, Eric Gindrup wrote:
     
> 
>         Perhaps better would be to hash the "block-space" so that the 
>      hashed sequence of blocks would be random enough to wander all over 
>      the keyspace.  Then percentages completed could be reported with 
>      incoming blocks to the client.  So a random block could be generated 
>      from the last x% of the hashed keyspace where x is the unchecked 
>      percentage.
>         There would always be some marginal percentage that a random block 
>      was wasted, but that percentage could be controlled by limiting the 
>      interval from which the proxies are assigning blocks under the 
>      assumption that the percentage complete indicator is updated 
>      occasionally at the client.
     
Uh - I don't see any advantage in hashing the key order - it will only 
make coordinating with other efforts more difficult (as in Cyberian 
telling us "How about we swap info as to what has already been done so we 
don't waste time...")...  It certainly won't make coordinating the 
keyspace any easier.
     
>      
>         Also, clients aren't expected to connect to get tardy blocks.  
>      Tardy blocks are expected to be assigned infrequently with a regular 
>      block.  So, if that client ever can't connect to get more blocks, it 
>      runs through its tardy blocks (or, equivalently, "highly useful 
>      'random' blocks") and then generates random blocks until it can report 
>      all completed work to a proxy.
     
Instead of buffering tardy blocks, why just not add the same number of 
extra buffers to the main cracking engine?  It is just as easy to download 
a "guaranteed-untested" block as a tardy one.  Plus, when the person who 
left his computer off for a month-long vacation comes back, he won't be 
wasting CPU time processing his now-worthless buffers.
     
>         The overhead of transmitting or storing the occasional tardy block 
>      is very low.  Furthermore, if one were concerned that a fast client 
>      with a reliable connection were to collect too many tardy blocks, then 
>      perhaps the client should have (yet another) option to limit the 
>      number of tardy blocks that it will collect.  Either it can work on 
>      them when the tardy limit is reached, or it can refuse to accept new 
>      tardy blocks.  A refused tardy block would just become tardy again and 
>      be reassigned to someone else.
>         The idea is that tardy blocks are assigned when the connection to 
>      the proxy is working and are only worked on when that connection is 
>      bad.  This increases the utility of the offline work over that of 
>      purely random block generation. 
>      
     
Again, this is the whole reason that we buffer keys in the first place - 
so that there is something to work on when the connection is bad.  The 
only reason that you would generate random-keys at all is that you cannot 
make the buffer infinately large (for obvious reasons)...  Instead of 
having clients keep track of 200 active keys and 50 tardy ones, it is at 
least as efficient and possibly more efficient to have it store 250 active 
ones...  This number can be set to any reasonable value, and is a lot 
easier to change in the programming than adding some secondary method of 
key-distribution...
     
>         Finally, the only reason I can see for supporting purely random 
>      block generation is concern that clients are improperly reporting 
>      completion of blocks.  Perhaps a rogue client or some such is 
>      misreporting block completions.  The random blocks would thus serve as 
>      a check that reported blocks actually don't contain the desired key.  
>      Simplicity of coding is also an issue in random block generation, but 
>      the simplest design is just to exit.
     
You have to admit that random keys get more work done than the "just exit" 
alternative.  Plus, when the connection resumes, the "just exit" 
alternative will be very costly...  Even if you were to handle tardy keys 
- imagine a prolonged period of bad connection - eventually you have to 
run out of tardy keys - either you waste time or generate random keys.
     
Is this argument really worth worrying about anyway?  Does anyone simply 
leave their computer running for days on end crunching random keys?  If 
so, I think the best idea is simply to increase the buffer-size (which has 
to be an elementary process)...
     
----------------------------------------------------------------- 
Richard T. Freeman <rfreeman at netaxs.com> - finger for pgp key
3D CB AF BD FF E8 0B 10 4E 09 27 00 8D 27 E1 93 
http://www.netaxs.com/~rfreeman - ftp.netaxs.com/people/rfreeman
     
----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the
body.
     


----
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.



More information about the rc5 mailing list