# Research on SKINNY Optimal Differential Trail Search

Authors: Shaoqiang Liu; Chaiyang Peng; Chunjiang Li
Journal: Security and Communication Networks
 (2020)

---

## Abstract

SKINNY is a tweakable lightweight block cipher algorithm. In order to test its security, this paper performs optimal differential trail search analysis on all SKINNY-64 versions under single-key setting based on the MILP (Mixed Integer Linear Programming) algorithm. Firstly, SKINNY round function is abstracted equivalently by precise constraints, and the objective function is set as the minimum number of active S-box number to optimize SKINNY-64 MILP model. Experiments show the differential trail searched by this method is not necessarily optimal. In order to directly search for the optimal differential trail, the S-box differential probability coding information is added to the optimized SKINNY-64 MILP model, the S-box differential characteristic is reconstructed, and the objective function is set to the minimum value of the probability coding information, which improves the SKINNY-64 MILP model. The results of experimental show that the improved MILP model can directly search for the optimal differential trail, and the complexity is slightly increased, but the search efficiency is significantly improved. Under single-key setting, this method has obvious advantage in searching the optimal differential trails of SKINNY-64 with low round number.


---

## Body

## 1. Introduction

SKINNY is a SPN-structured tweakable lightweight block cipher algorithm proposed by Beierle [1] at American Cryptography Conference in 2016. SKINNY is divided into six different versions, namely, SKINNY-64-64, SKINNY-64-128, SKINNY-64-192, SKINNY-128-128, SKINNY-128-256, and SKINNY-128-384.Since the announcement of the SKINNY algorithm, some scholars have used various methods to analyze its security. Tolba et al. [2] performed impossible differential attack analysis on 18, 20, and 22 rounds of SKINNY-n-n, SKINNY-n-2n, and SKINNY-n-3n, respectively. Sadegh Sadeghi et al. [3] obtained the 12-round impossible differential trails of SKINNY-64-64 and SKINNY-64-128 in SKINNY's TK1 and TK2 models, respectively, using the method of intermediate encounter. Hong Dou [4] used the intermediate encounter technology to search out all 16 truncated impossible differential trails of the 11 rounds of the SKINNY encryption algorithm and used one of them to analyze 20 rounds of SKINNY-64-128 using the impossible differential technique under a single key setting. The main approach of these papers is to find trails that are impossible to occur in the ciphertext, leaving only a reasonable number of differential trails to consider.Unlike methods that search for more impossible differential trails, Mixed integer linear programming(MILP) is a method that can search for differential trails directly. Mouha [5] and Wu [6] converted the minimum active S-boxes number of block ciphers into a MILP problem and applied the MILP method to cryptanalysis. However, this method has two shortcomings. One is that it cannot be directly applied to the SPN block cipher with a bit permutation layer because it does not consider the diffusion effect formed by the S-boxes replacement layer and the bit permutation layer. The second is that, for a given cryptographic algorithm, the MILP constraint set listed cannot fully describe the differential propagation characteristics of the linear diffusion layer [7]. Professor Sun [8] supplemented and optimized the method of Mouha and applied the method of obtaining the minimum number of active S-boxes to a bit-oriented block cipher. A linear inequality was generated based on the differential characteristics of S-boxes. Constraint inequality generated by XOR operation builds an MILP model to search for the differential characteristics of block ciphers under single-key and related-key setting [9], and the MILP model uses only partial linear inequality, making it solvable in real time.In recent years, some scholars have applied the MILP method to the research of SKINNY cryptographic algorithms. The designers of SKINNY performed a security evaluation of SKINNY. Using the MILP method, they obtained the lower bound of the minimum number of active S-boxes under the single-key and related-key setting. According to the lower limit of the number of differential active S-boxes in SKINNY, they further assumed that each S-box used the maximum differential probability to evaluate the security boundary of SKINNY. However, it is not clear whether such a difference trail with maximum probability that satisfies the lower bound exists. Therefore, Sun et al. [10] proposed a method to obtain stricter boundaries, verified whether the optimal differential trail using the maximum differential probability for all active S-boxes exists, and proposed the method of finding the optimal differential trail of the block cipher algorithm based on MILP. Liu et al. [11] firstly proposed the method of searching the actual differential trail of SKINNY under the relevant tweakable secret key model and used the indirect search method based on MILP to search the optimal differential trail of SKINNY-64 and SKINNY-128. The results show that the probability of the optimal differential trail is much smaller than that obtained from the lower bound of the active S-boxes in SKINNY with the increase of the number of rounds. However, their work is to analyze SKINNY under the related-key setting. Zhang et al. [12] proposed a method based on MILP to automatically search the number of 11 minimum active S-boxes of SKINNY-64/192 and obtained the number of 11 active S-boxes and the corresponding differential trail under this number, but their differential trails are no guarantee that are the optimal trails and other versions of SKINNY-64 are not considered.In this paper, we analyze the differential propagation characteristics of all SKINNY-64 versions under the single-key setting model by using MILP and obtain the optimal differential trails. The basic method is to establish the MILP model of SKINNY-64 under the single key setting and use the LPSolve optimizer to obtain an optimized solution with the objective function as the minimum number of active S-boxes. Combined with the differential probability coding information of S-boxes, the model was further improved to obtain the optimal differential trail.The rest of this paper is organized as follows. In Section2, the MILP model of all SKINNY-64 versions is proposed first. To search the optimal differential trails directly, an improved MILP model of SKINNY-64 and an experimental plan are introduced in Section 3, and also the two experimental results are discussed and analyzed. Finally, Section 4 concludes the work.


