Utilizing FWT in linear cryptanalysis of block ciphers with various structures

Linear cryptanalysis is one of the most classical cryptanalysis methods for block ciphers. Some critical techniques of the key-recovery phase are developed for enhancing linear cryptanalysis. Collard et al. improved the time complexity for last-round key-recovery attacks by using FWT. A generalized key-recovery algorithm for an arbitrary number of rounds with an associated time complexity formula is further provided by Flórez-Gutiérrez and Naya-Plasencia based on FWT in Eurocrypt 2020. However, the previous generalized algorithms are mainly applied to block ciphers with SPN structures, where the round-keys in the first and last round XORed to the state can be easily defined as outer keys. In Asiacrypt 2021, Leurent et al. applied the algorithm by Flórez-Gutiérrez et al. to Feistel structure ciphers. However, for other structures, such as NLFSR-based, the outer keys can not be directly deduced to utilize the previous algorithms. This paper extends the algorithm by Flórez-Gutiérrez et al. for more complicated structures, including but not limited to NLFSR-based, Feistel, ARX, and SPN. We also use the dependency relationships between ciphertext, plaintext and key information bits to eliminate the redundancy calculation and the improve analysis phase. We apply the algorithm with the improved analysis phase to KATAN (NLFSR-based) and SPARX (ARX). We obtain significantly improved results. The linear results we find for SPARX-128/128 beat other cryptanalytic techniques, becoming the best key recovery attacks on this cipher. The previous best linear attacks on KATAN32, KATAN48 and KATAN64 are improved by 9, 4, and 14 rounds, respectively.