Paper 2026/2959

Classical Free-Start Collision Attacks on Full-Round AES-256-DM and AES-256-MMO

Liyuan Tang, Tsinghua University
Yanzhao Shen, Shandong Institute of Blockchain
Xiaoyang Dong, Tsinghua University
Abstract

Despite extensive cryptanalysis of hash modes based on the Advanced Encryption Standard (AES), no classical free-start collision attack has previously been reported for full-round AES-256-DM or AES-256-MMO. In this work, we address this problem by extending the guess-and-determine (GD) rebound methodology. Our main technical contribution is a precomputation-based method for handling conflicts involving guessed variables in the GD procedure. By precomputing solutions to the corresponding systems of byte equations, such conflicts can be resolved in $O(1)$ online time. We further exploit triangular dependencies among controllable guessed variables to reduce the memory required for precomputation. Using this method, we construct classical free-start collision attacks applicable to both AES-256-DM and AES-256-MMO. For the full 14-round AES-256, the attacks require $2^{60}$ time and $2^{24}$ memory, providing the first classical free-start collision attacks on these full-round constructions. The same approach improves the time complexity of the full-round free-start differential $q$-multicollision attack from $q\cdot2^{67}$ to $q\cdot2^{60}$, with memory complexity $2^{24}$. We also obtain free-start collision attacks on the 12-round variants with time complexity $2^{54}$ and memory complexity $2^{24}$.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Published by the IACR in TOSC 2026
Keywords
Guess-and-Determine Rebound AttackFree-Start CollisionAES-256
Contact author(s)
tangly22 @ mails tsinghua edu cn
shanyanzhao @ sdibc cn
xiaoyangdong @ tsinghua edu cn
History
2026-11-22: approved
2026-11-20: received
See all versions
Short URL
https://ia.cr/2026/2959
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2959,
      author = {Liyuan Tang and Yanzhao Shen and Xiaoyang Dong},
      title = {Classical Free-Start Collision Attacks on Full-Round {AES}-256-{DM} and {AES}-256-{MMO}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2959},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2959}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.