## 2. Analysis of SKINNY Differential Trail Based on MILP

### 2.1. SKINNY Differential Characteristic Optimization Based on MILP

Due to the differential analysis of single-key setting, the key is assumed to be fixed, the round key difference is not considered, and only the state difference is considered. Therefore, the MILP model of all SKINNY-64 versions can be uniformly optimized by using the S-box constraint part, the Row Shift constraint part, and the column mixed constraint part. MILP model optimization is mainly carried out by reducing constraint inequalities and the number of variables. The specific parameters of a round of difference analysis before and after MILP optimization are shown in Table1. It can be seen that the optimization reduces the calculation amount and improves the operation efficiency.Table 1
Constraint conditions and number of variables of SKINNY-64 differential analysis before and after MILP model optimization.
Before optimizationThe optimizedThe constraint inequalities3712800The number of variables352288Theith round SKINNY-64 state differential transition after optimization is shown in Figure 1.In Figure1, XiandYi represent the state difference of the ith round and Yir is the state difference of Yi after Row Shifting, each containing 16 difference cells and a total of 64 bit difference. For example, Xi represents the output difference of the (i − 1)th or the plaintext pair difference x0,‥K.,x63 when i = 1. Each state XiandYi contains 16 difference cells, each cell is a nibble, respectively, represented by Xj and Yj, where j∈0,‥K.,15. Each difference cell can be expressed as Xj=x4j,x4j+1,x4j+2,x4j+3.Figure 1
Theith round SKINNY-64 state differential transfer diagram after MILP optimization.


#### 2.1.1. S-Box Differential Characteristic Optimization

The 1st round of SKINNY’s differential feature changes for each S-box has a total of 97 differential characteristics, as shown in Table2.Table 2
97 possible differential characteristics of the 1st round of the SKINNY-64 S-box.
x4i,x4i+1+x4i+2+x4i+3y4i,y4i+1,y4i+2,y4i+3i∈0,‥K.,150000000000011000 1001 1010 101100100001 0011 0101 011000111000 1001 1010 1011 1100 1101 1110 111101000010 0110 0111 1011 1100 110101010010 0110 0111 1010 1100 110101100001 0011 0100 0111 1000 1010 1101 111001110001 0011 0100 0111 1001 1011 1100 111110000100 0101 1100 1101 1110 111110010100 0101 1100 1101 1110 111110100101 0110 1000 1001 1010 101110110001 0011 1100 1101 1110 111111000010 0110 0111 1000 1110 111111010010 0110 0111 1001 1110 111111100001 0011 0100 0111 1001 1011 1101 111011110001 0011 0100 0111 1000 1010 1100 1111A set of truncated inequality describing these effective difference modes are obtained by computing the finite multipoint convex closure H-representations in a computational geometry system. Through the inequality generator function in the sage.geometry.polyhedron class of the SageMath, a convex closure of a specific S-box can be obtained and 202 inequalities are calculated. Our implementation follows the details presented in AppendixA. To obtain the optimal linear inequalities describing the SKINNY-64 S-box, we use the greedy algorithm to remove the invalid difference to optimize the model. Finally, it only needs 24 valid truncation inequalities (see Table 3) to solve SKINNY-64, which can accurately describe the difference feature of an S-box. The associated source codes of our implementation are listed at Appendix B.Table 3
24 efficient truncation inequalities generated.
24 effective truncation inequalitiesNumber of invalid difference modes removed/inequalities−2x0+3x1−3x2−2x3+5y0+4y1+y27y3≥027−x0+x1=2x2+x3+y0+3y1−2y3≥0244x0+3x1+2x2+3x3−y0−y1−y2−y3≥0182x0−x1+2x2+3y0−y1+3y2−y3≥013x0+3x1+x2−2x3+2y0−y1−2y2≥−29−3x0+2x1+x2−2x3−y0+3y1+y3≥−38x1−2x2+2x3−y0−2y1+y2+y3≥−37−2x0−3x1+2x2+x3+y0−y1+3y2−y3≥−47−x1−2x2−x3+y0−y1−2y2+2y3≥−56−x1−x2−x3+y0−2y1+2y2−2y3≥−552x0+x1+3x2+4x3−3y0+2y1−y2+3y3≥05x0−2x1+2x2−2x3−y0+y1−y2−2y3≥−65x1−2x2+2x3−y0−2y1−y2−y3≥−54x0−x1−x3+y0+2y1+2y2+2y3≥03x0−x2+x3−y0+y1−y3≥−23−x0−x2−x3−y0+y1−y3≥−43−x0−x1−x2+x3+y1+y3≥−223x0+x1+x2−2x3+2y0−y1+2y2−y3≥−12x1+x2+y0−y2≥02x0−x1−2x2−x3+y0−2y2+2y3≥−42x0+x1+x2+2x3−2y0+y1+y2≥02−x0−x1+x2−y1+y2≥−21x0+x1+x2−y1≥01x0+x2−y0−y1−y2≥−21Total159


#### 2.1.2. Shift Row Differential Characteristic

