Research On Cryptananlysis Of Symmetric Cipher Using Mixed Integer Linear Programming

Mixed Integer Linear Programming(MILP)is a class of problems to find the maximum or minimum value of an objective function under certain linear constraints.In recent years,MILP problems have been widely used in cryptanalysis and have become a powerful tool for automat-ed analysis of symmetric ciphers.In MILP model-based cryptanalysis,a core mathematical problem is to inscribe linear inequalities on the cryptographic properties of the core components of a cryptographic algorithm,give the constraints between them,and then solve them using software such as Gurobi,Cplex,etc.This paper mainly studies the symmetric cryptanalysis method based on mixed integer line-ar programming,using MILP tools to analyze several symmetric cryptographic algorithms and design a lightweight tweakable block cipher based on this basis.The specific cryptanalysis methods used include differential cryptanalysis,related-key differential cryptanalysis,impossible differential cryptanalysis and integral cryptanalysis.The block ciphers involved include AES,PRINCE,Midori,GIFT,and the new algorithm RAIN designed in this article.The main contri-butions are as follows:(1)In the view of the influence of the round constant on the validity of the differential characteristics in the SPN block cipher,the invalid differential characteristics are proved by the method of solving a system of equations and automatic search method based on MILP,and find the real valid differential characteristics.Many lightweight block ciphers employ a very simple key schedule in which the round keys only differ by addition of a round specific constant.By taking AES,PRINCE and Midori as ex-amples,we find that there are no feasible solutions to these inequalities by equivalently repre-senting the encryption process of two plaintexts by a system of linear programming inequalities and solving the inequalities to verify that some differential characteristics are actually invalid.The difference property of the 4-uniform S-box is also used to establish a system of equations that satisfies the connection between two plaintext several rounds encryption operations for a given difference,and it is shown that the system of equations has no solution,revealing the mathematical essence behind the existence of invalid differential characteristics.It is found that a reasonable choice of round constants not only reduces the symmetry of encryption but also makes some differential characteristics invalid for any key,and such differ-ential characteristics are called Zelig Differential Characteristic.The method of solving the sys-tem of equations and automated MILP-based search can also be used to check the validity of other SPN(Substitution-Permutation Networks)block cipher differential characteristics using simple key schedule.When characterizing the MILP model of the encryption algorithm,consid-ering the key schedule and the round constant,the real valid differential characteristics of 3 and 4rounds of PRINCE block cipher are found,which can be used for the differential cryptanalysis of PRINCE block cipher.(2)The related-key differential cryptanalysis for the reduced-round GIFT block cipher improves the number of rounds analyzed and reduces the data complexity of the key re-covery attack compared with the previous differential analysis results.GIFT is a lightweight block cipher proposed by Banik et al.at CHES2017,which is an im-proved version of the PRESENT block cipher,a Mini version of PRESENT.Compared with PRESENT,GIFT has greatly improved the efficiency of both hardware and software implemen-tation(smaller hardware area and faster encryption),and discarded the security flaws of PRESENT.In this paper,we use the related-key differential cryptanalysis method based on MILP tool to analyse GIFT.We propose 12-round and 13-round related-key differential charac-teristics of GIFT-64 and 7-round and 10-round related-key differential characteristics of GIFT-128.By using them as distinguishers,we apply key recovery attacks on the 19-round and20-round reduced GIFT-64 with data complexities of 2⁴⁷ and 2⁵⁶ plaintexts,respectively,which mean that the data complexities are lower.Furthermore,we improve the GIFT-64 key recovery attack using differential cryptanalysis by one round over the previous differential cryptanalysis.(3)The lightweight block cipher algorithm RAIN is designed and the algorithm secu-rity is self-evaluated.Combining the understood block cipher algorithms and accumulated knowledge of crypta-nalysis,a lightweight block cipher oriented to hardware and software and threshold implementa-tion is designed and named as RAIN,which reflects the lightness of the algorithm software and hardware implementation cost.The lightweight block cipher RAIN proposed in this paper is based on the SPN structure widely used in international block cipher design.It provides strong avalanche utility through iterative confusion layer S-box and diffusion layer,which not only guarantees strong security,but also takes into account the implementation of software and hard-ware.The algorithm supports 64-bit block and 128-bit block.Two different block lengths are implemented using the same round function structure,and the scheme is simple and beautiful.The confusion layer is implemented using a 4-bit S-box.When the S-box is implemented,not only its security is considered,but also the software and hardware implementation of the S-box is considered.The hybrid operation of the diffusion layer provides high implementation perfor-mance.We evaluated the algorithm and give differential analysis,impossible differential analysis,integral attack and invariant subspace analysis.In the process of analysis,we used automated search tools.Our algorithm can resist the existing attack,and has greater safety redundancy.RAIN algorithm is efficient on software and hardware implementation,and it has excellent per-formance on PC,ARM platform and hardware FPGA platform.The threshold mask of the S-box of the algorithm is low in cost and has strong ability to resist side-channel attacks.