Paper 2023/227

A Novel Automatic Technique Based on MILP to Search for Impossible Differentials

Yong Liu, Hubei University
Zejun Xiang, Hubei University
Siwei Chen, Hubei University
Shasha Zhang, Hubei University
Xiangyong Zeng, Hubei University

The Mixed Integer Linear Programming (MILP) is a common method of searching for impossible differentials (IDs). However, the optimality of the distinguisher should be confirmed by an exhaustive search of all input and output differences, which is clearly computationally infeasible due to the huge search space. In this paper, we propose a new technique that uses two-dimensional binary variables to model the input and output differences and characterize contradictions with constraints. In our model, the existence of IDs can be directly obtained by checking whether the model has a solution. In addition, our tool can also detect any contradictions between input and output differences by changing the position of the contradictions. Our method is confirmed by applying it to several block ciphers, and our results show that we can find 6-, 13-, and 12-round IDs for Midori-64, CRAFT, and SKINNY-64 within a few seconds, respectively. Moreover, by carefully analyzing the key schedule of Midori-64, we propose an equivalent key transform technique and construct a complete MILP model for an 11-round impossible differential attack (IDA) on Midori-64 to search for the minimum number of keys to be guessed. Based on our automatic technique, we present a new 11-round IDA on Midori-64, where 23 nibbles of keys need to be guessed, which reduces the time complexity compared to previous work. The time and data complexity of our attack are $2^{116.59}$ and $2^{60}$, respectively. To the best of our knowledge, this is the best IDA on Midori-64 at present.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. ACNS 2023
Contact author(s)
liuyong_crypto @ 163 com
xiangzejun @ hubu edu cn
chensiwei_hubu @ 163 com
amushasha @ 163 com
xzeng @ hubu edu cn
2023-02-21: approved
2023-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yong Liu and Zejun Xiang and Siwei Chen and Shasha Zhang and Xiangyong Zeng},
      title = {A Novel Automatic Technique Based on MILP to Search for Impossible Differentials},
      howpublished = {Cryptology ePrint Archive, Paper 2023/227},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.