In the difference analysis, the Row Shift operation process is the same as the Row Shift process of the SKINNY round function; only the 1st row of the internal state value needs to be fixed, and the 2nd, 3rd, and 4th rows are shifted to the right by 1, 2, and 3 bits, as shown in Figures1(b) and 1(c).


#### 2.1.3. Mix Column after Optimizing MILP Model

After optimizing the MILP model, the basic process of Column Mixing is shown in Figures1(c) and 1(d).Considering the difference of each bit, the 4 × 4 M matrix of SKINNY is transformed into a 16 × 16 matrix:(1)M=1000000010001000010000000100010000100000001000100001000000010001100000000000000001000000000000000010000000000000000100000000000000001000100000000000010001000000000000100010000000000001000100001000000010000000010000000100000000100000001000000001000000010000.Output differenceXi+1=M×Yir for the 1st round, corresponding to the 2nd round of input is shown in Table 4.Table 4
The 2nd round input.
x64=y0+y40+y52x80=y0x96=y28+y40x112=y0+y40x65=y1+y41+y53x81=y1x97=y29+y41x113=y1+y41x66=y2+y42+y54x82=y2x98=y30+y42x114=y2+y42x67=y3+y43+y55x83=y3x99=y31+y43x115=y3+y43x68=y4+y44+y56x84=y4x100=y16+y44x116=y4+y44x69=y5+y45+y57x85=y5x101=y17+y45x117=y5+y45x70=y6+y46+y58x86=y6x102=y18+y46x118=y6+y46x71=y7+y47+y59x87=y7x103=y19+y47x119=y7+y47x72=y8+y32+y60x88=y8x104=y20+y32x120=y8+y32x73=y9+y33+y61x89=y9x105=y21+y33x121=y9+y33x74=y10+y34+y62x90=y10x106=y22+y34x122=y10+y34x75=y11+y35+y63x91=y11x107=y23+y35x123=y11+y35x76=y12+y36+y48x92=y12x108=y24+y36x124=y12+y36x77=y13+y37+y49x93=y13x109=y25+y37x125=y13+y37x78=y14+y38+y50x94=y14x110=y26+y38x126=y14+y38x79=y15+y39+y51x95=y15x111=y27+y39x127=y15+y39Based on the XOR method of MILP modeling, the constraint conditions of Column Mixing can be obtained. If the input is tri-XOR, the intermediate variableui, i∈0,...,15, is introduced. In the column mixed operation, 64 sets of inequalities are generated. Let a⊕b=c, where a and b and c are the input and output differences of the XOR. Virtual variable d⊕ is introduced, when input a and b and output c are all zero, the variable d⊕ is zero. In any other cases, the variable d⊕ is 1. It introduces 64 d⊕.Therefore, a total of 336 constraint inequalities need to be listed in the 1st round of Column Mixing. Due to the large number of linear inequalities involved, representative constraint inequalities are listed in Table 5.Table 5
Column hybrid constraint example.
Three XOR inputsPosition replacementTwo XOR inputsx64=y0+y40+y52y0+y40=u0y0+y40+u0≥2d⊕d⊕≥y0,d⊕≥y40,d⊕≥u0y0+y40+u0≤2x64+y52+u0≥2d⊕d⊕≥x64,d⊕≥y52x64+y52+u0≤2x80=y0x81=y1x82=y2x83=y3...x92=y12x93=y13x94=y14x95=y15x96=y28+y40y28+y40+x96≥2d⊕d⊕≥y28,d⊕≥y40,d⊕≥x96y28+y40+x96≤2


### 2.2. Analysis of SKINNY-64 4-Round MILP Model Results

SKINNY-64 1st difference analysis contains 800 constrained inequalities involving 288 variables Therefore, a total of 2864 constraint inequalities and 816 variables are included in the four rounds of skinny-64 differential trail MILP analysis model.To find the differential trail, the number of active S-boxes needs to be determined. S-boxes with nonzero input and output differences are called active S-boxes. Generally, when the number of active S-boxes is determined, the greater the state differential probability in the S-box, the higher the probability of the differential trail. Similarly, the smaller the number of the minimum active S-boxes, the higher the probability of the differential trail [13]. In order to solve the minimum number of active S-boxes, the objective function is set:(2)min∑i=0i=63Ai.Among them,Ai=1,theS−box is active,0,otherwise,, i is the number of the difference units in each round.Using the LPSolve software to solve the model, the minimum number of active S-boxes for four rounds is finally found to be 8, and the total probabilities of four 4-round differential trails are 2−18(A0 = 1), 2−18(A1 = 1), 2−21(A2 = 1), and 2−18(A3 = 1), and the result is shown in Figure 2.Figure 2
Four 4-round SKINNY-64 differential trails searched after optimizing the model.The average successful search time is 16.0465s (the main configuration of the computer: Intel i7 8700, CPU frequency 3.2 GHz, memory 32G, hard disk 2 TB 7200RPM + 512 GB SSD). However, the experimental results show that these four trails are not optimal. This method is not conducive to the direct search of the optimal differential trail, which needs further improvement.


## 2.1. SKINNY Differential Characteristic Optimization Based on MILP

