International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Zhenzhen Bao , School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore; Institute for Network Sciences and Cyberspace, BNRist, Tsinghua University, Beijing, China
Jian Guo , School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Danping Shi , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Yi Tu , School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: 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.
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32128,
  title={Superposition Meet-in-the-Middle Attacks: Updates on Fundamental Security of AES-like Ciphers},
  publisher={Springer-Verlag},
  author={Zhenzhen Bao and Jian Guo and Danping Shi and Yi Tu},
  year=2022
}