Revisiting Cryptanalysis on ChaCha From Crypto 2020 and Eurocrypt 2021
Sabyasachi Dey, Chandan Dey, Santanu Sarkar, Willi Meier · IEEE Transactions on Information Theory · 2022
ChaCha has been one of the most prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack that exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3rd round. At Crypto 2020, Beierle et al. introduced for the first time the single bit distinguishers for 3.5th round, which contributed significantly to regaining the flow of the research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher at 3.5th round helped to produce a 7th round distinguisher of ChaCha and a further improvement in the key recovery. In this paper, first, we provide the theoretical framework for the distinguisher given by Beierle et al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at 3.5th round. Also, Beierle et al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next, we revisit the work of Coutinhoet al.(Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218and$2^{228.51}$respectively. We show that the differential correlation for the 3.5th round is much smaller than the claim of Coutinho et al. This makes the attack complexities much higher than their claim.