Research Article  Open Access
Pei Zhang, Wenying Zhang, "Differential Cryptanalysis on Block Cipher Skinny with MILP Program", Security and Communication Networks, vol. 2018, Article ID 3780407, 11 pages, 2018. https://doi.org/10.1155/2018/3780407
Differential Cryptanalysis on Block Cipher Skinny with MILP Program
Abstract
With the widespread use of RFID technology and the rapid development of Internet of Things, the research of lightweight block cipher has become one of the hot issues in cryptography research. In recent years, lightweight block ciphers have emerged and are widely used, and their security is also crucial. Skinny64/192 can be used to protect data security such as the applications of wireless multimedia and wireless sensor networks. In this paper, we use the new method to verify the security of Skinny64/192. The method is called mixedinteger linear programming (MILP) which can characterize precisely the linear operation and nonlinear operation in a round function. By applying MILP program, we can automatically find a 11round differential characteristic for Skinny64/192 with the minimum number of active sboxes. The probability of differential trail is , that is, far greater than which is the probability of success for an exhaustive search. In addition, comparing this method with the one proposed by Sun et al., we also have a great improvement; that is, no new variables will be added in ShiftRows operation. It can reduce greatly the number of variables and improve the running speed of the computer. Besides, the experimental result proves that Skinny64/192 is safe on 11round differential analysis and validates the effectiveness of the MILP method.
1. Introduction
Nowadays, with the development of big data and artificial intelligence technology, data security problem becomes increasingly serious. The problem of data security exists in the whole life cycle of data, from data collection and transfer to data usage, with the focus on data confidentiality [1, 2], integrity, and availability. Due to the continuous occurrence and intensification of data leakage events on the Internet, the confidentiality of data is particularly important. The confidentiality of data, on the one hand, is the direct protection of data and, on the other hand, is providing further privacy protection on the basis of leaks. From a technical point of view, to ensure the confidentiality of data without hindering the availability of data, the general approach is to encrypt the data by encryption algorithms.
The traditional encryption algorithms are DES [3] and AES [4]; they are widely used in the field of hardware and software. The hardware applications include data security in radio frequency IC card and encryption of hard disk data. And the software applications include voice, video information encryption, and database data encryption. The most classic applications are security applications on wireless network: one is the IEEE 803.11 protocol for WLAN and the IEEE 803.16 protocol for WMAN, and the other is the ZigBee protocol. The application of these encryption algorithms ensures the security of data effectively.
At present, the traditional cryptographic algorithm for encrypting wireless multimedia data faces a lot of challenges, such as fast resource consumption, high implementation cost, and other disadvantages. In this context, lightweight block cipher emerged. Compared with traditional cryptographic algorithms, lightweight block ciphers run faster and have lower resource consumption and implementation costs while ensuring data security. They are more suitable for radio frequency identification (RFID) tags, wireless sensor network (WSN) [5], wireless multimedia, and other micro devices. In recent years, many lightweight block ciphers have been proposed, such as PRESENT [6], PRINCE [7], Midori [8], and Skinny [9, 10], many of which have been defined as ISO standards and widely used in various fields.
Skinny is a family of tweakable lightweight block ciphers proposed by Beierle et al. at CRYPTO in 2016. It is a Substitution Permutation Network (SPN) [11, 12] structure. It supports two block lengths n=64 or 128 bits and for each of them, the tweakey t can be either n, 2n, or 3n. Skinny has been analyzed by many methods since it was proposed, such as impossible differential cryptanalysis [10] and relatedkey impossible differential attack [13].
Differential cryptanalysis [3, 13, 14] was firstly introduced by Biham and Shamir to analyze DES block cipher in 1990. Differential analysis is one of the most effective attack methods in block ciphers. Differential analysis is a selective plaintext attack, and its basic idea is to study the probability of differential propagation of specific plaintext differential values in the encryption process. We separate the block cipher from the permutation area and then carry out the key recovery attack on this basis. In other words, we find a high probability differential trail. Finally, by adding several rounds before and after the differential characteristic, guessing Roundkeys used in these rounds, encrypting plaintexts, and decrypting ciphertexts, we can determine the right key of block cipher.
Mixedinteger linear programming (MILP) [14, 15] is a mathematical optimization or feasibility scheme, where some or all variables are limited to integers. In many cases, the term refers to an integer linear program (ILP), which is linear in terms of objective function and constraint except for the integer constraint. MILP is frequently used in business and economics to solve problems of optimization.
In [14], Mouha et al. proposed an automatic search method based on MILP. However, the drawback of this method is that the proposed constraint cannot describe the trail of the differential propagation of the linear diffusion layer. Besides, Sun et al. [15] perfected the MILP method, then combined the MILP method and differential analysis into PRESENT, and finally obtained satisfactory experimental results. In this paper, we apply the new MILP method to obtain a lower bound on the number of active sboxes for differential cryptanalysis. Then, we use the maximum differential probability of the sboxes to derive an upper bound for the probability of the best characteristic.
The Organizational of the Paper. The paper is organized as follows: In Section 2, we introduce some basic properties and definitions and describe how to construct a MILP program by constraints to get the minimum number of active sboxes and the corresponding trail of differential propagation. In Section 3, the MILP program is constructed to search the differential trail of Skinny64/192. Through specific instances, the optimal solution of the minimum number of active sboxes is obtained for 11round differential characteristic of Skinny64/192. We conclude the paper and look forward to the future work in Section 4. The auxiliary materials are given in Appendix.
Our Contributions. In this paper, we apply a method proposed recently for obtaining a high probability of differential characteristic in Skinny64/192 called MILP method, which is used to search the minimum number of active sboxes automatically. Its minimum number of active sboxes is 54 of 11round differential characteristic. The number of active sboxes is one of the commonly used methods for evaluating the security of symmetric key encryption schemes against differential attack. As far as we know, this is the first time to combine differential analysis with MILP method to be applied to Skinny64/192.
MILP can characterize accurately the linear operation and nonlinear operation in the round function. Then a high probability of 11round differential characteristic is automatically searched. The probability of differential trail is , that is, far greater than which is the probability of success for an exhaustive search. This experimental result proves that 11round differential analysis of Skinny64/192 is safe, which can provide a safe reference for data encryption on wireless devices. At the same time, we also verified the effectiveness of MILP method through this experiment. In addition, we also have an improvement on MILP program; that is, no new variables can be added in ShiftRows operation, which can reduce the number of total variables greatly and improve the running speed of the computer.
2. The Minimum Number of Active SBoxes for Differential Cryptanalysis
In this section, we will describe how to construct the MILP program to calculate the number of active sboxes for differential analysis. This requires an accurate description of the nonlinear layers and linear layers in order to ensure the number of active sboxes is minimum. In general, if a large number of active sboxes exist, which indicates that the differential diffusion is fast, this suggests that the cryptographic algorithm is not vulnerable to attacks and has a high security. The core theorem for constructing the MILP program will be described in detail in the following.
2.1. Differential Cryptanalysis
Definition 1. For every input bitlevel difference, a 01 variable is introduced such that if and only if the difference at this bit is nonzero, as
2.2. Constraints for Nonlinear and Linear Operation
Generally, the SPNstructured encryption algorithm consists of sbox, XOR, ShiftRows, and MixColumn operations. In this subsection, we describe these four basic operations by constraints. Based on this, we can construct an rround inequality model for a specific encryption algorithm. This model can describe the trail of differential propagation accurately. Then by selecting the appropriate objective function, we can convert this model into a MILP program, using this MILP program to search automatically for the objective function.
Constraints Describing the SBox Operation [15]. Suppose and are the input and output bitlevel differences of a w×v sbox marked by . Firstly, to ensure that holds if and only if are not all zero, we require the following.For bijective sboxes, nonzero input difference must result in nonzero output difference and vice versa.
Constraints Describing the XOR Operation. The bitwise input difference is and the corresponding bitwise output difference is y for the XOR operation. The following linear constraints describe the relation between the input and output difference.
Constraints Describing the ShiftRows or ShuffleCell Operation. For every ShuffleCell operation, its input difference () and output difference are based on bit. If (), the constraints include the following.
Constraints Describing the MixColumn Operation. Let () and () be the input and output bitwise differences for the MixColumn operation. Suppose ; it is essential to set an intermediate variable u and let to get , so the constraints can be described as follows.
Definition 2 (the objective function [16]). Some notations for differential are used in the model; e.g., denotes the activity of an sbox and the objective function is as follows.The smaller the number of active sboxes is, the slower the differential diffusion is. This illustrates that the encryption algorithm will be attacked in more rounds, and this will threaten its security.
3. Constructing the MILP Program to Calculate the Minimum Number of Active SBoxes of Skinny64/192
It is well known that the security of an encryption algorithm must be evaluated before being put into use. In this section, we use the newly proposed MILP method to evaluate the security of Skinny64/192 on differential analysis. This is the first time to combine differential analysis with MILP method to be applied to Skinny64/192; the method is called MILP program. The MILP program can automatically obtain the minimum number of active sboxes on the 11round differential analysis. And MILP program consists of inequalities which can describe precisely the linear and nonlinear operation.
3.1. Description of Skinny64/192
Skinny is a family of tweakable lightweight block ciphers proposed by Beierle et al. at CRYPTO in 2016. The specifications for Skinny was given in [9]. Skinny64/192 provides 64bit block length and 192bit key length. We now give a short description of Skinny64/192. Skinny64/192 uses the SPN structure with Midori64like state. The state is arranged in a 4 × 4 matrix.Every cell is a nibble, .
The round function consists of SubCell, AddConstants, AddRoundTweakey, ShiftRows, and MixColumn. Since SubCell, ShiftRows, and MixColumn operations have an effect on differential diffusion, we only illustrate these operations in the paper. For more details, please refer to [9].
SubCells (SC). The 4×4 sbox defined in Table 1 is applied to each nibble in the state.

