SANSCrypt: A Sporadic-Authentication-Based Sequential Logic Encryption Scheme
^††thanks: Identify applicable funding agency here. If none, delete this.

SANSCrypt assumes a threat model that is consistent with the previous literature on sequential logic encryption [6, 20, 22]. The goal of the attack is to access the correct circuit functionality, by either reconstructing the deobfuscated circuit or finding the correct key sequence. To achieve this goal, the attacker can leverage one or more of the following resources: (i) the encrypted netlist; (ii) a working circuit providing correct input-output pairs; (iii) knowledge of the encryption technique. In addition, we assume that the attacker has no access to the scan chain and cannot directly observe or change the state of the circuit.

As shown in Fig. 1a, existing logic encryption techniques are mostly based on a single-authentication protocol, requiring users to be authenticated only once before using the correct circuit function. After authentication, the circuit remains functional unless it is powered off or reset. To attack the circuit, it is then sufficient to discover the correct key sequence that must be applied in the initial state.

We adopt, instead, the authentication protocol in Fig. 1b, where the functional circuit can “jump” back to the encrypted mode from the functional mode. Once the back-jumping occurs, another round of authentication is required to resume the normal operation. The back-jumping can be triggered multiple times and involve a different key sequence for each re-authentication step. The hardness of attacking this protocol stems from both the increased number of the key sequences to be produced and the uncertainty on the time at which each sequence should be applied. A new temporal dimension adds to the decryption procedure, which poses a significantly higher threshold to the attackers.

SANSCrypt is a sequential logic encryption scheme which supports random back-jumping, as represented in Fig. 2. When the circuit is powered or reset, the circuit falls into the reset state $E0$ of the encrypted mode. To transition to the initial (or reset) state $N0$ of the functional mode, the user must apply at startup the correct key sequence to the primary input ports.

Once in the functional mode, the circuit can deliberately, but randomly, jump back, as denoted by the blue edges in Fig. 2, to a state $s_{bj}$ in the encrypted mode, called back-jumping state, after a designated number of clock cycles $t_{bj}$, called back-jumping period. The user needs to apply another key sequence to resume normal operations, as shown by the red arrows. Both the back-jumping state $s_{bj}$ and the back-jumping period $t_{bj}$ are determined by a pseudo-random number generator (PRNG) embedded in the circuit. Therefore, when and where the back-jumping operation happens is unpredictable unless the attacker is able to break the PRNG or find its seed. The schematic of SANSCrypt is shown in Fig. 3 and consists of two additional blocks, a back-jumping module and an encryption finite state machine (ENC-FSM), besides the original circuit. We discuss each of these blocks in the following subsections.

The back-jumping module consists of an $n$-bit PRNG, an $n$-bit Counter, and a Back-Jumping Finite State Machine (BJ-FSM) which sends back-jumping commands to the rest of the circuit. As summarized in the flowchart in Fig. 4, when the circuit is in the encrypted mode, BJ-FSM checks whether the authentication has occurred. If this is the case, BJ-FSM stores the current PRNG output as the back-jumping period $t_{bj}$ and initializes the counter.

The counter increments its output at each clock cycle until it reaches $t_{bj}$. This event triggers BJ-FSM to sample again the current PRNG output $r$, which is generally different from $t_{bj}$, and use it to determine the back-jumping state $s_{bj}=f(r)$. For example, if $s_{bj}$ is an $l$-bit binary number, BJ-FSM can arbitrarily select $l$ bits from $r$ and assign the value to $s_{bj}$. If the first $l$ bits of $r$ are selected, we have $f(r)=r[0:l-1]$. At the same time, BJ-FSM sends a back-jumping request to the other blocks of the circuit and returns to its initial state, where it keeps checking the authentication status of the circuit. On receiving the back-jumping request, the circuit jumps back to state $s_{bj}$ in the encrypted mode and will stay there unless re-authentication is performed. Any PRNG architecture can be selected in this scheme, based on the design budget and the desired security level. For example, linear PRNGs, such as Linear Feedback Shift Registers (LFSRs), provide higher speed and lower area overhead but tend to be more vulnerable than cipher algorithm-based PRNGs, such as AES, which are, however, more expensive.

The Encryption Finite State Machine (ENC-FSM) determines whether the user’s key sequence is correct and, if it is not correct, takes actions to hide the functionality of the original circuit. The input of the ENC-FSM can be provided via the primary input ports, without the need to create extra input ports for authentication. The output $enc\_out$ of ENC-FSM, which is $n$ bit long, together with a set of nodes in the original circuit netlist, can be provided as an input to a set of XOR gates, to corrupt the circuit function as in combinational logic encryption [3]. For example, in Fig. 5, a 3-bit array $enc\_out$ is connected to six nodes in the original circuit via XOR gates. In this paper, XOR gates are inserted at randomly selected nodes. However, any other combinational logic encryption technique is also applicable. As a design parameter, we denote by node coverage the ratio between the number of inserted XOR gates and the total number of combinational logic gates in the circuit.

