Paper 2013/676

Automatic Security Evaluation and (Related-key) Differential Characteristic Search : Application to PRESENT-80/128, LBlock, DES(L) and Other Bit-oriented Block Ciphers

Siwei Sun, Lei Hu, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Ling Song

Abstract

In this paper, we propose two systematic methods to describe the differential property of an S-box with linear inequalities based on logical condition modelling and computational geometry. In one method, inequalities are generated according to some conditional differential properties 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 successfully 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 automatically 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 previously known results. The methodology presented in this paper is generic, automatic and applicable to many bit-oriented block ciphers, including but not limited to PRESENT, EPCBC, LBlock, DES(L), MIBS etc.

Note: A draft version of an ongoing work.