Cryptology ePrint Archive: Report 2019/019

Improving the MILP-based Security Evaluation Algorithms against Differential Cryptanalysis Using Divide-and-Conquer Approach

Chunning Zhou and Wentao Zhang and Tianyou Ding and Zejun Xiang

Abstract: In recent years, Mixed Integer Linear Programming (MILP) has been widely used in cryptanalysis of symmetric-key primitives. For differential and linear cryptanalysis, MILP can be used to solve the two problems: calculation of the minimum number of differential/linear active S-boxes, and search for the best differential/linear characteristics. There are already numerous papers published in this area which either find differential characteristics with good probabilities or ones with small numbers of active S-boxes. However, the efficiency is not satisfactory enough for many symmetric-key primitives. In this paper, we will greatly improve the efficiency of the search algorithms for both the two problems based on MILP. Solving the problems of the calculation of the minimum number of differential/linear active S-boxes and the search for the best differential/linear characteristics can be equivalent to solving an MILP model whose feasible region is the set of all possible differential/linear characteristics. However, searching the whole feasible region is inefficient and high-probability differential/linear characteristics are likely to appear on the smaller feasible region with a low number of active S-boxes at some round. Inspired by the idea of divide-and-conquer approach, we divide the whole feasible region into smaller ones and separately search them. We apply our method to 5 lightweight block ciphers: PRESENT, GIFT-64, RECTANGLE, LBLOCK and TWINE. For each cipher, we obtain better results than the best-known ones. For the calculation of the minimum number of differential active S-boxes, we can reach 31-round PRESENT, 28-round GIFT-64 and 17-round RECTANGLE respectively. For the search for the best differential characteristics, we can reach 23, 14, 15, 21 and 17 rounds for the five ciphers respectively. Based on the duality between the differential cryptanalysis and the linear cryptanalysis, we leave the case for linear cryptanalysis in our future work.

Category / Keywords: Block Cipher and Differential Cryptanalysis and MILP and Divide-and-Conquer

Date: received 7 Jan 2019

Contact author: zhouchunning at iie ac cn, zhangwentao@iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20190109:005024 (All versions of this report)

Short URL: ia.cr/2019/019


[ Cryptology ePrint archive ]