International Association
for Cryptologic Research

In this paper, we investigate the Mixed-integer Linear Programming (MILP) modelling of the differential and linear behavior of a wide rang of block ciphers.

The differential and linear behavior of the transformations involved in a block cipher can be described by a set $P \\subseteq \\{0,1\\}^n \\subseteq \\mathbb{R}^n$.

We show that $P$ is exactly the set of all 0-1 solutions of the H-representation of the convex hull of $P$. In addition, we can find a small number of inequalities in the H-representation of the convex hull of $P$ such that the set of all 0-1 solutions of these inequalities equals $P$.

~~~~~~Based on these discoveries 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 is able to obtain characteristic enjoying higher probability or covering more rounds of a cipher with less computational effort.

~~~~~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 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 implemented and extensive experiments are performed. To demonstrate the usefulness of these methods, we apply them to SIMON, PRESENT, Serpent, LBlock, DESL, and we obtain improved cryptanalytic results. For example, we find single-key differentials covering 16 and 22 rounds of SIMON48 and SIMON64 (block ciphers designed by the U.S. National Security Agency) respectively. These are the longest differentials for SIMON48 and SIMON64 published so far.