ChaCha, the stream cipher designed by Daniel Bernstein in 2008 as a variant of Salsa20, protects an enormous share of the world’s encrypted traffic. It runs inside TLS 1.3, QUIC, WireGuard, SSH, Noise and S/MIME 4.0, usually in the ChaCha-Poly1305 authenticated-encryption construction, and it owes its popularity to the fact that it is built entirely from three cheap operations: addition modulo 2 to the 32nd power, bitwise rotation, and XOR. This so-called ARX design makes ChaCha exceptionally fast in software, from cloud servers down to Internet-of-Things devices. But the same arithmetic simplicity that makes it fast also makes it a favorite target for cryptanalysts, who have spent nearly two decades probing how its security degrades as rounds are stripped away.
A new open-access study in the journal Cybersecurity, authored by Guoqiang Liu, Guiyan Ren, Bing Sun, Bo Yu and Chao Li of the National University of Defense Technology in Changsha, China, pushes that probing further by putting automation at the center of the analysis. The team combined mixed-integer linear programming (MILP) searches, massive correlation measurements on NVIDIA RTX 4090 graphics cards, and a mixed-integer quadratically constrained programming (MIQCP) model to re-examine the strongest known differential-linear attacks on reduced-round ChaCha. The result is a sharper, experimentally grounded estimate of a key component shared by several recent attacks, along with lower data and time complexity figures for 7- and 7.5-round variants of the cipher. Crucially, the full 20-round ChaCha deployed in real protocols remains far out of reach; the work measures the cipher’s security margin rather than signaling any practical threat to users.
The technique at the heart of the study is differential-linear cryptanalysis, a hybrid introduced by Langford and Hellman in 1994. Differential cryptanalysis, pioneered by Biham and Shamir against DES, tracks how a fixed difference between two plaintexts propagates through a cipher; linear cryptanalysis, introduced by Matsui, exploits statistical biases in linear approximations between input and output bits. The differential-linear combination splits a cipher into two sub-ciphers: a differential part that maps an input difference to an intermediate difference with probability p, and a linear part that connects that intermediate state to an output mask with correlation q. Under idealized independence assumptions, the combined distinguisher has correlation p times q squared, meaning an attacker can detect the bias given roughly the inverse square of that quantity in known keystream samples.
Reality is messier than those assumptions. Later work by Blondeau, Leander and Nyberg showed that the naive formula can be inaccurate, and Bar-On and colleagues introduced the Differential-Linear Connectivity Table at EUROCRYPT 2019 to handle dependencies between the two halves. For ChaCha specifically, the modern attack literature has converged on a four-round differential-linear component that starts from a two-bit input difference in the cipher’s state and ends, three and a half rounds later, at a five-bit output mask. Previous analyses estimated the correlation of this component at around 2 to the power of minus 32.2 by summing over a limited set of intermediate linear masks. The new paper attacks the same component from the differential side, enumerating the actual paths a difference can take rather than the masks it can be observed through.
The enumeration itself is a MILP tour de force. Exploiting the Lipmaa-Moriai formula for differential propagation through modular addition, the authors built a model whose objective minimizes the total differential weight of one-round characteristics. The search found all 128 one-round differentials with two-bit input differences and eight-bit output differences, including the 18 optimal characteristics previously reported by Bellini and coauthors at CT-RSA 2023. Focusing on the specific input difference used by the strongest published distinguishers, the model then enumerated 61 intermediate differences with differential weight at most 14, where weight denotes the negative binary logarithm of the transition probability. One path had weight 12, nine had weight 13, and 51 sat at the cutoff of 14.
Enumerating paths is only half the job; each path’s contribution to the overall correlation must be measured. The authors turned to GPUs, running Monte Carlo experiments with sample sizes between 2 to the 52nd and 2 to the 55th power, generating random inputs on the fly rather than storing them. A single reported correlation took roughly 24 hours of GPU time on average. Thirty-nine of the 61 paths yielded statistically reliable correlation estimates, each exceeding a Bonferroni-adjusted detection threshold for 39 simultaneous tests. The 22 remaining paths, two with probability 2 to the minus 13 and twenty with probability 2 to the minus 14, could not be resolved even at the largest sample size, but the authors bounded their total worst-case contribution at 2 to the minus 33.81, about sixteen percent of the measured sum. The signed weighted sum of the 39 resolved paths came to 2 to the power of minus 31.16, with a 95 percent confidence interval spanning roughly 2 to the minus 31.46 to 2 to the minus 30.92 when unresolved contributions are allowed to take adverse signs.
That refined four-round estimate of 2 to the minus 31.16 is the paper’s central number, and plugging it into published attack frameworks yields immediately improved complexity figures. Combining it with the Mixderive linear approximations of Li and colleagues, which have correlations of 2 to the minus 20.97 over two rounds and 2 to the minus 42.17 over two and a half rounds, gives distinguisher data complexities of 2 to the 160.20 for 7-round ChaCha and 2 to the 245.00 for 7.5 rounds, each a factor of about 2 to the 2.08 better than before. Applied to the ReBitP key-recovery framework of Wang and coauthors, which layers bit puncturing, partitioning, guessed-key covering and two-phase distillation on top of the same differential-linear component, the new estimate lowers the 7-round attack to 2 to the 125.91 data and 2 to the 140.00 time, and the 7.5-round attack to 2 to the 122.96 data and 2 to the 241.31 time, while preserving the original success probabilities of 88.27 and 99.99 percent respectively. A sensitivity analysis using the pessimistic endpoint of the confidence envelope shows the conclusions are robust to the residual statistical uncertainty.
The study’s second major contribution is a sobering audit of automated correlation prediction. The authors adapted an MIQCP framework, originally developed for the cipher Speck, that models how correlations propagate through ARX operations using continuous difference values, and tested it against GPU measurements on three fixed differential-linear distinguishers. The gaps were dramatic: predicted correlation weights exceeded experimental values by 26.86, 43.08 and 497.01 bits respectively, with the third prediction also carrying the wrong sign. A half-round-by-half-round comparison localized the failure, showing the gap stays below 0.3 bits through two rounds but explodes to 5.41 bits at 2.5 rounds and nearly 27 bits at three rounds. The authors trace the problem to two structural omissions: the model propagates a single scalar value per bit and cannot capture carry dependencies that couple successive modular additions within a ChaCha quarter-round, and it cannot represent the signed summation over competing paths that defines a differential-linear hull. Speck, with one modular addition per round, hides these issues; ChaCha’s quarter-round chains four additions together through XOR and rotation and exposes them brutally.
From this diagnosis the authors distill three concrete principles for the next generation of automated tools: link carry information across successive additions, for instance with joint carry-difference variables solved first on single quarter-rounds; enumerate the relevant differential-linear paths and sum their signed contributions explicitly, as the differential-cluster method does here; and validate predicted weights and signs on small-round instances with exact or GPU-measured correlations before trusting the model to search for long distinguishers. The paper’s supplementary material, including CUDA programs, C++ prediction code, MiniZinc models and a verification script for the complexity arithmetic, makes the entire pipeline reproducible.
For the cryptographic community, the study lands at an inflection point. The past three years have seen a rapid succession of improvements against reduced-round ChaCha, from syncopation at CRYPTO 2023 to bit puncturing at EUROCRYPT 2025 and divide-and-conquer trail enumeration at ASIACRYPT 2025, each shaving exponents off attacks that once seemed theoretical curiosities. The new work does not break ChaCha; it demonstrates that hybrid pipelines of MILP search, GPU-scale experimentation and optimization-based prediction can now quantify, and tighten, the exact components on which those attacks rest. As long as the security margin of the full 20-round cipher remains comfortable, that is precisely the kind of stress test a widely deployed primitive needs, and the methodological lessons about carry dependencies and signed path aggregation will echo well beyond ChaCha, informing automated cryptanalysis of the ARX ciphers that underpin lightweight security everywhere.
Subject of Research: Automated differential-linear cryptanalysis of the reduced-round ChaCha stream cipher
Article Title: Differential-linear cryptanalysis against ChaCha based on automated tools
Article References: Liu, G., Ren, G., Sun, B., Yu, B., & Li, C. (2026). Differential-linear cryptanalysis against ChaCha based on automated tools. Cybersecurity, 9(1), Article 228. https://doi.org/10.1186/s42400-026-00671-7
Image Credits: AI Generated
DOI: 10.1186/s42400-026-00671-7
Keywords: ChaCha, stream cipher, differential-linear cryptanalysis, MILP, MIQCP, GPU correlation estimation, ARX cipher, key recovery, bit puncturing, security margin, automated cryptanalysis, Cybersecurity journal
News Source: Denise Maddox. (October 9, 2026). Automated Tools Sharpen Cryptanalytic Attacks on Reduced-Round ChaCha. Scienmag.