Due to the differential analysis of single-key setting, the key is assumed to be fixed, the round key difference is not considered, and only the state difference is considered. Therefore, the MILP model of all SKINNY-64 versions can be uniformly optimized by using the S-box constraint part, the Row Shift constraint part, and the column mixed constraint part. MILP model optimization is mainly carried out by reducing constraint inequalities and the number of variables. The specific parameters of a round of difference analysis before and after MILP optimization are shown in Table1. It can be seen that the optimization reduces the calculation amount and improves the operation efficiency.Table 1
Constraint conditions and number of variables of SKINNY-64 differential analysis before and after MILP model optimization.
Before optimizationThe optimizedThe constraint inequalities3712800The number of variables352288Theith round SKINNY-64 state differential transition after optimization is shown in Figure 1.In Figure1, XiandYi represent the state difference of the ith round and Yir is the state difference of Yi after Row Shifting, each containing 16 difference cells and a total of 64 bit difference. For example, Xi represents the output difference of the (i − 1)th or the plaintext pair difference x0,‥K.,x63 when i = 1. Each state XiandYi contains 16 difference cells, each cell is a nibble, respectively, represented by Xj and Yj, where j∈0,‥K.,15. Each difference cell can be expressed as Xj=x4j,x4j+1,x4j+2,x4j+3.Figure 1
Theith round SKINNY-64 state differential transfer diagram after MILP optimization.


### 2.1.1. S-Box Differential Characteristic Optimization

The 1st round of SKINNY’s differential feature changes for each S-box has a total of 97 differential characteristics, as shown in Table2.Table 2
97 possible differential characteristics of the 1st round of the SKINNY-64 S-box.
x4i,x4i+1+x4i+2+x4i+3y4i,y4i+1,y4i+2,y4i+3i∈0,‥K.,150000000000011000 1001 1010 101100100001 0011 0101 011000111000 1001 1010 1011 1100 1101 1110 111101000010 0110 0111 1011 1100 110101010010 0110 0111 1010 1100 110101100001 0011 0100 0111 1000 1010 1101 111001110001 0011 0100 0111 1001 1011 1100 111110000100 0101 1100 1101 1110 111110010100 0101 1100 1101 1110 111110100101 0110 1000 1001 1010 101110110001 0011 1100 1101 1110 111111000010 0110 0111 1000 1110 111111010010 0110 0111 1001 1110 111111100001 0011 0100 0111 1001 1011 1101 111011110001 0011 0100 0111 1000 1010 1100 1111A set of truncated inequality describing these effective difference modes are obtained by computing the finite multipoint convex closure H-representations in a computational geometry system. Through the inequality generator function in the sage.geometry.polyhedron class of the SageMath, a convex closure of a specific S-box can be obtained and 202 inequalities are calculated. Our implementation follows the details presented in AppendixA. To obtain the optimal linear inequalities describing the SKINNY-64 S-box, we use the greedy algorithm to remove the invalid difference to optimize the model. Finally, it only needs 24 valid truncation inequalities (see Table 3) to solve SKINNY-64, which can accurately describe the difference feature of an S-box. The associated source codes of our implementation are listed at Appendix B.Table 3
24 efficient truncation inequalities generated.
24 effective truncation inequalitiesNumber of invalid difference modes removed/inequalities−2x0+3x1−3x2−2x3+5y0+4y1+y27y3≥027−x0+x1=2x2+x3+y0+3y1−2y3≥0244x0+3x1+2x2+3x3−y0−y1−y2−y3≥0182x0−x1+2x2+3y0−y1+3y2−y3≥013x0+3x1+x2−2x3+2y0−y1−2y2≥−29−3x0+2x1+x2−2x3−y0+3y1+y3≥−38x1−2x2+2x3−y0−2y1+y2+y3≥−37−2x0−3x1+2x2+x3+y0−y1+3y2−y3≥−47−x1−2x2−x3+y0−y1−2y2+2y3≥−56−x1−x2−x3+y0−2y1+2y2−2y3≥−552x0+x1+3x2+4x3−3y0+2y1−y2+3y3≥05x0−2x1+2x2−2x3−y0+y1−y2−2y3≥−65x1−2x2+2x3−y0−2y1−y2−y3≥−54x0−x1−x3+y0+2y1+2y2+2y3≥03x0−x2+x3−y0+y1−y3≥−23−x0−x2−x3−y0+y1−y3≥−43−x0−x1−x2+x3+y1+y3≥−223x0+x1+x2−2x3+2y0−y1+2y2−y3≥−12x1+x2+y0−y2≥02x0−x1−2x2−x3+y0−2y2+2y3≥−42x0+x1+x2+2x3−2y0+y1+y2≥02−x0−x1+x2−y1+y2≥−21x0+x1+x2−y1≥01x0+x2−y0−y1−y2≥−21Total159


### 2.1.2. Shift Row Differential Characteristic

In the difference analysis, the Row Shift operation process is the same as the Row Shift process of the SKINNY round function; only the 1st row of the internal state value needs to be fixed, and the 2nd, 3rd, and 4th rows are shifted to the right by 1, 2, and 3 bits, as shown in Figures1(b) and 1(c).


### 2.1.3. Mix Column after Optimizing MILP Model

