Design-for-Trust Techniques

Logic Locking

logic encryption flow

Logic locking (encryption/obfuscation) inserts locks into a given design netlist at the gate or RT level. The resulting netlist is locked; instead of taking the original design through the potentially untrusted flow, the netlist with the locks goes through the physical design steps and gets fabricated. Upon fabrication the chip is locked; the correct secret key needs to be loaded on the chip to unlock the chip. The chip, when locked, produces wrong outputs, and is thus useless. Logic locking therefore protects against overproduction by the foundry.

The locked design netlist can be obtained by reverse engieering during any of the untrusted stages; yet it will be of no use without the knowledge of the secret key. Logic locking therefore protects against design IP piracy.

logic encrypted netlist

When the foundry has produced chips with logic locking built-in, each chip will have to be unlocked (activated). Only then the chip produces the correct outputs and becomes functional. The key is the designer’s secret, and is hidden from all the untrusted parties, including the foundry. Unlocking the chip refers to loading this secret key somewhere safe on the chip; this can be tamper-proof memory, for instance. The same secret key can be shared for the entire family of chips produced from the same design, or unique keys can be used for individual chips by integrating a PUF into the design.

The lock elements can be simple XOR/XNOR gates — key gates — with one input controlled by the secret key bit. Every key gate needs to be configured into either a buffer or an inverter in order to restore the functionality of the original netlist. The exact configuration is dictated by the secret key, which is known only by the designer. Wrong key bits configure the key gates to wrong functionality, leading to “errors” stemming from the key gates. These errors may propagate to the outputs and corrupt them.

encrypted IC

Types/Objectives of Logic Locking

logic encryption types

In random logic locking, key gates are inserted at random locations in the letlist. This technique was proposed in: “EPIC: Ending piracy of integrated circuits” by Roy, Koushanfar and Markov at DATE 2008.

In fault analysis based logic locking, key gates are inserted so as to maximize corruption at the outputs when a random wrong key is loaded on the chip. Refer to our papers c55 and j41, or patent p9 for more details.

In strong logic locking, key gates are inserted such that they interfere with each other maximally, preventing individual sensitization of key bits to the outputs. For more details, please refer to our papers c58 and j49, or patent p14.

Random logic locking cannot ensure a controlled level of corruption at the outputs; when an attacker tries a random incorrect key, the chip may still produce almost correct outputs. We therefore developed fault analysis based logic locking; in this technique, key gates are inserted in locations that have the most influential effect on the outputs. The locations are identified via a fault analysis through the use of fault simulation. This way, when an attacker tries a random incorrect key, most of the outputs will produce wrong results (be corrupted).

We also showed that both random and fault analysis based logic locking techniques are vulnerable to attacks that have access to a reverse engineered locked netlist and a working chip (oracle). We illustrated this attack where the attacker computes, from the locked netlist, specialized input patterns that can “leak” key bits to the outputs. We refer to this attack as the sensitization attack. This attack then uses the specialized patterns on the working chip, and infers the secret key (stored on-chip) from the responses collected from the chip.

To protect against sensitization attacks, we developed strong logic locking. In this technique, the key gates are inserted in a way that maximizes interference between them, preventing their individual sensitization to the outputs. We used a graph-theoretical approach to identify the best locations in the design to insert key gates and form a large clique of interference between them.

Recent Attacks on Logic Locking

SAT attack

A recent Boolean Satisfiability (SAT) based attack was proposed by Subramanyan, Ray and Malik to break our strong logic locking. The paper “Evaluating the Security of Logic Encryption Algorithms” was presented at HOST 2015 and won the best paper award. The attack relies on iteratively determining discriminating inputs (DIs). When a DI is applied to two instances of the netlist with two different keys, the output of the two instances will be different. The attack employs a SAT solver to compute the DIs.

The computed DI is then applied to the chip. The chip response is used to eliminate the incorrect keys that lead to a response that differs from the one obtained from the chip. Subsequently, a new DI is determined, and this process is repeated until all the incorrect keys are determined, resulting in a successful attack. The output of the attack is the correct key. Mode details about this attack as well as the code is available online.

Defense Against SAT Attacks: SARLock [c95]

SARLock architecture. Logic under protection can be optionally locked (SLE). For one input combination, the design output needs to be flipped; that’s when the flip signal is asserted. For more information on SARLock, refer to our paper c95 and patent p17.

The worst-case scenario for the SAT attack arises when the attack can discriminate at most one incorrect key value with each DIP. We developed SARLock, a SAT attack resistant architecture, based on this simple observation. We modify the functionality of the design under protection by flipping its response to only one input combination. Optionally, in addition, the design under protection can be logic locked using strong logic locking. To restore the functionality of design under protection, we also use a flip signal, which is rarely active. It is asserted only for specific input and key value combinations; when asserted, it flips the output of the design back to the correct value.

The illustration above is for protecting only one logic cone (only one output), while it easily can be extended to multiple cones. The designer’s secret is the input combination for which the output of the design is flipped. It could be any input combination, leaving the attacker with exponentially many input combinations to try and find out. Furthermore, as the design under protection is made minimally different from the original version from a functionality point of view (the two produce different outputs for only one input combination), the resulting locked circuit achieves the desired resistance against the SAT attack (has exponential attack complexity on SARLock) at minimal overhead.

When to Activate Logic Locked Chips: Pre-Test or Post-Test? [c92]

logic encryption types

State of the art logic locking frameworks pursue two different activation models, pre-test and post-test activation,  that differ in the time of activation of an IC with respect to the manufacturing test.

Pre-test activation: The ICs are activated prior to the manufacturing test, typically conducted in the foundry or outsourced to an OSAT.
Since the IP owner does not want to reveal the secret key to the untrusted foundry, on-chip public key cryptographic infrastructure is used to load the secret key securely on the chip. On passing the manufacturing test, the ICs are shipped for assembly/sales directly from the foundry, which is  useful in meeting time-to-market constraints.

Post-test activation: The ICs are activated after performing the manufacturing test. Either remote activation or in-house activation can be employed. In-house activation requires shipping of the locked IC from the foundry to the trusted facility, eliminating the need for  on-chip cryptography.

Test Data Mining Attack [c92]

We developed a test data mining attack that can successfully determine the logic locking key of a pre-test activated chip by utilizing the test data. The attacker is a person in the foundry or test facility with access to an locked netlist and test stimuli and responses. The attack searches for the key that maximizes the fault coverage for the given set of test patterns on the locked netlist.

The rationale for the attack to return the correct key is that the test patterns have been generated with the objective of maximizing the fault coverage in the presence of the correct key as a constraint. When the same set of test patterns are used as constraints, the key that maximizes the fault coverage will  be the one that is used to generate the patterns.

Attacks and defenses on logic locking to be continued…