Quantum attacks on generalized Feistel networks based on the strong-weak separability

Generalized Feistel networks are important components of symmetric ciphers, and detailed security evaluations in the quantum setting remain to be explored. In this paper, based on the strong-weak separability of certain branch output function, we present polynomial-time quantum distinguishers for 4F-function and 2F-function structures in quantum chosen-plaintext attack setting for the first time, and then quantum key-recovery attacks are achieved through Grover-meet-Simon algorithm, respectively. Under the condition of the semi-strong separability, firstly, we give a quantum distinguisher on 8-round 4F-function structure, from which we carry out a 12-round quantum key-recovery attack to guess 10n-bit subkey, whose time complexities gain a factor of 2(5n). When attacking r >12 rounds, we can recover 4(r-12)n+10n-bit subkey in time 24(r-12)n+10m/2. Secondly, we show a quantum distinguisher on 5-round 2F-function structure, and a 7-round quantum key-recovery attack is performed on it, which can recover 3n-bit subkey in time 2(1.5n). When r>7, 2(r-7)n+3n-bit subkey can be recovered with time complexities by a factor of 22(r-7)n+3n/2. Furthermore, based on the weak separability, a 6-round quantum distinguisher for 2F-function structure is constructed, and an 8-round quantum key-recovery attack is achieved, and the time complexity is 22(r-8)n+3n/2 when r>8. The results show that the time complexity of each attack scheme we proposed is much better than that of Grover's brute force search.