After optimizing the MILP model, the basic process of Column Mixing is shown in Figures1(c) and 1(d).Considering the difference of each bit, the 4 × 4 M matrix of SKINNY is transformed into a 16 × 16 matrix:(1)M=1000000010001000010000000100010000100000001000100001000000010001100000000000000001000000000000000010000000000000000100000000000000001000100000000000010001000000000000100010000000000001000100001000000010000000010000000100000000100000001000000001000000010000.Output differenceXi+1=M×Yir for the 1st round, corresponding to the 2nd round of input is shown in Table 4.Table 4
The 2nd round input.
x64=y0+y40+y52x80=y0x96=y28+y40x112=y0+y40x65=y1+y41+y53x81=y1x97=y29+y41x113=y1+y41x66=y2+y42+y54x82=y2x98=y30+y42x114=y2+y42x67=y3+y43+y55x83=y3x99=y31+y43x115=y3+y43x68=y4+y44+y56x84=y4x100=y16+y44x116=y4+y44x69=y5+y45+y57x85=y5x101=y17+y45x117=y5+y45x70=y6+y46+y58x86=y6x102=y18+y46x118=y6+y46x71=y7+y47+y59x87=y7x103=y19+y47x119=y7+y47x72=y8+y32+y60x88=y8x104=y20+y32x120=y8+y32x73=y9+y33+y61x89=y9x105=y21+y33x121=y9+y33x74=y10+y34+y62x90=y10x106=y22+y34x122=y10+y34x75=y11+y35+y63x91=y11x107=y23+y35x123=y11+y35x76=y12+y36+y48x92=y12x108=y24+y36x124=y12+y36x77=y13+y37+y49x93=y13x109=y25+y37x125=y13+y37x78=y14+y38+y50x94=y14x110=y26+y38x126=y14+y38x79=y15+y39+y51x95=y15x111=y27+y39x127=y15+y39Based on the XOR method of MILP modeling, the constraint conditions of Column Mixing can be obtained. If the input is tri-XOR, the intermediate variableui, i∈0,...,15, is introduced. In the column mixed operation, 64 sets of inequalities are generated. Let a⊕b=c, where a and b and c are the input and output differences of the XOR. Virtual variable d⊕ is introduced, when input a and b and output c are all zero, the variable d⊕ is zero. In any other cases, the variable d⊕ is 1. It introduces 64 d⊕.Therefore, a total of 336 constraint inequalities need to be listed in the 1st round of Column Mixing. Due to the large number of linear inequalities involved, representative constraint inequalities are listed in Table 5.Table 5
Column hybrid constraint example.
Three XOR inputsPosition replacementTwo XOR inputsx64=y0+y40+y52y0+y40=u0y0+y40+u0≥2d⊕d⊕≥y0,d⊕≥y40,d⊕≥u0y0+y40+u0≤2x64+y52+u0≥2d⊕d⊕≥x64,d⊕≥y52x64+y52+u0≤2x80=y0x81=y1x82=y2x83=y3...x92=y12x93=y13x94=y14x95=y15x96=y28+y40y28+y40+x96≥2d⊕d⊕≥y28,d⊕≥y40,d⊕≥x96y28+y40+x96≤2


## 2.1.1. S-Box Differential Characteristic Optimization

The 1st round of SKINNY’s differential feature changes for each S-box has a total of 97 differential characteristics, as shown in Table2.Table 2
97 possible differential characteristics of the 1st round of the SKINNY-64 S-box.
x4i,x4i+1+x4i+2+x4i+3y4i,y4i+1,y4i+2,y4i+3i∈0,‥K.,150000000000011000 1001 1010 101100100001 0011 0101 011000111000 1001 1010 1011 1100 1101 1110 111101000010 0110 0111 1011 1100 110101010010 0110 0111 1010 1100 110101100001 0011 0100 0111 1000 1010 1101 111001110001 0011 0100 0111 1001 1011 1100 111110000100 0101 1100 1101 1110 111110010100 0101 1100 1101 1110 111110100101 0110 1000 1001 1010 101110110001 0011 1100 1101 1110 111111000010 0110 0111 1000 1110 111111010010 0110 0111 1001 1110 111111100001 0011 0100 0111 1001 1011 1101 111011110001 0011 0100 0111 1000 1010 1100 1111A set of truncated inequality describing these effective difference modes are obtained by computing the finite multipoint convex closure H-representations in a computational geometry system. Through the inequality generator function in the sage.geometry.polyhedron class of the SageMath, a convex closure of a specific S-box can be obtained and 202 inequalities are calculated. Our implementation follows the details presented in AppendixA. To obtain the optimal linear inequalities describing the SKINNY-64 S-box, we use the greedy algorithm to remove the invalid difference to optimize the model. Finally, it only needs 24 valid truncation inequalities (see Table 3) to solve SKINNY-64, which can accurately describe the difference feature of an S-box. The associated source codes of our implementation are listed at Appendix B.Table 3
24 efficient truncation inequalities generated.
24 effective truncation inequalitiesNumber of invalid difference modes removed/inequalities−2x0+3x1−3x2−2x3+5y0+4y1+y27y3≥027−x0+x1=2x2+x3+y0+3y1−2y3≥0244x0+3x1+2x2+3x3−y0−y1−y2−y3≥0182x0−x1+2x2+3y0−y1+3y2−y3≥013x0+3x1+x2−2x3+2y0−y1−2y2≥−29−3x0+2x1+x2−2x3−y0+3y1+y3≥−38x1−2x2+2x3−y0−2y1+y2+y3≥−37−2x0−3x1+2x2+x3+y0−y1+3y2−y3≥−47−x1−2x2−x3+y0−y1−2y2+2y3≥−56−x1−x2−x3+y0−2y1+2y2−2y3≥−552x0+x1+3x2+4x3−3y0+2y1−y2+3y3≥05x0−2x1+2x2−2x3−y0+y1−y2−2y3≥−65x1−2x2+2x3−y0−2y1−y2−y3≥−54x0−x1−x3+y0+2y1+2y2+2y3≥03x0−x2+x3−y0+y1−y3≥−23−x0−x2−x3−y0+y1−y3≥−43−x0−x1−x2+x3+y1+y3≥−223x0+x1+x2−2x3+2y0−y1+2y2−y3≥−12x1+x2+y0−y2≥02x0−x1−2x2−x3+y0−2y2+2y3≥−42x0+x1+x2+2x3−2y0+y1+y2≥02−x0−x1+x2−y1+y2≥−21x0+x1+x2−y1≥01x0+x2−y0−y1−y2≥−21Total159


