Paper 2026/2910
Automatic Preimage Attacks on Xoodyak Based on Linear Structures
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
-
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}
}