ShiftRows (SR). The rows of the state are rotated as in AES but to the right, i.e., the cell permutation is specified as follows.
MixColumn (MC). Each column in the state is multiplied by a binary matrix MC. MC is given as follows.
Tweakey Schedule. Skinny64/192 tweakey is updated through tweakey schedule. bits, and TK1 = TK2 = TK3 = 64 bits which be permuted by . Then, each cell in the first and second rows of TK2, TK3 is updated using LFSR operations shown in [10].
In Figure 1, represent the ith round state, respectively. represent a nibble of the state, respectively. Let () and () be the input and output bitwise differences in a round for Skinny64/192, and , and .
From the overall design of Skinny64/192, its structure is compact and has the advantages of low delay, high throughput, and low number of gate circuits in hardware implementation. Therefore, Skinny64/192 is more suitable for wireless multimedia and other micro device applications. Now, we apply the new MILP method to get the lower limit of the number of active sboxes for the differential analysis of Skinny64/192. Then, we use the maximum difference probability of the sbox to derive the upper bound of the best characteristic probability. Finally, the experimental results are used to determine whether Skinny64/192 is safe on differential analysis.
3.2. Employing MILP’s Method for Specific Operation
3.2.1. Compact Constraints for DDT of SBox
In Skinny64/192, combined with the Table 2, y = s(x), , it is possible to list the following vectors according to the input differential of 0001: , , , . Similarly, we can get all the differential vectors, so we get the input of SageMath [17].Running SageMath will output 202 inequalities. Then, the redundant inequalities are eliminated through a specific streamlined procedure (Appendix). Finally, the s1box can be accurately characterized with 24 inequalities. The inequality of describing s1 is shown as follows.A round of 16 sboxes can be characterized by 384 linear inequalities accurately. . , represent 4 bits. X_{0} and Y_{0} are input and output of s1, respectively.

