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
-
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},
url = {https://eprint.iacr.org/2015/122}
}