DynUnlock: Unlocking Scan Chains Obfuscated using Dynamic Keys

Outsourcing in semiconductor industry opened up venues for faster and cost-effective chip manufacturing. However, this also introduced untrusted entities with malicious intent, to steal intellectual property (IP), overproduce the circuits, insert hardware Trojans, or counterfeit the chips. Recently, a defense is proposed to obfuscate the scan access based on a dynamic key that is initially generated from a secret key but changes in every clock cycle. This defense can be considered as the most rigorous defense among all the scan locking techniques. In this paper, we propose an attack that remodels this defense into one that can be broken by the SAT attack, while we also note that our attack can be adjusted to break other less rigorous (key that is updated less frequently) scan locking techniques as well.


I. INTRODUCTION
Many threats have risen as a result of outsourcing in the IC supply chain. Untrusted entities such as foundry and end-user can use tools at their disposal, to steal intellectual property (IP) by reverse engineering, insert hardware Trojans, counterfeit or overproduce the chip [1], [2], [3]. To thwart these attacks, logic locking is considered a viable design-for-trust solution. Earlier logic locking schemes were implemented with high output corruptibility in mind; with an incorrect key the chip should produce most erroneous results for the given input patterns [4], [5]. However, this property was exploited by boolean satisfiability based attack known as the SAT attack in retrieving the secret key of logic locking [6].
SAT attack identifies a distinguishing input pattern (DIP) which prunes the key search space; the attack continues till no such DIP is found and terminates with the correct key. High output corruptibility assists this attack as a larger portion of the key search space is pruned with each DIP. To thwart this attack scan obfuscation/encryption approaches [7], [8] were proposed which obfuscates the scan-in and scan-out data based on a key. As all the successful attacks, such as (App)SAT [9], [6], in logic locking literature relies on scan access, these defenses can be said to thwart logic locking attacks. However, they incur significant area and delay overheads, and mainly find applications in Crypto chips. To protect against IP piracy attacks, more general and scalable solutions are required.
Recently, XOR/MUX based scan obfuscation techniques have been proposed [10], [11], [12], [13] to obfuscate the scan data via XOR/MUX operations based on a secret key through key gates inserted between the scan flops. In [10], a static key is used to obfuscate the scan chain content during scan in and out of patterns, effectively hindering unauthorized scan access. However, this defense was also recently broken by ScanSAT attack [14]. In [11], scan-out ports are blocked whenever the chip is in functional mode or upon a mode switch between functional and test mode, thereby, thwarting SAT-based attacks. However, this defense was also broken recently by shift-and-leak attack [15]. Further, in [12], [13], a dynamic scan locking key is used to obfuscate the scan data; the keys are generated using a Linear Feedback Shift Register (LFSR) based on a secret seed. In [12], the key is updated upon scanning in and out a constant number (p) of patterns, while in [13], the key is updated in every clock cycle. The defense in [13] can be viewed as the most rigorous, and thus, the most secure, dynamic scan locking defense. Indeed, the defense in [12] was broken recently even for its most rigorous version where the key is updated for every pattern (p=1) [16]. Yet, the defense in [13] remains unbroken. The evolution of scan locking defenses and attacks, focusing on the most recent years, is shown in Table I, illustrating the attention this area has been attracting lately.
Contributions: In this paper, we propose a state-of-the-art attack which can break all dynamic scan locking defenses [12], [13]. We present our DynUnlock attack on the most rigorous case of dynamic locking [13] where the scan data gets obfuscated with a new key in every clock cycle. The contributions of this paper are as follows: • We propose DynUnlock that can break all scan locking defenses. • We demonstrate our attack on a small ISCAS-89 dynamically scan locked circuit in Section III-A and perform it on six ISCAS-89 [17] and four ITC-99 [18] benchmarks for 10 different LFSR seeds each. • We aim to recover the secret LFSR seed generating the dynamic keys. We recover the unique seed for 70% of the circuits, and for the remaining 30% we obtain at most 128 seed candidates out of 2 128 , which can be further refined very quickly via brute-force to recover the secret seed. • The execution times of attack are maximum for s38584, s38417, and s35932 benchmarks (< 7 minutes) as they have the maximum number of scan flops post-synthesis.
c 2020 IEEE. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record is published in Proc. Design, Automation and Test in Europe Conference (DATE), 2020.

