Paper 2019/126

New Automatic search method for Truncated-differential characteristics: Application to Midori and SKINNY

AmirHossein E. Moghaddam and Zahra Ahmadian

Abstract

In this paper, using Mixed Integer Linear Programming, a new automatic search tool for truncated differential characteristic is presented. While the previous MILP models for truncated differential characteristic has been used just as a facilitator for finding the maximal probability bit-wise differential characteristic, ours treats truncated differential characteristic as an independent distinguisher. Our method models the problem of finding a maximal probability truncated differential characteristic, being able to distinguish the cipher from a pseudo random permutation. Our model enjoys a word-wise variable definitions which makes it much simpler and more easily solvable than its bit-wise counterpart. Using this method, we analyse Midori64 and SKINNY64/64,128 block ciphers, for both of which the existing results are improved. In both cases, the truncated differential characteristic is much more efficient than the upper bound of (bit-wise) differential characteristic proven by the designers, for all number of rounds. More specifically, the highest possible rounds, for which a differential characteristic can exist for Midori64 and SKINNY64/64,128, are 6 and 7 rounds respectively, for which differential characteristics with maximum probabilities of $2^{-60}$ and $2^{-52}$ may exist. However, we present new truncated differential characteristics for 6-round of Midori64 with probability $2^{-54}$. In case of SKINNY64/64,128, the gap is much wider, where for 7 rounds we find a truncated characteristic with probability $2^{-4}$, and even a 10-round truncated characteristic can be found with probability $2^{-40}$. Moreover, our result outperforms the only truncated differential analysis that exists on Midori64. This method can be used as a new tool for differential analysis of SPN block ciphers.