Cryptology ePrint Archive: Report 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.

Category / Keywords: Related-key differential attack, Active S-box, Mixed-integer Linear Programming, Logical condition modelling, Convex hull

Date: received 22 Oct 2013, last revised 13 Apr 2014

Contact author: sunsiwei at iie ac cn

Available format(s): PDF | BibTeX Citation

Note: A draft version of an ongoing work.

Version: 20140414:023605 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]