## 2.1.2. Shift Row Differential Characteristic

In the difference analysis, the Row Shift operation process is the same as the Row Shift process of the SKINNY round function; only the 1st row of the internal state value needs to be fixed, and the 2nd, 3rd, and 4th rows are shifted to the right by 1, 2, and 3 bits, as shown in Figures1(b) and 1(c).


## 2.1.3. Mix Column after Optimizing MILP Model

After optimizing the MILP model, the basic process of Column Mixing is shown in Figures1(c) and 1(d).Considering the difference of each bit, the 4 × 4 M matrix of SKINNY is transformed into a 16 × 16 matrix:(1)M=1000000010001000010000000100010000100000001000100001000000010001100000000000000001000000000000000010000000000000000100000000000000001000100000000000010001000000000000100010000000000001000100001000000010000000010000000100000000100000001000000001000000010000.Output differenceXi+1=M×Yir for the 1st round, corresponding to the 2nd round of input is shown in Table 4.Table 4
The 2nd round input.
x64=y0+y40+y52x80=y0x96=y28+y40x112=y0+y40x65=y1+y41+y53x81=y1x97=y29+y41x113=y1+y41x66=y2+y42+y54x82=y2x98=y30+y42x114=y2+y42x67=y3+y43+y55x83=y3x99=y31+y43x115=y3+y43x68=y4+y44+y56x84=y4x100=y16+y44x116=y4+y44x69=y5+y45+y57x85=y5x101=y17+y45x117=y5+y45x70=y6+y46+y58x86=y6x102=y18+y46x118=y6+y46x71=y7+y47+y59x87=y7x103=y19+y47x119=y7+y47x72=y8+y32+y60x88=y8x104=y20+y32x120=y8+y32x73=y9+y33+y61x89=y9x105=y21+y33x121=y9+y33x74=y10+y34+y62x90=y10x106=y22+y34x122=y10+y34x75=y11+y35+y63x91=y11x107=y23+y35x123=y11+y35x76=y12+y36+y48x92=y12x108=y24+y36x124=y12+y36x77=y13+y37+y49x93=y13x109=y25+y37x125=y13+y37x78=y14+y38+y50x94=y14x110=y26+y38x126=y14+y38x79=y15+y39+y51x95=y15x111=y27+y39x127=y15+y39Based on the XOR method of MILP modeling, the constraint conditions of Column Mixing can be obtained. If the input is tri-XOR, the intermediate variableui, i∈0,...,15, is introduced. In the column mixed operation, 64 sets of inequalities are generated. Let a⊕b=c, where a and b and c are the input and output differences of the XOR. Virtual variable d⊕ is introduced, when input a and b and output c are all zero, the variable d⊕ is zero. In any other cases, the variable d⊕ is 1. It introduces 64 d⊕.Therefore, a total of 336 constraint inequalities need to be listed in the 1st round of Column Mixing. Due to the large number of linear inequalities involved, representative constraint inequalities are listed in Table 5.Table 5
Column hybrid constraint example.
Three XOR inputsPosition replacementTwo XOR inputsx64=y0+y40+y52y0+y40=u0y0+y40+u0≥2d⊕d⊕≥y0,d⊕≥y40,d⊕≥u0y0+y40+u0≤2x64+y52+u0≥2d⊕d⊕≥x64,d⊕≥y52x64+y52+u0≤2x80=y0x81=y1x82=y2x83=y3...x92=y12x93=y13x94=y14x95=y15x96=y28+y40y28+y40+x96≥2d⊕d⊕≥y28,d⊕≥y40,d⊕≥x96y28+y40+x96≤2


## 2.2. Analysis of SKINNY-64 4-Round MILP Model Results

