Mixderive: A New Framework of Deriving Linear Approximations and Improved Differential-Linear Distinguishers for ChaCha

ChaCha is a well-known ARX-based cipher and has become one of the most widely used ciphers in the real world. In this paper, a systematic three-case framework called Mixderive to find linear approximations for ChaCha is proposed. By this new framework, new linear approximations for 3.5- and 4-round ChaCha are found, which are significantly better than the existing linear approximations proposed at EUROCRYPT 2021 and ASIACRYPT 2022. These improvements confirm the effectiveness of Mixderive. In addition, new 2- and 2.5-round linear approximations for ChaCha are found by Mixderive. Based on these new findings, new differential-linear distinguishers for 7- and 7.5-round ChaCha256 with complexities \({2^{162.28}}\) and \({2^{247.08}}\) are proposed, which improve the best known distinguishers by factors of \({2^{4.61}}\) and \({2^{4.46}}\) , respectively. To the best of our knowledge, both cryptanalytic results are the best.