Superposition meet-in-the-middle attacks: updates on fundamental security of AES-like hashing (Q6097257)

The Meet-in-the-Middle approach is one of the most powerful cryptanalysis techniques, demonstrated by its applications in preimage attacks on the full MD4, MD5, Tiger, HAVAL, and Haraka-512 v2 hash functions, and key recovery of the full block cipher KTANTAN. The success relies on the separation of a primitive into two independent chunks, where each active cell of the state is used to represent only one chunk or is otherwise considered unusable once mixed. The authors observe that some of such cells are linearly mixed and can be as useful as the independent ones. This leads to the introduction of superposition states and a whole suite of accompanying techniques, which they incorporate into the MILPbased search framework proposed by \textit{Z. Bao} et al. [Lect. Notes Comput. Sci. 12696, 771--804 (2021; Zbl 1479.94121)] and \textit{X. Dong} et al. [ibid. 12827, 278--308 (2021; Zbl 1487.94111)], and find applications on a wide range of AES-like hash functions and block ciphers. For the entire collection see [Zbl 1511.94002].