Only one state of ENC-FSM, termed $auth$, is used in the functional mode. In state $auth$, all bits in $enc\_out$ are set to zero and the original circuit functionality is activated. In the other states, the value of $enc\_out$ changes based on the state, but at least one of its bits is set to one to guarantee that the final output is incorrect. A sample truth table for a 3-bit $enc\_out$ array is shown in Table I. Even if the circuit is in the encrypted mode, $enc\_out$ changes its value based on the state of the encryption FSM. Such an approach makes it difficult for signal analysis attacks, aiming to locate signals with low switching activity in the encrypted mode, to find $enc\_out$ and bypass ENC-FSM. After a valid authentication, the circuit resumes its normal operation. Additional registers are, therefore, required in the ENC-FSM to store the circuit state before back-jumping so that it can be resumed after authentication.

Let us suppose that the number of primary input bits used as key inputs is $i$ and each re-authentication procedure requires $c$ clock cycles to apply the key sequence. If the attacker has no preference in selecting the key sequence, then she would have, on average, $(2^{i\cdot c}+1)/2\approx 2^{i\cdot c-1}$ attempts for each re-authentication procedure, which amounts to the same brute-force attack complexity of HARPOON. However, because the correct key sequence of each re-authentication procedure depends on the PRNG output, the number $N_{prng}$ of possible values of the PRNG output will also contribute to the attack effort. If each PRNG output corresponds to a unique key sequence which is independent from other key sequences, the average attack effort will be $N_{prng}\cdot 2^{i\cdot c-1}$. For a 10-bit PRNG, $i=32$, and $c=8$, the average attack effort will reach $5.93\times 10^{79}$.

A SAT-based attack can be carried out on sequential encryption by unrolling the sequential portions of the circuit [20]. This attack can be remarkably successful especially when the correct key is the same at each time (clock cycle) and the key input ports are different from the primary input ports. Similarly to HARPOON, SANSCrypt is resilient to this SAT-based attack variant, since the correct keys are generally not the same at different clock cycles.

We therefore analyze the resilience of SANSCrypt via a modified version of the sequential SAT-based attack [22] that is appropriate for schemes such as HARPOON and SANSCrypt, as shown in Fig. 6. Let us first assume that the encryption scheme requires $n$ clock cycles after reset to enter the functional mode. Then, the attacker can start the attack by unrolling the circuit $(n+1)$ times. The first $n$ copies of the circuit receive the keys at their primary input ports ($K_{a}$ and $K_{b}$), while the primary input and output ports of the $(n+1)^{th}$ circuit replica can be used to read the circuit input and output signals after $n$ cycles. If the SAT-based attack fails to find the correct key with $(n+1)$ circuit replicas, as in Fig. 6, the circuit will be unrolled one more time (see, e.g., [20]).

The attack above would be still ineffective on SANSCrypt, since it can retrieve the first key sequence but would fail to discover when the next back-jumping occurs and what would be the next key sequence. Even if the attacker knows when the next back-jumping occurs, the above SAT-based attack will fail due to the large number of circuit replicas needed to find all the key sequences, as empirically observed in Section V.

As discussed in Section II, a possible shortcoming of certain sequential encryption schemes is the clear boundary between the encrypted mode and the functional mode FSMs. As shown in Fig. 3, SANSCrypt addresses this issue by designing more than one transition between the two FSMs.

An attacker may also try to locate and isolate the output of ENC-FSM by looking for low signal switching activities when the circuit is in the encrypted mode. SANSCrypt addresses this risk by expanding the output of ENC-FSM from one bit to an array. The value of each bit changes frequently based on the state of the encrypted mode FSM, which makes it difficult for attackers to find the output of ENC-FSM based on signal switching activities.

Due to multiple back-jumping and authentication operations in SANSCrypt, additional clock cycles will be required in which no other operation can be executed. Suppose that authentication requires $t_{a}$ clock cycles and the circuit stays in the functional mode for $t_{b}$ clock cycles before the next back-jumping occurs, as shown in Fig. 7.

The cycle delay overhead can be computed as the ratio $O_{cd}={t_{a}}/{t_{b}}$.

Specifically, for an $n$-bit PRNG, the average $t_{b}$ is equal to the average output value, i.e., $2^{n-1}$. To illustrate how the cycle delay overhead is influenced by this encryption, Fig. 8 shows the relation between average cycle delay overhead and PRNG bit length. The clock cycles ($t_{a}$) required for (re-)authentication are set as 8, 16, 64, and 128.

When the PRNG bit length is small, the average cycle delay increases significantly with the increase of $t_{a}$. However, the cycle delay can be reduced by increasing the PRNG bit length. For example, the average cycle delay overhead becomes negligible for all the four cases when the PRNG bit length is 11 or larger. A key manager, available to the trusted user, will be in charge of automatically applying the key sequences from a tamper-proof memory at the right time, as computed from a hard-coded replica of the PRNG.