[Hardware] "success"

[Dan Oetting]

On Oct 18, 2006, at 7:23 PM, Martin Klingensmith wrote:

> How often is the first 28 bits of cypher text correctly matched?

If you used a fixed key and tested all 2^64 possible clear texts,  
there would be exactly 2^36 matches or on average 1 in 2^28. It is  
assumed that using a fixed clear text and varying the key will  
produce the same results. If the results were different it would  
indicate a weakness in the cypher that might be exploitable.

Keep in mind though that this is an average and there is no is no  
guarantee of the run between matches. It is possible to find adjacent  
keys that each produce a match. In fact I ran my own search to find  
examples of adjacent keys that caused a match in the first 32 bits in  
the cypher text so I could properly test my cores for this edge  
condition.

About 1/3rd of the time there will be no key within a block that  
generates a match. Another 1/3rd of the blocks will have exactly 1  
match and the rest will have 2 or more matches. I posted the numbers  
to this list about 2 years ago:

>> For an expected occurrence of 1 event in 2^32 the probability of N  
>> occurrences in 2^32 trials (ie: the number of partial match keys  
>> in 1 block) is:
>>
>> N		P
>> 0		0.36787944113	~1/e
>> 1		0.36787944121
>> 2		0.18393972061
>> 3		0.06131324019
>> 4		0.01532831004
>> 5		0.00306566201
>> 6		0.00051094367
>> 7		0.00007299195
>> 8		0.00000912399
>> 9		0.00000101378	about 1 in a million

There was a good discussion about hardware cores and interfacing with  
d.net around 8/15/04 on this list. You should jump back into the  
archives for that time period.

-- Dan Oetting