Enhanced Differential-Linear Cryptanalysis of Forró With MILP
IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 5237-5250
DOI: 10.1109/tit.2026.3695599 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Zhengting Li und 5 weiteren Autor:innen. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
ARX-based design is a major building block of modern cryptographic ciphers due to its efficiency in software. Forró is an ARX-based stream cipher proposed by Coutinho et al. at ASIACRYPT 2022, which was designed to provide higher security margin than the ChaCha stream cipher. In this paper, we propose a full automated MILP model called MinForró , to derive linear approximations for the Forró stream cipher. For the differential part, a two-stage strategy to search for single-bit differential trails with high differential correlations is presented, which helps us to find the first-ever 3-round differential trails for Forró. By combining the linear approximations obtained by MinForró and 3-round differential trail for Forró, we propose improved differential-linear distinguishers for 4-, 5-, 5.25-, 5.5-, 5.75-, 6-, 6.25- and 6.5-round Forró with complexities $2^{32.44}$ , $2^{46}$ , $2^{50}$ , $2^{64.32}$ , $2^{87.12}$ , $2^{117.92}$ , $2^{174.92}$ and $2^{226.88}$ , respectively. The proposed differential-linear distinguishers for 4-, 5-, 5.25- and 5.5-round Forró significantly improve the existing distinguishers by factors of $2^{4.11}$ , $2^{83.68}$ , $2^{127.64}$ and $2^{178.20}$ , respectively. To the best of our knowledge, this is the first differential-linear distinguisher for Forró that reaches 6.5 rounds, which is a significant advancement over the existing record of 5.5 rounds. We have implemented the differential-linear distinguishers for 4- and 5-round Forró on a common PC, and the experimental results confirm the correctness of these distinguishers. Furthermore, when combined with the Probabilistic Neutral Bits (PNB) technique, we obtain key recovery attacks on 5.5-, 6-, 6.5- and 6.75-round Forró with time complexities $2^{149.20}$ , $2^{151.84}$ , $2^{213.49}$ and $2^{251.97}$ , respectively. The proposed key recovery attack on 5.5-round Forró significantly improves the time complexity of the existing attack by a factor of $2^{75.84}$ . To the best of our knowledge, this is the first key recovery attack on Forró that reaches 6.75 rounds, which is a significant advancement over the existing record of 5.5 rounds.
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Li, Z., Ding, L., Wang, X., Wang, H., Wan, J., & Zhang, F. (2026). Enhanced Differential-Linear Cryptanalysis of Forró With MILP. IEEE Transactions on Information Theory, 72(7), 5237-5250. https://doi.org/10.1109/tit.2026.3695599
Vancouver
Li Z, Ding L, Wang X, Wang H, Wan J, Zhang F. Enhanced Differential-Linear Cryptanalysis of Forró With MILP. IEEE Transactions on Information Theory. 2026;72(7):5237-5250. doi:10.1109/tit.2026.3695599
BibTeX
@article{Li2026,
author = {Li, Zhengting and Ding, Lin and Wang, Xinhai and Wang, Honglei and Wan, Jiang and Zhang, Fan},
title = {Enhanced Differential-Linear Cryptanalysis of Forró With MILP},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {7},
pages = {5237--5250},
doi = {10.1109/tit.2026.3695599}
}
EUVIMED