"Designing and implementing malicious hardware"

[Ed Gerck]

Perry E. Metzger wrote:
> Ed Gerck <edgerck at nma.com> writes:
>> Each chip does not have to be 100% independent, and does not have to
>> be used 100% of the time.
>>
>> Assuming a random selection of both outputs and chips for testing, and
>> a finite set of possible outputs, it is possible to calculate what
>> sampling ratio would provide an adequate confidence level -- a good
>> guess is 5% sampling.
> 
> Not likely.
> 
> Sampling will not work. Sampling theory assumes statistical
> independence and that the events that you're looking for are randomly
> distributed. 

Provided you have access to enough chip diversity so as to build a 
correction channel with sufficient capacity, Shannon's Tenth Theorem 
assures you that it is possible to reduce the effect of bad chips on 
the output to an error rate /as close to zero/ as you desire. There is 
no lower, limiting value but zero.

Statistical independence is not required to be 100%. Events are not 
required to be randomly flat either. Sampling is required to  be 
independent, but also not 100%.

> We're dealing with a situation in which the opponent is
> doing things that are very much in violation of those assumptions.

The counter-point is that the existence of a violation can be tested 
within a desired confidence level, which confidence level is dynamic.

> The opponent is, on very very rare occasions, going to send you a
> malicious payload that will do something bad. Almost all the time
> they're going to do nothing at all. You need to be watching 100% of
> the time if you're going to catch him with reasonable confidence, but
> of course, I doubt even that will work given a halfway smart attacker.

The more comparison channels you have, and the more independent they 
are, the harder it is to compromise them /at the same time/.

In regard to time, one strategy is indeed to watch 100% of the time 
but for random windows of certain lengths and intervals. The duty 
ratio for a certain desired detection threshold depends on the 
correction channel total capacity, the signal dynamics, and some other 
variables. Different implementations will allow for different duty 
ratios for the same error detection capability.

> The paper itself describes reasonable ways to prevent detection on the
> basis of most other obvious methods -- power utilization, timing
> issues, etc, can all be patched over well enough to render the
> malhardware invisible to ordinary methods of analysis.

Except as above; using a correction channel with enough capacity the 
problem can /always/ be solved (ie, with an error rate as close to 
zero as desired).

> Truth be told, I think there is no defense against malicious hardware
> that I've heard of that will work reliably, and indeed I'm not sure
> that one can be devised.

As above, the problem is solvable (existence proof provided by 
Shannon's Tenth Theorem).  It is not a matter of whether it works -- 
the solution exists; it's a matter of implementation.

Cheers,
Ed Gerck

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com