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

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

Paper 2013/676

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

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

Abstract

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 respectively. 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 attack, and several techniques for obtaining tighter security bounds. We successfully prove that the 24-round PRESENT-80 is secure enough to resist against standard related-key differential attacks based on differential characteristic, and the probability of the best related-key differential characteristic of the full LBlock is upper bounded by $2^{-60}$. These are the tightest security bounds with respect to the related-key differential attack published so far for PRESENT-80 and LBlock. ~~~~Moreover, we present a new tool for finding (related-key) differential characteristics automatically for bit-oriented block ciphers. Using this tool, we obtain new single-key or related-key differential characteristics for SIMON48, 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.

Note: Add the example source code.

Metadata

Available format(s): PDF
Publication info: A major revision of an IACR publication in ASIACRYPT 2014
Keywords: Automatic cryptanalysis Related-key differential attack Mixed-integer Linear Programming Convex hull
Contact author(s): sunsiwei @ iie ac cn
History: 2014-09-12: last of 15 revisions; 2013-10-24: received; See all versions
Short URL: https://ia.cr/2013/676
License: CC BY

BibTeX

@misc{cryptoeprint:2013/676,
      author = {Siwei Sun and Lei Hu and Peng Wang and Kexin Qiao and Xiaoshuang Ma and Ling Song},
      title = {Automatic Security Evaluation and (Related-key) Differential Characteristic Search: Application to {SIMON}, {PRESENT}, {LBlock}, {DES}(L) and Other Bit-oriented Block Ciphers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/676},
      year = {2013},
      url = {https://eprint.iacr.org/2013/676}
}