Truncated Differential-Neural Key Recovery Attacks on Round-Reduced HIGHT

Abstract

Recently, differential-neural cryptanalysis, which integrates deep learning with differential cryptanalysis, has emerged as a powerful and practical cryptanalysis method. It has been particularly applied to lightweight block ciphers, which are characterized by simple structures and operations, and relatively small block and key sizes. In resource-constrained environments, such as Internet of Things (IoT), it is essential to verify the resistance of existing lightweight block ciphers against differential-neural cryptanalysis to ensure security. In differential-neural cryptanalysis, a deep learning model, known as a neural distinguisher, is trained to differentiate a target cipher from others, facilitating key recovery through statistical analysis. For successful differential-neural cryptanalysis, it is crucial to develop a highly accurate neural distinguisher and to optimize the key recovery attack algorithm. In this paper, we introduce a novel neural distinguisher and key recovery attack against the 15-round reduced HIGHT cipher. Our proposed neural distinguisher is capable of distinguishing HIGHT ciphertext by analyzing only a portion of the ciphertext, which we refer to as a truncated neural distinguisher. Notably, our experiments demonstrate that the truncated neural distinguisher achieves performance comparable to existing distinguishers trained on entire ciphertext blocks, while enabling a more efficient key recovery attack through a divide-and-conquer strategy. Furthermore, we observe a significant improvement in key recovery efficiency compared to traditional cryptanalysis methods.

1. Introduction

Deep learning has shown excellent outcomes in various fields such as object detection [1,2], natural language processing [3], and the decisions of trained models, which are quite correct (with accuracies of greater than 90%). In the field of cryptography, machine learning has been applied to cryptanalysis for decades, with most of the focus on side-channel attacks [4,5,6]. Recently, there have been attempts to apply deep learning techniques to the field of cryptanalysis, which focuses on analyzing the security of cryptographic algorithms. Notably, at CRYPTO ’19, A. Gohr [7] was the first to introduce differential-neural cryptanalysis, a novel approach that combines deep learning with the traditional cryptanalysis technique of differential cryptanalysis [8]. In differential-neural cryptanalysis, a dataset of ciphertext pairs, generated based on specific differential characteristics, is used to train a deep learning model. This trained model, known as a neural distinguisher, is capable of distinguishing whether the input ciphertext satisfies the learned differential characteristics. Through statistical analysis of the neural distinguisher’s results, A. Gohr successfully conducted a key recovery attack on 11-round SPECK-32/64, demonstrating that this approach was more efficient than traditional differential cryptanalysis. Following this development, differential-neural cryptanalysis has garnered significant attention in the field of cryptanalysis, leading to continuous research efforts, including improvements in neural distinguishers [9,10,11,12,13,14], key recovery attacks [15,16], and extensions to other block ciphers [17,18,19].

Meanwhile, lightweight block ciphers are being actively developed and standardized (including PRESENT [20], LEA [21], HIGHT [22], CLEFIA [23], and SPECK/SIMON [24]) as a key security technology for providing confidentiality in resource-constrained environments, such as IoT. Lightweight block ciphers are designed with simpler structures and operations, as well as smaller block and key sizes compared to general block ciphers, to ensure efficiency. While these characteristics offer advantages in terms of implementation and processing, they also make lightweight block ciphers susceptible to differential-neural cryptanalysis due to their simplicity. Since most lightweight block ciphers were not designed with resistance to deep learning-based attacks in mind, it is essential to conduct security evaluations against such threats to ensure their safe operation. In this regard, we conduct differential-neural cryptanalysis on the standard lightweight block cipher HIGHT, which was proposed at CHES 2005.

HIGHT, our target cipher, is one of the most representative Addition-Rotation-XOR(ARX)-based lightweight block ciphers. It is included to the open source cryptographic library CRYPTO++ [25], which is used world-widely. The security of HIGHT has been analyzed theoretically through various cryptanalytic methods [22,26,27,28]. However, these research results are all about theoretical security, and it is difficult to apply from a practical perspective. Additionally, although research on differential-neural cryptanalysis exists, including the 14-round neural distinguisher study by D. Pal et al. [29], its practical application to key recovery attacks has not yet been conducted (a more detailed explanation of this work can be found in Section 2.3). Therefore, in this paper, we develop an improved neural distinguisher and, based on this, propose a new neural key recovery attack algorithm against the 15-round reduced HIGHT. The contributions of this paper can be summarized as follows:

• We present a truncated neural distinguisher that learns only a part of the HIGHT block to distinguish real ciphertexts from others. The truncated neural distinguisher showed the same accuracy as the neural distinguisher, which learned the full ciphertext block of HIGHT. This means that full block information is not necessary to train neural distinguisher. To the best of our knowledge, this type of neural distinguisher was presented for the first time in this paper. The approach for making a truncated neural distinguisher is not dedicated to HIGHT, so it can be extended to various block ciphers (especially, we expect that it is effective against generalized Feistel-based ciphers).
• The results of our key recovery attack are the first differential-neural cryptanalysis-based key recovery attack on HIGHT, and show improved efficiency compared to the traditional differential key recovery attack.