II. BACKGROUND
SAT attack was a turning point for logic locking research; researchers have now started exploring approaches to thwart this fatal attack. Based on the observation that the success of SAT and other oracle-guided attacks relies on scan access, one promising approach is to obfuscate the scan data as it is delivered in and out of the scan chains.
The defense in [13] obfuscated the scan data dynamically by updating the key in every clock cycle (even within a pattern), resulting in the ultimate dynamic scan locking technique. In this paper, we propose an attack which will, break all versions of dynamic scan locking, including the most rigorous one [13]. We use [13] as a case study to showcase our attack methodology while we note that it is guaranteed to be successful on all other dynamic scan locking versions that are less rigorous than [13], where the key updates less frequently [12].

A. Case Study
Dynamic Encrypt Flip-Flop (EFF-Dyn) [13] combines scan locking approach from [10] and a PRNG, to introduce dynamicity in the defense. During functional mode or the capture operation in test mode (scan enable (SE) signal is low), the secret scan locking key that is stored in the Tamper-Proof Memory (TPM) controls the key gates. During testing, an externally provided test key is expected. When this test key matches the secret scan locking key, the key gates receive this correct key during the scan shift operations (SE signal is high) as well; in case of a mismatch, however, the PRNG that updates the key in every clock cycle controls the key gates dynamically. This is illustrated in Fig. 2.
With an incorrect scan locking key, the chip outputs will be highly corrupted. A testing facility, if trusted, can provide the scan locking secret key as the external test key to have this key (known to them) drive the key-gates during both shift and capture operations during test. Without the knowledge of this secret key, the access to the scan chains is locked based on a very dynamic scan locking key generated by the PRNG.
Security Properties. A dynamically obfuscated scan access is meant to prevent an attacker from applying the generated DIPs through the scan chains, as the PRNG would be updating the key in every clock cycle, thereby, providing resilience against the SAT attack. As a defense that thwarts both SAT and AppSAT attacks, EFF-Dyn seems to be a promising design IP protection technique.

III. PROPOSED ATTACK
In this section, we discuss an attack approach on dynamically locked scan chains with EFF-Dyn as a case study. In our attack, DynUnlock, we aim to recover the seed of the PRNG which produces the key sequence. With the secret seed known, an attacker can gain scan access without the knowledge of the scan locking secret key; an arbitrary test key can be used to leave the scan access control to the PRNG, which can be easily modeled by the attacker as long as its seed is known (see threat model below).
Threat Model. Consistent with the logic locking literature, we assume that the attacker can obtain the design netlist by reverse-engineering the GDSII files or a fabricated chip. This gives her access to all the structural information including the test authentication scheme, the location of key gates, and the PRNG structure and thus, its polynomial function. We also assume that the attacker has access to a working oracle (functional IC). Though she also has access to scan ports physically, the attacker needs to get past the scan obfuscation defense.

A. Attack Methodology
Flowchart. As discussed before, we aim to recover the PRNG or LFSR seed and not the secret key (SK) for this particular case. 1 But, the methodology can be extended to other dynamic scan locking techniques whose seed is the secret 1 Here we assume that the PRNG is designed using an LFSR. c 2020 IEEE. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record is published in Proc. Design, Automation and Test in Europe Conference (DATE), 2020.   Fig. 1 into a SAT attack compatible combinational circuit. s0, s1, and s2 are the seed bits. key [12]. We first start by reverse-engineering the LFSR circuit and obtaining the equations corresponding to each clock cycle. Next, we determine the location of key gates inserted between the scan flops and model this sequential logic circuit into a combinational circuit with scan flops replaced with inputs and outputs. As per the architecture, scan patterns are shifted in and out serially whereas key inputs are applied in parallel. Figure 3 explains the attack methodology in a flowchart.
Combinational Modeling. Consider scan locking on s208 ISCAS-89 benchmark shown in Fig. 1, where the key gates are inserted after 1 st , 2 nd , and 5 th scan flops. The scan-in patterns are denoted by a and scan-out patterns are denoted by b; a denotes the pattern delivered into an obfuscated scan chain and applied to the circuit, and b is the response of the circuit captured in the obfuscated scan chain. During shift operations where dynamic scan obfuscation is in place, a turns into a ; and post-capture, b turns into b, both due to scan obfuscation. Input: seed, a, b Output: a , b F F = number of scan flops in the circuit; seed = number of LFSR bits; cycles = number of LFSR rounds; k y = dynamic key for y th round; Algorithm 1 shows the construction of LFSR keys from a seed, and a relationship between aa and bb in terms of the dynamic key bits. The first for loop corresponds to the LFSR equations, the second for loop corresponds to the relation between aa , while the third for loop corresponds to the relation between bb . This completes our modeling step which results in a combinational locked circuit with seed bits acting as primary key inputs.
SAT attack. Once modeling is complete, the combinational locked circuit is fed to a SAT tool [6] as shown in Fig. 3, which provides a DIP and its corresponding output pattern. We modify the code-base to dump a conjunctive normal form (CNF) after each iteration, which may reveal some of the seed bits. Unlike [16], we can carry out our attack for just one capture cycle. To recover more bits, we restart the LFSR circuit and obtain a new DIP and its corresponding output pattern II: Results for scan locked circuits with 128-bit dynamic keys fed by an LFSR based on a secret seed. All ten benchmarks can be broken to obtain the complete 128-bit seed. For s5378, the attack recovers 16 seed candidates, whereas for s13207, it recovers 128 seed candidates, both of which can be easily brute forced to obtain the correct seed.  s5378  160  128  16  17  41  s13207  202  128  128  4  27  s15850  442  128  2  4  89  s38584  1,233  128  1  3  219  s38417  1,564  128  1  7  342  s35932  1,728  128  1  1  254  b20  429  128  1  1  63  b21  429  128  1  1  54  b22  611  128  1  1  99  b17  864  128  1  1  86 from the SAT tool, and recover more seed bits. We repeat the restart step until all the seed bits have been recovered, or the remaining seed bits can be brute-forced. Even if the number of remaining seed bits is large for brute force, we can obtain a combinational locked circuit for a new capture cycle and carry over the seed information recovered from previous capture cycles to either recover the entire seed or reduce the brute force effort. We, however, have not come across any benchmark, locked with a key of a practical size, where a second capture was required, as can be seen in Section IV.

