New Impossible Differential Search Tool from Design and Cryptanalysis Aspects Revealing Structural Properties of Several Ciphers

摘要

In this paper, a new tool searching for impossible differentials is presented. Our tool can detect any contradiction between input and output differences. It can also take into account the property inside the S-box when its size is small e.g. 4 bits. This is natural for ciphers with bit-wise diffusion like PRESENT, while finding such impossible differentials for ciphers with word-wise diffusion is novel. In addition, several techniques are proposed to evaluate 8-bit S-box. The tool improves the number of rounds of impossible differentials from the previous best results for Midori128, LILLIPUT, and Minalpher. The tool also finds new impossible differentials for ARIA and MIBS. We manually verify the impossibility of the searched results, which reveals new structural properties of those designs. The tool can be implemented by slightly modifying the previous differential search tool using Mixed Integer Linear Programming (MILP). 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.