New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes

In this paper, we present some new key-recovery attacks on Misty L-KF, Misty R-KF, and generalized Feistel schemes. Firstly, we propose a new 5-round distinguisher on Misty L-KF structure. Based on our new distinguisher attack, we propose a new 6-round Demiric–Selçuk meet-in-the-middle attack (DS-MITM attack) against Misty L-KF structure. Secondly, we extend our classical DS-MITM attack to a new quantum DS-MITM attack on Misty L-KF structure by using the quantum claw finding algorithm. In addition, we apply the above method to attack Misty R-KF and generalized Feistel schemes. To sum up, we construct our classical key-recovery attacks on the 6-round Misty L-KF structure and Misty R-KF structure with \( O (2^{3n/4}) \) $O(2^{3n/4})$ time and \( O (2^{n/2}) \) $O(2^{n/2})$ memory cost. By using a quantum computer, our new quantum key-recovery attacks on the 6-round Misty L-KF structures and Misty R-KF structures can be constructed with \( {\tilde{O}}(2^{n/2}) \) $\tilde{O}(2^{n/2})$ time and \( O (2^{n/2}) \) $O(2^{n/2})$ memory cost. Furthermore, we can construct our new quantum \((5d-4)\) $(5d-4)$ -round key-recovery attacks on the d-branch contracting Feistels with \({\tilde{O}}(2^{(d-1)n/d})\) $\tilde{O}(2^{(d-1)n/d})$ time and \(O (2^{(d-1)n/d})\) $O(2^{(d-1)n/d})$ memory cost. In the end, we can construct our new quantum \((4d-3)\) $(4d-3)$ -round and \((5d-4)\) $(5d-4)$ -round key-recovery attacks on the two types of d-branch expanding Feistels with \({\tilde{O}}(2^{(d-1)n/d})\) $\tilde{O}(2^{(d-1)n/d})$ time and \(O (2^{(d-1)n/d})\) $O(2^{(d-1)n/d})$ memory cost.