Linear Cancellations in the MitM Attacks on Sponge Functions

At EUROCRYPT 2023, Qin et al. proposed the MitM attack framework on sponge functions by separating the message bits into two sets of neutral bits. By assigning bit cancellations on one of the two sets, the states of the two sets can be computed independently and then filtered by some matching equations. To solve the bit cancellations, Qin et al. exhaustively compute the cancellations of all message bits, and store them in a huge hash table, which leads to attacks with huge memory. In this paper, we separate the bit cancellations into linear and nonlinear cancellations for the MitM attacks, where the linear cancellations are solved by Gaussian elimination, and only the nonlinear cancellations are dealt with the hash table. Hence, the memory cost is significantly reduced. In order to search new attacks with efficient memory (fewer nonlinear cancellations and more linear cancellations), we propose a new MILP model whose encoding scheme can distinguish linear and nonlinear cancellations. Besides, dedicated tricks such as the so-called weak-diffusion structure and two-stage search are proposed to further accelerate solving the MILP models. Finally, the memory complexities of MitM attacks on 4-round Keccak[1024], 3-round Xoodyak-Xof, 4-round Ascon-Xof, and full Subterranean 2.0 are reduced by 2⁴⁹, 2⁵⁹, 2¹⁶, and 2³⁶, respectively. Besides, our memory-efficient approach can turn invalid MitM attacks (where memory complexity is the dominant factor in old framework) into valid MitM attacks. For example, we propose the first MitM preimage attack on 4-round Keccak[768] and the first 3-round collision attack on Xoodyak-Xof with 128-bit tag.