Searching all truncated impossible differentials in SPN

This study concentrates on finding all truncated impossible differentials in substitution-permutation networks (SPNs) ciphers. Instead of using the miss-in-the-middle approach, the authors propose a mathematical description of the truncated impossible differentials. First, they prove that all truncated impossible differentials in an r+1 rounds SPN cipher could be obtained by searching entry 0' in D(P)(r), where D(P) denotes the differential pattern matrix (DPM) of P-layer, thus the length of impossible differentials of an SPN cipher is upper bounded by the minimum integer r such that there is no entry 0' in D(P)(r). Second, they provide two efficient algorithms to compute the DPMs for both bit-shuffles and matrices over GF(2(n)). Using these tools they prove that the longest truncated impossible differentials in SPN structure is 2-round, if the P-layer is designed as an maximum distance separable (MDS) matrix. Finally, all truncated impossible differentials of advanced encryption standard (AES), ARIA, AES-MDS, PRESENT, MAYA and Puffin are obtained.