Paper 2015/122

Constructing Mixed-integer Programming Models whose Feasible Region is Exactly the Set of All Valid Differential Characteristics of SIMON

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

Abstract

In IACR ePrint 2014/747, a method for constructing mixed-integer linear programming (MILP) models whose feasible regions are exactly the sets of all possible differential (or linear) characteristics for a wide range of block ciphers is presented. These models can be used to search for or enumerate differential and linear characteristics of a block cipher automatically. However, for the case of SIMON (a lightweight block cipher designed by the U.S. National Security Agency), the method proposed in IACR ePrint 2014/747 is not {\it exact} anymore. That is, the feasible region of the MILP model constructed for SIMON contains invalid differential characteristics due to the dependent input bits of the AND operations, and these invalid characteristics must be filtered out by other methods. This is a very inconvenient process and reduces the level of automation of the framework of MILP-based automatic differential analysis. In this paper, by using quadratic constraints or constraints from the H-representation of a specific convex hull, we give a method for constructing mixed-integer (non)linear programming models whose feasible regions are exactly the sets of all valid differential characteristics for SIMON. The technique presented in this paper may be also useful for other ciphers. How to construct an MILP model whose feasible region is exactly the set of all linear characteristics of SIMON is still an open problem.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Automatic cryptanalysisRelated-key differential attackMixed-integer Linear ProgrammingConvex hullSIMON
Contact author(s)
sunsiwei @ iie ac cn
History
2015-02-26: received
Short URL
https://ia.cr/2015/122
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/122,
      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 = {Constructing Mixed-integer Programming Models whose Feasible Region is Exactly the Set of All Valid Differential Characteristics of SIMON},
      howpublished = {Cryptology ePrint Archive, Paper 2015/122},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/122}},
      url = {https://eprint.iacr.org/2015/122}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.