"Designing and implementing malicious hardware"
Ed Gerck
edgerck at nma.com
Mon Apr 28 15:58:23 EDT 2008
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
More information about the cryptography
mailing list