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

Hi Dan,

Thanks for the talking points. When I started this path several years
ago I had a DigiLab XLA, and several Xilinx AFX BG560 (and other) boards
with Virtex and Virtex-E parts. By far the easiest way to deal with most
Xilinx derivative boards with with JTAG, which allows the part to be
controlled, monitored, programmed, and even provides real-time diagnostic
interfaces to your FPGA code that can be useful as a standard means of
controlling your project and recieving results back from it. I will try
over the next couples weeks to offer up a sample JTAG serial core that
can be easily ported and packed into most Xilinx Spartan and Virtex parts.

It's not clear to me that searching blocks with high order bits set is
the best way to attack this problem. While I'm the farthest thing from
a math head, certain concepts are almost difficult to escape once you
get hooked on crypto. One strong side interest for tackling the larger
keys is to use concepts from probabilistic number theory and computational
number theory to generate the search sequence. Some very significant parts
of the key space may have very very low probablities, plus several choices
in key sequence generation can impact inner loop performance/work.

Finding very large keys has some components not that different than
playing the lottery ... blind luck with some intuition.

Study of run lengths in 32 bit numbers:
Run     Number  MaxLength  Num%  Max%
00           0          0   .00   .00
01 35433480192         32 51.56   .00
02 17179869184    9227431 25.00   .21
03  8321499136  389618073 12.10  9.07
04  4026531840 1153584655  5.85 26.85
05  1946157056 1161804348  2.83 27.05
06   939524096  757380532  1.36 17.63
07   452984832  413906593   .65  9.63
08   218103808  210083327   .31  4.89
09   104857600  103266008   .15  2.40
10    50331648   50026536   .07  1.16
11    24117248   24061184   .03   .56
12    11534336   11524608   .01   .26
13     5505024    5503472   .00   .12
14     2621440    2621224   .00   .06
15     1245184    1245161   .00   .02
16      589824     589823   .00   .01
17      278528     278528   .00   .00
18      131072     131072   .00   .00
19       61440      61440   .00   .00
20       28672      28672   .00   .00
21       13312      13312   .00   .00
22        6144       6144   .00   .00
23        2816       2816   .00   .00
24        1280       1280   .00   .00
25         576        576   .00   .00
26         256        256   .00   .00
27         112        112   .00   .00
28          48         48   .00   .00
29          20         20   .00   .00
30           8          8   .00   .00
31           3          3   .00   .00
32           1          1   .00   .00
33 68719476736 4294967295

These numbers omit runs of high order zeros, so there are a few
counts missing, which are almost insigificant numerically.

These numbers don't change significantly as you go up to 64 or 72 bit
words, other than the max run lengths are up a digit or two, which you
can expect from the increased probability from the table above. Given
that most crypto algorithms are designed to produce what appears to be
a random uniform bit field for keys and encrypted data, probability
theory would suggest searching the key space in the order of the most
probable bit run lengths in the key space. In this case, I believe
searching keys with one or two maximum run lengths of 5, then 6 (either
zeros or ones), is the most probable place to find a solution, then work
out from there. This generally suggests that checking keys with a run
of 30 zeros or ones may be spending effort checking a very unlikely key.

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.

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.

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