In contrast, it is simple to construct constrains for the ShiftRows operation of Skinny64/192. Referring to (5), the ShiftRows operation can be characterized precisely by the next 64 constraint equations. .In the ShiftRows operation, comparing with the method in [15], we also make a great improvement in which no new variables will be added. It reduces the number of variables greatly and improves the running speed of the computer. In this case, we can reduce the use of 64 variables in one round. Therefore, the variable Z can be omitted.
3.2.2. Compact Constraints for the Linear Transform
In linear layer, MixColumn operations are the most difficult to be described utilizing the novel technique, but in this work, we can introduce an intermediate variable U to solve the problems. This operation is broken down into the following steps.
Step 1. Convert the matrix MC_{4×4} to MC_{16×16} of Skinny64/192.
Step 2. After the MixColumn, we can get the value of , in which . For example .
Step 3. We introduce the intermediate variable U, u_{0} = y_{40} + y_{52}, and then x_{64} = y_{0} + u_{0}. Combining (4) and (6), the constraints between them can be expressed as follows.In a round, we need to use 16 intermediate variables, , .
3.3. Calculate the Minimum Number of Active SBoxes
In the MILP program, we must add a linear constraint to ensure that at least one sbox is active. The setting of objective function refers to (7). And all variables must be binary variable. In order to optimize the MILP model, we also need CPLEX [18] tool. Finally, we obtain the minimum number of active sboxes which is 54 for 11round differential analysis of Skinny64/192. In Table 3, the differential distribution table of sbox of Skinny64/192 is presented.

