Improved Cryptanalysis of an ISO Standard Lightweight Block Cipher with Refined MILP Modelling

Abstract

Differential and linear cryptanalysis are two of the most effective attacks on block ciphers. Searching for (near) optimal differential or linear trails is not only useful for the security evaluation of block ciphers against these attacks, but also indispensable to the cryptanalysts who want to attack a cipher with these techniques. In recent years, searching for trails automatically with Mixed-Integer Linear Programming (MILP) gets a lot of attention. At first, Mouha et al. translated the problem of counting the minimum number of differentially active S-boxes into an MILP problem for word-oriented block ciphers. Subsequently, in Asiacrypt 2014, Sun et al. extended Mouha et al.’s method, and presented a technique which can find actual differential or linear characteristics of a block cipher in both the single-key and related-key models. In this paper, we refine the constraints of the 2-XOR operation in order to reduce the overall number of variables and constraints. Experimental results show that MILP models with the refined constraints can be solved more efficiently. We apply our method to HIGHT (an ISO standard), and we find differential (covering 11 rounds) or linear trails (covering 10 rounds) with higher probability or correlation. Moreover, we find so far the longest differential and linear distinguishers of HIGHT.

1 Introduction

In recent years, with the rapid development of the Internet of Things (IoT), the application of micro computing equipment is more and more popular, such as RFID chips and wireless sensor networks. At the same time, how to ensure the security of information stored on or transmitted over such devices with constrained resources attracts more and more attention. Hence, the pursuit of efficient and secure lightweight block ciphers came into being. Researchers have put forward many lightweight block ciphers. Roughly speaking, those lightweight block cipher can be divided into two categories, one type based on small S-boxes, such as LBlock [1], PRESENT [2], SKINNY [3] and RECTANGLE [4]. Another type doesn’t use S-boxes. Instead, they adopt the ARX construction, where modular addition, rotation and XOR are used. These operations are easy to implement in software, such as HIGHT [5], TEA [6], SPECK [7], Sparx [8] etc.

Differential cryptanalysis [9] and linear cryptanalysis [10] are two main attacks on symmetric-key ciphers. For these attacks, finding an optimal differential or linear trails are important to make an effective attack. Among the methods proposed in the literature on finding optimal differential and linear characteristics, automatic searching is a very popular one, which is relatively easy to implement. Matsui’s branch and bound search algorithm is the classic methods for obtaining DES differential characteristics [11]. Recently, with the aim to raise the efficiency of it, Chen et al. proposed some variant methods [12, 13]. In CT-RSA 2014, Biryukov and Velichkov extended Matsui’s algorithm [14], they proposed a new automatic search tool to search for the differential characteristics of ARX ciphers by introducing the new concept of a partial difference distribution table (pDDT). In 2013, Mouha and Preneel proposed an automatic tool to search for the optimal differential characteristic for ARX ciphers Salsa20 [15], The main idea is to convert the problem of searching for differential characteristics to a Boolean satisfiability problem, which only involves writing out simple equations for every operation in the cipher, and applies an off-the-shelf SAT solver. In 2011, Mouha et al. translated the problem of counting the number of active S-boxes into an MILP problem which can be solved with MILP solvers [16]. Subsequently, In Asiacrypt 2014, Sun et al. extended Mouha et al.’s method, and presented methods for searching the differential or linear characteristics of bit-oriented block ciphers both the single-key and related-key models [17]. In FSE 2016, Fu et al. proposed an MILP-based tool for automatic search for differential and linear trails in ARX ciphers, through the properties of differential and linear characteristics for modular addition operation, and gave a systematic method to describe the differential and linear characteristics with some constraints [18]. In FSE 2017, automatic search was also conducted based on constraint programming, which was able to analyze ciphers with $8\times 8$ S-boxes [19].

HIGHT [5] was introduced by Hong et al. in CHES 2006, which is an ISO standard lightweight block cipher [20]. The designers gave the differential and linear attack results, and found some 11-round differential characteristics with probability $2^{-58}$ and several 10-round linear approximations with correlation $2^{-26}$.¹

In this paper, we improve Sun et al.’s method for automatic search differential and linear trails based on the MILP model. We accurately describe the 2-XOR operations with new constraints. The new constraints can reduce the overall number of variables and constraints in MILP model, which can save the time for solving the MILP model. Subsequently, we apply our refined MILP model to the lightweight block cipher HIGHT. As a result, we not only search the better differential characteristic for 11-round HIGHT and linear approximation for 10-round HIGHT, but also find the optimal differential characteristic for 13-round HIGHT and linear approximation for 11-round HIGHT. These results are shown in Table 1. (The p and cor in the table, represent the probability of differential characteristic and the correlation of linear approximation respectively)

Table 1. Summary of differential characteristics and linear approximations for HIGHT

Organization. This paper is organised as follows. In Sect. 2, we introduce the related knowledge, and give a brief description of the HIGHT. In Sect. 3, we give a brief introduction the automatic search method of differential and linear trails based on MILP model. In Sect. 4, a refined MILP model is presented. As an application, we utilize the refined MILP model to search the differential and linear characteristics for HIGHT. Then in Sect. 5, the results of differential and linear cryptanalysis of HIGHT are given. Finally, we conclude the paper in Sect. 6.

