# Stealthy Hardware Trojan Based Algebraic Fault Analysis of HIGHT Block Cipher

Authors: Hao Chen; Tao Wang; Fan Zhang; Xinjie Zhao; Wei He; Lumin Xu; Yunfei Ma
Journal: Security and Communication Networks
 (2017)

---

## Abstract

HIGHT is a lightweight block cipher which has been adopted as a standard block cipher. In this paper, we present a bit-level algebraic fault analysis (AFA) of HIGHT, where the faults are perturbed by a stealthy HT. The fault model in our attack assumes that the adversary is able to insert a HT that flips a specific bit of a certain intermediate word of the cipher once the HT is activated. The HT is realized by merely 4 registers and with an extremely low activation rate of about 0.000025. We show that the optimal location for inserting the designed HT can be efficiently determined by AFA in advance. Finally, a method is proposed to represent the cipher and the injected faults with a merged set of algebraic equations and the master key can be recovered by solving the merged equation system with an SAT solver. Our attack, which fully recovers the secret master key of the cipher in 12572.26 seconds, requires three times of activation on the designed HT. To the best of our knowledge, this is the first Trojan attack on HIGHT.


---

## Body

## 1. Introduction

The resource-constrained devices such as RFID tags and smart cards have been pervasively used in the daily activities of human society, such as intelligent transportation, modern logistics, and food safety [1, 2]. As these devices have inherent constrains in storage space, computation ability, and power supply, modern cryptographic primitives like DES, AES, or RSA are difficult to be deployed on them. Hence, the research of lightweight cryptography, which aims at designing and implementing security primitives fitting the needs of low-resource devices, has been focused on a large scale ‎[3]. Particularly, the lightweight block cipher is one of the most studied metrics, which has been extensively explored in numerous prior papers. There have existed a lot of lightweight block ciphers, such as PRESENT ‎[4], LED ‎[5], SIMON ‎[6], mCrypton ‎[7], and HIGHT ‎[8, 9].Hardware Trojan is a circuit maliciously inserted into integrated circuit (IC) that typically functions to deactivate the host circuit, change its functionality, or provide covert channels through which sensitive information can be leaked ‎[10, 11]. They can be implemented as hardware modifications to ASICs, commercial-off-the-shelf (COTS) parts, microprocessors, microcontrollers, network processors, or digital-signal processors (DSPs) and can also be implemented as firmware modifications to, for example, FPGA bitstreams [12]. An adversary is expected to make a Trojan stealthy in nature, that is, to evade detection by methods such as postmanufacturing test, optical inspection, or side-channel analysis [13–15]. Due to outsourcing trend of the semiconductor design and fabrication, hardware Trojan attacks have emerged as a major security concern for integrated circuits (ICs) [13].Differential Fault Analysis (DFA) [16] was one of the earliest techniques invented to attack block ciphers by provoking a computational error. DFA retrieves the secret key based on information of the characteristics of the injected faults and the difference of the ciphertexts and faulty ciphertexts. However, since DFA relies on manual analysis, it often has inherit inherent limitations in scenarios that have very high complexity, for example, when faults are located in deeper rounds of the cipher or when the exact location of the injected faults in a deep round is unknown.In eSmart 2010, Courtois and Pieprzyk combine algebraic cryptanalysis [17] with fault analysis to propose a more powerful fault analysis technique called algebraic fault analysis (AFA) [18]. The basic idea of AFA is to convert both the cipher and the injected faults into algebraic equations and recover the secret key with automated solvers such as SAT instead of the manual analysis on fault propagations in DFA, hence making it easier to extend AFA to deep rounds and different ciphers and fault models. AFA has been successfully used to improve DFA on the stream ciphers such as Trivium [19] and Grain [20] and block ciphers such as AES [21], LED [22, 23], KASUMI [24], and Piccolo [25].


### 1.1. Motivation

HIGHT is a lightweight block cipher that has attracted a lot of attention because it is constructed by only ARX operations (modular addition, bitwise rotation, bitwise shift, and XOR), which exhibits high performance in terms of hardware compared to other block ciphers. HIGHT has been selected as a standardized block cipher by Telecommunications Technology Association (TTA) of Korea and ISO/IEC 18033-3 [9].It is noted that both the DFA and AFA require high precision in the fault injection in terms of location and timing. In practice, low-cost fault injection techniques like reduction of the feeding voltage or clock manipulation do not achieve the required accuracy, while highly precise methods such as pinpointed irradiation of desired fault sites by intensive laser light are difficult to perform and require costly equipment [26]. However, if the adversary is able to insert hardware Trojan (HT) to the underlying cryptographic hardware [10], AFA can be easily achieved. A well designed HT can precisely inject any type of faults to enable AFA and evade detections, by having low cost and with low activation rate.In addition, since the design of lightweight block ciphers is compact, especially for HIGHT whose construction only based on ARX operations, it is simple to represent the cipher as a set of algebraic equations. It is also easier to implant hardware Trojans into devices that adopt such lightweight algorithms because these devices are normally used in RFID system and composed of sorts of IPs, and they are typically designed and manufactured by offshore design houses or foundries. In theory, any parties involving into the design or manufacturing stages can make alterations in the circuits for malicious purpose [15], and thus these circuits are more vulnerable to algebraic fault attacks which inject faults by triggering HT.


### 1.2. Contribution

In this paper, we show that the lightweight block cipher HIGHT is prone to algebraic fault analysis, which can be feasible with a stealthy HT. The proposed analysis of HIGHT is implemented on SASEBO-GII board soldering a 65 nm Virtex-5 FPGA [27] and recovers the 128-bit secret master key with only 3 faults. The main contributions of the paper are summarized as follows:(1) We design a stealthy FSM-based HT by using 4 flip-flops overhead which is a 1.63% additional cost in flip-flops for HIGHT implemented on SASEBO-GII board and with an extremely low activation rate of about 0.000025. The HT enables the adversary to induce a single-bit fault precisely in both location and time when it is activated and thus make the bit-level AFA efficiently.(2) Some properties of faults are given to maximize the utilization of the fault leakages and show that the adversary can predetermine the optimal location for the HT by AFA to maximize the attack efficiency.(3) A very simple and efficient method is proposed to describe HIGHT and the injected faults as a merged set of algebraic equations and transform the problem of searching for the secret master key into solving the merged equation system with an SAT solver.(4) It is proven that the lower bound for the number of the required faults is 3 and an efficient distinguisher is proposed to uniquely determine the secret master key.


### 1.3. Organization

The rest of this paper is organized as follows. Section2 introduces the related works. Section 3 lists the notations used in the paper and briefly describes the HIGHT algorithm and the overview of the attack. Section 4 presents some important properties of the faults and the details of the HT are given in Section 5. Then, Section 6 describes our attack on HIGHT and the experimental results are shown in Section 7. Finally, Section 8 concludes the paper.


## 1.1. Motivation

HIGHT is a lightweight block cipher that has attracted a lot of attention because it is constructed by only ARX operations (modular addition, bitwise rotation, bitwise shift, and XOR), which exhibits high performance in terms of hardware compared to other block ciphers. HIGHT has been selected as a standardized block cipher by Telecommunications Technology Association (TTA) of Korea and ISO/IEC 18033-3 [9].It is noted that both the DFA and AFA require high precision in the fault injection in terms of location and timing. In practice, low-cost fault injection techniques like reduction of the feeding voltage or clock manipulation do not achieve the required accuracy, while highly precise methods such as pinpointed irradiation of desired fault sites by intensive laser light are difficult to perform and require costly equipment [26]. However, if the adversary is able to insert hardware Trojan (HT) to the underlying cryptographic hardware [10], AFA can be easily achieved. A well designed HT can precisely inject any type of faults to enable AFA and evade detections, by having low cost and with low activation rate.In addition, since the design of lightweight block ciphers is compact, especially for HIGHT whose construction only based on ARX operations, it is simple to represent the cipher as a set of algebraic equations. It is also easier to implant hardware Trojans into devices that adopt such lightweight algorithms because these devices are normally used in RFID system and composed of sorts of IPs, and they are typically designed and manufactured by offshore design houses or foundries. In theory, any parties involving into the design or manufacturing stages can make alterations in the circuits for malicious purpose [15], and thus these circuits are more vulnerable to algebraic fault attacks which inject faults by triggering HT.


## 1.2. Contribution

In this paper, we show that the lightweight block cipher HIGHT is prone to algebraic fault analysis, which can be feasible with a stealthy HT. The proposed analysis of HIGHT is implemented on SASEBO-GII board soldering a 65 nm Virtex-5 FPGA [27] and recovers the 128-bit secret master key with only 3 faults. The main contributions of the paper are summarized as follows:(1) We design a stealthy FSM-based HT by using 4 flip-flops overhead which is a 1.63% additional cost in flip-flops for HIGHT implemented on SASEBO-GII board and with an extremely low activation rate of about 0.000025. The HT enables the adversary to induce a single-bit fault precisely in both location and time when it is activated and thus make the bit-level AFA efficiently.(2) Some properties of faults are given to maximize the utilization of the fault leakages and show that the adversary can predetermine the optimal location for the HT by AFA to maximize the attack efficiency.(3) A very simple and efficient method is proposed to describe HIGHT and the injected faults as a merged set of algebraic equations and transform the problem of searching for the secret master key into solving the merged equation system with an SAT solver.(4) It is proven that the lower bound for the number of the required faults is 3 and an efficient distinguisher is proposed to uniquely determine the secret master key.


## 1.3. Organization

The rest of this paper is organized as follows. Section2 introduces the related works. Section 3 lists the notations used in the paper and briefly describes the HIGHT algorithm and the overview of the attack. Section 4 presents some important properties of the faults and the details of the HT are given in Section 5. Then, Section 6 describes our attack on HIGHT and the experimental results are shown in Section 7. Finally, Section 8 concludes the paper.


## 2. Related Work

