Re: Notes... The case for an open client

On Aug 15, 2004, at 2:35 AM, jbass-/[email protected] 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 
> the
> need of 100% searching the key space worst case. I just don't think 
> it's
> useful to spend 30 years searching unlikely corners of the key space 
> first.

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 
> specific
> 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 
units each).

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.

_______________________________________________
Hardware mailing list
Hardware-Ra3b/QYEcJ3d140v2zMXi0fjHoOT/h/[email protected]
http://lists.distributed.net/mailman/listinfo/hardware