2 Preliminaries

In this section, we introduce some notations and terms, and briefly describe the lightweight block cipher HIGHT.

2.1 Notations

The following notations are used in this paper:

• $(X_{i}^{7}\Vert X_{i}^{6}\Vert \cdot \cdot \cdot \Vert X_{i}^{0})$: The 64-bit input of the i-th round is considered as concatenations of 8 bytes $X_{i}^{j}$, $0\le j \le 7$.

• $(SK_{4i+3}\Vert SK_{4i+2}\Vert SK_{4i+1}\Vert SK_{4i})$: The 32-bit subkey of the i-th round is considered as concatenations of 4 bytes $SK_{4i+j}$, $0\le j \le 3$.

• $\oplus$: Bitwise exclusive OR (XOR)

• $\boxplus$: Addition modulo $2^{n}$

• $x\lll s$: Rotation of x to the left by s positions

• $\varDelta x$: The XOR difference of $x_1$ and $x_2$, $x_1\oplus x_2=\varDelta x$

• x[i]: The bit at position i of word x

2.2 Description of HIGHT

The HIGHT [5] is a lightweight block cipher, it was proposed in CHES 2006, and was adopted as an ISO standard cryptography. The HIGHT utilize an 8-branch Type-II generalized Feistel structure, 64-bit block size and 128-bit key size, consisting of 32 rounds with four parallel Feistel functions in each round. The round function of HIGHT is shown in Fig. 1.²

Fig. 1.

The round function of HIGHT.

The round function transforms $(x_{i}^{7}||x_{i}^{6}||\cdots ||x_{i}^{0})$ into $(x_{i+1}^{7}||x_{i+1}^{6}||\cdots ||x_{i+1}^{0})$ as follows:

$$\begin{aligned}{\begin{array}{c} x_{i+1}^{1}=x_{i}^{0}; x_{i+1}^{3}=x_{i}^{2}; x_{i+1}^{5}=x_{i}^{4}; x_{i+1}^{7}=x_{i}^{6};\\ x_{i+1}^{0}=x_{i}^{7}\oplus ({{F}_{0}}(x_{i}^{6})\boxplus S{{K}_{4i+3}});\\ x_{i+1}^{2}=x_{i}^{1}\boxplus ({{F}_{1}}(x_{i}^{0})\oplus S{{K}_{4i+2}});\\ x_{i+1}^{4}=x_{i}^{3}\oplus ({{F}_{0}}(x_{i}^{2})\boxplus S{{K}_{4i+1}});\\ x_{i+1}^{6}=x_{i}^{5}\boxplus ({{F}_{1}}(x_{i}^{4})\boxplus S{{K}_{4i}}). \end{array}} \end{aligned}$$

The $F_{0}$ and $F_1$ used in the round function are defined as follows:

$$\begin{aligned} F_{0}(x)&=(x<<<1)\oplus (x<<<2)\oplus (x<<<7);\\ F_{1}(x)&=(x<<<3)\oplus (x<<<4)\oplus (x<<<6). \end{aligned}$$

The inner functions $F_{0}$ and $F_1$ provide bitwise diffusion. These functions can be regarded as linear transformations from $GF(2)^{8}$ to $GF(2)^{8}$. The two linear transformations selected in the design of the cipher have the best diffusion property.

In this paper, we only consider the single-key model. Therefore, we omit key schedule in this paper. For further details, please refer to [5].

2.3 Security Analysis Results of HIGHT

Since the HIGHT has been put forward, it has received a great deal of attention. At present, there are many cryptanalysis results of HIGHT, which also includes some cryptanalysis results given by the designer.

In [5], the designer gives the differential characteristic probability is $2^{-58}$ for the 11-round HIGHT, and gave the 13-round HIGHT differential attack result. At the same time, find the 10-round linear approximation with bias ${\varepsilon ={2}^{-27}}$. By using the linear approximation, the designer proposed 13-round linear attack for HIGHT, in the attack process, it requires $2^{57}$ plaintexts with the success rate 96.7$\%$ to recover 36 bits of the subkeys. In addition, the designer use this 14-round impossible differential characteristic to attack 18-round HIGHT. This attack requires $2^{46.8}$ chosen-plaintexts and $2^{109.2}$ encryptions of 18-round HIGHT. Except for some of the above attacks, the designer also presented truncated differential cryptanalysis [21], boomerang attack [22], sliding attack [23] and related key attack [24] and so on. These results indicate that the HIGHT has sufficient security.

Lu et al. [25] gave the first impossible differential cryptanalysis result for 25-round HIGHT, this attack requires ${{2}^{60}}$ chosen-plaintexts and ${{2}^{126.78}}$ encryptions. At ACISP 2009, Özen et al. [26] applied the impossible differential technique to attack 26-round HIGHT with data complexity of ${{2}^{61}}$ plaintexts, and time complexity of about ${{2}^{119.53}}$ encryptions. Then, At AFRICACRYPT 2012, Chen et al. [27] presented the impossible differential attack on the 27-round HIGHT with data complexity of ${{2}^{58}}$, and time complexity of about ${{2}^{126.6}}$ encryptions, which is smaller than exhaustive search. In 2016, Cui et al. [28] proposed MILP-based automatic tool to search all cases of 17-round impossible differentials that both hamming weights of input and output differences are one, They found 4 impossible differentials for 17-round HIGHT, which are the longest ones until now.

