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

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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},
      note = {\url{https://eprint.iacr.org/2013/676}},
      url = {https://eprint.iacr.org/2013/676}
}