Improved meet-in-the-middle collision attack on round-reduced Xoodyak

With the growing prevalence of compact and resource-constrained computing devices, demand for lightweight cryptographic schemes is burgeoning. , a lightweight hash function that entered the final round of the NIST Lightweight Cryptography (LWC), has received extensive attention owing to its security and high efficiency. Meet-in-the-Middle (MitM) attack serves as an effective method for the analysis of sponge-based hashing. Nevertheless, constrained by the large search space, the optimization of MitM attack remains to be further investigated. We introduce an improved approach, overall-weak-diffusion structure searching strategy, to identify a weak diffusion neutral set in the heuristic two-stage searching strategy, and apply it to 3-round . Ultimately, the time complexity of MitM collision attack against 3-round is reduced to 2124.24 2 124.24 and the memory is 2¹²³ 2 123 . To our knowledge, this establishes the most efficient collision attack against 3-round , which lowers both the time and memory complexities by half compared to the current best results achieved at CRYPTO 2024. Furthermore, this paper also evaluates the resistance of 3-round -like hashing against MitM collision attack and provides recommendations for parameter selection.