At ICISC 2010, Koo et al. [29] presented the first attack on the full HIGHT using related-key rectangle attack with $2^{123.169}$ encryptions, $2^{57.84}$ data, and 4 related keys.

In 2015, Igarashi et al. [30] gave 19-round HIGTH using meet-in-the-middle attack with Splice-and-Cut technique, the attacked with $2^{8}$ bytes of memory, $2^{8}+2$ pairs of chosen plain and cipher texts, and $2^{120.7}$ times of the encryption operation.

3 MILP-Based Automatic Search for Differential and Linear Trails

In this section, we first introduce the mixed integer linear programming problem, Then we briefly describe the method of constructing constraint inequalities for every operation in the ARX ciphers.

3.1 Mixed Integer Linear Programming (MILP)

MILP: Assume $A\in R^{m\times n}$, $b\in R^{m}$ and $c_{1}$, $c_{2}$, $\cdot \cdot \cdot$, $c_{n}\in R^{n}$, find a vector $x=(x_{1},x_{2}$, $\cdot \cdot \cdot$, $x_{n})$, such that the linear function $c_{1}x_{1}+c_{2}x_{2}+\cdot \cdot \cdot +c_{n}x_{n}$ is minimized (or maximized) with respect to the linear constraint $Ax\le b$.

The MILP problem is a kind of optimization problem, which aims at finding the optimal solution of the objective function under the constraints. This problem can be solved by a lot of commercial software, such as Gurobi [31], CPLEX [32], MAGMA [33], etc.

3.2 Differential Constraints for Different Operations

Suppose an ARX cipher is composed of the following three operations:

• Rotations

• XOR

• Modular addition

It is obvious that the differential constraint of rotations operation can be obtained, according to [17], the constraints on the XOR operation as follows.

Constraints for XOR Operation [17]. According to Sun et al.’s differential automatic search method. For XOR operation with input differences $\varDelta a$, $\varDelta b$ and output difference $\varDelta c$, the constraints are presented as follows:

