Paper 2021/575

Superposition Meet-in-the-Middle Attacks: Updates on Fundamental Security of AES-like Hashing

Zhenzhen Bao, Nanyang Technological University, Tsinghua University
Jian Guo, Nanyang Technological University
Danping Shi, Institute of Information Engineering, Chinese Academy of Sciences, University of Chinese Academy of Sciences
Yi Tu, Nanyang Technological University

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. We 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 accompanied techniques, which we incorporate into the MILP-based search framework proposed by Bao et al. at EUROCRYPT 2021 and Dong et al. at CRYPTO 2021, and find applications on a wide range of AES-like hash functions and block ciphers.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2022
Whirlpool Grøstl AES hashing modes MITM MILP
Contact author(s)
baozhenzhen10 @ gmail com
guojian @ ntu edu sg
shidanping @ iie ac cn
TUYI0002 @ e ntu edu sg
2022-06-23: last of 3 revisions
2021-05-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhenzhen Bao and Jian Guo and Danping Shi and Yi Tu},
      title = {Superposition Meet-in-the-Middle Attacks: Updates on Fundamental Security of AES-like Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2021/575},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.