Revisiting Impossible Differential Cryptanalysis and Expanding the Application of MILP in Impossible Differential Attack

Impossible differential cryptanalysis is a powerful tool for analyzing the security of symmetric-key ciphers. While it has achieved excellent results for many ciphers, errors often occur in some impossible differential attacks. In this paper, we identify the limitations presented in Boura et al.’s multiple impossible differential attack, rendering it infeasible for application to some block ciphers. Furthermore, we find an error in Derbez et al.’s time complexity formula. To address these shortcomings, we propose a new multiple impossible differential attack and provide an accurate formula for calculating the time complexity. Additionally, we conduct a comprehensive review of previous impossible differential attacks and make some new discoveries. Firstly, we introduce a new key sieving strategy that, when combined with traditional methods, yields improved results. Secondly, we establish a correlation between the impossible differential and the probability of the remaining key in block ciphers with Feistel structure. This relationship enables the efficient selection of optimal impossible differentials. To improve the memory complexity of the attack, we propose a technique called Pre-filtering. Finally, we demonstrate the practical implementation of an optimal impossible differential attack using the MILP-aided method. We apply our findings to CLEFIA-128 and SIMON, successfully rectifying Boura et al.’s flawed attack on CLEFIA-128 and achieving the current best result. For SIMON, we improve the memory complexity across all versions and the time complexity in select versions. Furthermore, our approach achieves a one-round advancement in the attack on SIMON128/192.