In this paper, we propose a canonical prune-and-SAT (CP&SAT) attack for breaking state-of-the-art routing-based obfuscation techniques. In the CP&SAT attack, we first encode the key-programmable routing blocks (keyRBs) based on an efficient SAT encoding mechanism suited for detailed routing constraints, and then efficiently re-encode and reduce the CNF corresponded to the keyRB using a bounded variable addition (BVA) algorithm. In the CP&SAT attack, this is done before subjecting the circuit to the SAT attack. We illustrate that this encoding and BVA-based pre-processing significantly reduces the size of the CNF corresponded to the routing-based obfuscated circuit, in the result of which we observe 100% success rate for breaking prior art routing-based obfuscation techniques. Further, we propose a new intercorrelated logic and routing locking technique, or in short InterLock, as a countermeasure to mitigate the CP&SAT attack. In Interlock, in addition to hiding the connectivity, a part of the logic (gates) in the selected timing paths are also implemented in the keyRB(s). We illustrate that when the logic gates are twisted with keyRBs, the BVA could not provide any advantage as a pre-processing step. Our experimental results show that, by using InterLock, with only three 8×8 or only two 16×16 keyRBs (twisted with actual logic gates), the resilience against existing attacks as well as our new proposed CP&SAT attack would be guaranteed while, on average, the delay/area overhead is less than 10% for even medium-size benchmark circuits.
more »
« less
BeSAT: behavioral SAT-based attack on cyclic logic encryption
Cyclic logic encryption is newly proposed in the area of hardware security. It introduces feedback cycles into the circuit to defeat existing logic decryption techniques. To ensure that the circuit is acyclic under the correct key, CycSAT is developed to add the acyclic condition as a CNF formula to the SAT-based attack. However, we found that it is impossible to capture all cycles in any graph with any set of feedback signals as done in the CycSAT algorithm. In this paper, we propose a behavioral SAT-based attack called BeSAT. Be-SAT observes the behavior of the encrypted circuit on top of the structural analysis, so the stateful and oscillatory keys missed by CycSAT can still be blocked. The experimental results show that BeSAT successfully overcomes the drawback of CycSAT.
more »
« less
- NSF-PAR ID:
- 10121848
- Date Published:
- Journal Name:
- Asia and South Pacific Design Automation Conference
- Page Range / eLocation ID:
- 657 to 662
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Logic encryption is a powerful hardware protection technique that uses extra key inputs to lock a circuit from piracy or unauthorized use. The recent discovery of the SAT-based attack with Distinguishing Input Pattern (DIP) generation has rendered all traditional logic encryptions vulnerable, and thus the creation of new encryption methods. However, a critical question for any new encryption method is whether security against the DIP-generation attack means security against all other attacks. In this paper, a new high-level SAT-based attack called SigAttack has been discovered and thoroughly investigated. It is based on extracting a key-revealing signature in the encryption. A majority of all known SAT-resilient encryptions are shown to be vulnerable to SigAttack. By formulating the condition under which SigAttack is effective, the paper also provides guidance for the future logic encryption design.more » « less
-
Logic locking has emerged as a promising solution to protect integrated circuits against piracy and tampering. However, the security provided by existing logic locking techniques is often thwarted by Boolean satisfiability (SAT)-based oracle-guided attacks. Criteria for successful SAT attacks on locked circuits include: (i) the circuit under attack is fully combinational, or (ii) the attacker has scan chain access. To address the threat posed by SAT-based attacks, we adopt the dynamically obfuscated scan chain (DOSC) architecture and illustrate its resiliency against the SAT attacks when inserted into the scan chain of an obfuscated design. We demonstrate, both mathematically and experimentally, that DOSC exponentially increases the resiliency against key extraction by SAT attack and its variants. Our results show that the mathematical estimation of attack complexity correlates to the experimental results with an accuracy of 95% or better. Along with the formal proof, we model DOSC architecture to its equivalent combinational circuit and perform SAT attack to evaluate its resiliency empirically. Our experiments demonstrate that SAT attack on DOSC-inserted benchmark circuits timeout at minimal test time overhead, and while DOSC requires less than 1% area and power overhead.more » « less
-
null (Ed.)With many fabless companies outsourcing integrated circuit (IC) fabrication, the extent of design information recoverable by any third-party foundry remains clouded. While traditional reverse engineering schemes from the layout employ expensive high-resolution imaging techniques to recover design information, the extent of design information that can be recovered by the foundry remains ambiguous. To address this ambiguity, we propose ReGDS, a layout reverse engineering (RE) framework, posing as an inside-foundry attack to acquire original design intent. Our framework uses the layout, in GDSII format, and the technology library to extract the transistor-level connectivity information, and exploits unique relationship-based matching to identify logic gates and thereby, recover the original gate-level netlist. Employing circuits ranging from few hundreds to millions of transistors, we validate the scalability of our framework and demonstrate 100% recovery of the original design from the layout. To further validate the effectiveness of the framework in the presence of obfuscation schemes, we apply ReGDS to layouts of conventional XOR/MUX locked circuits and successfully recover the obfuscated netlist. By applying the Boolean SATisfiability (SAT) attack on the recovered obfuscated netlist, one can recover the entire key and, thereby, retrieve the original design intent. Thus ReGDS results in accelerated acquisition of the gate-level netlist by the attacker, in comparison to imaging-based RE schemes. Our experiments unearth the potential threat of possible intellectual property (IP) piracy at any third-party foundry.more » « less
-
Logic encryption is a hardware security technique that uses extra key inputs to prevent unauthorized use of a circuit. With the discovery of the SAT-based attack, new encryption techniques such as SARLock and Anti-SAT are proposed, and further combined with traditional logic encryption techniques, to guarantee both high error rates and resilience to the SAT-based attack. In this paper, the SAT-based bit-flipping attack is presented. It first separates the two groups of keys via SAT-based bit-flippings, and then attacks the traditional encryption and the SAT-resilient encryption, by conventional SAT-based attack and by-passing attack, respectively. The experimental results show that the bit-flipping attack successfully returns a circuit with the correct functionality and significantly reduces the execution time compared with other advanced attacks.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3287624.3287670
