Bounding the length of impossible differentials for SPN block ciphers

Evaluating the security of a block cipher against impossible differential cryptanalysis, is an important aspect during the design process. Themaximum length of impossible differentials is often used to evaluate this security. There have been many methods on giving upper bounds on the length of impossible differentials or finding longer impossible differentials. Two notable examples are the "Primitive Index" method proposed by Sun et al. at EUROCRYPT2016 and the MILP method proposed by Sasaki et al. at EUROCRYPT2017. However, these existing methods can only give upper bounds for some special SPN block ciphers or cannot give upper bounds due to the high time complexity. In this paper, we show that when ignoring the differential property of the underlying S-box, giving upper bounds on the length of impossible differentials is a linear problem. By using linear algebra, wepropose the Expansion Index of the linear layer, with which we can give upper bounds on the length of impossible differentials for any SPN block cipher with the detail of the S-box omitted. The core of this method is establishing and solving systems of linear equations, thus the verification of a single differential has linear time complexity. What's more, to give upper bounds with this method, we only need to establish and solve systems for differentials whose input and output differences have only one active S-box, which greatly reduces its time complexity from O(2(t)) to O(t) (here t denotes the number of S-boxes in the S-layer). The method in this paper is implemented in C and encapsulated into a tool freely available to readers. By applying our method on some SPN block ciphers, we give, for the first time, upper bounds on the length of impossible differentials for Midori, Skinny, CRYPTON, mCrypton, Minalpher.