Automatic Security Evaluation and (Related-key) Differential Characteristic Search:

Abstract. In this paper, we propose two systematic methods to describe the differential property of an S-box with linear inequalities based on log-ical condition modelling and computational geometry. In one method, in-equalities are generated according to some conditional differential prop-erties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-Integer Linear Programming (MILP) technique, we propose an automatic method for evaluating the security of bit-oriented block ciphers against the (related-key) differential attacks, and several techniques for obtaining tighter security bounds. we success-fully prove that 24-round PRESENT-80 is secure enough to resist against standard related-key differential attacks, and the probability of the best related-key differential characteristic of full LBlock is upper bounded by 2−60. These are the tightest security bound with respect to related-key differential attack published so far for PRESENT-80 and LBlock. Also, we present a new tool for finding (related-key) characteristics au-tomatically for bit-oriented block ciphers. Using this tool, we obtain new related-key characteristics for LBlock, DESL and PRESENT-128, which cover larger number of rounds or have larger probability than all previ-ously known results. The methodology presented in this paper is generic, automatic and ap-plicable to many bit-oriented block ciphers, including but not limited t