Paper 2016/1181

New Impossible Differential Search Tool from Design and Cryptanalysis Aspects

Yu Sasaki and Yosuke Todo


In this paper, a new tool searching for impossible differentials against symmetric-key primitives is presented. Compared to the previous tools, our tool can detect any contradiction between input and output differences, and it can take into account the property inside the S-box when its size is small e.g. 4 bits. In addition, several techniques are proposed to evaluate 8-bit S-box. With this tool, the number of rounds of impossible differentials are improved from the previous best results by 1 round for Midori128, Lilliput, and Minalpher. The tool also finds new impossible differentials of ARIA and MIBS. We manually verify the impossibility of the searched results, which reveals new structural properties of those designs. Our tool can be implemented only by slightly modifying the previous differential search tool using Mixed Integer Linear Programming (MILP), while the previous tools need to be implemented independently of the differential search tools. This motivates us to discuss the usage of our tool particular for the design process. With this tool, the maximum number of rounds of impossible differentials can be proven under reasonable assumptions and the tool is applied to various concrete designs.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
sasaki yu @ lab ntt co jp
2016-12-30: received
Short URL
Creative Commons Attribution


      author = {Yu Sasaki and Yosuke Todo},
      title = {New Impossible Differential Search Tool from Design and Cryptanalysis Aspects},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1181},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.