SKINNY-64 1st difference analysis contains 800 constrained inequalities involving 288 variables Therefore, a total of 2864 constraint inequalities and 816 variables are included in the four rounds of skinny-64 differential trail MILP analysis model.To find the differential trail, the number of active S-boxes needs to be determined. S-boxes with nonzero input and output differences are called active S-boxes. Generally, when the number of active S-boxes is determined, the greater the state differential probability in the S-box, the higher the probability of the differential trail. Similarly, the smaller the number of the minimum active S-boxes, the higher the probability of the differential trail [13]. In order to solve the minimum number of active S-boxes, the objective function is set:(2)min∑i=0i=63Ai.Among them,Ai=1,theS−box is active,0,otherwise,, i is the number of the difference units in each round.Using the LPSolve software to solve the model, the minimum number of active S-boxes for four rounds is finally found to be 8, and the total probabilities of four 4-round differential trails are 2−18(A0 = 1), 2−18(A1 = 1), 2−21(A2 = 1), and 2−18(A3 = 1), and the result is shown in Figure 2.Figure 2
Four 4-round SKINNY-64 differential trails searched after optimizing the model.The average successful search time is 16.0465s (the main configuration of the computer: Intel i7 8700, CPU frequency 3.2 GHz, memory 32G, hard disk 2 TB 7200RPM + 512 GB SSD). However, the experimental results show that these four trails are not optimal. This method is not conducive to the direct search of the optimal differential trail, which needs further improvement.


## 3. Improved SKINNY Differential Trail Search Method

The above method can search multiple differential trails with the minimum number of active S-boxes, but the trails with the minimum number of active S-boxes are not all optimal differential trails. Therefore, the MILP model of SKINNY-64 needs to be improved to make it directly find the optimal differential trail.


### 3.1. New S-Box Differential Characteristic Based on Improved MILP Model

The improved MILP model is mainly to modify the S-box differential feature analysis of the above model, add probability coding information to the optimized MILP model, and reconstruct the S-box differential characteristic.Each valid differential characteristic of 16 S-boxesx4i,...,x4i+3,yi,...,y4i+3,i∈0,...,15, in the 1st round is combined with the corresponding probability information coding, to construct a new difference pattern x4i,...,x4i+3,yi,...,y4i+3,pi,qi∈ℝ10.The coding method of probability information is shown in Table 6:Table 6
Probability information coding.
pi,qiPrx4i,...,x4i+3,yi,...,y4i+3,i∈0,...,15(0, 0)2−0(0, 1)2−2(1, 1)2−3According to Table6, the probability information of the S-box differential characteristic can be expressed as 2−pi+2qi. The main idea of the improved method lies in the constraint of S-box difference mode and the choice of objective function. The constraints of the improved S-box model are combined with the coding information of the difference probability, which is closely related to the probability of the difference trail.So, set the objective function to(3)min∑i=0i=63pi+2qi.Although the S-box difference mode is changed after the probability coding information is added, the solution method is the same. Ninety seven new differential characteristics are available with the addition of probabilistic coding information, as shown in Table7:Table 7
All possible new differential characteristics for 1st round of SKINNY-64 S-box.
25 effective truncation inequalitiesNumber of invalid difference modes removed/inequalities−x0−x1−x3−y0+y2−y3−p0+5q0≥0484−2x1−x2−x3−2y1−y2−y3+4p0+4q0≥0127x1+x2+y0+y1−p0−q0≥097x1−x2+x3−3y0−y1+2p0+2q0≥062x0−2x1−4x2−x3+y1+2y2+3y3+5p0+q0>=030x0+2x1+x2+y0−p0−q0≥0242x2+y0+y1+y2−p0−q0≥020−x2+2y0+y1−y2+2y3−p0+q0≥016−3x0+3x1+x2+3x3−2y0+2y1−2y2−y3+5p0+2q0≥011x2+y1−p0≥08−3x1+2y0−y1+y2−y3+2p0+2q0≥073x0+2x1+x2+2x3−y0−y2−p0≥06x1+y0−p0≥06−2x0+x1−2x3−y0+2y1−y3−p0+5q0≥05−3x0−x1−x2−2x3−3y0−2y1−y2+2y3+5p0+7q0≥04−x0−x1+x2−y1+y2+2q0≥03x0−x1−3x2−2x3−y2+y3+2p0+4q0≥03x0−x1+x3−y0+y1+2y2−y3+p0+q0≥03−x2+x3−y0−y1−y2−y3+p0+3q0≥02−x0−x1−3x2+x3−2y0+2y1−2y2+y3+4p0+4q0≥02x0+2x2−y0−3y1−y2+2p0+2q0≥02−x0−x1−3x2+x3−y0+y2+y3+2p0+3q0≥02−x1−x2−x3−y1+y2−y3+p0+3q0≥012x0+x1+2x3−y0−y2−y3−p0+2q0≥01x0−x2+x3−y0−y1+2y2+2y3+2p0≥01Total927


### 3.2. Analysis of Improved SKINNY-64 Four-Round MILP Model

After improving the model, the 1st round of SKINNY-64 difference analysis process contains 816 constraint inequalities and 320 variables. Therefore, SKINNY-64 four round differential trail MILP analysis model contains a total of 2928 constraint inequalities and 944 variables.After the improvement, the optimal differential trail for SKINNY-64 4-round can be found directly. When the minimum number of S-box number in the 4-round is 4, the maximum probability of 4 optimal difference trails is 2−16, which just satisfies the upper bound of the differential probability in the 4-round is shown in Figure 3. The experimental results show that the average successful search time is 19.8945s, which is only 3.848s more than the former (the main configuration of the computer: Intel i7 8700, CPU frequency 3.2 GHz, memory 32G, hard disk 2 TB 7200RPM + 512 GB SSD). Obviously, compared with the previous method, this direct search method has advantages in low rounds.Figure 3
Four 4-round SKINNY-64 optimal differential trails searched after improving the model.


