[Hardware] The market of ASICs (One GigaKey / Second?)

Elektron elektron_rc5 at yahoo.ca
Tue Aug 10 14:33:57 EDT 2004


>> pt 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.
>
> Here is the magic that makes it work:
>
> Currently the client compares the encrypted result of each key to the 
> target cypher text. We replace this compare with a mask and test for 
> 0. If we are testing the first 32 bits and the mask has 8 bits set an 
> average of only 1 in 256 keys will pass this first test and we have 
> done no more work than the client already does. The second half of the 
> encrypted text will also be tested with the second half of the mask 
> and only 1 in 65536 keys will pass this second test.

It's probably better to have more bits in the first mask than to bother 
with loading the second mask, albeit giving the server a little more 
work to do.

> The "best" key is defined as numerically closest to the real key after 
> passing the mask test. At this point we load the real cypher text, xor 
> with the encrypted result, load the previous best result and compare. 
> If the new result is smaller than the previous result we save the new 
> result and the current "best" key. All this extra work only happens 
> for a small number of keys so the overhead is minimal (except for 
> hardware implementations that can't branch).

"numerically closest to the real key"? But how do you know the real 
key? (I think you mean real cipher text)

Hardware implementations that can't branch may be a problem, but then, 
it's a problem anyway (since it won't know what to do when it finds a 
match). An easy way is to pass matches to a separate unit, which 
compares with the ciphertext when data comes in (and then stuff a FIFO 
between them, since it's probably going to be slower).

- Purr



More information about the Hardware mailing list