Cryptology ePrint Archive: Report 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, 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.

Category / Keywords: Automatic cryptanalysis, Related-key differential attack, Mixed-integer Linear Programming, Convex hull, SIMON

Date: received 17 Feb 2015, last revised 19 Feb 2015

Contact author: sunsiwei at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20150226:120156 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]