International Association
for Cryptologic Research

To penetrate more rounds with Meet-in-the-Middle (MitM) attack, the neutral words are usually subject to some linear constraints, e.g., Sasaki and Aoki's initial structure technique. At CRYPTO 2021, Dong et al. found the neutral words can be nonlinearly constrained. They introduced a table-based method to precompute and store the solution space of the neutral words, which led to a huge memory complexity. In this paper, we find some nonlinearly constrained neutral words can be solved efficiently by Khovratovich et al.'s triangulation algorithm (TA). Furthermore, motivated by the structured Gaussian elimination paradigm developed by LaMacchia et al. and Bender et al., we improve the TA to deal with the case when there are still many unprocessed equations, but no variable exists in only one equation (the original TA will terminate). Then, we introduce the new MitM attack based on our improved TA, called triangulating MitM attack. As applications, the memory complexities of the single-plaintext key-recovery attacks on 4-/5-round AES-128 are significantly reduced from $2^{80}$ to the practical $2^{24}$ or from $2^{96}$ to $2^{40}$. Besides, a series of new one/two-plaintext attacks are proposed for reduced AES-192/-256 and Rijndael-EM, which are the basic primitives of NIST PQC candidate FAEST. A partial key-recovery experiment is conducted on 4-round AES-128 to verify the correctness of our technique. For AES-256-DM, the memory complexity of the 10-round preimage attack is reduced from $2^{56}$ to $2^{8}$, thus an experiment is also implemented. Without our technique, the impractical memories $2^{80}$ or $2^{56}$ of previous attacks in the precomputation phase will always prevent any kind of (partial) experimental simulations. In the full version, we extend our techniques to 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 249, 259, 216, and 236, 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.

This paper proposes general meet-in-the-middle (MitM) attack frameworks for preimage and collision attacks on hash functions based on (generalized) sponge construction. As the first contribution, our MitM preimage attack framework covers a wide range of sponge-based hash functions, especially those with lower claimed security level for preimage compared to their output size. Those hash functions have been very widely standardized (e.g., {\tt Ascon-Hash}, {\tt PHOTON}, etc.), but are rarely studied against preimage attacks. Even the recent MitM attack framework on sponge construction by Qin et al. (EUROCRYPT 2023) cannot attack those hash functions. As the second contribution, our MitM collision attack framework shows a different tool for the collision cryptanalysis on sponge construction, while previous collision attacks on sponge construction are mainly based on differential attacks. Most of the results in this paper are the first third-party cryptanalysis results. If cryptanalysis previously existed, our new results significantly improve the previous results, such as improving the previous 2-round collision attack on {\tt Ascon-Hash} to the current 4 rounds, improving the previous 3.5-round quantum preimage attack on SPHINCS$^+$-{\tt Haraka} to our 4-round classical preimage attack, etc.

In the CAESAR competition, Deoxys-I and Deoxys-II are two important authenticated encryption schemes submitted by Jean et al. Recently, Deoxys-II together with Ascon, ACORN, AEGIS-128, OCB and COLM have been selected as the final CAESAR portfolio. Notably, Deoxys-II is also the primary choice for the use case “Defense in depth”. However, Deoxys-I remains to be one of the third-round candidates of the CAESAR competition. Both Deoxys-I and Deoxys-II adopt Deoxys-BC-256 and Deoxys-BC-384 as their internal tweakable block ciphers.In this paper, we investigate the security of round-reduced Deoxys-BC-256/-384 and Deoxys-I against the related-tweakey boomerang and rectangle attacks with some new boomerang distinguishers. For Deoxys-BC-256, we present 10-round related-tweakey boomerang and rectangle attacks for the popular setting (|tweak|, |key|) = (128, 128), which reach one more round than the previous attacks in this setting. Moreover, an 11-round related-tweakey rectangle attack on Deoxys-BC-256 is given for the first time. We also put forward a 13-round related-tweakey boomerang attack in the popular setting (|tweak|, |key|) = (128, 256) for Deoxys-BC-384, while the previous attacks in this setting only work for 12 rounds at most. In addition, the first 14-round relatedtweakey rectangle attack on Deoxys-BC-384 is given when (|tweak| < 98, |key| > 286), that attacks one more round than before. Besides, we give the first 10-round rectangle attack on the authenticated encryption mode Deoxys-I-128-128 with one more round than before, and we also reduce the complexity of the related-tweakey rectangle attack on 12-round Deoxys-I-256-128 by a factor of 228. Our attacks can not be applied to (round-reduced) Deoxys-II.