Paper 2025/1369

Cube-Attack-Like Cryptanalysis of Keccak-Based Constructions Exploiting State Differences (Full Version)

Abstract

This paper presents an enhancement to cube-attack-like cryptanalysis by minimizing output-bit dependency on related key bits, thereby improving attack complexity. We construct two distinct initial states differing exclusively in predetermined bit positions. Through independent cube summation and state difference analysis, we observed reduced related key bits dependency for specific output bits. We validate our approach by targeting three Keccak keyed variants Ketje Minor, Keccak-MAC-512 and Keccak-MAC-384, developing a dedicated tool to recover all output-bit superpolies. Using our computational resources, we successfully attacked 4-round of Ketje Minor and 5-round of other variants, confirming both the method's validity and practical applicability. While the best known attacks on these structures reach 7-round, our results improve upon the 5-round. We construct our initial state configurations based on the automated method proposed by Bi et al.\ in \textit{Design, Codes and Cryptography} (2019), and compare our results with theirs. For the 4-round Ketje Minor, we reduce the time complexity from \(2^{20}\) to \(2^{16.8}\); for 5 round Keccak-MAC-512, from \(2^{34}\) to \(2^{31.2}\); and for 5 round Keccak-MAC-384, from \(2^{27.6}\) to \(2^{26.5}\).