First, the s1box of Skinny64/192 is set as an active sbox with the input difference of 1001. And the probability of obtaining the second round of input difference is 2^{−2}, and the number of active sboxes is 3. By analogy, the output difference of the 11th round has an active sbox which is 1000. The total probability of the 11 round differential characteristic is 2^{−147}. The minimum number of the active sboxes is 54 for 11 rounds of Skinny64/192. The details are shown in Table 4.

According to Table 4, we can get a specific probability for each round of 11round differential characteristic for Skinny64/192 in Figure 2. The probability of differential trail is 2^{−147}, that is, far greater than 2^{−192} which is the probability of success for an exhaustive search.
The experimental result leads us to obtain the minimum number of active sboxes which is 54 for the 11round differential trail. Since the same number of rounds is attacked, the minimum active sboxes number of the Skinny64/192 is bigger than that of ENOCORO128v2, PRESENR80. This not only illustrates that Skinny64/192 is relatively safe, but also can be implemented in hardware to protect the safety of data. The bigger the number of active sboxes, the faster the differential diffusion; the security of cryptographic algorithm is relatively higher.
The MILP program corresponding to Skinny64/192’s 11round differential trail consists of 7440 constraints and 1680 binary variables including 1520 continuous variables and 160 intermediate variables. Compared with Sun et al., our improvement reduced the use of 640 continuous variables in total and improved the speed of the computer. The experiments are implemented on a 64bit operating system, Intel Core i77700 CPU @ 3.60GHz, with 16GB of RAM.
4. Conclusion
In this paper, a new result is obtained on the differential analysis of lightweight block cipher Skinny64/192. We get a 11round differential characteristic with minimum active sboxes. The minimum number of active sboxes is 54. The probability of 11round differential trail is 2^{−147}, that is, far greater than 2^{−192} which is the probability of success for an exhaustive search.
The experimental result not only proves that Skinny64/192 cannot resist 11round differential analysis and validates the effectiveness of MILP method, but also has other important reference values. First, the lightweight block cipher Skinny64/192 is relatively secure and can be used on wireless multimedia devices to protect data security. Second, Skinny64/192 can resist 11round differential analysis, so it can be used as a candidate encryption algorithm for differential privacy protection technology. Finally, by verifying the effectiveness of MILP method on differential analysis, the method can significantly reduce the workload of cryptanalysts. Besides, MILP method can be applied to more cryptanalysis, such as relatedkey differential analysis, impossible differential analysis, and relatedkey impossible differential analysis. We believe that there will be greater gains.
Appendix
The specific streamlined procedure to select certain number of inequalities (see Algorithm 1).

