Differential-Linear Cryptanalysis of Reduced Round ChaCha

Abstract

ChaCha is a well-known stream cipher that has been used in many network protocols and software. In this paper, we study the security of reduced round ChaCha. First, by considering the differential-linear hull effect, we improve the correlation of a four-round differential-linear distinguisher proposed at FSE 2023 by providing other intermediate linear masks. Then, based on the four-round differential-linear distinguisher and the PNB method, by using the assignment 100 ··· 00 for consecutive PNBs, higher backward correlation is obtained and improved key recovery attacks of 7-round and 7.25-round ChaCha are obtained with time complexity 2^189.7 and 2^223.9, which improve the previously best-known attacks by 2^17.1 and 2^14.44, respectively. Finally, we consider the equivalence of the security between (R + 0.25)-round and (R + 0.5)^⊕-round ChaCha, and show that (R + 0.25)-round and (R + 0.5)^⊕-round ChaCha provide the same security against chosen(known) plaintext attacks. As a result, improved differential-linear cryptanalysis of 7.5^⊕-round ChaCha can also be obtained similarly to that of 7.25-round ChaCha, which improves the previously best-known attack by 2¹⁹.