Exploiting output bits and the χ operation in MitM preimage attacks on Keccak

Keccak, the cryptographic hash function at the core of the SHA-3 standard, offers enhanced security and efficiency for data integrity and authentication. Qin et al. (EUROCRYPT 2023) first introduced a Meet-in-the-Middle (MitM) preimage attack on Keccak using a Mixed-Integer Linear Programming (MILP) model. In this paper, we further analyze Keccak’s security against this MitM preimage attack. In Qin’s work, the model relied only on the digest portion of Keccak’s output to find match points, though the digest represents only part of the full output. Our improved MILP model expands on this by incorporating both the digest and additional selected bits from the remaining output of Keccak. Additionally, we exploit the properties of theχ operation to optimize the model further. This new model increases the number of match points in MitM attacks and effectively reduces time complexity. Applying it to Keccak-384 and Keccak-512, we achieve the best-known results for 4-round Keccak-512, with a time complexity of 2502.8 and memory complexity of 279. Moreover, We present the first MitM preimage attack on weak digests for Keccak-384 and Keccak-512, where “weak digests” refers to digests that are more vulnerable to efficient attacks compared to others. For 4-round Keccak-512, the attack has a time complexity of 2491 and memory complexity of 268. Since we fix the values of 57 bits in the digest, this attack is effective for 2455 digests. For 4-round Keccak-384, it achieves a time complexity of 2376.1 and memory complexity of 273. Since we fix the values of 12 bits in the digest, this attack is effective for 2372 digests.