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

> And therein lies the problem, the bits are not random, but the results
> of a deterministic function, so when I said "may" I ment exactly that..
> I'm not a math head, and I'm not ready to prove or disprove that one
> should simplify the problem with the assumption that the bits are
> effectively random, and use random probabilities to declare that keys
> are all equal in probability. Since you assert that, with "If each bit
> is random" as your proof my choice is wrong and that I'm clueless here,
> I'm very interested in your studied proof that they should be.

Actually, it wouldn't be hard to measure the spin of an electron. Or 
use a Geiger counter (this is actually a worse method, depending on how 
the element decays).

It is NOT simplifying the problem. It's called Game Theory. Pick a 
number between 1 and 4, inclusive. It's probably 3. People pick numbers 
that 'appear' random, and though 1 and 4 are as random as 2 and 3, 2 
and 3 are probably more common.

You somehow assume that computers pick numbers that are 'more random'. 
This is not the case.

> There is significant grey area between without "ANY" and having it your
> choosen field of primary interest to the point that you just "KNOW"
> without question the relationship between numbers in most systems that
> have been extensively studied and are instantly able to recognize
> non-intuitive relationships.

You divided [0,2^32-1] and decided to split it by maximum run length, 
and decided "since maximum runs of 4 and 5 account for most of the 
keys, searching those first will save work". Now, since it's 54% of the 
keyspace, there's a 54% chance you'll get the key (assuming the key is 
random in the interval [0,2^32-1], at 54% of the effort to search the 
entire keyspace. This is true for ANY portion of the keyspace, whether 
it's the first 54%, the last 54%, the middle 54%, or every 42nd key 
that hasn't been tried yet until you get to 54%.

Your list of numbers also assumes that all keys are equally likely, too 
(since each number has an equal weight when you calculate the 
percentages).

If, as you claim, some keys are more likely than others, then imagine 
there exists the following one-to-one function:
f(x) = y, with both x and y in [0,2^72-1], such that P(k=f(x)) >= 
P(k=f(x+1)) for x in [0,2^72-2]. IOW, the function f(x) produces keys y 
in order of decreasing probability with increasing input x. Thus, f(0) 
is the most likely key, f(2^72-1) is the least likely key.

Imagine you know this function, so you start cracking. You increase x 
from 0 to 2^72-1, set y=f(x), and see if k = y. In this way, you search 
the more likely keys first.

Noq, Imagine I hypothetically work at RSA labs, and have produced a 
not-so-random y with the given function. But now, I solve x for f(x) = 
y. Then I set k=f(2^31-1-x). Thus, what was the most likely key is now 
the least likely key, what was the least likely key is now the most 
likely key.

So now your algorithm searches all the unlikely keys first, and 
searches the likely keys last, making it take longer (on average) to 
find the correct key. Except you think it's the other way around. And 
while you're searching the wrong keys, d.net has beaten you.

> I believe with 100 years or so of search time, there is a certain 
> degree
> of luck or intuition in finding the next keys. Why is using a 
> sequential
> key search sequence any more valid than a function which is 
> non-sequential,
> has identical 100% coverage, same work, but has a strong preference to
> order the search by run density?

We (d.net and friends) don't do it purely sequentially, because that 
would be stupid (by allowing RSA labs to dictate when the key was 
found). Instead, I'm quite sure, we allocate "superblocks" to proxies, 
which allocate blocks to clients, which search sequentially.

The best way to search the keyspace is to pick a random 72-bit number 
and start from there. That way, RSA can't predict which keys you'll try 
'first' and use the ones they think you'll try 'last'.

Why is pick-a-silly-function-that-eventually-searches-all-keys invalid? 
Because the overhead of running that function is HUGE. Here we are, 
trying to get small speed increases. The G4 can get a key in 90-some 
cycles. Can you code this function to not incur more than a 10% 
penalty? I doubt it. Can you split it into blocks, which go into stats? 
Probably not.

> Everybody is quick to prefer saving the last couple tests using partial
> matches since that saves a few instructions. A different key ordering
> does exactly the same thing on the front end of the problem, which
> also makes doing sequential searches slightly more expensive over
> a search order specifically designed to avoid the first few tests.

Saving "a few cycles" is a GUARANTEED return. By skipping a few 
calculations, you only need to check 32 bits. Those 32 bits are correct 
only 1/2^32 times, or 1 in 4 billion. Since AltiVec does 4 per cycle, 1 
in a billion. Now, if you save a clock cycle in 90, you do 89/90 of the 
work. On the rare occasion that you find a 32-bit match, abort and 
stuff it through a core that checks the other 32 bits. Assume the 
overheads involved take the time of checking two keys. On average, you 
do 89/90 + 1/1000000000*2 of the work you would have otherwise. That's 
about 98.89%. You guarantee yourself a saving of 1.11%.

Searching the keys in a different order poses no guaranteed return, and 
you need to generate the order. Do it in under 10 cycles, and maybe 
it'll be worthwhile. What do you mean "a search order specifically 
designed to avoid the first few tests"? Do you really think we start 
handing out blocks from 0? Certainly, "[Aug 15 21:46:11 UTC] RC5-72: 
Loaded CA:5F0EA9CD:00000000:1*2^32" makes it look like it doesn't.

- Purr

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