Data Availability
The data used to support the findings of this study are available from the corresponding author upon request.
Conflicts of Interest
The authors declare that they have no conflicts of interest.
Acknowledgments
This work is partially supported by National Natural Science Foundation of China (Nos. 61672330, 61602287, and 61802235), the Key Research Development Project of Shandong Province (No. 2016GGX101024), China Postdoctoral Science Foundation (2018M632712), the Key Research and Development Plan of Shandong Province (2018GGX101037), and the Major Innovation Project of Science and Technology in Shandong Province (2018CXGC0702).
References
 L. S. Melro and L. R. Jensen, “Influence of functionalization on the structural and mechanical properties of graphene,” Computers, Materials and Continua, vol. 53, no. 2, pp. 111–131, 2017. View at: Google Scholar
 Z. Pan, J. Lei, Y. Zhang, and F. L. Wang, “Adaptive fractionalPixel motion estimation skipped algorithm for efficient HEVC motion estimation,” ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), vol. 14, no. 1, pp. 1–19, 2018. View at: Google Scholar
 E. Biham and A. Shamir, “Differential cryptanalysis of DESlike cryptosystems,” Journal of Cryptology, vol. 4, no. 1, pp. 3–72, 1991. View at: Publisher Site  Google Scholar
 J. Daemen and V. Rijmen, The Design of Rijndael: AESThe Advanced Encryption Standard, Springer, Berlin, Germany, 2002. View at: Publisher Site  MathSciNet
 G. Cheng, C. Yang, X. Yao et al., “When Deep Learning Meets Metric Learning: Remote Sensing Image Scene Classification via Learning Discriminative CNNs,” IEEE Transactions on Geoscience & Remote Sensing, vol. 99, pp. 1–11, 2018. View at: Google Scholar
 M. H. Faghihi Sereshgi, M. Dakhilalian, and M. Shakiba, “Biclique cryptanalysis of MIBS80 and PRESENT80 block ciphers,” Security and Communication Networks, vol. 9, no. 1, pp. 27–33, 2016. View at: Publisher Site  Google Scholar
 J. Borghoff, A. Canteaut, T. Güneysu et al., “PRINCE – A LowLatency Block Cipher for Pervasive Computing Applications,” in Advances in Cryptology – ASIACRYPT 2012, vol. 7658 of Lecture Notes in Computer Science, pp. 208–225, Springer Berlin Heidelberg, Heidelberg, Germany, 2012. View at: Publisher Site  Google Scholar
 S. Banik, A. Bogdanov, T. Isobe et al., “Midori: a block cipher for low energy,” in Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Lecture Notes in Comput. Sci., pp. 411–436, Springer Berlin, 2014. View at: Google Scholar
 C. Beierle, J. Jean, Moradi A. et al., “The SKINNY Family of Block Ciphers and Its LowLatency Variant MANTIS,” in Proceedings of the Part II, of the 36th Annual International Cryptology Conference on Advances in CryptologyCRYPTO, vol. 9815, pp. 123–153, SpringerVerlag, 2016. View at: Google Scholar  MathSciNet
 M. Tolba, A. Abdelkhalek, and A. M. Youssef, “Impossible Differential Cryptanalysis of ReducedRound SKINNY,” 2017. View at: Google Scholar
 G. Han and W. Zhang, “Improved biclique cryptanalysis of the lightweight block cipher piccolo,” Security and Communication Networks, vol. 2017, 2017. View at: Google Scholar
 Y. Zheng, B. Jeon, and L. Sun, “Student’s tHidden Markov Model for Unsupervised Learning Using Localized Feature Selection,” IEEE Transactions on Circuits & Systems for Video Technology, vol. 99, no. 11, 2017. View at: Google Scholar
 R. Ankele, S. Banik, A. Chakraborti et al., “Relatedkey impossibledifferential attack on reducedround Skinny,” in Applied Cryptography and Network Security, vol. 10355 of Lecture Notes in Comput. Sci., pp. 208–228, Springer, Cham, 2017. View at: Publisher Site  Google Scholar  MathSciNet
 N. Mouha, Q. Wang, D. Gu, and B. Preneel, “Differential and linear cryptanalysis using mixedinteger linear programming,” in Information Security and Cryptology, pp. 57–76, Springer, 2012. View at: Google Scholar
 S. Sun, L. Hu, P. Wang et al., “Automatic Security Evaluation and (Relatedkey) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES (L) and Other BitOriented Block Ciphers, ASIACRYPT,” 2014. View at: Google Scholar
 L. Sun, W. Wang, R. Liu, and M. Wang, “MILPaided bitbased division property for ARX ciphers,” Science China Information Sciences, vol. 61, no. 11, Article ID 118102, 2018. View at: Google Scholar  MathSciNet
 R. A. Mezei, An Introduction to SAGE Programming: With Applications to SAGE Interacts for Numerical Methods, Inc, 2015.
 “Division C.: Using the CPLEX Callable Library,” 1997. View at: Google Scholar
Copyright
Copyright © 2018 Pei Zhang and Wenying Zhang. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.