The remainder of this paper is organized as follows. Section 2 provides the preliminaries for understanding our proposed attack, including a brief description of HIGHT and A. Gohr’s differential-neural cryptanalysis. Section 3 presents our approaches to make neural distinguishers of HIGHT. Section 4 presents a new key recovery attack on 15-round HIGHT based on our truncated neural distinguisher and experiment results. In Section 5, we discuss the resistance of HIGHT to differential-neural cryptanalysis based on the results of this paper, as well as future directions. Finally, we conclude this paper and draw the future directions in Section 6.

2. Preliminaries

2.1. A Brief Description of Lightweight Block Cipher HIGHT

HIGHT is an ARX-based lightweight block cipher designed to use only modular addition, XOR, and rotation operations, making it efficiently implementable in resource-constrained computing environments such as Radio-Frequency Identification (RFID) and Ubiquitous Sensor Network (USN). The overall structure is based on a generalized Feistel network [30]. The block size of HIGHT is 64 bits, and the key size is 128 bits. The plaintext P and ciphertext C is treated as a concatenation of bytes such as $P=P_7\Vert \dots \Vert P_1\Vert P_0$ and $C=C_7\Vert C_6\Vert \dots \Vert C_1\Vert C_0$. Similarly, the master key is denoted as $\mathit{MK}={\mathit{MK}}_{16}\Vert {\mathit{MK}}_{15}\Vert \dots \Vert {\mathit{MK}}_1\Vert$${\mathit{MK}}_0$. In addition, the operations are performed on a byte-level, specifically utilizing a modular addition in $2^8$ (denoted as ⊞), XOR (denoted as ⊕), and 8-bit left rotation (denoted as ⋘).

The encryption process consists of three procedures including Initial Transformation, Round Function, and Final Transformation. In here, the whitening key $\mathit{WK}$ and subkey $\mathit{SK}$, which are derived from $\mathit{MK}$ using the key schedule (Algorithm 1). Let the i-th round internal state in encryption process be $X_i=X_{i,7}\Vert X_{i,6}\Vert \dots \Vert X_{i,1}\Vert X_{i,0}$. The initial and final transformations are performed once at the beginning and finish, respectively. The round function, which is shown in Figure 1, is performed 32 times. Here, $F_0$ and $F_1$ are defined as follows:

$$\begin{array}{c}\hfill F_0\left(x\right)=x^{⋘1}\oplus x^{⋘2}\oplus x^{⋘7},\\ \hfill F_1\left(x\right)=x^{⋘3}\oplus x^{⋘4}\oplus x^{⋘6}.\end{array}$$

(1)

Algorithm 2 specifies the overall process of HIGHT encryption. In addition, the decryption process uses a modular subtraction in $2^8$⊟ instead of ⊞, and performs the encryption process in the opposite direction using the reverse order of $\mathit{WK}$ and $\mathit{SK}$.

Algorithm 1 Key Schedule of HIGHT