Since the proposal of HIGHT, there have been many studies on the security of HIGHT. The preliminary security analysis [8], conducted during the HIGHT design process, includes the assessment of the cipher with respect to different cryptanalytic attacks such as differential cryptanalysis, related-key attack, saturation attack, and algebraic attack and the designers claim that at least 20 rounds of HIGHT are secure against these attacks. But in 2007, Lu [28] presents the first public cryptanalysis of reduced versions of HIGHT which indicates the reduced versions of HIGHT are less secure than the designers claimed. Then in 2009, Lu’s attack results were improved by Özen et al. [29] by presenting an impossible differential attack on 26-round HIGHT and a related-key impossible differential attack on 31 round HIGHT. At CANS 2009, Zhang et al. [30] present a 22-round saturation attack on HIGHT including full whitening keys with 262.04 chosen plaintext and 2118.71 22-round encryptions. The first attack on full HIGHT was proposed by Koo et al. at ICISC 2010 [31] using related-key rectangle attack based on a 24-round related-key distinguisher with the data complexity of 257.84 chosen plaintext and the time complexity of 2123.17 encryptions. The second attack on full HIGHT was proposed by Hong et al. at ICISC 2011 [32] with a Biclique cryptanalysis of the full HIGHT which recovers the 128-bit secret master key with the computational complexity of 2126.4, faster than exhaustive search. In [33], Lee et al. present the first DFA against HIGHT. In this attack, authors claimed that the full secret master key of HIGHT can be recovered in a few minutes or seconds with a success rate of 96%, computational complexity of O(232), and memory complexity of O(212) by injecting 12 faults based on a random byte fault model.The main idea of this attack is to collect pairs of correct and faulty ciphertexts by injecting adequate faults and use them to distinguish where the faults are injected. Once the fault locations are determined, a number of equations can be built based on manual analysis of the fault propagations to filter out the wrong subkey candidates and thus to recover the secret master key. However, since the adversary analyzes fault propagations and filters out wrong subkey candidates manually, the fault leakages are not maximally utilized and the attack can be further improved.In this paper, we elaborate an algebraic fault analysis of HIGHT with a stealthy HT. The fault model we choose in this attack is the one in which the adversary is assumed to inject a single-bit fault precisely in both location and the time of the disturbance by a HT which is activated just by choosing certain plaintexts. The attack converts both the cipher and the injected faults into algebraic equations automatically and recovers the secret master key with an SAT solver. The attack recovers the secret master key with a success rate of 96% within 12,572.26 seconds and requires only 3 faults. We summarize our results as well as the major previous results in Table1.Table 1
Summary of the attacks on HIGHT.
Attack
#rounds
Complexities
References
Data
Time
Imp. Diff.
18
246.8 CP
2109.2 EN
[8]
Saturation
22
262.04 CP
2118.71 EN
[30]
Imp. Diff.
25
260 CP
2126.78 EN
[29]
Imp. Diff.
26
261 CP
2119.53 EN
[22]
Rel.-Key Rec.
26
251.2 CP
2120.41 EN
[28]
Rel.-Key Imp.
28
260 CP
2125.54 EN
[28]
Rel.-Key Imp.
31
263 CP
2127.28 EN
[29]
Rel.-Key Rec. for Weak.
32 (full)
2
57.84
CP
2
123.17
EN
[31]
Biclique
32 (full)
2
48
CP
2
126.4
EN
[32]
DFA
32 (full)
12 faults
O(2
32
) Com. + O(2
32
) Mem. +22 seconds
[33]
AFA with HT
32 (full)
3 faults
12572.26 seconds (≈3.49 Hours)
This paper
Imp.: impossible, Diff.: differential, Rel.: related, Rec.: rectangle, Weak.: weak key, CP: chosen plaintext, EN: encryptions, Com.: computational, and Mem.: memory.


## 3. Preliminaries

In this section, the notations used in the paper are listed in Section3.1. Then, we briefly describe the HIGHT algorithm in Section 3.2 and the overview of the attack is given in Section 3.3.


### 3.1. Notations

In the rest of the paper, the following notations are used:1.
⊞: x⊞y means x+ymod28, where 0≤x,y<28.2.
⊕,∥: bitwise XOR and concatenation operations.3.
A⋘s: s-bit left rotation of an 8-bit value A.4.
′: sign for denoting faulty ciphertext or intermediate values.5.
P,C,C′: the 64-bit plaintext, ciphertext, and faulty ciphertext.6.
MK=MK15∥⋯MK1∥MK0: the 16 bytes master key.7.
WKi: the whitening keys, 0≤i≤7.8.
SKk: the round keys, 0≤k≤127.9.
Xr=Xr,7∥⋯Xr,1∥Xr,0: the 64-bit input of the (r+1)th round, 0≤r≤32.10.
Xr,ik: the kth bit of Xr,ik, 0≤k≤7.


### 3.2. Brief Description of HIGHT Cipher

HIGHT is a lightweight block cipher with 64-bit block length and 128-bit key length. The encryption process of HIGHT is as follows.(1) TheKeySchedule is performed to generate 8 bytes whitening keys WKi(0≤i≤7) and 128 bytes SKi(0≤i≤127):(1)WKi=MKi+12i=0,1,2,3;(2)WKi=MKi-4i=4,5,6,7;(3)SK16i+j=MKj-imod8⊞δ16i+j0≤i,j≤7,(4)SK16i+j+8=MKj-imod8+8⊞δ16i+j+80≤i,j≤7.(2) TheInitialTransformation is performed to transform the 64-bit plaintextP to the input of the first round X0 by using four bytes whitening keys WK0, WK1, WK2, and WK3. (5)X0,0=P0⊞WK0;X0,1=P1;X0,2=P2⊕WK1;X0,3=P3;X0,4=P4⊞WK2;X0,5=P5;X0,6=P6⊕WK3;X0,7=P7.(3) For i=1,2,…,31,RoundFunction is performed to transform Xi into Xi+1 as follows: (6)Xi,0=Xi-1,7⊕F0Xi,6⊞SK4i-1;Xi,2=Xi-1,1⊞F0Xi,0⊕SK4i-4;Xi,4=Xi-1,3⊕F0Xi,2⊞SK4i-3;Xi,6=Xi-1,5⊞F0Xi,4⊕SK4i-2;Xi,1=Xi-1,0;Xi,3=Xi-1,2;Xi,5=Xi-1,4;Xi,7=Xi-1,6.For i=32, (7)Xi,1=Xi-1,1⊞F1Xi-1,0⊕SK4i-4;Xi,3=Xi-1,3⊕F0Xi-1,2⊞SK4i-3;Xi,5=Xi-1,5⊞F1Xi-1,4⊞SK4i-2;Xi,7=Xi-1,7⊕F0Xi-1,6⊞SK4i-1;Xi,0=Xi-1,0;Xi,2=Xi-1,2;Xi,4=Xi-1,4;Xi,6=Xi-1,6.The two auxiliary functions F0 and F1 are defined as follows:(8)F0x=x⋘1⊕x⋘2⊕x⋘7,F1x=x⋘3⊕x⋘4⊕x⋘6.(4) TheFinalTransformation transforms X32 into the ciphertext C:(9)C0=X32,1⊞WK4;C1=X32,2;C2=X32,3⊕WK5;C5=X32,6;C4=X32,5⊞WK6;C3=X32,4;C6=X32,7⊕WK7;C7=X32,0.For complete description of HIGHT, the reader is referred to [8, 9].


### 3.3. Overview of the Attack

As illustrated in Figure1, our attack consists of four steps.Figure 1
Overview of the attack on HIGHT.(
1) Inducing the Designed HT in a Selected Location. The task of this step is to design a HT and insert it in the cipher chip. The optimal location of inserting a HT should be in a deeper round to enable the fault to involve the whole master key bytes during its propagation. It also should ensure that the injected HT escapes detections by having low cost and with extremely low activation rate.(
2) Constructing Boolean Equations for the Cipher. In this step, the target cipher and its key schedule are described by a set of Boolean equations C, which contain unknowns (master key bits, whitening key bits, subkey bits, and intermediate variables) and constants (plaintext and ciphertext bits). The most important and difficult part in this step for HIGHT is to describe nonlinear operations like addition mod 2n and complicated linear functions like F0(·) and F1(·).(
3) Constructing Boolean Equations for the Faults. After the fault injections, the faults are also represented with a set of Boolean equations D. It is obvious that the more secret variables D contains, the more master key bits that can be recovered. Therefore, the key point of this step is how to make D contain secret variables that were involved during the fault propagation as many as possible in an efficient and simple way.(
4) Solving the Algebraic Equation System. The problem of searching for the secret master key is now transformed into solving the merged equation system C and D. Many automatic tools [25, 34–37] can be leveraged.


## 3.1. Notations

In the rest of the paper, the following notations are used:1.
⊞: x⊞y means x+ymod28, where 0≤x,y<28.2.
⊕,∥: bitwise XOR and concatenation operations.3.
A⋘s: s-bit left rotation of an 8-bit value A.4.
′: sign for denoting faulty ciphertext or intermediate values.5.
P,C,C′: the 64-bit plaintext, ciphertext, and faulty ciphertext.6.
MK=MK15∥⋯MK1∥MK0: the 16 bytes master key.7.
WKi: the whitening keys, 0≤i≤7.8.
SKk: the round keys, 0≤k≤127.9.
Xr=Xr,7∥⋯Xr,1∥Xr,0: the 64-bit input of the (r+1)th round, 0≤r≤32.10.
Xr,ik: the kth bit of Xr,ik, 0≤k≤7.


## 3.2. Brief Description of HIGHT Cipher

HIGHT is a lightweight block cipher with 64-bit block length and 128-bit key length. The encryption process of HIGHT is as follows.(1) TheKeySchedule is performed to generate 8 bytes whitening keys WKi(0≤i≤7) and 128 bytes SKi(0≤i≤127):(1)WKi=MKi+12i=0,1,2,3;(2)WKi=MKi-4i=4,5,6,7;(3)SK16i+j=MKj-imod8⊞δ16i+j0≤i,j≤7,(4)SK16i+j+8=MKj-imod8+8⊞δ16i+j+80≤i,j≤7.(2) TheInitialTransformation is performed to transform the 64-bit plaintextP to the input of the first round X0 by using four bytes whitening keys WK0, WK1, WK2, and WK3. (5)X0,0=P0⊞WK0;X0,1=P1;X0,2=P2⊕WK1;X0,3=P3;X0,4=P4⊞WK2;X0,5=P5;X0,6=P6⊕WK3;X0,7=P7.(3) For i=1,2,…,31,RoundFunction is performed to transform Xi into Xi+1 as follows: (6)Xi,0=Xi-1,7⊕F0Xi,6⊞SK4i-1;Xi,2=Xi-1,1⊞F0Xi,0⊕SK4i-4;Xi,4=Xi-1,3⊕F0Xi,2⊞SK4i-3;Xi,6=Xi-1,5⊞F0Xi,4⊕SK4i-2;Xi,1=Xi-1,0;Xi,3=Xi-1,2;Xi,5=Xi-1,4;Xi,7=Xi-1,6.For i=32, (7)Xi,1=Xi-1,1⊞F1Xi-1,0⊕SK4i-4;Xi,3=Xi-1,3⊕F0Xi-1,2⊞SK4i-3;Xi,5=Xi-1,5⊞F1Xi-1,4⊞SK4i-2;Xi,7=Xi-1,7⊕F0Xi-1,6⊞SK4i-1;Xi,0=Xi-1,0;Xi,2=Xi-1,2;Xi,4=Xi-1,4;Xi,6=Xi-1,6.The two auxiliary functions F0 and F1 are defined as follows:(8)F0x=x⋘1⊕x⋘2⊕x⋘7,F1x=x⋘3⊕x⋘4⊕x⋘6.(4) TheFinalTransformation transforms X32 into the ciphertext C:(9)C0=X32,1⊞WK4;C1=X32,2;C2=X32,3⊕WK5;C5=X32,6;C4=X32,5⊞WK6;C3=X32,4;C6=X32,7⊕WK7;C7=X32,0.For complete description of HIGHT, the reader is referred to [8, 9].


## 3.3. Overview of the Attack

As illustrated in Figure1, our attack consists of four steps.Figure 1
Overview of the attack on HIGHT.(
1) Inducing the Designed HT in a Selected Location. The task of this step is to design a HT and insert it in the cipher chip. The optimal location of inserting a HT should be in a deeper round to enable the fault to involve the whole master key bytes during its propagation. It also should ensure that the injected HT escapes detections by having low cost and with extremely low activation rate.(
2) Constructing Boolean Equations for the Cipher. In this step, the target cipher and its key schedule are described by a set of Boolean equations C, which contain unknowns (master key bits, whitening key bits, subkey bits, and intermediate variables) and constants (plaintext and ciphertext bits). The most important and difficult part in this step for HIGHT is to describe nonlinear operations like addition mod 2n and complicated linear functions like F0(·) and F1(·).(
3) Constructing Boolean Equations for the Faults. After the fault injections, the faults are also represented with a set of Boolean equations D. It is obvious that the more secret variables D contains, the more master key bits that can be recovered. Therefore, the key point of this step is how to make D contain secret variables that were involved during the fault propagation as many as possible in an efficient and simple way.(
4) Solving the Algebraic Equation System. The problem of searching for the secret master key is now transformed into solving the merged equation system C and D. Many automatic tools [25, 34–37] can be leveraged.