$$\begin{aligned} {\left\{ \begin{array}{ll} \varDelta a+\varDelta b+\varDelta c\ge 2d_{\oplus } \\ d_{\oplus }\ge \varDelta a,d_{\oplus }\ge \varDelta b,d_{\oplus }\ge \varDelta c\\ \varDelta a+\varDelta b+\varDelta c\le 2 \end{array}\right. } \end{aligned}$$

(1)

where $d_{\oplus }$ is a dummy variable.

Constraints for Modular Addition Operation [18]. Assume $\alpha$, $\beta$ and $\gamma$ be n-bit XOR differences, $\alpha$, $\beta$ are the input differences for modular addition operation, and $\gamma$ is the output difference. In [18], if $i=0$, $\alpha [i]\oplus \beta [i]=\gamma [i]$, the constraints are shown in formula (1), if $i\in [1,n-1]$, Fu et al. proposed 13 inequalities in formula (2) to express it.

$$\begin{aligned} {\left\{ \begin{array}{ll} \beta [i]-\gamma [i]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ \alpha [i]-\beta [i]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ -\alpha [i]+\gamma [i]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ -\alpha [i]-\beta [i]-\gamma [i]-T(\alpha [i],\beta [i],\gamma [i])\ge -3 \\ \alpha [i]+\beta [i]+\gamma [i]-T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ -\beta [i]+\alpha [i+1]+\beta [i+1]+\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ \beta [i]+\alpha [i+1]-\beta [i+1]+\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ \beta [i]-\alpha [i+1]+\beta [i+1]+\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ \beta [i]+\alpha [i+1]+\beta [i+1]-\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge 0 \\ \gamma [i]-\alpha [i+1]-\beta [i+1]-\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge -2 \\ -\beta [i]+\alpha [i+1]-\beta [i+1]-\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge -2 \\ -\beta [i]-\alpha [i+1]+\beta [i+1]-\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge -2 \\ -\beta [i]-\alpha [i+1]-\beta [i+1]+\gamma [i+1]+T(\alpha [i],\beta [i],\gamma [i])\ge -2 \end{array}\right. } \end{aligned}$$

(2)

When $\alpha [i]=\beta [i]=\gamma [i]$, $T(\alpha [i],\beta [i],\gamma [i])=1$; otherwise, $T(\alpha [i],\beta [i],\gamma [i])=0$. the differential probability $xdp^{+}$ is calculated as follows:

$xdp^{+}=2^{-\sum _{i=0}^{n-2} T(\alpha [i],\beta [i],\gamma [i])}$

Fu et al. set the objective function for r-round differential MILP model as the $\sum _{j=0}^r \sum _{i=0}^{n-2} {T(\alpha [i],\beta [i],\gamma [i])}$.

3.3 Linear Constraints for Different Operations

In order to automatically search the linear trial of HIGHT, we must consider the propagation of the linear masks. Notice that the rotations is a simple bit permutation, we can give the corresponding linear constraints. Next, the constraints for the following operations can be given.

• XOR

• Branching

• Modular addition

Constraints for XOR Operation [34]. For XOR operation with input masks a, b and output mask c, include the following constraints:

$$\begin{aligned} a=b=c \end{aligned}$$

Constraints for Branching Operation [34]. For branching operation with input mask a and output masks b, c, include the following constraints:

$$\begin{aligned} a\oplus b\oplus c=0 \end{aligned}$$

Constraints for Modular Addition Operation [18]. Let modular addition operation with input masks $\wedge _{\alpha },\wedge _{\beta }\in F_{2}^{n}$ and output mask $\varGamma \in F_{2}^{n}$. and $\wedge _{\alpha }=(\wedge _{\alpha }[n-1],\cdot \cdot \cdot ,\wedge _{\alpha }[0])$, $\wedge _{\beta }=(\wedge _{\beta }[n-1],\cdot \cdot \cdot ,\wedge _{\beta }[0])$, $\varGamma =(\varGamma [n-1],\cdot \cdot \cdot ,\varGamma [0])$. In [18], Fu et al. utilize 8 linear inequalities to describe the possible transitions, as shown in formula (3).

$$\begin{aligned} {\left\{ \begin{array}{ll} {{s}_{i+1}}-\varGamma [i]-{{\varLambda }_{\alpha }}[i]+{{\varLambda }_{\beta }}[i]+{{s}_{i}}\ge 0 \\ {{s}_{i+1}}+\varGamma [i]+{{\varLambda }_{\alpha }}[i]-{{\varLambda }_{\beta }}[i]-{{s}_{i}}\ge 0 \\ {{s}_{i+1}}+\varGamma [i]-{{\varLambda }_{\alpha }}[i]-{{\varLambda }_{\beta }}[i]+{{s}_{i}}\ge 0 \\ {{s}_{i+1}}-\varGamma [i]+{{\varLambda }_{\alpha }}[i]-{{\varLambda }_{\beta }}[i]+{{s}_{i}}\ge 0 \\ {{s}_{i+1}}+\varGamma [i]-{{\varLambda }_{\alpha }}[i]+{{\varLambda }_{\beta }}[i]-{{s}_{i}}\ge 0 \\ {{s}_{i+1}}-\varGamma [i]+{{\varLambda }_{\alpha }}[i]+{{\varLambda }_{\beta }}[i]-{{s}_{i}}\ge 0 \\ -{{s}_{i+1}}+\varGamma [i]+{{\varLambda }_{\alpha }}[i]+{{\varLambda }_{\beta }}[i]+{{s}_{i}}\ge 0 \\ {{s}_{i+1}}+\varGamma [i]+{{\varLambda }_{\alpha }}[i]+{{\varLambda }_{\beta }}[i]+{{s}_{i}}\le 4 \\ \end{array}\right. } \end{aligned}$$

(3)

The correlation of addition modulo $2^n$($cor_{\boxplus }$) can be computed as follows: $|cor_{\boxplus }(\varGamma ,\wedge _{\alpha },\wedge _{\beta })|=2^{-\sum _{i=1}^{n-1} s_{i}}$. Taking the above observation into account, Fu et al. set the objective function for r-round linear MILP model as the $\sum \nolimits _{j=1}^{r}{\sum \nolimits _{i=1}^{n-1}{{{s}_{i}}}}$.

For more details, please refer to [18, 35].

4 The Refined MILP Model and Application to HIGHT

In this section, we present our refined MILP model, and then we apply the refined MILP model to the lightweight block cipher HIGHT.

4.1 The Refined MILP Model

It is observed that the number of variables in the MILP model will affect the efficiency of the solver. By analyzing the differential propagation of XOR operation in detail, in Eurocrypt 2017, Sasaki et al. gave the following constraints to model XOR operation.³

$$\begin{aligned} {\left\{ \begin{array}{ll} \varDelta a+\varDelta b+\varDelta c\le 2 \\ \varDelta a+\varDelta b\ge \varDelta c \\ \varDelta a+\varDelta c\ge \varDelta b \\ \varDelta b+\varDelta c\ge \varDelta a \\ \end{array}\right. } \end{aligned}$$

(4)

where $\varDelta a$ and $\varDelta b$ are the input differences of the XOR operation, and $\varDelta c$ is the output difference.

In the previous work, we obtain the five constraint inequalities by computing the H-representation of the convex hull for the four possible differential propagation modes. Now, we obtain the same four constraint inequalitys with the greedy algorithm [17]. Compared with/the constraints given in the formula (1), the formula (4) not only introduces no new dummy variables, but also reduces one constraint, which can reduce 16 variables and constraints in just one round HIGHT. Similarly, in the modular addition and the branching operations, the XOR constraints also reduce a part of variables and constraints.

Next, we focus on the functions $F_{0}$ and $F_1$ for HIGHT.

$$\begin{aligned} F_{0}(x)=(x<<<1)\oplus (x<<<2)\oplus (x<<<7)\\ F_{1}(x)=(x<<<3)\oplus (x<<<4)\oplus (x<<<6) \end{aligned}$$

For the 2-XOR operations in each function, in accordance with the above formula (4), we need to introduce an intermediate variable to generate the constraints, in this case, we convert constrained $F_{0}$ and $F_1$ to the following question.

Let $\varDelta {a}\oplus \varDelta {b}\oplus \varDelta {c}=\varDelta {d}$, where $\varDelta {a}$, $\varDelta {b}$ and $\varDelta {c}$ are the input differences, and $\varDelta {d}$ is the output difference. The differential propagation of the 2-XOR operations is shown in Fig. 2.

Fig. 2.

The differential propagation of the 2-XOR operations.

By analyzing these possible differential patterns in detail, We give the constraints as shown in formula (5). These constraints can be clearly seen from Table 2, we can know the 8 constraints are chosen to describe the possible difference patterns for the 2 XOR operations. In Table 2, the constraint $\varDelta a+\varDelta b+\varDelta c-\varDelta d\ge 0$ can remove the impossible differential propagation mode (0, 0, 0, 1). The eight constraint inequalities in formula (5) satisfy all possible input-output differential modes, and also exclude all impossible input-output differential modes.

$$\begin{aligned} {\left\{ \begin{array}{ll} \varDelta a+\varDelta b+\varDelta c-\varDelta d\ge 0 \\ \varDelta a+\varDelta b+\varDelta c-\varDelta d\le 2 \\ \varDelta a+\varDelta b+\varDelta d-\varDelta c\ge 0 \\ \varDelta a+\varDelta b+\varDelta d-\varDelta c\le 2 \\ \varDelta a+\varDelta c+\varDelta d-\varDelta b\ge 0 \\ \varDelta a+\varDelta c+\varDelta d-\varDelta b\le 2 \\ \varDelta b+\varDelta c+\varDelta d-\varDelta a\ge 0 \\ \varDelta b+\varDelta c+\varDelta d-\varDelta a\le 2 \\ \end{array}\right. } \end{aligned}$$

(5)

Table 2. Remove all impossible differential propagations for the 2-XOR operations

By comparing the introduction of the intermediate variable with the constraint given by the formula (4), we can reduce 8 variables in each function by the formula (5). When solving the MILP model with Gurobi, it can save computing time and improve the solving efficiency through the above constraints.

4.2 Construct the Refined MILP Model for HIGHT

According to the refined constraints given by the XOR and 2-XOR operations, we apply these refined constraints to the MILP model of the HIGHT. According to Sun et al. MILP-based automatic search technology and constraints for modular addition operation, it is easy to construct a refined MILP model for HIGHT.

Without loss of generality, we just give the method of constructing the differential MILP model for 1-round HIGHT in detail. The differential and linear MILP model for r-round HIGHT can be constructed in the similar way.

We assume that the new value introduced in modular addition operation $T(\alpha [i],\beta [i],\gamma [i])$ is denoted by $T_{1}^{(i)}$, where $i\in [0,6]$. As there are 4 modular addition operations in a round of HIGHT, the number of the new values $T(\alpha [i],\beta [i],\gamma [i])$ is 28 in total, which is denoted by $(T_{1}^{(0)},T_{1}^{(1)},\cdots ,T_{1}^{(27)})$. Then the sum of the values: $T_{1}^{(0)}+T_{1}^{(1)}+\cdots +T_{1}^{(27)}$ is chosen as the objective function to be minimized.

Assume that the 64-bit input difference for the 1-round HIGHT is denoted by $\varDelta X=(\varDelta {{X}_{0}},\cdots ,\varDelta {{X}_{i}},\cdots ,\varDelta {{X}_{7}})$, where $\varDelta {{X} _ {i}}$ is an 8-bit differential variable, $\varDelta {{X}_{i}}=(\varDelta {{X}_{i}}^{(0)},\varDelta {{X}_{i}}^{(1)}\cdots ,\varDelta {{X}_{i}}^{(7)})$. According to the round function of HIGHT, the 1-8, 17-24, 33-40, 49-56 bits position of the outputs are the same as the corresponding differential positions of the inputs for 1-round HIGHT. So, the 64-bit output difference for the 1-round HIGHT is denoted by $\varDelta Y=(\varDelta {{X}_{1}},\varDelta {{Y}_{0}},\varDelta {{X}_{3}},\varDelta {{Y}_{1}},\varDelta {{X}_{5}},\varDelta {{Y}_{2}},\varDelta {{X}_{7}},\varDelta {{Y}_{3}})$, where $\varDelta {{Y}_{i}}$ is an 8-bit differential variable, $\varDelta {{Y}_{i}}= (\varDelta {{Y}_{i}}^{(0)}, \varDelta {{Y}_{i}}^{(1)}\cdots , \varDelta {{Y}_{i}}^{(7)})$. At the same time, the output difference between the four F-functions from left to right is $\varDelta Z =(\varDelta {{Z} _ {0}}, \varDelta {{Z} _ {1}})$, $\varDelta {{Z}_{i}}$ is an 8-bit differential variable, and $\varDelta {{Z}_{i}}=(\varDelta {{Z}_{i}}^{(0)},\varDelta {{Z}_{i}}^{(1)}\cdots ,\varDelta {{Z}_{i}}^{(7)})$. The difference between the output of the first and third addition modulo operation from left to right is $\varDelta M=(\varDelta {{M}_{0}},\varDelta {{M}_{1}})$, where $\varDelta {{M} _ {i}}$ is an 8-bit differential variable, then $\varDelta {{M} _ {i}} = (\varDelta {{M_{i}}^{ 0}}, \varDelta {{M}_{i}}^{(1)}, \cdots , \varDelta {{M}_{i}}^{(7)})$. These differential variables are shown in Fig. 3.

Fig. 3.

Differential variable values for the 1-round MILP model of HIGHT.

Firstly, to make sure the non-zero input difference, we should add the constraint:

$$\begin{aligned} \varDelta {{X}_{0}}^{(0)}+\varDelta {{X}_{0}}^{(1)}+\cdots +\varDelta {{X}_{0}}^{(63)}\ge 1 \end{aligned}$$

In the first generalized feistel structure, the input difference of the F-function is $(\varDelta {{X}_{1}}^{(0)},\varDelta {{X}_{1}}^{(1)},\cdots ,\varDelta {{X}_{1}}^{(7)})$, and the output difference is $(\varDelta {{Z}_{0}}^{(0)},\varDelta {{Z}_{0}}^{(1)},\cdots , \varDelta {{Z}_{0}}^{(7)})$. When $j=0$, according to formula (5), we can get the constraints as follows:

$$\begin{aligned} {\left\{ \begin{array}{ll} \varDelta {{X}_{1}}^{(1)}+\varDelta {{X}_{1}}^{(2)}+\varDelta {{X}_{1}}^{(7)}-\varDelta {{Z}_{0}}^{(0)}\ge 0\\ \varDelta {{X}_{1}}^{(1)}+\varDelta {{X}_{1}}^{(2)}+\varDelta {{X}_{1}}^{(7)}-\varDelta {{Z}_{0}}^{(0)}\le 2 \\ \varDelta {{X}_{1}}^{(1)}+\varDelta {{X}_{1}}^{(2)}+\varDelta {{Z}_{0}}^{(0)}-\varDelta {{X}_{1}}^{(7)}\ge 0 \\ \varDelta {{X}_{1}}^{(1)}+\varDelta {{X}_{1}}^{(2)}+\varDelta {{Z}_{0}}^{(0)}-\varDelta {{X}_{1}}^{(7)}\le 2 \\ \varDelta {{X}_{1}}^{(1)}+\varDelta {{X}_{1}}^{(7)}+\varDelta {{Z}_{0}}^{(0)}-\varDelta {{X}_{1}}^{(2)}\ge 0 \\ \varDelta {{X}_{1}}^{(1)}+\varDelta {{X}_{1}}^{(7)}+\varDelta {{Z}_{0}}^{(0)}-\varDelta {{X}_{1}}^{(2)}\le 2 \\ \varDelta {{X}_{1}}^{(2)}+\varDelta {{X}_{1}}^{(7)}+\varDelta {{Z}_{0}}^{(0)}-\varDelta {{X}_{1}}^{(1)}\ge 0 \\ \varDelta {{X}_{1}}^{(2)}+\varDelta {{X}_{1}}^{(7)}+\varDelta {{Z}_{0}}^{(0)}-\varDelta {{X}_{1}}^{(1)}\le 2 \\ \end{array}\right. } \end{aligned}$$

(6)

when $j\ge 1$, the constraints can be obtained with the same method. So $8\times 32 = 256$ linear constraints are proposed to describe the differential property for the 2 XOR operations in the 1-round HIGHT.

The constraints of the modular addition operations are introduced in the following text. In the first generalized feistel structure, the two input differences are $(\varDelta {{Z}_{0}}^{(0)},\varDelta {{Z}_{0}}^{(1)},\cdots ,\varDelta {{Z}_{0}}^{(7)})$ and 0, the output difference is $(\varDelta {{M}_{0}}^{(0)},\varDelta {{M}_{0}}^{(1)},\cdots ,\varDelta {{M}_{0}}^{(7)})$. When $j=7$, the constraint is $\varDelta {{Z}_{0}}^{(0)}-\varDelta {{M}_{0}}^{(0)}=0$, obviously. According to formula (2), when $j=0$, the constraints are shown in formula (7).

$$\begin{aligned} {\left\{ \begin{array}{ll} -\varDelta M_{0}^{(1)}+T_{0}^{(0)}\ge 0 \\ \varDelta Z_{0}^{(1)}+T_{0}^{(0)}\ge 0 \\ \varDelta M_{0}^{(1)}-\varDelta Z_{0}^{(1)}+T_{0}^{(0)}\ge 0 \\ -\varDelta Z_{0}^{(1)}+\varDelta M_{0}^{(1)}+T_{0}^{(0)}\le 3 \\ -\varDelta Z_{0}^{(1)}+\varDelta M_{0}^{(1)}-T_{0}^{(0)}\ge 0 \\ \varDelta Z_{0}^{(1)}+\varDelta M_{0}^{(0)}+T_{0}^{(0)}\ge 0 \\ \varDelta Z_{0}^{(0)}+\varDelta M_{0}^{(0)}\ge 0 \\ -\varDelta Z_{0}^{(0)}+\varDelta M_{0}^{(0)}+T_{0}^{(0)}\ge 0 \\ \varDelta Z_{0}^{(1)}+\varDelta Z_{0}^{(0)}-\varDelta M_{0}^{(0)}+T_{0}^{(0)}\ge 0 \\ \varDelta M_{0}^{(1)}+\varDelta Z_{0}^{(0)}-\varDelta M_{0}^{(0)}+T_{0}^{(0)}\ge -2 \\ \varDelta Z_{0}^{(0)}-\varDelta M_{0}^{(0)}+T_{0}^{(0)}\ge -2 \\ -\varDelta Z_{0}^{(0)}-\varDelta M_{0}^{(0)}+T_{0}^{(0)}\ge -2 \\ \varDelta M_{0}^{(0)}-\varDelta Z_{0}^{(0)}+T_{0}^{(0)}\ge -2 \\ \end{array}\right. } \end{aligned}$$

(7)

The constraints when $1\le j\le 6$ can be calculated in the similar way. Therefore, we can produce $2\times (7\times 13+1)+ 2\times (7\times 13+4)= 374$ constraints to represent the differential property for modular addition in the 1-round HIGHT.

Finally, we focus on the XOR operations, whose input difference are $(\varDelta {{X}_{0}}^{(0)}, \varDelta {{X}_{0}}^{(1)},\cdots ,\varDelta {{X}_{0}}^{(7)})$ and $(\varDelta {{M}_{0}}^{(0)},\varDelta {{M}_{0}}^{(1)},\cdots ,\varDelta {{M}_{0}}^{(7)})$, and the output difference is $(\varDelta {{Y}_{3}}^{(0)},\varDelta {{Y}_{3}}^{(1)},\cdots ,\varDelta {{Y}_{3}}^{(7)})$. When $j=0$, the constraints are shown in formula (8).

$$\begin{aligned} {\left\{ \begin{array}{ll} \varDelta X_{0}^{(0)}+\varDelta M_{0}^{(0)}-\varDelta Y_{3}^{(0)}\ge 0 \\ \varDelta X_{0}^{(0)}+\varDelta Y_{3}^{(0)}-\varDelta M_{0}^{(0)}\ge 0 \\ \varDelta Y_{3}^{(0)}+\varDelta M_{0}^{(0)}-\varDelta X_{0}^{(0)}\ge 0 \\ \varDelta X_{0}^{(0)}+\varDelta M_{0}^{(0)}+\varDelta Y_{3}^{(0)}\le 2 \\ \end{array}\right. } \end{aligned}$$

(8)

The constraints when $j\ge 1$ can be calculated in the same way. Thus, we have $2\times 4\times 8= 64$ constraints for XOR operation in the 1-round HIGHT. So far, we construct a complete MILP model for 1-round HIGHT. In total, we have 256 + 374 + 64 + 1 = 695 constraints to exactly describe the difference $\varDelta {{X}}\rightarrow \varDelta {{Y}}$.

4.3 Comparison of Constraints and Variables in the MILP Model

In order to distinguish these two types of MILP models and also for the convenience of our statement in this paper, the MILP model without adding new constraints is named as the original MILP model, and the MILP model with new constraints is named as the refined MILP model.

We establish the differential MILP model for r-round HIGHT. The original MILP model have $776r+2$ constraints and $214r+65$ variables for the r-rounds HIGHT, but the refined MILP model for r-round HIGHT only needs $694r+2$ constraints and $108r+65$ variables, Figs. 4 and 5 show the number of constraints and variables in the original and the refined differential MILP model for the first 12-round HIGHT, respectively.

Fig. 4.

Comparison of the number of constraints in the original and refined differential MILP model for the first 12-round.

Fig. 5.

Comparison of the number of variables in the original and refined differential MILP model for the first 12-round.

As you can see in Fig. 4, the original model has 7762 constraints for the 10-round HIGHT, while the refined model has only 6942 constraints, in comparison, 820 constraint inequalities are reduced. In Fig. 5, the original model has 2205 variables for the 10-round HIGHT, while the refined model has only 1145 variables, 1060 variables are reduced.

We establish the linear MILP model for r-round HIGHT. The original MILP model have $736r+2$ constraints and $288r+65$ variables for the r-rounds HIGHT, but the refined MILP model for r-round HIGHT only needs $640r+2$ constraints and $192r+65$ variables, Figs. 6 and 7 show the number of constraints and variables in the original and the refined linear MILP model for the first 12-round HIGHT, respectively.

Fig. 6.

Comparison of the number of constraints in the original and refined linear MILP model for the first 12-round.

Fig. 7.

Comparison of the number of variables in the original and refined linear MILP model for the first 12-round.

As you can see in Fig. 6, the original model has 7362 constraints for the 10-round HIGHT, while the refined model has only 6402 constraints, in comparison, 960 constraint inequalities are reduced. In Fig. 7, the original model has 2945 variables for the 10-round HIGHT, while the refined model has only 1985 variables, 960 variables are reduced.

5 The Differential and Linear Cryptanalysis for HIGHT

Based on the refined MILP model, according to Sect. 4.2, we generate the differential and linear MILP models in “lp” format [14] for HIGHT through a small python program, and call Gurobi 7.0.2 to solve it. There are $108r+65$ variables and $694r+1$ constraints for r-round HIGHT in differential MILP model, and there are 192r + 65 variables and 640r + 2 constraints for r-round HIGHT in linear MILP model. The MILP model was solved on a server, the server configuration is shown in Table 3.

Table 3. Experimental environment for solving the MILP model

5.1 The Differential Cryptanalysis for HIGHT

By solving the refined differential MILP model, the probability of differential characteristic for reduced-round HIGHT obtained by our refined MILP model is listed in Table 4, the ${{p}_{r}}$ denotes the probability of differential characteristic for the r-round HIGHT.

Table 4. The differential cryptanalysis results for refined MILP model application to HIGHT

From Table 4 we know that the refined MILP model for the 11-round HIGTH consists of 1253 0-1 variables, 7635 constraints. The MILP model can be solved within 1012556 s and we find the better probability of differential characteristic for 11-round HIGHT is ${{2}^{-45}}$. Note that the probability of the best single-key characteristic previously published covering 11-round is ${{2}^{-58}}$. Furthermore, using the refined tool, we obtain the new single-key differential characteristics for HIGHT, which cover larger number of rounds. We obtain the 12- and 13-round single-key differential characteristics of HIGHT with probability ${{2}^{-53}}$ and ${{2}^{-61}}$. For the 14-round HIGHT, the optimal probability for differential characteristic is less than ${{2}^{-64}}$. The probability of success for an exhaustive search, thus, we concluded that the all-round HIGHT has a sufficient resistance to differential attacks.

Finally, the differential trails for 12 and 13-round HIGHT are listed in Tables 5 and 6, respectively.

Table 5. Differential trail for 12-round HIGHT

Table 6. Differential trail for 13-round HIGHT

In order to clarify that the refined MILP model can solve more efficiently, we establish the MILP model for the first 9-round HIGHT, and solve the MILP model in the same experimental environment. In less than 10 days, the original differential MILP model of the first 9-round HIGHT was solved, and the optimal differential probability is the same as Table 4. But the time expendure of round 1 to 9 is 1 s, 1 s, 123 s, 568 s, 2135 s, 21268 s, 48392 s, 124536 s and 671258 s, respectively. Figure 8 shows a comparison of the solve time between the original and the refined differential MILP model for the first 9-round HIGHT.

Fig. 8.

Comparison of the solve time in the original and refined differential MILP model for the first 9-round HIGHT.

From Fig. 8 we know that the original differential MILP model can be solved within 671258 s for the 9-round HIGHT. Nevertheless, the refined differential MILP model just needed 125565 s. Comparatively speaking, the solve time of the refined MILP model is 5 times faster than the original MILP model.

5.2 The Linear Cryptanalysis for HIGHT

By solving the refined linear MILP model, the correlation of linear approximation for reduced-round HIGHT obtained by our refined MILP model is listed in Table 7, the ${cor_{r}}$ denotes the correlation of linear approximation for the r-round HIGHT.

Table 7. The linear cryptanalysis results for refined MILP model application to HIGHT

For linear attack, from Table 7 we know that linear approximation for the 10-round HIGHT with correlation ${{2}^{-25}}$, the correlation of the best linear approximation previously published covering 10-round is ${{2}^{-26}}$. Moreover, we obtain the new linear approximation for 11-round HIGHT with correlation ${{2}^{-31}}$, the maximum linear bias is ${{\varepsilon }^{2}}={{2}^{-64}}$, then the linear attack on the 11-round HIGHT require ${{2}^{64}}$ known plaintext, but the all-round HIGHT require plaintext is certainly greater than ${{2}^{64}}$. Therefore, it can be concluded that all-round HIGHT are sufficiently resistant to linear attack. Finally, the linear trail for 11-round HIGHT is listed in Table 8.

Table 8. Linear trail for 11-round HIGHT

In order to clarify that the refined MILP model can solve more efficiently, we establish the MILP model for the first 8-round HIGHT, and solve the MILP model in the same experimental environment. In less than 10 days, the original linear MILP model of the first 8-round HIGHT was solved, and the optimal linear correlation is the same as Table 7. But the time expendure of round 1 to 8 is 1 s, 157 s, 882 s, 5029 s, 18653 s, 79523 s and 4264131 s, respectively. Figure 9 shows a comparison of the solve time between the original and the refined linear MILP model for the first 8-round HIGHT.

Fig. 9.

Comparison of the solve time in the original and refined linear MILP model for the first 8-round.

From Fig. 9 we know that the original linear MILP model can be solved within 426413 s for the 8-round HIGHT. Nevertheless, the refined differential MILP model just needed 165348 s. By contrast, the solve time of the refined MILP model is 2.5 times faster than the original MILP model.

6 Conclusion

In this paper, we analyze the differential propagation for the 2-XOR operations in detail, and improve Sun et al.’s method for describing XOR operation with refined constraints. In the refined MILP model, the number of variables and constraints are reduced, which leads to quickly solve for the refined MILP model.

As an application, we implement our refined MILP model to the lightweight block cipher HIGHT. Compared with the existing attack results, the refined MILP model searches the optimal differential characteristic and linear approximation for HIGHT, the differential and linear trails increased to 13-round and 11-round. These results indicate that the refined MILP model is more efficient in practical cryptanalysis.