Paper 2021/1245

SeqL+: Secure Scan-Obfuscation with Theoretical and Empirical Validation

Abstract

Existing logic-locking attacks are known to successfully decrypt a functionally correct key of a locked combinational circuit. Extensions of these attacks to real-world Intellectual Properties (IPs, which are sequential circuits) have been demonstrated through the scan-chain by selectively initializing the combinational logic and analyzing the responses. In this paper, we propose SeqL+ to mitigate a broad class of such attacks. The key idea is to lock selective functional-input/scan-output pairs of flip-flops without feedback to cause attackers to decrypt an incorrect key, and to scramble flip-flops with feedback to increase key length without introducing further vulnerabilities. We conduct a formal study of the scan-locking and scan-scrambling problems and demonstrate automating our proposed defense on any given IP. This study reveals the first formulation and complexity analysis of Boolean Satisfiability (SAT)-based attack on scan-scrambling. We formulate the attack as a conjunctive normal form (CNF) using a worst-case O(n^3) reduction in terms of scramble-graph size n, making SAT-based attack applicable and show that scramble equivalence classes are equi-sized and of cardinality 1. In order to defeat SAT-based attack, we propose an iterative swapping-based scan-cell scrambling algorithm that has linear implementation time-complexity and exponential SAT-decryption time-complexity in terms of a user-configurable cost constraint. We empirically validate that SeqL+ hides functionally correct keys from the attacker, thereby increasing the likelihood of the decrypted key being functionally incorrect. When tested on pipelined combinational benchmarks (ISCAS, MCNC), sequential benchmarks (ITC), and a fully-fledged RISC-V CPU, SeqL+ gave 100% resilience to a broad range of state-of-the-art attacks including SAT [1], Double-DIP [2], HackTest [3], SMT [4], FALL [5], Shift-and-Leak [6], Multi-cycle [7], Scan-flushing [8], and Removal [9] attacks.