Differential-linear cryptanalysis against ChaCha based on automated tools

Abstract

ChaCha is a widely deployed ARX stream cipher used in modern secure-communication protocols. Reduced-round cryptanalysis assesses its security margin and tests automated methods without implying a threat to the full 20-round cipher. We combine MILP search, GPU correlation estimation, and MIQCP-based prediction. MILP finds 128 one-round differential characteristics and enumerates 61 paths whose differential weights are at most 14. GPU measurements resolve 39 paths, whose signed weighted sum is 2-31.16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{-31.16}$$\end{document}. Following the widely used practical strategy of truncated enumeration of dominant paths, this value gives 7- and 7.5-round distinguisher data complexities of 2160.20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{160.20}$$\end{document} and 2245.00\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{245.00}$$\end{document}. Applying the same four-round estimate to ReBitP gives data/time complexities of 2125.91/2140.00\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{125.91}/2^{140.00}$$\end{document} and 2122.96/2241.31\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{122.96}/2^{241.31}$$\end{document}. The MIQCP comparison quantifies substantial gaps between predicted and measured correlation weights and identifies concrete directions for refining ChaCha correlation models. Together, these results provide a reproducible path-cluster analysis, lower data and time complexity estimates for 7- and 7.5-round ChaCha, and experimentally grounded directions for automated correlation estimation.