Applying MILP Method to Searching Integral Distinguishers Based on Division Property for 6 Lightweight Block Ciphers
Division property is a generalized integral property proposed by Todo at EUROCRYPT 2015, and very recently, Todo et al. proposed bit-based division property and applied to SIMON32 at FSE 2016. However, this technique can only be applied to block ciphers w
- PDF / 505,710 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 9 Downloads / 189 Views
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China {xiangzejun,zhangwentao,baozhenzhen,ddlin}@iie.ac.cn 2 University of Chinese Academy of Sciences, Beijing, China
Abstract. Division property is a generalized integral property proposed by Todo at EUROCRYPT 2015, and very recently, Todo et al. proposed bit-based division property and applied to SIMON32 at FSE 2016. However, this technique can only be applied to block ciphers with block size no larger than 32 due to its high time and memory complexity. In this paper, we extend Mixed Integer Linear Programming (MILP) method, which is used to search differential characteristics and linear trails of block ciphers, to search integral distinguishers of block ciphers based on division property with block size larger than 32. Firstly, we study how to model division property propagations of three basic operations (copy, bitwise AND, XOR) and an Sbox operation by linear inequalities, based on which we are able to construct a linear inequality system which can accurately describe the division property propagations of a block cipher given an initial division property. Secondly, by choosing an appropriate objective function, we convert a search algorithm under Todo’s framework into an MILP problem, and we use this MILP problem appropriately to search integral distinguishers. As an application of our technique, we have searched integral distinguishers for SIMON, SIMECK, PRESENT, RECTANGLE, LBlock and TWINE. Our results show that we can find 14-, 16-, 18-, 22- and 26-round integral distinguishers for SIMON32, 48, 64, 96 and 128 respectively. Moreover, for two SP-network lightweight block ciphers PRESENT and RECTANGLE, we found 9-round integral distinguishers for both ciphers which are two more rounds than the best integral distinguishers in the literature [22, 29]. For LBlock and TWINE, our results are consistent with the best known ones with respect to the longest distinguishers. Keywords: MILP SIMON · SIMECK
1
· Division property · Integral cryptanalysis · · PRESENT · RECTANGLE · LBlock · TWINE
Introduction
Programming problem is a mathematical optimization which aims to achieve the minimal or maximal value of an objective function under certain constraints, and c International Association for Cryptologic Research 2016 J.H. Cheon and T. Takagi (Eds.): ASIACRYPT 2016, Part I, LNCS 10031, pp. 648–678, 2016. DOI: 10.1007/978-3-662-53887-6 24
Applying MILP Method to Searching Integral Distinguishers
649
it has a wide range of applications from industry to academic community. Mixed Integer Linear Programming (MILP) is a kind of programming problem whose objective function and constraints are linear, and all or some of the variables involved in the problem are restricted to be integers. In recent years, MILP has found its applications in cryptographic community. Mouha et al. [11] and Wu et al. [21] applied MILP method to automatically count differential and linear active Sboxes for word-based block ci
Data Loading...