IV. EXPERIMENTAL RESULTS
Setup. We conducted our DynUnlock attack on six ISCAS-89 [17] and four ITC-99 [18] benchmarks with dynamically locked scan chains with a 128-bit key. Synopsys Design Compiler was used to synthesize these benchmarks. All the experiments have been carried out on a 24-core Intel Xeon processor running at 3.33 GHz with 96 GB RAM.
Attack results. Our attack results are given in Table II which shows the number of seed candidates recovered, number of iterations required by the lingeling SAT solver, and the attack execution time. As we can see, DynUnlock successfully unlocks all the circuits by recovering the 128-bit seed. For benchmarks s5378, s13207, and s15850, the attack obtains more than one seed candidate, which highlights that with just one capture cycle, SAT tool was not able to resolve all the CNF equations. However, these seed candidates are very few in number which can be easily brute forced to obtain the correct seed. For the rest of the benchmarks, we directly obtain the correct seed. All these benchmarks are run for 10 different LFSR seeds, and the number of seed candidates, number of iterations, and the execution times are averaged over these 10 runs.
Attack scalability. In our attack, we include the LFSR structure in the combinational modeling. All the seed bits are correlated with other seed bits as shown in Fig. 4. Hence, the SAT attack sometimes resolves only these clauses and leaves with multiple values for the variables in these clauses, thereby, increasing the seed candidates. For larger circuits, we obtain only one seed candidate. Intuitively, in a larger circuit with a larger number of scan flops, attack success should be higher as the seed bits will repeat for a larger number of times. We confirm this intuition from the results in Table II. Furthermore, for larger circuits (s38584, s38417, and s35932), even if the key-size is 240 bits, we still recover one seed as shown in Table III, and upto key sizes of 368, we obtain at most 16 seed candidates, which can be easily brute forced to recover the correct seed. Thus, our attack is scalable with number of scan flops as well as with increasing key sizes.

V. DISCUSSION AND CONCLUSION
Among the scan locking solutions that follow the same threat model used in logic locking, the only defenses that our attack cannot circumvent are those that incorporate cryptographic functions [7], [8] or PUF structures [19] to generate dynamic keys. Our attack cannot model such modules into their combinational logic equivalent. While this is a limitation of our attack, we note that cryptographic functions incur significant area and power cost, limiting the use of such defenses to chips that have these blocks already.
In this paper, we present a novel attack which circumvents the most dynamic case of scan locking proposed in [13]. We model the sequential circuit into a locked combinational circuit on which the SAT attack [6] can be applied. We conducted experiments on large circuits in ISCAS-89 and ITC-99 benchmark suites and recovered the LFSR seed within seven minutes for all the benchmarks under consideration. We also evaluated the scalability of our attack with increasing key sizes and recovered the seed using at most 27 iterations and within 23 hours for all the 15 cases for key sizes as large as 368 bits. Our attack can break any version of dynamic scan locking. With our attack process, we will never run out of iterations, as the attack will always provide seed candidates, if not the correct unique seed. III: Results for s38584, s38417, and s35932 benchmarks locked using larger keys. We observe that even for a key size as large as