Re: The market of ASICs (One GigaKey / Second?)

>> There's also no easy way to verify bogus results - you could force 
>> the client to check for a key in the block which causes the encrypted 
>> output to match some 32-bit value specified by the server
>
> If you ask the client to search for a fixed result a bogus client 
> would be able to quit once it found that result and on average only 
> search half the keyspace. The trick is to ask the client to search for 
> the best match to a pattern where the real key is always the very best 
> match possible and a second key that the server picked is a known 
> pretty good match. A valid client will return either the key selected 
> by the server or a better matching key. A bogus client would not know 
> when it finds one match if the secondary key known by the server is an 
> even better match. The percentage or the keyspace not searched 
> corresponds to a probability that the bogus client will  be caught. 
> After a sufficient number of blocks any cheater will eventually be 
> caught.
>
> The best part is that searching for the pattern requires at most 1 
> additional instruction in the main loop and no additional registers.
>
> A side benefit is that returning the real key is no longer a specially 
> handled case in the client or any of the secondary servers.

Except you do need to load the pattern from memory at some point, or 
keep it in a register, which is expensive. You then need to figure out 
what 'best matching' means, which takes a few extra cycles (and in a 
land where 3% is a lot, it may not really be worth it). You also need 
to find a 'pretty good match', which means the server has to hunt 
through the keyspace too, which is wasteful.

And the client cannot bail after searching half the keyspace, because 
on average there will be one false-positive in each 32-bit block (since 
we only tell it to check 32 bits). I wrote a simulator for what would 
happen if the client bails after each 'challenge' key has a match 
(shortly after I hacked one of the PPC cores).

With only one challenge key,
3314913138638848/9007199254740992 keys tested, 771662/2097152 blocks 
rejected
0.36803 keys actually tested, 0.63204 blocks into stats

With two, three, and four,
4678371744415744/9007199254740992 keys tested, 988268/2097152 blocks 
rejected
0.5194 keys actually tested, 0.52876 blocks into stats

5468646085361664/9007199254740992 keys tested, 1086408/2097152 blocks 
rejected
0.60714 keys actually tested, 0.48196 blocks into stats

5990341302747136/9007199254740992 keys tested, 1141522/2097152 blocks 
rejected
0.66506 keys actually tested, 0.45568 blocks into stats

Of course, this also means we have up to 2^32 matches in each block. We 
can just allocate space for, say, 32 matches, and let the client off if 
it manages to fill all of these (of course, it means that the client 
could choose to skip the rest of the keys once this happens, but that's 
rare enough).

It doesn't matter if we only use one challenge anyway, since (assuming 
it's for stats purposes) the 36% of blocks that don't make it into 
stats are hard to avoid. Of course, the challenge key would have to be 
generated using some hash-function and a secret, which each proxy would 
have, which might have security risks.

- Purr

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