[rc5] Random keyblocks
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 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
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
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
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: [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
> 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
> 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
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5