Paper 2026/1999
Revisiting Single-Color Initial Structures in Meet-In-The-Middle Attacks
Abstract
The meet-in-the-middle (MITM) attack framework is one of the most powerful cryptanalytic techniques with broad influence to preimage, key recovery, and collision attacks. In this paper, we present two generic techniques. First, we observe that the constant space in MITM attacks is an exploitable source of degrees of freedom: its value-independence enables MITM-style partition and acceleration of attack subprocesses. With this intuition in mind, we revisit the single-color initial structure technique by Chen et al. at Asiacrypt 2025, and find an improved algorithm that relaxes the canonical optimization objective in automatic search for MITM attacks. Second, we extend the partial-target-preimage-to-collision conversion by Li, Isobe, and Shibutani at FSE 2012 used in MITM-based collision attacks to the settings of chosen-prefix collision and diamond structure construction. We demonstrate the practical relevance of our techniques by presenting a number of improved results in (pseudo-)preimage, (chosen-prefix) collision, and herding attacks on AES-like constructions over the state-of-the-art.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in ASIACRYPT 2026
- Keywords
- Meet-in-the-MiddleSingle-Color Initial StructurePreimageChosen-Prefix CollisionDiamond StructureHerding
- Contact author(s)
- tianyu005 @ e ntu edu sg
- History
- 2026-09-16: revised
- 2026-09-13: received
- See all versions
- Short URL
- https://ia.cr/2026/1999
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1999,
author = {Shiyao Chen and Jian Guo and Wenjie Nan and Danping Shi and Tianyu Zhang},
title = {Revisiting Single-Color Initial Structures in Meet-In-The-Middle Attacks},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1999},
year = {2026},
url = {https://eprint.iacr.org/2026/1999}
}