## 3.1. New S-Box Differential Characteristic Based on Improved MILP Model

The improved MILP model is mainly to modify the S-box differential feature analysis of the above model, add probability coding information to the optimized MILP model, and reconstruct the S-box differential characteristic.Each valid differential characteristic of 16 S-boxesx4i,...,x4i+3,yi,...,y4i+3,i∈0,...,15, in the 1st round is combined with the corresponding probability information coding, to construct a new difference pattern x4i,...,x4i+3,yi,...,y4i+3,pi,qi∈ℝ10.The coding method of probability information is shown in Table 6:Table 6
Probability information coding.
pi,qiPrx4i,...,x4i+3,yi,...,y4i+3,i∈0,...,15(0, 0)2−0(0, 1)2−2(1, 1)2−3According to Table6, the probability information of the S-box differential characteristic can be expressed as 2−pi+2qi. The main idea of the improved method lies in the constraint of S-box difference mode and the choice of objective function. The constraints of the improved S-box model are combined with the coding information of the difference probability, which is closely related to the probability of the difference trail.So, set the objective function to(3)min∑i=0i=63pi+2qi.Although the S-box difference mode is changed after the probability coding information is added, the solution method is the same. Ninety seven new differential characteristics are available with the addition of probabilistic coding information, as shown in Table7:Table 7
All possible new differential characteristics for 1st round of SKINNY-64 S-box.
25 effective truncation inequalitiesNumber of invalid difference modes removed/inequalities−x0−x1−x3−y0+y2−y3−p0+5q0≥0484−2x1−x2−x3−2y1−y2−y3+4p0+4q0≥0127x1+x2+y0+y1−p0−q0≥097x1−x2+x3−3y0−y1+2p0+2q0≥062x0−2x1−4x2−x3+y1+2y2+3y3+5p0+q0>=030x0+2x1+x2+y0−p0−q0≥0242x2+y0+y1+y2−p0−q0≥020−x2+2y0+y1−y2+2y3−p0+q0≥016−3x0+3x1+x2+3x3−2y0+2y1−2y2−y3+5p0+2q0≥011x2+y1−p0≥08−3x1+2y0−y1+y2−y3+2p0+2q0≥073x0+2x1+x2+2x3−y0−y2−p0≥06x1+y0−p0≥06−2x0+x1−2x3−y0+2y1−y3−p0+5q0≥05−3x0−x1−x2−2x3−3y0−2y1−y2+2y3+5p0+7q0≥04−x0−x1+x2−y1+y2+2q0≥03x0−x1−3x2−2x3−y2+y3+2p0+4q0≥03x0−x1+x3−y0+y1+2y2−y3+p0+q0≥03−x2+x3−y0−y1−y2−y3+p0+3q0≥02−x0−x1−3x2+x3−2y0+2y1−2y2+y3+4p0+4q0≥02x0+2x2−y0−3y1−y2+2p0+2q0≥02−x0−x1−3x2+x3−y0+y2+y3+2p0+3q0≥02−x1−x2−x3−y1+y2−y3+p0+3q0≥012x0+x1+2x3−y0−y2−y3−p0+2q0≥01x0−x2+x3−y0−y1+2y2+2y3+2p0≥01Total927


## 3.2. Analysis of Improved SKINNY-64 Four-Round MILP Model

After improving the model, the 1st round of SKINNY-64 difference analysis process contains 816 constraint inequalities and 320 variables. Therefore, SKINNY-64 four round differential trail MILP analysis model contains a total of 2928 constraint inequalities and 944 variables.After the improvement, the optimal differential trail for SKINNY-64 4-round can be found directly. When the minimum number of S-box number in the 4-round is 4, the maximum probability of 4 optimal difference trails is 2−16, which just satisfies the upper bound of the differential probability in the 4-round is shown in Figure 3. The experimental results show that the average successful search time is 19.8945s, which is only 3.848s more than the former (the main configuration of the computer: Intel i7 8700, CPU frequency 3.2 GHz, memory 32G, hard disk 2 TB 7200RPM + 512 GB SSD). Obviously, compared with the previous method, this direct search method has advantages in low rounds.Figure 3
Four 4-round SKINNY-64 optimal differential trails searched after improving the model.


## 4. Conclusion

In this paper, mainly analyze all SKINNY-64 versions’ differential trails under single-key setting. During the differential analysis, the key is assumed to be fixed, the round key difference is not considered, and only the state difference is considered. Therefore, the MILP model of all SKINNY-64 versions can be uniformly constructed. The state difference process of SKINNY is equivalently abstracted by specific constraints and variables to construct a MILP model. In order to improve the operation efficiency, the MILP model was optimized from two aspects: on the one hand, reducing the number of constraint inequalities, and on the other hand, reducing the number of variables. The optimized model reduces the number of constraints by 2912 and the number of variables by 64. However, the optimal trail cannot be searched directly in this scenario. In order to search the optimal trail more accurately, the MILP model is improved. The differential features of the S-box are reconstructed by adding the differential probability coding information of the S-box, and the model under the new difference mode of the S-box is obtained. Finally, the optimal difference trail of skinny-64 4-round is searched successfully. Our model has obvious advantages in searching the low rounds of SKINNY-64 the optimal differential trails under single-key setting.



---

*Source: 6789281-2020-06-22.xml*