Hardware-Trojan resilient blockcipher implementation based on multi-party computation

Integrated circuits are now deployed in a continuously increasing range of applications. For many of them, sensitive data is manipulated, leading to technical and legal issues regarding its security. In this context, protection mechanisms are usually included in order to prevent various types of adversaries. At the most abstract level, cryptographic algorithms and protocols ensure that it is theoretically feasible to communicate privately and to guarantee message authenticity. More practically, various type of physical attacks can take advantage of features and imperfections in cryptographic implementations. Well-known threats are the cases of side-channel adversaries (taking advantage of unintended information leakages, e.g. due to the power consumption of the implementations) or fault adversaries (trying to force the implementation to perform erroneous computations). In this work, we are concerned with an even more powerful type of physical adversary, next denoted as the hardware Trojan adversary. In summary, the hardware Trojan adversary is not only able to observe the implementation at run time, but to maliciously modify its hardware at manufacturing time. Typical examples of hardware Trojans are “cheat codes” (e.g., sending the secret data under some rare input pattern) or “time bombs” (e.g., sending secret data at some time). Such extreme adversaries are motivated by the increasing need of trust in integrated circuits. That is, recent news have shown that untrusted software is deployed and exploited (as typically emphasized by the Snowden revelations). Ultimately, this implies that the design of secure systems has to start by trusted hardware -- a problem for which little solutions exist so far. More precisely, the state-of-the-art literature suggests that detecting hardware Trojans is both technically challenging (if not impossible), and hard to formalize (which implies hard to quantify risks). Hence, an alternative is to prevent hardware Trojans actively. In this respect, a recent work published at ACM CCS 2016 introduced a theoretically founded way to mitigate hardware Trojans thanks to “testing amplification”. It essentially exploits secret sharing and multiparty computation to prevent cheat codes, and redundant randomized testing to prevent time bombs. Based on this solution, it is possible to render the probability of a hardware Trojan attack exponentially small, if the run time of the circuit is limited. In this paper, we extend this theoretical work towards practice in two important directions. First, we designed a hardware architecture for a Trojan-resilient circuit for two block ciphers (the standard AES and lightweight Mysterion), based on an improved multi-party computation protocol, and implemented the architecture on a concrete prototype connecting three FPGAs. This allowed us to evaluate the performances of such a Trojan-resilient circuit on a concrete basis, confirm practical applicability, and to identify bottlenecks and tracks for improvement. Second, one core assumption of such Trojan-resilient circuits is the existence of a small “trusted master circuit”, of which the size has to be minimized. We analyzed the implementation of such a master, confirmed that it is indeed minimum compared to the implementation of the full block ciphers, confirming theoretical analyses with quantitative experimental data. We additionally investigated the effectiveness of a side-channel based hardware Trojan detection for such a small master and show positive results for the practically-relevant case of time bombs.