Truncated Differential Attacks on Contracting Feistel Ciphers

Abstract

We improve truncated differential attacks on t-branch contracting Feistel ciphers with a domain size of N^t. Based on new truncated differentials, a generic distinguisher for t² + t − 2 rounds using O(N^t−1) data and time is obtained. In addition, we obtain a key-recovery attack on t² + 1 rounds with Õ(N^t−2) data and Õ(N^t−1) time. Compared to previous results by Guo et al. (ToSC 2016), our attacks cover more rounds with a lower data-complexity. Applications of the generic truncated differential to concrete ciphers include full-round attacks on some instances of GMiMC-crf, and the best-known key-recovery attack on 17 rounds of the Chinese block cipher standard SM4. In addition, we propose an automated search method for truncated differentials using SMT, which is effective even for trails with probability below the probability of the truncated differential for a random permutation.