Paper 2014/747

Towards Finding the Best Characteristics of Some Bit-oriented Block Ciphers and Automatic Enumeration of (Related-key) Differential and Linear Characteristics with Predefined Properties

Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, and Kai Fu


In this paper, we investigate the Mixed-integer Linear Programming (MILP) modelling of the differential and linear behavior of a wide range of block ciphers. We point out that the differential behavior of an arbitrary S-box can be exactly described by a small system of linear inequalities. ~~~~~Based on this observation and MILP technique, we propose an automatic method for finding high probability (related-key) differential or linear characteristics of block ciphers. Compared with Sun {\it et al.}'s {\it heuristic} method presented in Asiacrypt 2014, the new method is {\it exact} for most ciphers in the sense that every feasible 0-1 solution of the MILP model generated by the new method corresponds to a valid characteristic, and therefore there is no need to repeatedly add valid cutting-off inequalities into the MILP model as is done in Sun {\it et al.}'s method; the new method is more powerful which allows us to get the {\it exact lower bounds} of the number of differentially or linearly active S-boxes; and the new method is more efficient which allows to obtain characteristic with higher probability or covering more rounds of a cipher (sometimes with less computational effort). ~~~~~Further, by encoding the probability information of the differentials of an S-boxes into its differential patterns, we present a novel MILP modelling technique which can be used to search for the characteristics with the maximal probability, rather than the characteristics with the smallest number of active S-boxes. With this technique, we are able to get tighter security bounds and find better characteristics. ~~~~~Moreover, by employing a type of specially constructed linear inequalities which can remove {\it exactly one} feasible 0-1 solution from the feasible region of an MILP problem, we propose a method for automatic enumeration of {\it all} (related-key) differential or linear characteristics with some predefined properties, {\it e.g.}, characteristics with given input or/and output difference/mask, or with a limited number of active S-boxes. Such a method is very useful in the automatic (related-key) differential analysis, truncated (related-key) differential analysis, linear hull analysis, and the automatic construction of (related-key) boomerang/rectangle distinguishers. ~~~~~The methods presented in this paper are very simple and straightforward, based on which we implement a Python framework for automatic cryptanalysis, and extensive experiments are performed using this framework. To demonstrate the usefulness of these methods, we apply them to SIMON, PRESENT, Serpent, LBlock, DESL, and we obtain some improved cryptanalytic results.

Note: Change log: Add method to find the best characteristics, rather than the characteristic with minimum number of active S-boxes

Available format(s)
Publication info
Preprint. MINOR revision.
Automatic cryptanalysisRelated-key differential cryptanalysisLinear cryptanalysisMixed-integer Linear ProgrammingConvex hullEnumeration
Contact author(s)
sunsiwei @ iie ac cn
2015-02-09: last of 7 revisions
2014-09-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Siwei Sun and Lei Hu and Meiqin Wang and Peng Wang and Kexin Qiao and Xiaoshuang Ma and Danping Shi and Ling Song and Kai Fu},
      title = {Towards Finding the Best Characteristics of Some Bit-oriented Block Ciphers and Automatic Enumeration of (Related-key) Differential and Linear Characteristics with Predefined Properties},
      howpublished = {Cryptology ePrint Archive, Paper 2014/747},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.