The existing differential-linear attacks against ChaCha are based on the idea of probabilistic neutral bits (PNB), which are the key bits with less influence on the distinguisher. This paper presents a novel approach, which is based on bringing about some transformation in the PNB-based attack procedure that significantly improves upon existing attacks. Unlike previous methods that focused on finding PNBs for the entire linear combination of multiple bits of output difference, we separately identify PNBs for each output difference bit that constitutes the linear combination. This divide-and-conquer approach helps to reduce the number of operations to observe the PNB-based differential-linear correlation, providing significant gain in the attack complexity. Specifically, we present an attack on 7-round ChaCha256 that is 213.91 times faster than the existing best attack. We are able to produce the first-ever attack on the 7.5-round ChaCha256. Apart from these, this idea also provides significant improvement on 7.25-round ChaCha256, as well as the 6-round and 6.5 round versions of ChaCha128.

We present numerous refinements to the previous differential-linear attacks on ChaCha in this study. Beierle et al. discovered a 3.5-round differential at CRYPTO 2020, which was based on the condition that suitable key-IV pairs are picked, which they termed as 'right pair'. They were able to refine their approach by doing so, but they also observed that the acquisition of a right pair requires an average of 25iterations. In our work, we propose a method for achieving the right pairs with the help of listing, so that the extra multiplication of 25in the overall complexity can be avoided. In addition, we present a tactical enhancement in 'Probabilistic Neutral Bit'- searching algorithm, a change in complexity computation and a novel attack strategy based on two input-output pairs. We employ them to lower the attack complexity from 2230.86to 2218.95for the 7-round ChaCha256. Furthermore, after almost ten years, we enhance the complexity of a 6-round 128-bit version of ChaCha (Shi et al: ICISC 2012) by more than 78 million times and for the first time, propose attacks on 7.25-round ChaCha256 and 6.5-round ChaCha128 with time complexities 2244.85and 2121.40respectively.

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.