## 4. Some Properties of the Faults

This section is devoted to presenting the fault properties, which are helpful to our attack. For the sake of simplicity, we denote the deduction ofB from A by equation ∗ by(10)A→∗B.Property 1.
Assume that a fault was induced toXr,i, then define(11)Ωr,i=WKω,SKξ∣Xr,i⟶WKω,SKξas the set of subkey bytes and whitening key bytes that were involved by the fault during its propagation form round r toFinalTransformation, where 1≤r≤32, 0≤ω≤15, 0≤ξ≤127, 0≤i≤7, and 0≤m≤3. Then we have(12)Ωr,i=Ωr+1,i+1+Ωr+1,i+2mod8+SK4r+m,r<31,i=2mΩr+1,i+1mod8+SK4r+m,r<31,i=2m+1Ωr+1,i+Ωr+1,i+SK4r+m,r=31,i=2mΩr+1,i+SK4r+m,r=31,i=2m+1.Proof.
Without loss of generality, we assume that the fault was induced toXr,i.
(1) Fori=2m, 1≤r<31, and 0≤m≤3, the fault will propagate to Xr+1,2(m+1)mod8 and Xr+1,2m+1 in the next round as shown in Figure 2; thus we have Ωr,i=Ωr+1,i+1+Ωr+1,i+2mod8+SK4r+m.
When the fault was injected inr=31, the fault will propagate to Xr+1,2mmod8 and Xr+1,2m+1mod8 in the final round. Then, we have Ωr+1,i+Ωr+1,i+SK4r+m.
(2) Fori=2m+1, 1≤r<31, and 0≤m≤3, the fault will only propagate to Xr+1,2(m+1)mod8 in the next round as shown in Figure 3; thus we have Ωr,i=Ωr+1,i+1mod8+SK4r+m.
In the similar way, the fault will propagate toXr+1,2mmod8 and Xr+1,2m+1mod8 in the next round for r=31. Then, we have Ωr,i=Ωr+1,i+SK4r+m.Figure 2
The fault was injected inXr,2m for 1≤r<31.Figure 3
The fault was injected inXr,2m+1 for 1≤r<31.Property 2.
Assume that a fault was induced toXr,i, then define (13)Σr,i=MKτ∣Xr,i⟶MKτ,1≤r≤32,0≤τ≤15,0≤i≤7as the set of the master key bytes that were involved during the propagation of the fault.Then we have the following conclusion.Proof.
From Section3.2, for theFinalTransformation of HIGHT, we have the following formula:(14)X32,2m→7WKm+4,0≤m≤3.
For theKeySchedule of HIGHT, we have the following formula:(15)WKn→2MKn-4,4≤n≤7.
For (14)~(15), we have(16)X32,2m→1415MKm,0≤m≤3,(17)X32,2m+1→1415⌀,0≤m≤3.Thus, we have Ω32,2m+1=⌀ and Ω32,2m=WKm. Moreover, according to Property 2, then we have the desired conclusions which are shown in Table 2.
Note that, to fully recover the master key, the entire master key bytes must be included in the merged equation system. That is, the master key bytes can possibly be recovered only for the case thatΣr,i=MK.Table 2
The location of fault for#Σr,i=16 or #(Σr,i∪Σr,j)=16.
r
#
(
Σ
r
,
i
)
=
16 or #(Σr,i∪Σr,j)=16
I
(
i
,
j
)
25
0,1
,
2,3
,
4
(
0,1
)
,
…
,
(
0,7
)
,
(
1,2
)
,
…
,
(
1,7
)
,
(
2,3
)
,
…
,
(
2,7
)
,
(
3,4
)
,
…
,
(
3,7
)
,
(
4,5
)
,
(
4,6
)
,
(
4,7
)
26
–
(
0,2
)
,
(
0,3
)
,
(
0,4
)
,
(
0,5
)
,
(
1,4
)
,
(
1,5
)
,
(
2,4
)
,
(
2,5
)
,
(
2,6
)
,
(
2,7
)
,
(
3,6
)
,
(
3,7
)
,
(
4,6
)
,
(
4,7
)
,
(
5,6
)
,
(
5,7
)
27
–
(
0,4
)
,
(
0,5
)
,
(
0,6
)
,
(
1,4
)
,
(
1,5
)
,
(
1,6
)
,
(
2,6
)
(
3,6
)
28
–
(
2,6
)
,
(
2,7
)Property 3.
Given that a single-bit fault is inserted inXt,2m, the fault propagation paths are shown in Figure 4. The intermediate words Xr,2m+1, Xr,2m+2, Xr+1,2m+2, Xr+1,2m+3, Xr+2,2m+3, and X32,n are all corrupted that ΔXr,2m+1=Δ1, ΔXr,2m+2=ΔXr+1,2m+3=Δ2, ΔXr+1,2m+2=Δ3, ΔXr+2,2m+3=Δ5, and ΔX32,n=Δ6. Then the intermediate words are included in (18)Xr+1,2m+3⊞SK4m+1+1⊕F1Xr+1,2m+2⊕Xr+1,2m+3⊕Δ2⊞SK4m+1+1⊕F1Xr+1,2m+2⊕Δ2=Δ4,WKt⊞X32,n⊕WKt⊞X32,n⊕Δ5=ΔCn.More generally, if we use 8-bit words x and y to denote the inputs of modular addition, α and β to denote the difference of the inputs, and γ to denote the corresponding output difference in (18), then the above two equations can be simplified as (19)x⊞y⊕x⊕α⊞y⊕β=γ,(20)x⊞y⊕x⊞y⊕α=γ.That is, the intermediate words, whitening keys and subkeys can be recovered by solving the two equations.Figure 4
Fault propagation paths for the case where the fault is induced toXt,2m.


## 5. The Proposed Trojan Circuit

In this section, we give the details of the HT. In general, a hardware Trojan consists of two parts:trigger logic (TL) andpayload logic (PL). The TL is used to judge whether the values of signal lines and states meet the activation condition which is referred to the values of signal lines and states set by the adversary in advance. Once the activation condition is satisfied, the PL executes attacks. Attacks of Trojan circuit may deactivate the circuit (denial-of-service), change its functionality, or provide covert channels through which the protected secret information can be leaked.


### 5.1. Assumption of Trojan Circuits

In this paper, we make three assumptions about the design of hardware Trojan circuits.(1) HIGHT is implemented in a cryptographic intellectual property (IP) with advanced protections like sensors from an untrusted IP vendor or system integrator. The prototype is on a Xilinx FPGA device implementing a cryptographic IP. In fact, it is a common practice to deploy physical sensors alongside cryptographic IP in industrial designs.(2) The adversary is assumed to be able to assign the plaintext to be encrypted. And he is also assumed to be able to insert a smart but functional hardware Trojan in Register Transfer Level (RTL) by either modifying the RTL or the corresponding logic elements in the postplace or route netlist. But he only has the access to the Xilinx Design Language (XDL) file and no access to the design stage.(3) The hardware Trojan is designed to introduce a fault by flipping only one bit of a certain intermediate word of the cipher when it was activated.


### 5.2. Trigger Design

The FSM-based Trojans [38] have two prominent advantages over many other Trojans: one is that they can be designed to be arbitrarily complicated with the same amount of resources and can reuse both combinational logic and flip-flops of the original circuit, and the other is that the FSM-based Trojans are bidirectional which means they can have state transitions leading back to the previous or initial state, thus causing the final Trojan state to be reached only if the entire state sequence is satisfied in consecutive clock cycles. The above two advantages both make the FSM-based Trojans harder-to-detect than other Trojans.As shown in Figure6, to design a hard-to-detect Trojan circuit, the TL of the proposed HT is designed based on a finite state machine (FSM). In this FSM, a 3-bit register is used to store the current state. The Trojan circuit undergoes state transition under the certain state transition diagram which is defined by the adversary in advance and shown in Figure 5. Moreover, only the adversary knows the predefined state transition diagram. The 3-bitinput is derived from any three of the four different 8-bit intermediate words X0,1, X0,3, X0,5, and X0,7, randomly. And it is assigned as the transition condition of the FSM that causes the state transition. If theinput agrees with the current state, the FSM will transition to the next state; otherwise the FSM will go back to the previous state. When the FSM reaches the final state S16, the Trojan output is activated (the single act is “1” ) and the PL will cause a single-bit fault in the original circuit. In the next clock cycle, the Trojan will automatically go back to the initial state S0; thus the Trojan can be disguised as a random fault.Figure 5
State transition graph of the FSM.Figure 6
The structure of the Trojan.Since a 3-bit register is able to store 8 different states, the test space that is to activate the trigger logic is 8! (>215); that is, the probability of activating the HT is Pr ≈ 0.000024 which is an extremely low probability. However, since according toInitialTransformation(see (5)), the required four plaintext bytesP1,P3,P5, andP7 can be directly deduced byX0,1,X0,3,X0,5, andX0,7. Hence, the adversary can trigger the HT by carefully choosing P1,P3,P5, andP7. The total logic overhead of the implemented trigger logic is three flip-flops and four 3-input LUTs.


### 5.3. Payload Design

For clarity, themth encryption and plaintext are denoted as Em and Pm, respectively.A pair of correct and faulty ciphertexts (Cm,Cm′) is required to be collected for the same plaintextPm. The payload component PL(A) is designed to inject a single-bit fault in round r during Em. When the HT is triggered by carefully choosing some certain plaintexts, a “1” is stored in the flip-flop M which waits for the target round r+1. A signalRflag, derived from state machine, indicates whether the current round is the target round r+1 or not. The value of (r,i,k) is determined by AFA which will be described in detail in Section 7.2.1. Once the Trojan is triggered, the kth bit of Xr,i, that is, Xr,ik, is flipped due to PL(A) in Em. This is realized by function f as shown in Figure 6. The total costs of implementing the payload logic are a flip-flop and a 3-input payload gate f(a,b,c) that can be implemented by 1 LUT in both 4-input and 6-input FPGA series.


## 5.1. Assumption of Trojan Circuits

In this paper, we make three assumptions about the design of hardware Trojan circuits.(1) HIGHT is implemented in a cryptographic intellectual property (IP) with advanced protections like sensors from an untrusted IP vendor or system integrator. The prototype is on a Xilinx FPGA device implementing a cryptographic IP. In fact, it is a common practice to deploy physical sensors alongside cryptographic IP in industrial designs.(2) The adversary is assumed to be able to assign the plaintext to be encrypted. And he is also assumed to be able to insert a smart but functional hardware Trojan in Register Transfer Level (RTL) by either modifying the RTL or the corresponding logic elements in the postplace or route netlist. But he only has the access to the Xilinx Design Language (XDL) file and no access to the design stage.(3) The hardware Trojan is designed to introduce a fault by flipping only one bit of a certain intermediate word of the cipher when it was activated.


## 5.2. Trigger Design

