4 ms·

One idea on how to verify equivalence between a design and a physical chip: If we have the design, could we generate instruction sequences (or, in general, inp

by catern 7y ago

One idea on how to verify equivalence between a design and a physical chip: If we have the design, could we generate instruction sequences (or, in general, input sequences) and deterministically predict the time required and power consumed to execute those instruction sequences? Then we could fuzz the chip with a bunch of generated code and measure that the consumed time and power matches what we expect. Any backdoor would throw off the measurements. Can anyone who knows hardware better comment on whether there are other kinds of attacks that this wouldn't cover? This idea is inspired by a paper I read once which used a somewhat similar approach for verifying that a hardware system hadn't been infected by persistent firmware malware. The authors had the system compute a function which had a known memory-optimal implementation which required the use of all the persistent memory available in the system (including firmware, etc.). Unfortunately I can't find the paper now.

darawk 7y ago
Not an expert, but AFAIK that is how most "remote attestation" schemes work, so it seems like a viable approach.
anfilt 7y ago
Well math wise its kinda impossible to know if a black box implementation is malicious from outputs alone. Its in a similar vein to the halting problem. Whether side channels such as power work I would have to find the paper, but what your suggesting is impossible at least in general from my understanding. I have also read a few papers also using emf emissions. Although they all certainly would increase attack difficulty. There also the problem of margin of error. Could an attack hide in the allowed tolerances of error. Also if the tolerance is too small a lot genuine/unaltered devices may trigger false positives.
bunnie 7y ago
While power signatures are repeatable on a single-chip basis, from chip-to-chip the variation in individual transistor performance will require a tolerance to be applied on the threshold criteria for determining if a given power signature is correct or not across a population of chips. Furthermore, power consumption is also dependent upon temperature and voltage so that will need to be carefully controlled for the measurement. The wider the tolerance on the power measurement, the larger the implant that can be buried. Unfortunately transistor performance can vary quite widely for a single design; recall that a single CPU mask design is often sold in several speed grades. These aren't different designs, they are all the exact same design but then tested to pass at a given frequency and power profile. My intuition is that a simple implant would probably escape power characterization, and larger implants can be left off until a trigger condition is met. That condition could be made so that fuzzing is highly unlikely to hit it, e.g. a particular 64-bit number pattern has to appear in a given register to power on the implant. The technique may be suitable to detect gross anomalous execution in a single well-characterized chip but I feel any robust criteria against false positives would also leave a sufficiently large margin for small implants to slip through undetected.
- catern 7y ago
  Thanks for the in-depth reply! That makes sense that the primary flaw is that nondeterministic attributes of a particular physical chip generated from a design will cause its individual characteristics to vary too widely. It's interesting - there is a loose analogy to reproducible builds chasing down and squashing every source of nondeterminacy in software builds. I'm guessing that's not possible to do that for chip fabs for deep physics reasons + reasons of efficiency, but maybe some other trick (recording the "random seed"?) could be used... And the thought that verified chips require a verified chip fab process is appealing! But I know nothing about chip fabrication processes, so I'll leave it at that.
- anfilt 7y ago
  Yea state space is also a huge problem, like even something as simple as 2 random numbers in 2 different 64 bit registers gives your an 2^128 possible inputs. Aka basically impossible to randomly stumble across and fuzzing would never show it.
krupan 7y ago
Every chip design created also has a large number of test vectors created with it. If the test team has done their job well then those will include random fuzzing and power monitoring like you mention. As I read this article I thought about this as well. Every chip is tested as part of the manufacturing process, but as Bunnie points out, to be really secure you can't just trust the manufacturer when they say the tests all passed. If there were some way to run all the tests on the finished silicon product myself, would I trust it? It's very hard (expensive, time consuming) to test everything in a modern chip, however, it would certainly make it harder for a malicious mask change to go unnoticed.

by catern 7y ago

darawk 7y ago

Not an expert, but AFAIK that is how most "remote attestation" schemes work, so it seems like a viable approach.

anfilt 7y ago

Well math wise its kinda impossible to know if a black box implementation is malicious from outputs alone. Its in a similar vein to the halting problem. Whether side channels such as power work I would have to find the paper, but what your suggesting is impossible at least in general from my understanding. I have also read a few papers also using emf emissions. Although they all certainly would increase attack difficulty. There also the problem of margin of error. Could an attack hide in the allowed tolerances of error. Also if the tolerance is too small a lot genuine/unaltered devices may trigger false positives.

bunnie 7y ago

While power signatures are repeatable on a single-chip basis, from chip-to-chip the variation in individual transistor performance will require a tolerance to be applied on the threshold criteria for determining if a given power signature is correct or not across a population of chips. Furthermore, power consumption is also dependent upon temperature and voltage so that will need to be carefully controlled for the measurement. The wider the tolerance on the power measurement, the larger the implant that can be buried. Unfortunately transistor performance can vary quite widely for a single design; recall that a single CPU mask design is often sold in several speed grades. These aren't different designs, they are all the exact same design but then tested to pass at a given frequency and power profile. My intuition is that a simple implant would probably escape power characterization, and larger implants can be left off until a trigger condition is met. That condition could be made so that fuzzing is highly unlikely to hit it, e.g. a particular 64-bit number pattern has to appear in a given register to power on the implant. The technique may be suitable to detect gross anomalous execution in a single well-characterized chip but I feel any robust criteria against false positives would also leave a sufficiently large margin for small implants to slip through undetected.

catern 7y ago
Thanks for the in-depth reply! That makes sense that the primary flaw is that nondeterministic attributes of a particular physical chip generated from a design will cause its individual characteristics to vary too widely. It's interesting - there is a loose analogy to reproducible builds chasing down and squashing every source of nondeterminacy in software builds. I'm guessing that's not possible to do that for chip fabs for deep physics reasons + reasons of efficiency, but maybe some other trick (recording the "random seed"?) could be used... And the thought that verified chips require a verified chip fab process is appealing! But I know nothing about chip fabrication processes, so I'll leave it at that.
anfilt 7y ago
Yea state space is also a huge problem, like even something as simple as 2 random numbers in 2 different 64 bit registers gives your an 2^128 possible inputs. Aka basically impossible to randomly stumble across and fuzzing would never show it.

krupan 7y ago

Every chip design created also has a large number of test vectors created with it. If the test team has done their job well then those will include random fuzzing and power monitoring like you mention. As I read this article I thought about this as well. Every chip is tested as part of the manufacturing process, but as Bunnie points out, to be really secure you can't just trust the manufacturer when they say the tests all passed. If there were some way to run all the tests on the finished silicon product myself, would I trust it? It's very hard (expensive, time consuming) to test everything in a modern chip, however, it would certainly make it harder for a malicious mask change to go unnoticed.