Paper 2026/2910

Automatic Preimage Attacks on Xoodyak Based on Linear Structures

Zhaoyue Huang, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences
Meicheng Liu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences
Dongdai Lin, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences
Abstract

Xoodyak was one of the ten finalists in the NIST Lightweight Cryptography standardization process (2018-2023). In this paper, we investigate preimage attacks on Xoodyak-XOF using linear structures with the allocation model. A key challenge in applying this approach is to identify suitable linear structures that lead to efficient preimage attacks. To address this challenge, we propose an automatic framework for searching suitable linear structures. The framework incorporates three techniques: a mixed exact and linear approximation of the $\chi$ function in the final round, a mixed integer linear programming model for describing the propagation of linear variables through the $\chi$ and XOR functions, and weighted condition constraints with a weight update algorithm to guide the structure search. Based on the linear structures identified by the proposed framework, we improve the preimage attacks on 2-round and 3-round Xoodyak-XOF with a 128-bit output, reducing their complexities to $2^{93.934}$ and $2^{115.715}$, respectively, which are the best known results to date. In addition, we present the first theoretical preimage attack on 4-round Xoodyak-XOF, with a complexity of $2^{126.245}$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Contact author(s)
huangzhaoyue @ iie ac cn
liumeicheng @ iie ac cn
ddlin @ iie ac cn
History
2026-11-21: approved
2026-11-16: received
See all versions
Short URL
https://ia.cr/2026/2910
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2910,
      author = {Zhaoyue Huang and Meicheng Liu and Dongdai Lin},
      title = {Automatic Preimage Attacks on Xoodyak Based on Linear Structures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2910},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2910}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.