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 2189.7 and 2223.9, which improve the previously best-known attacks by 217.1 and 214.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 219.

Keywords

• ChaCha
• Differential-linear cryptanalysis
• Probabilistic Neutral Bits(PNBs)