The FSM-based Trojans [38] have two prominent advantages over many other Trojans: one is that they can be designed to be arbitrarily complicated with the same amount of resources and can reuse both combinational logic and flip-flops of the original circuit, and the other is that the FSM-based Trojans are bidirectional which means they can have state transitions leading back to the previous or initial state, thus causing the final Trojan state to be reached only if the entire state sequence is satisfied in consecutive clock cycles. The above two advantages both make the FSM-based Trojans harder-to-detect than other Trojans.As shown in Figure6, to design a hard-to-detect Trojan circuit, the TL of the proposed HT is designed based on a finite state machine (FSM). In this FSM, a 3-bit register is used to store the current state. The Trojan circuit undergoes state transition under the certain state transition diagram which is defined by the adversary in advance and shown in Figure 5. Moreover, only the adversary knows the predefined state transition diagram. The 3-bitinput is derived from any three of the four different 8-bit intermediate words X0,1, X0,3, X0,5, and X0,7, randomly. And it is assigned as the transition condition of the FSM that causes the state transition. If theinput agrees with the current state, the FSM will transition to the next state; otherwise the FSM will go back to the previous state. When the FSM reaches the final state S16, the Trojan output is activated (the single act is “1” ) and the PL will cause a single-bit fault in the original circuit. In the next clock cycle, the Trojan will automatically go back to the initial state S0; thus the Trojan can be disguised as a random fault.Figure 5
State transition graph of the FSM.Figure 6
The structure of the Trojan.Since a 3-bit register is able to store 8 different states, the test space that is to activate the trigger logic is 8! (>215); that is, the probability of activating the HT is Pr ≈ 0.000024 which is an extremely low probability. However, since according toInitialTransformation(see (5)), the required four plaintext bytesP1,P3,P5, andP7 can be directly deduced byX0,1,X0,3,X0,5, andX0,7. Hence, the adversary can trigger the HT by carefully choosing P1,P3,P5, andP7. The total logic overhead of the implemented trigger logic is three flip-flops and four 3-input LUTs.


## 5.3. Payload Design

For clarity, themth encryption and plaintext are denoted as Em and Pm, respectively.A pair of correct and faulty ciphertexts (Cm,Cm′) is required to be collected for the same plaintextPm. The payload component PL(A) is designed to inject a single-bit fault in round r during Em. When the HT is triggered by carefully choosing some certain plaintexts, a “1” is stored in the flip-flop M which waits for the target round r+1. A signalRflag, derived from state machine, indicates whether the current round is the target round r+1 or not. The value of (r,i,k) is determined by AFA which will be described in detail in Section 7.2.1. Once the Trojan is triggered, the kth bit of Xr,i, that is, Xr,ik, is flipped due to PL(A) in Em. This is realized by function f as shown in Figure 6. The total costs of implementing the payload logic are a flip-flop and a 3-input payload gate f(a,b,c) that can be implemented by 1 LUT in both 4-input and 6-input FPGA series.


## 6. The AFA with a HT of HIGHT

### 6.1. The Optimal Location Selection

LetXr,ik be the location where the HT is inserted, 0≤r≤32, 0≤i, and k≤7. In order to search the optimal location, four properties are desired:(1) Note that the secret master key can be recovered only for the case that they are involved during the fault propagation; thus the number of elements inΣr,i should be equal to 16.(2) The required number of faults to recover the secret master key and the reduced key search spaceφ(K) after the injection to Xr,ik should be both minimized to make the attack more practical.(3) The average time of the solver to solve the merged equation system should be minimized to increase the effectiveness of the attack.(4)Xr,ik should be in a deeper round to maximize utilize the fault leakages and to evade the detection.In order to search the optimal bit location for the HT, AFA is used to enumerate every possible (r,i,k). The attempts are conducted in advance, which can guide the logic designs of the HT and reduce costs. Since AFA is executed as machine-based automation, all possible key candidates will be eventually checked along the fault propagation paths. The utilization of fault leakages is maximized. The automation shows its advantage over traditional manual analysis, such as DFA, especially when the analysis goes into the deeper round.


### 6.2. Constructing Algebraic Equations for Encryption of HIGHT

The task of this stage is to represent HIGHT cipher with a large system of low degree Boolean equations. SupposeXr=Xr,7∥Xr,6⋯∥Xr,1∥Xr,0 and C=C7∥C6∥⋯∥C1∥C0 are the 64-bit input of round r+1 and ciphertext, respectively. Since the key schedule of HIGHT is very simple, we mainly focus on the encryption of HIGHT which is shown in Algorithm 1. From Algorithm 1, the most important yet difficult problem is to construct the equations for ARX operations.Algorithm 1:ConstructEquEncryption(Xr,i).
for m=rto31do
X
m
,
0
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
,
X
m
,
1
⊕
X
m
-
1,0
=
0
X
m
,
2
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
2
=
0
,
X
m
,
3
⊕
X
m
-
1,2
=
0
X
m
,
4
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
⊕
X
m
-
1,4
=
0
X
m
,
6
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊕
S
K
4
m
-
4
=
0
,
X
m
,
7
⊕
X
m
-
1,6
=
0
end for
for m=32do
X
m
,
0
⊕
X
m
-
1,0
=
0
,
X
m
,
1
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
4
=
0
X
m
,
2
⊕
X
m
-
1,2
=
0
,
X
m
,
3
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
X
m
,
4
⊕
X
m
-
1,4
=
0
,
X
m
,
5
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊞
S
K
4
m
-
2
=
0
X
m
,
6
⊕
X
m
-
1,6
=
0
,
X
m
,
7
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
end for
C
0
⊕
X
32,0
⊞
W
K
4
=
0
,
C
1
⊕
X
32,1
=
0
,
C
2
⊕
X
32,2
⊕
W
K
5
=
0
,
C
3
⊕
X
32,3
=
0
C
4
⊕
X
32,4
⊞
W
K
6
=
0
,
C
5
⊕
X
32,5
=
0
,
C
6
⊕
X
32,6
⊕
W
K
7
=
0
,
C
7
⊕
X
32,7
=
0
C
=
C
7
∥
C
6
∥
C
5
∥
C
4
∥
C
3
∥
C
2
∥
C
1
∥
C
0It is stressed that in general the adversary will not choose a very deep round as the target round. That is, the rounds between the target round andFinalTransformationare not very large. Therefore, instead of constructing equations for the full rounds of the cipher, we only construct equations for the rounds from the target round to theFinalTransformation which will result in a smaller equation script and thus will accelerate the solving procedure.According to Algorithm1, for every fault that is injected in Xr,i, there are 64×(32-r+1) variables and 8×(8×(32-r+1)+8) ANF equations were introduced to the equation system C. In addition, 32×(32-r+1) variables and ANF equations are required for round keys, 64 variables and ANF equations are for the whitening keys, and 128 variables and ANF equations are for the master keys.


#### 6.2.1. The Equations for Addition mod2n

AssumeX, Y, Z∈GF(2n) are the two inputs and output of addition modulo 2n, where X=(xn-1,xn-2,…,x0), Y=(yn-1,yn-2,…,y0), and Z=(zn-1,zn-2,…,z0) with x0, y0, and z0 being the least significant bit, respectively. Then addition modulo 2n can be described as Boolean equations as follows:(21)z0=x0⊕y0z1=x1⊕y1⊕x0y0z2=x2⊕y2⊕x1y1⊕x1⊕y1x1⊕y1⊕z1⋮zi=xi⊕yi⊕xi-1yi-1⊕xi-1⊕yi-1xi-1⊕yi-1⊕zi-1⋮zn-1=xn-1⊕yn-1⊕xn-2yn-2⊕xn-2⊕yn-2xn-2⊕yn-2⊕zn-2.


#### 6.2.2. The Equations forF0(·) and F1(·)

Given that the input and output ofF0(·) and F1(·) are X=(x7,x6,…,x0) and Y=(y7,y6,…,y0), respectively, then F0(·) and F1(·) can be described as the following Boolean equations:(22)F0·⟺y7=x6⊕x5⊕x0y6=x7⊕x5⊕x4y5=x6⊕x4⊕x3y4=x5⊕x3⊕x2y3=x4⊕x2⊕x1y2=x3⊕x1⊕x0y1=x7⊕x2⊕x0y0=x7⊕x6⊕x1,F1·⟺y7=x4⊕x3⊕x1y6=x3⊕x2⊕x0y5=x7⊕x2⊕x1y4=x6⊕x1⊕x0y3=x7⊕x5⊕x0y2=x7⊕x6⊕x4y1=x6⊕x5⊕x3y0=x5⊕x4⊕x2.


### 6.3. Constructing Equations for the Injected Faults