KeySchedule$\left(\mathit{MK}\right)$ {     // Whitening Key Generation     For $i=0$ to 7 {        If $0\le i\le 3$, then ${\mathit{WK}}_{\mathit{i}}\leftarrow {\mathit{MK}}_{\mathit{i}+\mathit{12}}$;        Else, ${\mathit{WK}}_i\leftarrow {\mathit{MK}}_{i-4}$;     }     // Constant Generation ($\delta$)     $s_0\leftarrow 0_2$; $s_1\leftarrow 1_2$; $s_2\leftarrow 0_2$; $s_3\leftarrow 1_2$; $s_4\leftarrow 1_2$;     $s_5\leftarrow 0_2$; $s_6\leftarrow 1_2$;     ${\delta }_0\leftarrow s_6\left|\right|s_5\left|\right|s_4\left|\right|s_3\left|\right|s_2\left|\right|s_1\left|\right|s_0$;     For $i=0$ to 127 {        $s_{i+6}\leftarrow s_{i+2}\oplus s_{i-1}$;        ${\delta }_i\leftarrow s_6\left|\right|s_5\left|\right|s_4\left|\right|s_3\left|\right|s_2\left|\right|s_1\left|\right|s_0$;     }     // Subkey Generation     For $i=0$ to 7 {        For $j=0$ to 7 {             ${\mathit{SK}}_{16i+j}\leftarrow {\mathit{MK}}_{j-imod8}⊞{\delta }_{16i+j}$;        }        For $j=0$ to 7 {             ${\mathit{SK}}_{16i+j+8}\leftarrow {\mathit{MK}}_{(j-imod8)+8}⊞{\delta }_{16i+j+8}$;        }     }     return $\mathit{WK},\mathit{SK}$ }

Algorithm 2 Encryption of HIGHT

HightEncryption$(P,\mathit{WK},\mathit{SK})$ {    // Initial Transformation    $X_{0,0}\leftarrow P_0⊞{\mathit{WK}}_0$; $X_{0,1}\leftarrow P_1$;    $X_{0,2}\leftarrow P_2\oplus {\mathit{WK}}_1$; $X_{0,3}\leftarrow P_3$;    $X_{0,4}\leftarrow P_4⊞{\mathit{WK}}_2$; $X_{0,5}\leftarrow P_5$;    $X_{0,6}\leftarrow P_6\oplus {\mathit{WK}}_3$; $X_{0,7}\leftarrow P_7$;    // Round Function    For $i=0$ to 31 {       $X_{i+1,1}\leftarrow X_{i,0}$; $X_{i+1,3}\leftarrow X_{i,2}$;       $X_{i+1,5}\leftarrow X_{i,4}$; $X_{i+1,7}\leftarrow X_{i,6}$;       $X_{i+1,0}\leftarrow X_{i,7}\oplus (F_0\left(X_{i,6}\right)⊞{\mathit{SK}}_{4i+3})$;       $X_{i+1,2}\leftarrow X_{i,1}⊞(F_1\left(X_{i,0}\right)\oplus {\mathit{SK}}_{4i+2})$;       $X_{i+1,4}\leftarrow X_{i,3}\oplus (F_0\left(X_{i,2}\right)⊞{\mathit{SK}}_{4i+2})$;       $X_{i+1,6}\leftarrow X_{i,5}⊞(F_1\left(X_{i,4}\right)\oplus {\mathit{SK}}_{4i+1})$;    }    // Final Transformation    $C_0\leftarrow X_{32,1}⊞{\mathit{WK}}_4$; $C_1\leftarrow X_{32,2}$;    $C_2\leftarrow X_{32,3}\oplus {\mathit{WK}}_5$; $C_3\leftarrow X_{32,4}$;    $C_4\leftarrow X_{32,5}⊞{\mathit{WK}}_6$; $C_5\leftarrow X_{32,6}$;    $C_6\leftarrow X_{32,7}\oplus {\mathit{WK}}_7$; $C_7\leftarrow X_{32,0}$;    return C }

2.2. Neural Distinguisher and Its Utilization for Key Recovery Attack

A neural distinguisher [7] is a trained deep learning model for distinguishing the real ciphertexts from the random ciphertexts. Let the plaintext pair be represented as $(P,P^{\prime })$, the ciphertext pair as $(C,C^{\prime })$, and the block cipher encryption function with a secret key be represented as $E_K$, where K is a secret key. The real ciphertext pair refers to a ciphertext pair $(C=E_K\left(P\right),C^{\prime }=E_K\left(P^{\prime }\right))$, corresponding to the plaintext pair $P\oplus P^{\prime }=\alpha$. In the case of real ciphertext pairs, it is labeled as $label=1$, whereas it is labeled as $label=0$ in the case of random ciphertext pairs. The dataset composed of real and random ciphertext pairs can be expressed as follows:

$$\left\{\begin{array}{c}(C,C^{\prime },label=1),\mathrm{if}P\oplus P^{\prime }=\alpha \hfill \\ (C,C^{\prime },label=0),\mathrm{if}P\oplus P^{\prime }\ne \alpha \hfill \end{array}\right.$$

(2)

Then, the problem that the neural distinguisher has to solve from the ciphertext dataset is a binary classification problem of classifying whether the input ciphertext $(C,C^{\prime })$ has a label of 1 or 0. This can be thought of as learning multiple differentials of the output differences propagated from the input difference $\alpha$, in the perspective of cryptanalysis, to distinguish between real ciphertext pairs and random ciphertext pairs. In A. Gohr’s work, the strategy for choosing the input difference is that the input difference has a small hamming weight and has a differential trail with a high probability. In this regard, $\alpha$ was set 0x0040/0000, which is a three-round characteristic of nine-round differential characteristic for SPECK-32/64 [31].

The neural distinguisher’s structure was composed of a residual network preceded by a single bit-sliced convolution and followed by a densely connected prediction head. The size of input channels was set to maintain the word size of target cipher (note that the word size of SPECK-32/64 is 16 bits). The dataset was composed ${10}^7$ samples, and the last ${10}^6$ samples were used for validation. The epochs for training was set 200, and optimization was performed against mean square error loss with an L2 weight regularization using the Adam optimizer. In addition, a cyclic learning rate scheduler was used. The detailed descriptions of the structure and training pipeline of the neural distinguisher are shown in Sections 4.2 and 4.3 in [7]. Following this training pipeline, A. Gohr could obtain five-, six-, seven-, and eight-round neural distinguishers for SPECK-32/64.

Table 1. Accuracy of A. Gohr’s SPECK-32/64 neural distinguisher.

Rounds	Distinguisher	Accuracy	TPR 1	TNR 2
5	Neural Distinguisher	0.929	0.904	0.954
5	Differential Distinguisher	0.911	0.877	0.947
6	Neural Distinguisher	0.788	0.724	0.853
6	Differential Distinguisher	0.758	0.680	0.837
7	Neural Distinguisher	0.616	0.533	0.699
7	Differential Distinguisher	0.591	0.543	0.640
8	Neural Distinguisher	0.514	0.519	0.508
8	Differential Distinguisher	0.512	0.496	0.527

¹ True positive rate. ² True negative rate.

shows the accuracy of the trained neural distinguishers. Here, the accuracy is calculated by comparing the classification results and labels. The classification is performed through the response of the neural distinguisher Z, and the input ciphertext pair is classified as the real case if $Z>0.5$.

Then, the response of the neural distinguisher trained in this manner is utilized to recover the subkey. As shown in Figure 2, the idea of key recovery is that when the neural distinguisher was trained for n-round, we prepare $(n+1)$-round ciphertexts, partially decrypt one round, denoted as $D_K$ using the key K, and then check the response of the neural distinguisher against the partially decrypted ciphertexts. Let the $(n+1)$-round ciphertext pair be denoted as $(C_i,C_i^{\prime })$, where $i=0,\dots ,t-1$ and t is total number of ciphertext pairs. The response of the neural distinguisher for the i-th ciphertext pair is represented as $Z_i^k$, where k is the key which is used for partial decryption. It represents the likelihood $Pr\left(real\right|(D_k\left(C_i\right),D_k\left(C_i^{\prime }\right)))$ of each input data following the real ciphertext pair distribution. The input data are classified as the real ciphertext if $Z_i^k>0.5$. This likelihood $Z_i^k$ can be transformed the key-dependent score $v_k$ to utilize from the recovery perspective through the following formula:

$$v_k:=\sum _{i=1}^t{log}_2(Z_i^k/(1-Z_i^k))$$

(3)

where $v_k$ is a summed result of logarithms of real vs. random likelihood ratio. Therefore, this will be the larger value when the larger response of the neural distinguisher is classified as real cases for each partial decryption. As a result, if the guessed key is the right key, more real cases will appear than the wrong key, so we can identify the right key by performing key ranking according to $v_k$.

2.3. Existing Works Related to Neural Distinguisher

After A. Gohr’s differential neural cryptanalysis, A. Benamira et al. [10] presented research results on the interpretation of the features learned by the neural distinguisher and the accuracy of the neural distinguisher at EUROCRYPT 2021. Here, it was experimentally confirmed that the features learned by A. Gohr’s neural distinguisher could be interpreted as intermediate round truncated differential characteristics from a cryptanalysis perspective. Additionally, it was confirmed that the initial convolution operation in the neural distinguisher’s internal layer converts the input ciphertext data into a form that can represent the difference. Specifically, when a 64-bit ciphertext pair $(C,C^{\prime })$ is expressed as word units $(C_l,C_r,C^{\prime }l,C^{\prime }r)$, through the initial convolution, the input ciphertext pair data are transformed into $(\Delta L,\Delta V,V_0,V_1)$, where $\Delta L=C_l\oplus C_r$, $\Delta V=V_0\oplus V_1$, $V_0=C_l\oplus C_r$, $V_1=C_l^{\prime }\oplus C_r^{\prime }$.

In D. Pal et al. [29], a neural distinguisher study was conducted on the HIGHT cipher targeted in this paper. In this study, the seven-round characteristic 0x0080000000000000 of HIGHT differential characteristic, proposed by J. Yin et al. [26], was set as the input difference to generate the ciphertext pairs $(C,C^{\prime })$. Additionally, the difference $C\oplus C^{\prime }$ of the ciphertext pairs was concatenated to form a 192-bit dataset (i.e., $(C,C^{\prime },C\oplus C^{\prime })$) and used for training. As a result, an eight-round neural distinguisher with 98% accuracy was obtained, and a fourteen-round neural distinguisher was constructed by prepending a six-round differential characteristic (0x80008AC28A01A0 → 0x0080000000000000) with a probability of $2^{30}$. The HIGHT neural distinguisher constructed in our study selects the input difference from the 13-round characteristic of [32], similar to the D. Pal’s HIGHT neural distinguisher, but there are differences in the input difference setting value and the dataset format. In addition, our neural distinguisher works for 15 rounds (not 14 rounds) using the partial difference of 15-round ciphertext pairs.

3. HIGHT Neural Distinguishers

3.1. Approach for Making HIGHT Neural Distinguisher

In this study, we focused on designing efficiently to create and utilize the neural distinguisher. The main idea for constructing a neural distinguisher for this purpose is to create a neural distinguisher that depends on a partial key $k^{\prime }\subset k$. As explained in Section 2.2, when utilizing a neural distinguisher from a key recovery perspective, the response $Z_i^k$ of an n-round neural distinguisher is transformed into $v_k$, making it dependent on the $(n+1)$-round encryption key k. While finding round keys is more efficient than directly recovering the master key, the search space for keys increases exponentially as the size of the round keys grows, making this approach a significant burden. However, by using a divide-and-conquer method to first guess $k^{\prime }$ instead of k, and then guess the remaining key bits, the exponential complexity of key guessing can be improved.

To construct a neural distinguisher that is dependent on a partial key $k^{\prime }$, instead of using the entire ciphertext as input data for the neural distinguisher, we developed a new method to distinguish between real and random inputs by training on information based on partial ciphertexts. In detail, we constructed the input of the neural distinguisher using the difference for $(X_{i+1,6},X_{i+1,5},X_{i+1,2},X_{i+1,1})$ in the output word of the i-th round HIGHT round function. Since the neural distinguisher trained on this dataset uses only partial information of the ciphertext, it does not care about any information on $(X_{i+1,7},X_{i+1,4},X_{i+1,3},X_{i+1,0})$. In addition, it means that the neural distinguisher focuses only on the difference rather than the output distribution. In other words, our intention is to train the neural distinguisher to propagate the multiple truncated differential characteristic $(\Delta X_{i+1,6},\Delta X_{i+1,5},\Delta X_{i+1,2},\Delta X_{i+1,1})$ from the input difference ${\Delta }_{in}$ in terms of the differential characteristic. Accordingly, we named the neural distinguisher constructed based on this approach as a truncated neural distinguisher. Figure 3 shows an overview of the proposed truncated neural distinguisher. The detailed descriptions and rationale of the proposed neural distinguisher are in the following subsection.

3.2. Rationale of Our Neural Distinguisher

The basic design rationales of the proposed neural distinguisher, including the input difference setting and neural network structure, are similar to A. Gohr’s neural distinguisher design principles. The input difference was set to the 6-round characteristic 0x0000010000000000 of the 13-round differential characteristic (

Table 2. Differential characteristics for 13-round HIGHT [32].

Rounds	Characteristic	${\mathit{log}}_{\mathbf{2}}\mathit{p}$
0	0x01004483E20084F2	-
1	0x000083E20080F201	−3
2	0x0000E2C1804A0100	−9
3	0x0000C1184A010000	−6
4	0x000018C801000000	−6
5	0x0000C80100000000	−4
6	0x0000010000000000	−3
7	0x0001000000000000	−1
8	0x0100000000000082	−2
9	0x00000000009C8201	−3
10	0x000000039C7A0100	−8
11	0x00E803BC7A010000	−5
12	0xE800BCF801000002	−6
13	0x00B6F80100B002E8	−5
-	$\Sigma {log}_{2}p$	−61

) proposed by E. Bagherzadeeh and Z. Ahmadian [32]. The input difference is propagated with a probability of 1/2, and has a Hamming weight of 1, which is consistent with the HIGHT neural distinguisher proposed by D. Pal et al. The neural network structure is composed of a residual network with a depth of 1, and it is designed to maintain the word unit (8-bit) of HIGHT internally. However, through the following analysis, the proposed neural distinguisher is designed to use only partial information of the ciphertext.

The design of the proposed neural distinguisher to operate in a truncated manner was based on the observation of input conversion in A. Benamira et al.’s neural distinguisher construction method, which was described in Section 2.3. A. Benamira et al. transformed input data to $(\Delta L,\Delta V,V_0,V_1)$ from the ciphertext pairs $(C_l,C_r,C_l^{\prime },C_r^{\prime })$ to improve the accuracy of the neural distinguisher. When each element of the transformed form corresponds to the internal state of SPECK-32/64, it is related to the pre- and post-information of the non-linear operation, namely modular addition. Based on this, we hypothesized that the neural distinguisher explores the pre- and post-difference characteristics of modular addition to learn the characteristics of non-linear operations during training. We performed a property analysis of modular addition in HIGHT based on this conjecture.

Considering the i-round HIGHT round function, we can see that values prior to word rotation are two types of operation results. These two types have different characteristics from the XOR difference perspective of a ciphertext pair. To explain this, let us denote the left and right inputs of the internal operation as a and b, respectively, and the round key as $sk$. Also, let the Type-1 operation be denoted as $G:\{a,b,sk\}\to \{c,d\}$ and Type-2 operation as $H:\{a,b,sk\}\to \{c,d\}$. If we denote the function G as H, then they can be defined as follows:

$$\begin{array}{c}\hfill G(a,b,sk):=(c=(F_0\left(b\right)⊞sk)\oplus a,d=a),\\ \hfill H(a,b,sk):=(c=(F_1\left(b\right)\oplus sk)⊞a,d=a).\end{array}$$

(4)

If the XOR differences between the left and right words are $\alpha$ and $\beta$, respectively (i.e., $a\oplus a^{\prime }=\alpha$ and $b\oplus b^{\prime }=\beta$), since all operations except modular addition are linear operations with respect to XOR differences, then the differences are propagated as shown in Figure 4. The output XOR difference of the right word of G and H maintains the input difference as $\beta$. However, the left difference has a different property. First, in the case of G, the modular addition is performed with respect to the output of $F_0$ and $sk$, so the difference is probabilistically propagated. Here, if we denote the output difference of modular addition as $\gamma$, the output difference of the left word of G is $\alpha \oplus \gamma$. On the other hand, in the case of H, the round key addition is performed through XOR, so $F_0\left(\beta \right)$ is maintained with a probability of 1 (note that both $F_0$ and $F_1$ are linear operations from the XOR difference perspective because they are composed of rotation and XOR operations). Subsequently, the difference is probabilistically propagated through modular addition. Here, if we denote the output difference of modular addition as $\theta$, the output difference of the left word of H is $\theta$. The output difference of the left word for both G and H ($\alpha \oplus \gamma$ and $\theta$, respectively) is probabilistically propagated, but there is a different property on these output differences in whether they depend on the round key $sk$. While $\gamma$ in $\alpha \oplus \gamma$ varies depending on the value of $sk$, $\theta$ is independent of the value of $sk$. In other words, the output difference of G is affected by the round key, but that of H is not.

From the perspective of the neural distinguisher learning the characteristics of G and H, consider given data of ($\Delta c$, $\Delta d$) for neural distinguisher training. Based on the conjecture we built earlier, that the neural distinguisher learns the pre- and post-relationship of modular addition using ($\Delta c$, $\Delta d$), it is easier to learn H than G. For G, it consists of ($\Delta c=\alpha \oplus \gamma$, $\Delta \beta$). Here, the right word difference $\Delta \beta$ can be easily derived, as it is linearly related to one of the inputs of the modular addition, $F_0\left(\beta \right)$. However, the left word difference $\alpha \oplus \gamma$ that is masked from the value of $\gamma$, which itself varies probabilistically with the value of $sk$, is known only to the neural distinguisher. On the other hand, for H, it consists of ($\Delta c=\theta$, $\Delta d=\beta$). Here, $\beta$ can be easily derived from the input of the modular addition, $F_1\left(\beta \right)$, regardless of the value of $sk$. Furthermore, the left word difference $\theta$ is the output difference of the modular addition, allowing the neural distinguisher to focus on learning the non-linear operation. Based on these analysis results, we constructed two types of neural distinguishers: a Type-1 neural distinguisher that learns only the output of G, and a Type-2 neural distinguisher that learns only the output of H, denoted as $N{D}_{T1}$ and $N{D}_{T2}$, respectively. For $N{D}_{T1}$ and $N{D}_{T2}$, the dataset was sorted to the state before the word rotation of the round function to represent the output form of G and H, respectively. Accordingly, the dataset for $N{D}_{T1}$ consisted of $(C_{n,0},C_{n,7},C_{n,4},C_{n,3})$, and the dataset for $N{D}_{T2}$ consisted of $(C_{n,6},C_{n,5},C_{n,2},C_{n,1})$. We present a comparison of the two types of neural distinguishers in the following section.

3.3. Training Results

The training pipeline for $N{D}_{T1}$ and $N{D}_{T2}$ was constructed as follows. We generated ${10}^7$ pairs of HIGHT ciphertexts $(C,C^{\prime })$, satisfying the plaintext pair $(P,P^{\prime })$ with input difference ${\Delta }_{in}=$ 0x0000010000000000. The generated ciphertexts were preprocessed to transform them into the difference form corresponding to the input of each neural distinguisher. From the generated dataset, ${10}^6$ samples were used for validation, while the remaining samples were allocated for training. The batch size and optimization were configured the same as A. Gohr’s training pipeline (batch size: 5000, loss: MSE with L2 weights regularization, optimization: Adam, learning rate: cyclic learning rate scheduler). The training was performed for a total of 200 epochs.

The model was implemented using Tensorflow and the training environment was Intel Xeon Gold 6230R (26 Core/2.1 GHz) with a Geforce RTX 3090 and 64 GB RAM. Each neural distinguisher training took an average of 11,634.5 s (approximately 3.2 h) in our environment.

Table 3. Accuracy of various types of HIGHT neural distinguisher.

Round	Neural Distinguishers	Accuracy
6	$N{D}_{T2}$	100.00%
6	$N{D}_{T1}$	93.47%
7	$N{D}_{T2}$	93.00%
7	$N{D}_{T1}$	99.90%
8	$N{D}_{T2}$	93.43%
8	$N{D}_{T1}$	92.95%
9	$N{D}_{T2}$	82.18%
9	$N{D}_{T1}$	58.93%
10	$N{D}_{T2}$	50.07%
10	$N{D}_{T1}$	57.07%
11	$N{D}_{T2}$	50.05%
11	$N{D}_{T1}$	50.08%

shows the comparison of the training performance of the neural distinguishers. As a result of the training, while the neural distinguisher was able to distinguish the input ciphertext with an accuracy of over 90% from the sixth to the eighth rounds, a significant drop in accuracy was observed in the ninth round, with $N{D}_{T2}$ showing approximately 82% accuracy and $N{D}_{T1}$ showing about 59%. Furthermore, from the 10th round onwards, except for $N{D}_{T1}$, which had an accuracy of about 57%, the results dropped to around 50%, which is essentially meaningless when considering the binary classification problem that the neural distinguisher is designed to solve. When comparing the accuracy of $N{D}_{T1}$ and $N{D}_{T2}$ for rounds 6 to 9, where both types of neural distinguishers showed meaningful performance, $N{D}_{T2}$ consistently exhibited higher accuracy, except for the seventh round. In particular, in the ninth round, the accuracy difference between $N{D}_{T1}$ and $N{D}_{T2}$ was significant, with a gap of 23%. This supports our earlier conjecture that H is easier to learn than G.

Based on this analysis of the training results, we chose the nine-round $N{D}_{T2}$ as the most optimal option for designing a key recovery attack. The reason is that in key recovery attacks, which require repeated queries to the neural distinguisher, the closer the accuracy is to 50%, the less reliable the query results become. Therefore, selecting a neural distinguisher with significantly higher accuracy allows for a more efficient key recovery attack. Detailed explanations of the key recovery attack will be covered in the next section.

4. Key Recovery Attack Based on Truncated Neural Distinguisher

4.1. Overview of the Proposed Attack

In this section, we propose a HIGHT key recovery attack using the previously constructed nine-round $N{D}_{T2}$. In the attack described in this paper, HIGHT is reduced to 15 rounds, assuming the application of initial and final transformations. The goal is to recover ${\mathit{WK}}_4\left({\mathit{MK}}_0\right),{\mathit{WK}}_6\left({\mathit{MK}}_{\mathit{2}}\right)$ used in the final transformation. Figure 5 shows an overview of the proposed attack. We expanded the nine-round truncated neural distinguisher to a fifteen-round truncated neural distinguisher by prepending a six-round differential characteristic (${\Delta }_{initial}\to {\Delta }_{in}$) with a probability of $2^{-31}$ (here, ${\Delta }_{inital}=0\mathrm{x}01004483\mathrm{E}20084\mathrm{F}2$ and ${\Delta }_{in}=0\mathrm{x}0000010000000000$). The process of the key recovery attack based on the expanded truncated neural distinguisher is as follows:

• Prepare a set of chosen plaintext pairs $P_i=(p,p^{\prime })$ satisfying $p\oplus p^{\prime }={\Delta }_{initial}$, where $i=0,1,\dots ,c-1$ (this maintains ${\Delta }_{initial}$ with a probability of $2^{-8}$ after the initial transformation is performed).
• Obtain a set of corresponding ciphertext pairs $C_i=(c,c^{\prime })$ for the plaintext pairs $P_i$ based on the chosen plaintext attack scenario, where $i=0,1,\dots ,c-1$ (with a probability of $2^{-31}$ for satisfying the differential characteristic ${\Delta }_{initial}\to {\Delta }_{in}$ up to six rounds).
• For candidate keys $W{K}_4$ and $W{K}_6$, perform partial decryption (⊟) on ($C_5^i$, $C_4^i$, $C_1^i$, $C_0^i$) of ciphertext pairs C to obtain the differences of partial plaintext pairs ($\Delta X_6^i$, $\Delta X_5^i$, $\Delta X_2^i$, $\Delta X_1^i$) (note that we increase the index by 1 to account for the word rotation in the final transformation).
• Obtain the response of the 15-round truncated neural distinguisher $Z_{W{K}_4,W{K}_6}^i$ for the differences of partial plaintext pairs $(\Delta X_6^i,\Delta X_5^i,\Delta X_2^i,\Delta X_1^i)$.
• Convert the responses of the neural distinguisher to key scores by calculating $V_{W{K}_4,W{K}_6}$$={\sum }_{i=0}^{c-1}{Z}_{W{K}_4,W{K}_6}^i/(1-Z_{W{K}_4,W{K}_6}^i)$.
• Return the $W{K}_4$ and $W{K}_6$ corresponding to the highest key score.

4.2. Experiments and Evaluation

The experiments for the proposed attack were performed by assuming that ${\Delta }_{inital}\to {\Delta }_{in}$ holds with probability $2^{-8}\times 2^{-31}=2^{-39}$ for six rounds after the initial transformation, and recovering $W{K}_4$ and $W{K}_6$ of nine-round HIGHT with the final transformation applied. The experiments were conducted on the same Intel Xeon Gold 6230R (26 Core/2.1 GHz) with Geforce RTX 3090 environment as the training environment of the neural distinguisher, and were performed approximately 100 times. The number of selected plaintext pairs used in the attack was 8 (i.e., $c=2^3$). As a result, each attack took an average of 9 s (911.5 s for 100 trials). The success of the attack was measured by how similar the returned keys were to the real value of $W{K}_4$ and $W{K}_6$. The results showed that $W{K}_4$ and $W{K}_6$ had different recovery performances. Specifically, $W{K}_6$ was accurately recovered in about 39 out of 100 trials, and for the remaining cases, it was recovered with a Hamming distance of 2 from the real key. However, $W{K}_4$ was not accurately recovered in all of the trials, and a result with a Hamming distance of approximately 4 from the actual key was obtained. These results indicate that, although it is difficult to accurately recover against $W{K}_4$, it can recover $W{K}_6$ and effective key candidate reduction can be achieved with a small amount of data.

4.3. Complexity of the Proposed Attack

As the partial whitening keys could be recovered using eight chosen plaintext pairs in our experiment, the data complexity of the proposed attack for 15-round HIGHT is $2\times 2^3\times 2^{39}=2^{43}$, considering the prepending initial transformation and six-round differential characteristic. From a time complexity perspective, the proposed attack needs to perform key guessing for a total of $2^{16}$ cases of $W{K}_4$ and $W{K}_6$, each with $2^8$ cases. Additionally, partial decryption (⊟) and neural distinguisher queries must be performed for each ciphertext pair. Therefore, the time complexity is $2^{16}\times 2^{42}=2^{58}$ for partial decryption and neural distinguisher prediction times.

To compare the complexity of the proposed attack with that of traditional cryptanalysis methodologies, a brief explanation of previously known HIGHT cryptanalysis results is provided. The most representative attacks on full-round HIGHT are O. Özen et al. [33]’s related-key impossible differential attack and D. Hong et al. [28]’s biclique attack, both of which have theoretical time complexities exceeding $2^{125}$, making them impractical. Since the assumptions underlying the previously explained attacks differ from the proposed attack in this paper, direct comparisons are difficult. Therefore, we performed a comparison based on the complexity analysis of a traditional differential attack using the best differential characteristic presented in [32]. Following the traditional differential attack methodology in [34], constructing an attack by applying the 13-round differential characteristic with a probability of $2^{-61}$ (Table 2), the data complexity is $2\times 2^3\times 2^{61}=2^{65}$, and the time complexity is the sum of the partial decryption time for $W{K}_6$ and $W{K}_4$ guessing, which is $2^8\times 2^{64}+2^8\times 2^{64}=2^{73}$ partial decryption times. Compared to the traditional differential attack, the proposed attack is capable of targeting more rounds and demonstrates significantly better performance in terms of both data complexity and time complexity.

5. Discussion and Future Directions

In the previous section, we demonstrated that partial key recovery is possible based on the nine-round $N{D}_{T2}$ trained by targeting the H of HIGHT. In particular, the proposed attack was able to analyze more rounds more efficiently compared to traditional differential attacks. This suggests that by learning the partial output when constructing the neural distinguisher, more efficient differential-neural cryptanalysis can be achieved in the context of key recovery attacks. Furthermore, it overcomes the limitation where traditional differential cryptanalysis struggled to analyze beyond 13 rounds of HIGHT. However, the results of the proposed attack in this paper do not imply that the overall security of HIGHT is compromised. The version of HIGHT targeted in this paper can recover partial keys when reduced to 15 rounds, but the standardized HIGHT, which is used in resource-constrained environments such as IoT devices, operates with 32 rounds. To extend the key recovery attack to more rounds, constructing a truncated neural distinguisher with higher accuracy is essential. However, the truncated neural distinguisher with meaningful accuracy could only be constructed up to 10 rounds, and it did not show meaningful accuracy beyond 11 rounds (see Table 3). In the proposed attack we performed, the neural distinguisher was used by prepending a six-round differential characteristic, so the resistance of HIGHT against the proposed attack can be considered up to 16 rounds. However, if a key recovery attack is extended with a 16-round distinguisher, it is unlikely to be more efficient than a traditional differential attack, due to its low accuracy. Therefore, the practical resistance starts from 16 rounds. Consequently, full-round HIGHT currently holds sufficient security against differential-neural cryptanalysis, and the devices using HIGHT are considered secure. However, the results presented in this paper suggest that differential-neural cryptanalysis based on truncated neural distinguishers could provide improved analysis for HIGHT and similar ciphers that have been analyzed through traditional differential cryptanalysis, especially generalized Feistel-based block ciphers. For this reason, further research is needed to extend truncated neural distinguisher studies to other block ciphers with similar structures to HIGHT.

6. Conclusions

In this paper, we conducted differential-neural cryptanalysis on HIGHT, an international standard lightweight block cipher. Through analysis of the internal operation properties of the HIGHT round function, we proposed a new concept of neural distinguisher, named the truncated neural distinguisher, that can distinguish ciphertext using only partial words of the plaintext. From the perspective of utilization in key recovery attacks, the truncated neural distinguisher can perform partial decryption for specific words and allow for efficient key recovery by dividing and conquering the key search. In the experiment, the truncated neural distinguisher was built for a nine-round HIGHT. Using this truncated neural distinguisher, we performed partial whitening key recovery for a 15-round HIGHT by prepending a 6-round differential characteristic. The proposed key recovery attack showed significantly improved data and time complexity compared to traditional differential key recovery attacks. We expect that the proposed truncated neural distinguisher can be extended to various generalized Feistel-based block ciphers and plan to conduct future research in this regard.