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

[Dan Oetting]

On Aug 10, 2004, at 4:09 AM, Elektron wrote:

>> 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.

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.

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).

The server needs only to find a key where the encrypted text has 8 or 
more zero bits in common with the real cypher text in the first word. 
On average the server should need to look at only 2 keys per block.

Proxy servers don't need to share the same secret to generate blocks as 
long as the master knows all the secrets and knows which proxy 
generated the block.