This stage illustrates the method of constructing equations for the injected faults. To clarify the method, the example is shown in Figure7.Figure 7
The fault propagation corresponding to the case whereX25,0 is faulted.Given that every time the HT was activated, a single-bit faultβ was introduced to flip the most significant bit of X25,3. The fault propagation paths are shown by bold line in Figure 7. The correct and faulty 64-bit inputs to the rth round are denoted by Xr=Xr,7∥⋯Xr,1∥Xr,0 and Xr′=Xr,7′∥⋯Xr,1′∥Xr,0′, respectively. Then, the complex fault propagation paths can be described as a set of algebraic equations with the variables that were involved. Since the fault flips the most significant bit of X25,0, we have(23)X25,3⊕X25,3′⊕β=0,where β=(1,0,…,0). For the fault propagation paths that from round 25 to theFinalTransformation, they can be described by equations as Algorithm 2.Algorithm 2:ConstructgEquFault(Xr,i).
Θ
=
I
-
S
e
a
r
c
h
F
a
u
l
t
I
n
t
e
r
V
a
l
X
r
,
i;
while
X
i
,
φ
∈
Θ
do
X
i
,
φ
′
⊕
X
i
,
φ
=
0
end while
for
m
=
r
to
31
do
X
m
,
0
′
⊕
X
m
-
1,7
′
⊕
F
0
X
m
-
1,6
′
⊞
S
K
4
m
-
1
=
0
,
X
m
,
1
′
⊕
X
m
-
1,0
′
=
0
X
m
,
2
′
⊕
X
m
-
1,1
′
⊞
F
1
X
m
-
1,0
′
⊕
S
K
4
m
-
4
=
0
,
X
m
,
3
′
⊕
X
m
-
1,2
′
=
0
X
m
,
4
′
⊕
X
m
-
1,3
′
⊕
F
0
X
m
-
1,2
′
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
′
⊕
X
m
-
1,4
′
=
0
X
m
,
6
′
⊕
X
m
-
1,5
′
⊞
F
1
X
m
-
1,4
′
⊕
S
K
4
m
-
2
=
0
,
X
m
,
7
′
⊕
X
m
-
1,6
′
=
0
end for
for
m
=
32
do
X
m
,
0
′
⊕
X
m
-
1,0
′
=
0
,
X
m
,
1
′
⊕
X
m
-
1,1
′
⊞
F
1
X
m
-
1,0
′
⊕
S
K
4
m
-
4
=
0
X
m
,
2
′
⊕
X
m
-
1,2
′
=
0
,
X
m
,
3
′
⊕
X
m
-
1,3
′
⊕
F
0
X
m
-
1,2
′
⊞
S
K
4
m
-
3
=
0
X
m
,
4
′
⊕
X
m
-
1,4
′
=
0
,
X
m
,
5
′
⊕
X
m
-
1,5
′
⊞
F
1
X
m
-
1,4
′
⊞
S
K
4
m
-
2
=
0
X
m
,
6
′
⊕
X
m
-
1,6
′
=
0
,
X
m
,
7
′
⊕
X
m
-
1,7
′
⊕
F
0
X
m
-
1,6
′
⊞
S
K
4
m
-
1
=
0
end for
C
0
′
⊕
X
32,0
′
⊞
W
K
4
=
0
,
C
1
′
⊕
X
32,1
′
=
0
,
C
2
′
⊕
X
32,2
′
⊕
W
K
5
=
0
,
C
3
′
⊕
X
32,3
′
=
0
C
4
′
⊕
X
32,4
′
⊞
W
K
6
=
0
,
C
5
′
⊕
X
32,5
′
=
0
,
C
6
′
⊕
X
32,6
′
⊕
W
K
7
=
0
,
C
7
′
⊕
X
32,7
′
=
0
C
′
=
C
7
′
∥
C
6
′
∥
C
5
′
∥
C
4
′
∥
C
3
′
∥
C
2
′
∥
C
1
′
∥
C
0Algorithm2 constructs the equations for the injected faults. The main idea is that every time a fault was induced, the intermediate variables from round r to round 32 were viewed as new variables Xi,φ′. Then, we reconstruct the equations for the encryption by replacing Xi,φ with Xi,φ′. Furthermore, for variables that were not involved along the fault propagation paths Θ which can be deduced by the functionSearchFaultyInterVal(Xr,i), we have Xi,φ′=Xi,φ. Thus, there are 64×(32-r+1) variables and 8×(#(Θ)+8×(32-r+1)+8) ANF equations were introduced to the equation system D for every fault that was injected in Xr,i.The function,SearchFaultyInterVal(Xr,i) searches the faulty intermediate variables automatically according to the fault locationXr,i and finally returns them. The main idea is explained earlier in Section 3. Algorithm 3 describes the procedure.Algorithm 3:SearchFaultyInterVal(Xr,i).
F
a
u
l
t
y
I
n
t
e
r
V
a
l
←
X
r
,
i
T
e
m
p
A
r
r
a
y
←
X
r
,
i
for
m
=
r
to
32
do
whileXm,φ∈TempArraymdo
ifm<32then
ifφ%2==0then
TempArraym+1←Xm,φ+1,Xm,φ+2%8
end if
ifφ%2==1then
TempArraym+1←Xm,φ+1%8
end if
end if
ifm==32then
ifφ%2==0then
TempArraym+1←Xm,φ,Xm,φ+1
end if
ifφ%2==1then
TempArraym+1←Xm,φ
end if
end if
end while
F
a
u
l
t
y
I
n
t
e
r
V
a
l
←
F
a
u
l
t
y
I
n
t
e
r
V
a
l
∪
T
e
m
p
A
r
r
a
y
m
end for
Return
F
a
u
l
t
y
I
n
t
e
r
V
a
l


### 6.4. Solving the Equations System

After activating the inserted HT to introduce single-bit faults and constructing the merged equation system for both the cipher and faults, the whole secret master key can be fully recovered by solving the merged equation system with an automatic solver. Since the SAT-based solvers [39, 40] have prominent advantage of the memory usage when solving large equations systems over many other automatic tools, such as mutantXL algorithm [35, 37] and Gröbner basis-based [41] solvers and recently further significant improvements have been made to SAT-based solvers, we have chosen the CryptoMiniSAT v4.4 which is a DPLL-based SAT solver developed from MiniSAT to solve the equation system. The readers can refer to [25, 35, 40, 42] for details of how to generate equations and how to feed them to the solvers.


## 6.1. The Optimal Location Selection

LetXr,ik be the location where the HT is inserted, 0≤r≤32, 0≤i, and k≤7. In order to search the optimal location, four properties are desired:(1) Note that the secret master key can be recovered only for the case that they are involved during the fault propagation; thus the number of elements inΣr,i should be equal to 16.(2) The required number of faults to recover the secret master key and the reduced key search spaceφ(K) after the injection to Xr,ik should be both minimized to make the attack more practical.(3) The average time of the solver to solve the merged equation system should be minimized to increase the effectiveness of the attack.(4)Xr,ik should be in a deeper round to maximize utilize the fault leakages and to evade the detection.In order to search the optimal bit location for the HT, AFA is used to enumerate every possible (r,i,k). The attempts are conducted in advance, which can guide the logic designs of the HT and reduce costs. Since AFA is executed as machine-based automation, all possible key candidates will be eventually checked along the fault propagation paths. The utilization of fault leakages is maximized. The automation shows its advantage over traditional manual analysis, such as DFA, especially when the analysis goes into the deeper round.


## 6.2. Constructing Algebraic Equations for Encryption of HIGHT

The task of this stage is to represent HIGHT cipher with a large system of low degree Boolean equations. SupposeXr=Xr,7∥Xr,6⋯∥Xr,1∥Xr,0 and C=C7∥C6∥⋯∥C1∥C0 are the 64-bit input of round r+1 and ciphertext, respectively. Since the key schedule of HIGHT is very simple, we mainly focus on the encryption of HIGHT which is shown in Algorithm 1. From Algorithm 1, the most important yet difficult problem is to construct the equations for ARX operations.Algorithm 1:ConstructEquEncryption(Xr,i).
for m=rto31do
X
m
,
0
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
,
X
m
,
1
⊕
X
m
-
1,0
=
0
X
m
,
2
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
2
=
0
,
X
m
,
3
⊕
X
m
-
1,2
=
0
X
m
,
4
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
⊕
X
m
-
1,4
=
0
X
m
,
6
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊕
S
K
4
m
-
4
=
0
,
X
m
,
7
⊕
X
m
-
1,6
=
0
end for
for m=32do
X
m
,
0
⊕
X
m
-
1,0
=
0
,
X
m
,
1
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
4
=
0
X
m
,
2
⊕
X
m
-
1,2
=
0
,
X
m
,
3
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
X
m
,
4
⊕
X
m
-
1,4
=
0
,
X
m
,
5
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊞
S
K
4
m
-
2
=
0
X
m
,
6
⊕
X
m
-
1,6
=
0
,
X
m
,
7
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
end for
C
0
⊕
X
32,0
⊞
W
K
4
=
0
,
C
1
⊕
X
32,1
=
0
,
C
2
⊕
X
32,2
⊕
W
K
5
=
0
,
C
3
⊕
X
32,3
=
0
C
4
⊕
X
32,4
⊞
W
K
6
=
0
,
C
5
⊕
X
32,5
=
0
,
C
6
⊕
X
32,6
⊕
W
K
7
=
0
,
C
7
⊕
X
32,7
=
0
C
=
C
7
∥
C
6
∥
C
5
∥
C
4
∥
C
3
∥
C
2
∥
C
1
∥
C
0It is stressed that in general the adversary will not choose a very deep round as the target round. That is, the rounds between the target round andFinalTransformationare not very large. Therefore, instead of constructing equations for the full rounds of the cipher, we only construct equations for the rounds from the target round to theFinalTransformation which will result in a smaller equation script and thus will accelerate the solving procedure.According to Algorithm1, for every fault that is injected in Xr,i, there are 64×(32-r+1) variables and 8×(8×(32-r+1)+8) ANF equations were introduced to the equation system C. In addition, 32×(32-r+1) variables and ANF equations are required for round keys, 64 variables and ANF equations are for the whitening keys, and 128 variables and ANF equations are for the master keys.


### 6.2.1. The Equations for Addition mod2n

AssumeX, Y, Z∈GF(2n) are the two inputs and output of addition modulo 2n, where X=(xn-1,xn-2,…,x0), Y=(yn-1,yn-2,…,y0), and Z=(zn-1,zn-2,…,z0) with x0, y0, and z0 being the least significant bit, respectively. Then addition modulo 2n can be described as Boolean equations as follows:(21)z0=x0⊕y0z1=x1⊕y1⊕x0y0z2=x2⊕y2⊕x1y1⊕x1⊕y1x1⊕y1⊕z1⋮zi=xi⊕yi⊕xi-1yi-1⊕xi-1⊕yi-1xi-1⊕yi-1⊕zi-1⋮zn-1=xn-1⊕yn-1⊕xn-2yn-2⊕xn-2⊕yn-2xn-2⊕yn-2⊕zn-2.


### 6.2.2. The Equations forF0(·) and F1(·)

Given that the input and output ofF0(·) and F1(·) are X=(x7,x6,…,x0) and Y=(y7,y6,…,y0), respectively, then F0(·) and F1(·) can be described as the following Boolean equations:(22)F0·⟺y7=x6⊕x5⊕x0y6=x7⊕x5⊕x4y5=x6⊕x4⊕x3y4=x5⊕x3⊕x2y3=x4⊕x2⊕x1y2=x3⊕x1⊕x0y1=x7⊕x2⊕x0y0=x7⊕x6⊕x1,F1·⟺y7=x4⊕x3⊕x1y6=x3⊕x2⊕x0y5=x7⊕x2⊕x1y4=x6⊕x1⊕x0y3=x7⊕x5⊕x0y2=x7⊕x6⊕x4y1=x6⊕x5⊕x3y0=x5⊕x4⊕x2.


## 6.2.1. The Equations for Addition mod2n

AssumeX, Y, Z∈GF(2n) are the two inputs and output of addition modulo 2n, where X=(xn-1,xn-2,…,x0), Y=(yn-1,yn-2,…,y0), and Z=(zn-1,zn-2,…,z0) with x0, y0, and z0 being the least significant bit, respectively. Then addition modulo 2n can be described as Boolean equations as follows:(21)z0=x0⊕y0z1=x1⊕y1⊕x0y0z2=x2⊕y2⊕x1y1⊕x1⊕y1x1⊕y1⊕z1⋮zi=xi⊕yi⊕xi-1yi-1⊕xi-1⊕yi-1xi-1⊕yi-1⊕zi-1⋮zn-1=xn-1⊕yn-1⊕xn-2yn-2⊕xn-2⊕yn-2xn-2⊕yn-2⊕zn-2.


## 6.2.2. The Equations forF0(·) and F1(·)

Given that the input and output ofF0(·) and F1(·) are X=(x7,x6,…,x0) and Y=(y7,y6,…,y0), respectively, then F0(·) and F1(·) can be described as the following Boolean equations:(22)F0·⟺y7=x6⊕x5⊕x0y6=x7⊕x5⊕x4y5=x6⊕x4⊕x3y4=x5⊕x3⊕x2y3=x4⊕x2⊕x1y2=x3⊕x1⊕x0y1=x7⊕x2⊕x0y0=x7⊕x6⊕x1,F1·⟺y7=x4⊕x3⊕x1y6=x3⊕x2⊕x0y5=x7⊕x2⊕x1y4=x6⊕x1⊕x0y3=x7⊕x5⊕x0y2=x7⊕x6⊕x4y1=x6⊕x5⊕x3y0=x5⊕x4⊕x2.


## 6.3. Constructing Equations for the Injected Faults

This stage illustrates the method of constructing equations for the injected faults. To clarify the method, the example is shown in Figure7.Figure 7
The fault propagation corresponding to the case whereX25,0 is faulted.Given that every time the HT was activated, a single-bit faultβ was introduced to flip the most significant bit of X25,3. The fault propagation paths are shown by bold line in Figure 7. The correct and faulty 64-bit inputs to the rth round are denoted by Xr=Xr,7∥⋯Xr,1∥Xr,0 and Xr′=Xr,7′∥⋯Xr,1′∥Xr,0′, respectively. Then, the complex fault propagation paths can be described as a set of algebraic equations with the variables that were involved. Since the fault flips the most significant bit of X25,0, we have(23)X25,3⊕X25,3′⊕β=0,where β=(1,0,…,0). For the fault propagation paths that from round 25 to theFinalTransformation, they can be described by equations as Algorithm 2.Algorithm 2:ConstructgEquFault(Xr,i).
Θ
=
I
-
S
e
a
r
c
h
F
a
u
l
t
I
n
t
e
r
V
a
l
X
r
,
i;
while
X
i
,
φ
∈
Θ
do
X
i
,
φ
′
⊕
X
i
,
φ
=
0
end while
for
m
=
r
to
31
do
X
m
,
0
′
⊕
X
m
-
1,7
′
⊕
F
0
X
m
-
1,6
′
⊞
S
K
4
m
-
1
=
0
,
X
m
,
1
′
⊕
X
m
-
1,0
′
=
0
X
m
,
2
′
⊕
X
m
-
1,1
′
⊞
F
1
X
m
-
1,0
′
⊕
S
K
4
m
-
4
=
0
,
X
m
,
3
′
⊕
X
m
-
1,2
′
=
0
X
m
,
4
′
⊕
X
m
-
1,3
′
⊕
F
0
X
m
-
1,2
′
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
′
⊕
X
m
-
1,4
′
=
0
X
m
,
6
′
⊕
X
m
-
1,5
′
⊞
F
1
X
m
-
1,4
′
⊕
S
K
4
m
-
2
=
0
,
X
m
,
7
′
⊕
X
m
-
1,6
′
=
0
end for
for
m
=
32
do
X
m
,
0
′
⊕
X
m
-
1,0
′
=
0
,
X
m
,
1
′
⊕
X
m
-
1,1
′
⊞
F
1
X
m
-
1,0
′
⊕
S
K
4
m
-
4
=
0
X
m
,
2
′
⊕
X
m
-
1,2
′
=
0
,
X
m
,
3
′
⊕
X
m
-
1,3
′
⊕
F
0
X
m
-
1,2
′
⊞
S
K
4
m
-
3
=
0
X
m
,
4
′
⊕
X
m
-
1,4
′
=
0
,
X
m
,
5
′
⊕
X
m
-
1,5
′
⊞
F
1
X
m
-
1,4
′
⊞
S
K
4
m
-
2
=
0
X
m
,
6
′
⊕
X
m
-
1,6
′
=
0
,
X
m
,
7
′
⊕
X
m
-
1,7
′
⊕
F
0
X
m
-
1,6
′
⊞
S
K
4
m
-
1
=
0
end for
C
0
′
⊕
X
32,0
′
⊞
W
K
4
=
0
,
C
1
′
⊕
X
32,1
′
=
0
,
C
2
′
⊕
X
32,2
′
⊕
W
K
5
=
0
,
C
3
′
⊕
X
32,3
′
=
0
C
4
′
⊕
X
32,4
′
⊞
W
K
6
=
0
,
C
5
′
⊕
X
32,5
′
=
0
,
C
6
′
⊕
X
32,6
′
⊕
W
K
7
=
0
,
C
7
′
⊕
X
32,7
′
=
0
C
′
=
C
7
′
∥
C
6
′
∥
C
5
′
∥
C
4
′
∥
C
3
′
∥
C
2
′
∥
C
1
′
∥
C
0Algorithm2 constructs the equations for the injected faults. The main idea is that every time a fault was induced, the intermediate variables from round r to round 32 were viewed as new variables Xi,φ′. Then, we reconstruct the equations for the encryption by replacing Xi,φ with Xi,φ′. Furthermore, for variables that were not involved along the fault propagation paths Θ which can be deduced by the functionSearchFaultyInterVal(Xr,i), we have Xi,φ′=Xi,φ. Thus, there are 64×(32-r+1) variables and 8×(#(Θ)+8×(32-r+1)+8) ANF equations were introduced to the equation system D for every fault that was injected in Xr,i.The function,SearchFaultyInterVal(Xr,i) searches the faulty intermediate variables automatically according to the fault locationXr,i and finally returns them. The main idea is explained earlier in Section 3. Algorithm 3 describes the procedure.Algorithm 3:SearchFaultyInterVal(Xr,i).
F
a
u
l
t
y
I
n
t
e
r
V
a
l
←
X
r
,
i
T
e
m
p
A
r
r
a
y
←
X
r
,
i
for
m
=
r
to
32
do
whileXm,φ∈TempArraymdo
ifm<32then
ifφ%2==0then
TempArraym+1←Xm,φ+1,Xm,φ+2%8
end if
ifφ%2==1then
TempArraym+1←Xm,φ+1%8
end if
end if
ifm==32then
ifφ%2==0then
TempArraym+1←Xm,φ,Xm,φ+1
end if
ifφ%2==1then
TempArraym+1←Xm,φ
end if
end if
end while
F
a
u
l
t
y
I
n
t
e
r
V
a
l
←
F
a
u
l
t
y
I
n
t
e
r
V
a
l
∪
T
e
m
p
A
r
r
a
y
m
end for
Return
F
a
u
l
t
y
I
n
t
e
r
V
a
l


## 6.4. Solving the Equations System

After activating the inserted HT to introduce single-bit faults and constructing the merged equation system for both the cipher and faults, the whole secret master key can be fully recovered by solving the merged equation system with an automatic solver. Since the SAT-based solvers [39, 40] have prominent advantage of the memory usage when solving large equations systems over many other automatic tools, such as mutantXL algorithm [35, 37] and Gröbner basis-based [41] solvers and recently further significant improvements have been made to SAT-based solvers, we have chosen the CryptoMiniSAT v4.4 which is a DPLL-based SAT solver developed from MiniSAT to solve the equation system. The readers can refer to [25, 35, 40, 42] for details of how to generate equations and how to feed them to the solvers.


## 7. Theoretical and Simulation Results

In order to verify the effectiveness of the proposed attack on HIGHT and optimize the implementation of HT, we conduct many experiments and report the results in this section.In the phase of searching the optimal location for the HT, we conduct the fault injection with software level simulations. The HIGHT software implementation was written in C and the CryptoMiniSAT 4.4 solver is running on a PC with Intel Core i7-4790, 3.60 GHZ, 12 G memory, and Windows 7 64-bit OS. Aninstance refers to one run of our attack on a set of (P, MK,C). The instance fails if the solver does not give an output within48 hours (172800 seconds). In the online phase, the HIGHT hardware implementation and HT are both running in SASEBO-GII board soldering a 65 nm Virtex-5 FPGA.


### 7.1. Data Complexity Analysis

Our aim is to fully recover the entire master key, which is mainly depending on solving the two equations (19) and (20) in Section 4. Our task is to investigate the number of queries (α,β) and (0,β) to solve the equations. We notice that this issue was already explored from a theoretical point of view in [41]. And a worst case lower bound on the number of queries (α,β) to solve (16) is a constant 3, and the corresponding number of queries (0,β) to solve (20) in the worst case is (8-t), wheret is the position of the least significant “1” of x and 0≤t≤7.Additionally, we useNto denote the amount of faults required to recover the entire master key bits. In our case, every encryption the master key bits are assumed to be fixed while the plaintext was chosen randomly by the adversary. And since queries (α,β) and (0,β) are introduced by activating the HT to flip one fixed bit of a certain intermediate word, the lower bound on the number of HT activated in the worst case is N≥3.


### 7.2. Experimental Results

#### 7.2.1. Cost-Optimization Implementation of the HT

6-input LUT is the mainstream look-up-table (LUT) architecture widely used from the 65 nm Virtex-5 FPGAs to the 20 nm Ultrascale FPGAs. In these devices,slice is the fundamental logic unit and eachslice contains four 6-input LUTs. A single 6-input LUT is able to implement either one Boolean equation up to 6 inputs or two Boolean equations with no more than 5 different input signals in total. The structure of the 6-input LUT is shown in Figure 8.Figure 8
The structure of 6-input LUT.According to Section5, both the payload gate f(a,b,c) which is illustrated in Figure 6 and the LUTs required to implement the trigger logic have 3 inputs. Moreover, occupied LUTs with 3 or less used inputs can be found by searching the XDL. In this stage, the payload gate f(a,b,c) and the required four 3-input LUTs can be implemented by five arbitrarily occupied LUTs with no more than 3 used inputs, by just modifying the corresponding slice instances on XDL. Since the Trojan LUTs are implemented with existing logic, the eventual cost is4 extra flip-flops. The experiment result is shown in Table 3, which reports a 1.63% additional cost in flip-flops for the HT implemented on a 65 nm Virtex-5 FPGA.Table 3
Overhead report of inserted HT.
Slice
LUT
Flip-flop
HIGHT
404
750
245
Trojan HIGHT
404
750
249
Overhead
0%
0%
1.63%


#### 7.2.2. The Optimal Location Selection for Inserting the HT

(
1) Determining k. According to Section 5.1, to make the designed HT stealthy and reduce the costs, the HT is designed to flip only one bit of the 8-bit intermediate word when it is activated. Since the lower bound on the number of queries (α,β) to solve (16) in the worst case is inversely proportional to the size of t, we choose the most significant bit of the 8-bit intermediate word to be flipped. That is, k=7. And in that case, the resulting N is minimum.(
2) Determining (r,i). According to Property 3 of the faults (Section 4), only when r≤25 the entire master key bytes can be involved during the fault propagation. Thus, the HT should be inserted in Xr,ir≤25 to ensure the entire secret master key variables are included in the algebraic equations of the injected faults (Section 6.3). And there are 5 candidate locations (r,i)={(25,0),(25,1),(25,2),(25,3),(25,4)} and each of them is tested by AFA to get the optimal location for the HT.According to the equations for addition mod2n in Section 6.2.1, the most significant bit of x and y for (19) and (20) can be never recovered for no observation which can be made about the most significant bit ofγ. Thus, there are multiple solutions for (19) and (20); that is, multiple candidates for MK will be collected by solving the merged equation system with an SAT solver. To determine MK uniquely, a distinguisher is required to further filter the MK candidates.The CryptoMiniSAT solver searches for the given amount of solutions, which means all candidates for MK will be checked if the given amount of solutions is set large enough. With this property, we can build a distinguisher. Note the fact that the unknown intermediate wordsXr and the known ciphertext C are both depending on (P,MK); we can filter the MK candidates against C by constructing equations for the full rounds of HIGHT. For every MK candidate, C∗ will be automatically deduced by the solver based on the MK candidate and the knownP.If C∗ does not match C, the candidate will be eliminated. Thus, with this property of the solver, an efficient distinguisher can be built just by constructing equations for the full rounds of HIGHT. Since the equations for round r toFinalTransformationhas been constructed in Algorithm 1, we only need to construct equations forInitialTransformation to round r-1 of HIGHT to build the distinguisher which is shown in Algorithm 4. Hence, there are additional 64×r variables and 8×(8×r+8) ANF equations are required for the intermediate words, 32×r variables and ANF equations are required for round keys, and 64 variables and ANF equations are required for the whitening keys.Algorithm 4:ConstructDistinguisher(Xr,i).
P
=
P
7
∥
P
6
∥
P
5
∥
P
4
∥
P
3
∥
P
2
∥
P
1
∥
P
0
X
0,0
⊕
P
0
⊞
W
K
0
=
0
,
X
0,1
⊕
P
1
=
0
,
X
0,2
⊕
P
2
⊕
W
K
1
=
0
,
X
0,3
⊕
P
3
=
0
X
0,4
⊕
P
4
⊞
W
K
2
=
0
,
X
0,5
⊕
P
5
=
0
,
X
0,6
⊕
P
6
⊕
W
K
2
=
0
,
X
0,7
⊕
P
7
=
0
f
o
r
m
=
0
t
o
r
-
1
d
o
X
m
,
0
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
,
X
m
+
1,1
⊕
X
m
,
0
=
0
X
m
,
2
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
4
=
0
,
X
m
+
1,3
⊕
X
m
,
2
=
0
X
m
,
4
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
⊕
X
m
-
1,4
=
0
X
m
,
6
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊕
S
K
4
m
-
2
=
0
,
X
m
,
7
⊕
X
m
-
1,6
=
0
e
n
d
f
o
rIn order to verify the effectiveness of the distinguisher, that is, whether the entire master key bits can be uniquely determined, we set the given amount of solutions to 2128 for the solver. And the simulations are conducted under two different modes: one is denoted by mode A which is with the distinguisher and the other is denoted by mode B which is without the distinguisher. We use the method in Section 6 to build the emerged algebraic equation system for the cipher and the injected faults. The results in Table 4, which are derived statistically from 100 instances, show the statistics of solutions corresponding to different (r,i) under mode A and mode B with the number of faults N which varies from 3 to 9. We can see that the cases, which are conducted under mode A, have a unique solution for N≥3; that is, the entire 128-bit master key can be uniquely determined for these cases. However, when these attacks are conducted under mode B, the CryptoMiniSAT solver always outputs multiple solutions and the number of solutions seem to be inversely proportional to N. Thus, the experimental results indicate that the distinguisher is feasible and effectiveness and also proving the lower bound in the worst case for N is 3.Table 4
Statistics of solutions corresponds to different(r,i) under mode A and mode B.
(
r
,
i
)
Mode A (with a distinguisher)
Mode B (without a distinguisher)
N = 9
N = 8
N = 7
N = 6
N = 5
N = 4
N = 3
N = 9
N = 8
N = 7
N = 6
N = 5
N = 4
N = 3
(25, 0)
1
1
1
1
1
1
–
8.24
8.48
8.64
8.96
9.44
11.74
–
(25, 1)
1
1
1
1
1
1
1
16.76
17.55
18.58
21.33
26.40
264.47
9660.49
(25, 2)
1
1
1
1
1
1
1
2.12
2.40
2.66
2.78
3.20
3.93
2654.37
(25, 3)
1
1
1
1
1
1
1
34.74
34.82
35.66
36.57
39.31
55.77
5782.57
(25, 4)
1
1
1
1
1
1
–
8.32
8.48
8.96
8.96
10.88
21.69
–Serving the purpose of accelerating the experiments, five PCs with the same configuration are employed to run the CryptoMiniSAT solver in parallel so as to finish these attacks. Each PC runs 20 instances. Figure9 shows the average solving time of the CryptoMiniSAT solver corresponding to the cases where the HT is inserted in X25,i(i=0,1,2,3,4) under mode A. The figure shows that when N<3, the secret master key is failed to be recovered in 48 hours. And for the cases where the HT is inserted in (25,0) and (25,4), the minimum value forNis 4, while for the cases (25,1), (25,2), and (25,3) the minimum value for N is 3. The figure also clearly shows the distributions corresponding to the case (25,3) having a lower average compared to the other. Thus the optimal location for inserting the HT is (25,3) and the corresponding average solving time when N=3 is t0=12572.26 seconds (≈3.49 hours).Figure 9
The results of the cases where the HT is inserted inX25,i under mode A.


#### 7.2.3. Success Rate of the Attack

To evaluate the success rate of the attack under mode A where the HT is inserted in the optimal location determined in Section7.2.2, 100 instances are tested with different (P,MK). Figure 10 shows the success rate of the attack. It can be seen that whenN is lower than 3, the success rate of the attack remains 0%. OnceN is greater than or equal to 3, asN taken grows, the success rate of the attack increases. And the success rate of the attack can reach 100% by increasingN to 7. It can be also seen in the lower part of Figure 10 that whenNis equal to 3, only 4 instances fail to recover the secret master key in 48 hours; thus the success rate of the attack is 96%.Figure 10
Success rate of the attack.


## 7.1. Data Complexity Analysis

Our aim is to fully recover the entire master key, which is mainly depending on solving the two equations (19) and (20) in Section 4. Our task is to investigate the number of queries (α,β) and (0,β) to solve the equations. We notice that this issue was already explored from a theoretical point of view in [41]. And a worst case lower bound on the number of queries (α,β) to solve (16) is a constant 3, and the corresponding number of queries (0,β) to solve (20) in the worst case is (8-t), wheret is the position of the least significant “1” of x and 0≤t≤7.Additionally, we useNto denote the amount of faults required to recover the entire master key bits. In our case, every encryption the master key bits are assumed to be fixed while the plaintext was chosen randomly by the adversary. And since queries (α,β) and (0,β) are introduced by activating the HT to flip one fixed bit of a certain intermediate word, the lower bound on the number of HT activated in the worst case is N≥3.


## 7.2. Experimental Results

### 7.2.1. Cost-Optimization Implementation of the HT

6-input LUT is the mainstream look-up-table (LUT) architecture widely used from the 65 nm Virtex-5 FPGAs to the 20 nm Ultrascale FPGAs. In these devices,slice is the fundamental logic unit and eachslice contains four 6-input LUTs. A single 6-input LUT is able to implement either one Boolean equation up to 6 inputs or two Boolean equations with no more than 5 different input signals in total. The structure of the 6-input LUT is shown in Figure 8.Figure 8
The structure of 6-input LUT.According to Section5, both the payload gate f(a,b,c) which is illustrated in Figure 6 and the LUTs required to implement the trigger logic have 3 inputs. Moreover, occupied LUTs with 3 or less used inputs can be found by searching the XDL. In this stage, the payload gate f(a,b,c) and the required four 3-input LUTs can be implemented by five arbitrarily occupied LUTs with no more than 3 used inputs, by just modifying the corresponding slice instances on XDL. Since the Trojan LUTs are implemented with existing logic, the eventual cost is4 extra flip-flops. The experiment result is shown in Table 3, which reports a 1.63% additional cost in flip-flops for the HT implemented on a 65 nm Virtex-5 FPGA.Table 3
Overhead report of inserted HT.
Slice
LUT
Flip-flop
HIGHT
404
750
245
Trojan HIGHT
404
750
249
Overhead
0%
0%
1.63%


### 7.2.2. The Optimal Location Selection for Inserting the HT

(
1) Determining k. According to Section 5.1, to make the designed HT stealthy and reduce the costs, the HT is designed to flip only one bit of the 8-bit intermediate word when it is activated. Since the lower bound on the number of queries (α,β) to solve (16) in the worst case is inversely proportional to the size of t, we choose the most significant bit of the 8-bit intermediate word to be flipped. That is, k=7. And in that case, the resulting N is minimum.(
2) Determining (r,i). According to Property 3 of the faults (Section 4), only when r≤25 the entire master key bytes can be involved during the fault propagation. Thus, the HT should be inserted in Xr,ir≤25 to ensure the entire secret master key variables are included in the algebraic equations of the injected faults (Section 6.3). And there are 5 candidate locations (r,i)={(25,0),(25,1),(25,2),(25,3),(25,4)} and each of them is tested by AFA to get the optimal location for the HT.According to the equations for addition mod2n in Section 6.2.1, the most significant bit of x and y for (19) and (20) can be never recovered for no observation which can be made about the most significant bit ofγ. Thus, there are multiple solutions for (19) and (20); that is, multiple candidates for MK will be collected by solving the merged equation system with an SAT solver. To determine MK uniquely, a distinguisher is required to further filter the MK candidates.The CryptoMiniSAT solver searches for the given amount of solutions, which means all candidates for MK will be checked if the given amount of solutions is set large enough. With this property, we can build a distinguisher. Note the fact that the unknown intermediate wordsXr and the known ciphertext C are both depending on (P,MK); we can filter the MK candidates against C by constructing equations for the full rounds of HIGHT. For every MK candidate, C∗ will be automatically deduced by the solver based on the MK candidate and the knownP.If C∗ does not match C, the candidate will be eliminated. Thus, with this property of the solver, an efficient distinguisher can be built just by constructing equations for the full rounds of HIGHT. Since the equations for round r toFinalTransformationhas been constructed in Algorithm 1, we only need to construct equations forInitialTransformation to round r-1 of HIGHT to build the distinguisher which is shown in Algorithm 4. Hence, there are additional 64×r variables and 8×(8×r+8) ANF equations are required for the intermediate words, 32×r variables and ANF equations are required for round keys, and 64 variables and ANF equations are required for the whitening keys.Algorithm 4:ConstructDistinguisher(Xr,i).
P
=
P
7
∥
P
6
∥
P
5
∥
P
4
∥
P
3
∥
P
2
∥
P
1
∥
P
0
X
0,0
⊕
P
0
⊞
W
K
0
=
0
,
X
0,1
⊕
P
1
=
0
,
X
0,2
⊕
P
2
⊕
W
K
1
=
0
,
X
0,3
⊕
P
3
=
0
X
0,4
⊕
P
4
⊞
W
K
2
=
0
,
X
0,5
⊕
P
5
=
0
,
X
0,6
⊕
P
6
⊕
W
K
2
=
0
,
X
0,7
⊕
P
7
=
0
f
o
r
m
=
0
t
o
r
-
1
d
o
X
m
,
0
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
,
X
m
+
1,1
⊕
X
m
,
0
=
0
X
m
,
2
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
4
=
0
,
X
m
+
1,3
⊕
X
m
,
2
=
0
X
m
,
4
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
⊕
X
m
-
1,4
=
0
X
m
,
6
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊕
S
K
4
m
-
2
=
0
,
X
m
,
7
⊕
X
m
-
1,6
=
0
e
n
d
f
o
rIn order to verify the effectiveness of the distinguisher, that is, whether the entire master key bits can be uniquely determined, we set the given amount of solutions to 2128 for the solver. And the simulations are conducted under two different modes: one is denoted by mode A which is with the distinguisher and the other is denoted by mode B which is without the distinguisher. We use the method in Section 6 to build the emerged algebraic equation system for the cipher and the injected faults. The results in Table 4, which are derived statistically from 100 instances, show the statistics of solutions corresponding to different (r,i) under mode A and mode B with the number of faults N which varies from 3 to 9. We can see that the cases, which are conducted under mode A, have a unique solution for N≥3; that is, the entire 128-bit master key can be uniquely determined for these cases. However, when these attacks are conducted under mode B, the CryptoMiniSAT solver always outputs multiple solutions and the number of solutions seem to be inversely proportional to N. Thus, the experimental results indicate that the distinguisher is feasible and effectiveness and also proving the lower bound in the worst case for N is 3.Table 4
Statistics of solutions corresponds to different(r,i) under mode A and mode B.
(
r
,
i
)
Mode A (with a distinguisher)
Mode B (without a distinguisher)
N = 9
N = 8
N = 7
N = 6
N = 5
N = 4
N = 3
N = 9
N = 8
N = 7
N = 6
N = 5
N = 4
N = 3
(25, 0)
1
1
1
1
1
1
–
8.24
8.48
8.64
8.96
9.44
11.74
–
(25, 1)
1
1
1
1
1
1
1
16.76
17.55
18.58
21.33
26.40
264.47
9660.49
(25, 2)
1
1
1
1
1
1
1
2.12
2.40
2.66
2.78
3.20
3.93
2654.37
(25, 3)
1
1
1
1
1
1
1
34.74
34.82
35.66
36.57
39.31
55.77
5782.57
(25, 4)
1
1
1
1
1
1
–
8.32
8.48
8.96
8.96
10.88
21.69
–Serving the purpose of accelerating the experiments, five PCs with the same configuration are employed to run the CryptoMiniSAT solver in parallel so as to finish these attacks. Each PC runs 20 instances. Figure9 shows the average solving time of the CryptoMiniSAT solver corresponding to the cases where the HT is inserted in X25,i(i=0,1,2,3,4) under mode A. The figure shows that when N<3, the secret master key is failed to be recovered in 48 hours. And for the cases where the HT is inserted in (25,0) and (25,4), the minimum value forNis 4, while for the cases (25,1), (25,2), and (25,3) the minimum value for N is 3. The figure also clearly shows the distributions corresponding to the case (25,3) having a lower average compared to the other. Thus the optimal location for inserting the HT is (25,3) and the corresponding average solving time when N=3 is t0=12572.26 seconds (≈3.49 hours).Figure 9
The results of the cases where the HT is inserted inX25,i under mode A.


### 7.2.3. Success Rate of the Attack

To evaluate the success rate of the attack under mode A where the HT is inserted in the optimal location determined in Section7.2.2, 100 instances are tested with different (P,MK). Figure 10 shows the success rate of the attack. It can be seen that whenN is lower than 3, the success rate of the attack remains 0%. OnceN is greater than or equal to 3, asN taken grows, the success rate of the attack increases. And the success rate of the attack can reach 100% by increasingN to 7. It can be also seen in the lower part of Figure 10 that whenNis equal to 3, only 4 instances fail to recover the secret master key in 48 hours; thus the success rate of the attack is 96%.Figure 10
Success rate of the attack.


## 7.2.1. Cost-Optimization Implementation of the HT

6-input LUT is the mainstream look-up-table (LUT) architecture widely used from the 65 nm Virtex-5 FPGAs to the 20 nm Ultrascale FPGAs. In these devices,slice is the fundamental logic unit and eachslice contains four 6-input LUTs. A single 6-input LUT is able to implement either one Boolean equation up to 6 inputs or two Boolean equations with no more than 5 different input signals in total. The structure of the 6-input LUT is shown in Figure 8.Figure 8
The structure of 6-input LUT.According to Section5, both the payload gate f(a,b,c) which is illustrated in Figure 6 and the LUTs required to implement the trigger logic have 3 inputs. Moreover, occupied LUTs with 3 or less used inputs can be found by searching the XDL. In this stage, the payload gate f(a,b,c) and the required four 3-input LUTs can be implemented by five arbitrarily occupied LUTs with no more than 3 used inputs, by just modifying the corresponding slice instances on XDL. Since the Trojan LUTs are implemented with existing logic, the eventual cost is4 extra flip-flops. The experiment result is shown in Table 3, which reports a 1.63% additional cost in flip-flops for the HT implemented on a 65 nm Virtex-5 FPGA.Table 3
Overhead report of inserted HT.
Slice
LUT
Flip-flop
HIGHT
404
750
245
Trojan HIGHT
404
750
249
Overhead
0%
0%
1.63%


## 7.2.2. The Optimal Location Selection for Inserting the HT

(
1) Determining k. According to Section 5.1, to make the designed HT stealthy and reduce the costs, the HT is designed to flip only one bit of the 8-bit intermediate word when it is activated. Since the lower bound on the number of queries (α,β) to solve (16) in the worst case is inversely proportional to the size of t, we choose the most significant bit of the 8-bit intermediate word to be flipped. That is, k=7. And in that case, the resulting N is minimum.(
2) Determining (r,i). According to Property 3 of the faults (Section 4), only when r≤25 the entire master key bytes can be involved during the fault propagation. Thus, the HT should be inserted in Xr,ir≤25 to ensure the entire secret master key variables are included in the algebraic equations of the injected faults (Section 6.3). And there are 5 candidate locations (r,i)={(25,0),(25,1),(25,2),(25,3),(25,4)} and each of them is tested by AFA to get the optimal location for the HT.According to the equations for addition mod2n in Section 6.2.1, the most significant bit of x and y for (19) and (20) can be never recovered for no observation which can be made about the most significant bit ofγ. Thus, there are multiple solutions for (19) and (20); that is, multiple candidates for MK will be collected by solving the merged equation system with an SAT solver. To determine MK uniquely, a distinguisher is required to further filter the MK candidates.The CryptoMiniSAT solver searches for the given amount of solutions, which means all candidates for MK will be checked if the given amount of solutions is set large enough. With this property, we can build a distinguisher. Note the fact that the unknown intermediate wordsXr and the known ciphertext C are both depending on (P,MK); we can filter the MK candidates against C by constructing equations for the full rounds of HIGHT. For every MK candidate, C∗ will be automatically deduced by the solver based on the MK candidate and the knownP.If C∗ does not match C, the candidate will be eliminated. Thus, with this property of the solver, an efficient distinguisher can be built just by constructing equations for the full rounds of HIGHT. Since the equations for round r toFinalTransformationhas been constructed in Algorithm 1, we only need to construct equations forInitialTransformation to round r-1 of HIGHT to build the distinguisher which is shown in Algorithm 4. Hence, there are additional 64×r variables and 8×(8×r+8) ANF equations are required for the intermediate words, 32×r variables and ANF equations are required for round keys, and 64 variables and ANF equations are required for the whitening keys.Algorithm 4:ConstructDistinguisher(Xr,i).
P
=
P
7
∥
P
6
∥
P
5
∥
P
4
∥
P
3
∥
P
2
∥
P
1
∥
P
0
X
0,0
⊕
P
0
⊞
W
K
0
=
0
,
X
0,1
⊕
P
1
=
0
,
X
0,2
⊕
P
2
⊕
W
K
1
=
0
,
X
0,3
⊕
P
3
=
0
X
0,4
⊕
P
4
⊞
W
K
2
=
0
,
X
0,5
⊕
P
5
=
0
,
X
0,6
⊕
P
6
⊕
W
K
2
=
0
,
X
0,7
⊕
P
7
=
0
f
o
r
m
=
0
t
o
r
-
1
d
o
X
m
,
0
⊕
X
m
-
1,7
⊕
F
0
X
m
-
1,6
⊞
S
K
4
m
-
1
=
0
,
X
m
+
1,1
⊕
X
m
,
0
=
0
X
m
,
2
⊕
X
m
-
1,1
⊞
F
1
X
m
-
1,0
⊕
S
K
4
m
-
4
=
0
,
X
m
+
1,3
⊕
X
m
,
2
=
0
X
m
,
4
⊕
X
m
-
1,3
⊕
F
0
X
m
-
1,2
⊞
S
K
4
m
-
3
=
0
,
X
m
,
5
⊕
X
m
-
1,4
=
0
X
m
,
6
⊕
X
m
-
1,5
⊞
F
1
X
m
-
1,4
⊕
S
K
4
m
-
2
=
0
,
X
m
,
7
⊕
X
m
-
1,6
=
0
e
n
d
f
o
rIn order to verify the effectiveness of the distinguisher, that is, whether the entire master key bits can be uniquely determined, we set the given amount of solutions to 2128 for the solver. And the simulations are conducted under two different modes: one is denoted by mode A which is with the distinguisher and the other is denoted by mode B which is without the distinguisher. We use the method in Section 6 to build the emerged algebraic equation system for the cipher and the injected faults. The results in Table 4, which are derived statistically from 100 instances, show the statistics of solutions corresponding to different (r,i) under mode A and mode B with the number of faults N which varies from 3 to 9. We can see that the cases, which are conducted under mode A, have a unique solution for N≥3; that is, the entire 128-bit master key can be uniquely determined for these cases. However, when these attacks are conducted under mode B, the CryptoMiniSAT solver always outputs multiple solutions and the number of solutions seem to be inversely proportional to N. Thus, the experimental results indicate that the distinguisher is feasible and effectiveness and also proving the lower bound in the worst case for N is 3.Table 4
Statistics of solutions corresponds to different(r,i) under mode A and mode B.
(
r
,
i
)
Mode A (with a distinguisher)
Mode B (without a distinguisher)
N = 9
N = 8
N = 7
N = 6
N = 5
N = 4
N = 3
N = 9
N = 8
N = 7
N = 6
N = 5
N = 4
N = 3
(25, 0)
1
1
1
1
1
1
–
8.24
8.48
8.64
8.96
9.44
11.74
–
(25, 1)
1
1
1
1
1
1
1
16.76
17.55
18.58
21.33
26.40
264.47
9660.49
(25, 2)
1
1
1
1
1
1
1
2.12
2.40
2.66
2.78
3.20
3.93
2654.37
(25, 3)
1
1
1
1
1
1
1
34.74
34.82
35.66
36.57
39.31
55.77
5782.57
(25, 4)
1
1
1
1
1
1
–
8.32
8.48
8.96
8.96
10.88
21.69
–Serving the purpose of accelerating the experiments, five PCs with the same configuration are employed to run the CryptoMiniSAT solver in parallel so as to finish these attacks. Each PC runs 20 instances. Figure9 shows the average solving time of the CryptoMiniSAT solver corresponding to the cases where the HT is inserted in X25,i(i=0,1,2,3,4) under mode A. The figure shows that when N<3, the secret master key is failed to be recovered in 48 hours. And for the cases where the HT is inserted in (25,0) and (25,4), the minimum value forNis 4, while for the cases (25,1), (25,2), and (25,3) the minimum value for N is 3. The figure also clearly shows the distributions corresponding to the case (25,3) having a lower average compared to the other. Thus the optimal location for inserting the HT is (25,3) and the corresponding average solving time when N=3 is t0=12572.26 seconds (≈3.49 hours).Figure 9
The results of the cases where the HT is inserted inX25,i under mode A.


## 7.2.3. Success Rate of the Attack

To evaluate the success rate of the attack under mode A where the HT is inserted in the optimal location determined in Section7.2.2, 100 instances are tested with different (P,MK). Figure 10 shows the success rate of the attack. It can be seen that whenN is lower than 3, the success rate of the attack remains 0%. OnceN is greater than or equal to 3, asN taken grows, the success rate of the attack increases. And the success rate of the attack can reach 100% by increasingN to 7. It can be also seen in the lower part of Figure 10 that whenNis equal to 3, only 4 instances fail to recover the secret master key in 48 hours; thus the success rate of the attack is 96%.Figure 10
Success rate of the attack.


## 8. Conclusions

In this paper, analgebraic fault analysis(AFA), relying on the stealthy hardware Trojan, against HIGHT cipher has been proposed. To facilitate a bit-level AFA of HIGHT, a FSM-based stealthy HT is designed with an extremely low activation rate of around 0.000025. The optimal location for inserting the HT is determined by AFA in advance. Experiments report a 1.63% additional cost in flip-flops for the HT implemented on a 65 nm Virtex-5 FPGA. As for HIGHT implementation, a single-bit flip on the most significant bit of X25,3 when the HT is activated requires only 3 injections to recover the secret master key with a success rate of 96%. In this paper, we showed that even with very limited number of faults from a lightweight Trojan, modern cryptographies are still vulnerable against algebraic attacks. This work certified the severity of the lightweight HT for the security-critical ciphers in ICs, and hence extensive security investigations must be devoted throughout the entire design and manufacture process of the security chips.In the future work, we aim at explore effective solutions to detect the stealthy Trojan injected inside the cryptographic circuits.



---

*Source: 8051728-2017-12-20.xml*