[Hardware] Notes... The case for an open client
dan_oetting at uswest.net
Sun Aug 15 14:17:08 EDT 2004
On Aug 15, 2004, at 2:35 AM, jbass at dmsd.com wrote:
> Finding very large keys has some components not that different than
> playing the lottery ... blind luck with some intuition.
The strategy you suggest is not valid for crypto contest because the
key actually is random and not just appears random. For picking
lottery numbers it makes sense to look at the appearance of randomness
but your strategy needs to be inverted because the actual lottery
results are random but you want to avoid sharing the prize with other
people that mostly pick numbers based on the appearance of randomness
and personal numbers.
> Sure the key might well have a long run length, which doesn't remove
> need of 100% searching the key space worst case. I just don't think
> useful to spend 30 years searching unlikely corners of the key space
In the crypto contests the key is generated by a computer random number
generator with a uniform distribution. No human has ever seen the key
so it cannot have been filtered out for not looking random enough.
Every possible key has exactly the same probability of being the real
key so there is no strategy to searching when there is only 1 player.
> Any key allocation system should allow the researcher to ask for a
> key block. If the key sequence is not purely sequential, the researcher
> should be able to specify that the block was not 100% checked, and that
> should be noted in the database as a block that should be sequentially
> checked at some point.
Do you have a magic ability to out guess a random number generator?
If there are multiple groups searching a large key space the space
should be divided into several large blocks and allow each group to
pick the block they will process next. It won't make any difference in
finding the winning key but it will prevent groups from blaming their
failure on someone else's pick. To prevent the groups failure being
blamed on the individual that picked the groups block each group will
probably use a random event to pick the block anyway.
The problem with allowing self assigned blocks for individuals is the
management and tracking of those block assignments. There is a maximum
size table that can be easily managed through the life of the project.
If the assignments are managed by hand the upper limit is a few hundred
or thousand. If the management is automated a few million is doable.
The RC5-72 key space is 72 bits. Individual work units process 32 of
those bits. In the last contest d.net was handling blocks of 2^28 work
units at a time. This leaves 12 bits or 4096 super blocks to be picked
and processed. Taking into account todays larger disk and memory on
faster processors it man not be unreasonable for projects to work
blocks of 2^32 work units (except that 32 bit databases cannot store a
full 2^32 records and might need to be handled as 2 parts of 2^31 work
With projects handling 64 bits at a time that leaves 8 bits or 256
blocks for projects to pick from. Coordination of these assignments can
easily be handled by the projects publicly declaring which blocks
they've done, the block they are currently processing and the next
block they plan to work.
From the rc5 reference code published by d.net I presume that the low
byte of the low word of the key is the project block number. Someone
with inside knowledge at d.net might want to confirm this and also
report which project block d.net is starting with.
More information about the Hardware