Santanu Sarkar

Salsa and ChaCha are two of the most famous stream ciphers in recent times. Most of the attacks available so far against these two ciphers are differential attacks, where a difference is given as an input in the initial state of the cipher and in the output some correlation is investigated. This correlation works as a distinguisher. All the key recovery attacks against these ciphers are based on these observed distinguishers. However, the distinguisher in the differential attack was purely an experimental observation, and the reason for this bias was unknown so far. In this paper, we provide a full theoretical proof of both the observed distinguishers for Salsa and ChaCha. In the key recovery attack, the idea of probabilistically neutral bit also plays a vital role. Here, we also theoretically explain the reason of a particular key bit of Salsa to be probabilistically neutral. This is the first attempt to provide a theoretical justification of the idea of differential key recovery attack against these two ciphers.

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 Coutinho et al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218 and $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.

In FSE 2015, Armknecht et al. proposed a new technique to design stream ciphers, which involves repeated use of keybits in each round of the keystream bit generation. This technique showed the possibility to design stream ciphers where the internal state size is significantly lower than twice the key size. They proposed a new cipher based on this idea, named Sprout. But soon Sprout was proved to be insecure. In Crypto 2015, Lallemand et al. proposed an attack which was 2 10 times faster than the exhaustive search. But the new idea used in Sprout showed a new direction in the design of stream cipher, which led to the proposal of several new ciphers with small size of internal state. Fruit is a recently proposed cipher where both the key size and the state size are 80. In this paper, we attack full round Fruit by a divide-and-conquer method. Our attack is equivalent to 2 74.95 many Fruit encryptions, which is around 16.95 times faster than the average exhaustive key search. Our idea also works for the second version of Fruit.

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 25 iterations. In our work, we propose a method for achieving the right pairs with the help of listing, so that the extra multiplication of 25 in 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.86 to 2218.95 for 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.85 and 2121.40 respectively.

Salsa and ChaCha are well known names in the family of stream ciphers. In this paper, we first revisit the existing attacks on these ciphers. We first perform an accurate computation of the attack complexities of the existing technique instead of the estimation used in previous works. This improves the complexity by some margin. The differential attacks using probabilistic neutral bits against ChaCha and Salsa involve two probability biases: Forward probability bias (ϵd) and backward probability bias (ϵa). In the second part of the paper, we suggest a method to increase the backward probability bias, which helps reduce the attack complexity. Finally, we focus on the design principle of ChaCha. We suggest a slight modification in the design of this cipher as a countermeasure of the differential attacks against it. We show that the key recovery attacks proposed against ChaCha will not be effective on this modified version.

RC4 has attracted many cryptologists due to its simple structure. In [9], Paterson, Poettering and Schuldt reported the results of a large scale computation of RC4 biases. Among the biases reported by them, we try to theoretically analyze a few which show very interesting visual patterns. We first study the bias which relates the key stream byte, where k is the first byte of the secret key. We then present a generalization of the Roos bias. In 1995, Roos observed the bias of initial bytes S of the permutation after KSA towards f. Here we study the probability of S. Our generalization provides a complete correlation between z i. We also analyze the key-keystream relation z i = f i - 1 which was studied by Maitra and Paul [6] in FSE 2008. We provide more accurate formulas for the probability of both z i = i - f i {z-{i}=i-f-{i}} and z i = f i - 1 {z-{i}=f-{i-1}} for different i's than the existing works.

In this paper, we provide several improvements over the existing differential-linear attacks on ChaCha. ChaCha is a stream cipher which has 20 rounds. At CRYPTO 2020, Beierle et al. observed a differential in the 3.5-th round if the right pairs are chosen. They produced an improved attack using this, but showed that to achieve a right pair, we need 2 5 iterations on average. In this direction, we provide a technique to find the right pairs with the help of listing. Also, we provide a strategical improvement in PNB construction, modification of complexity calculation and an alternative attack method using two input-output pairs. Using these, we improve the time complexity, reducing it to 2 221.95 from 2 230.86 reported by Beierle et al. for 256 bit version of ChaCha. Also, after a decade, we improve existing complexity (Shi et al. ICISC 2012) for a 6-round of 128 bit version of ChaCha by more than 11 million times and produce the first-ever attack on 6.5-round ChaCha128 with time complexity 2 123.04.

In this paper, using a matrix, at first we revisit the work of Mantin on finding the probability distribution of the RC4 permutation after the completion of the KSA. After that, we extend the same idea to analyse the probabilities during any iteration of the Pseudo Random Generation Algorithm. Next, we study the bias of Zr = r (where Zr is the r-th output keystream byte), which is one of the significant biases observed in the RC4 output keystream. This bias has played an important role in the plaintext recovery attack proposed by Isobe et al. in FSE 2013. However, the accurate theoretical explanation of the bias of Zr = r is still a mystery. Though several attempts have been made to prove this bias, none of those provides an accurate justification. Here, using the results found with the help of the probability transition matrix we justify this bias of Zr = r accurately and settle this issue. The bias obtained from our proof matches the experimental observations perfectly.

Salsa20 and ChaCha20 are two of the most promising ciphers in recent days. The most significant step in the cryptanalysis of Salsa and ChaCha is the idea of Probabilistic Neutral Bits, which was introduced by Aumasson et al. (FSE 2008). After that, no significant improvement is achieved in the procedure of choosing Probabilistic Neutral Bits. The works in this direction mostly were concerned about forward probabilities. In this paper, we give a new algorithm to construct Probabilistic Neutral Bits. We use this algorithm to improve the existing attacks for reduced rounds of both Salsa and ChaCha. Our attacks on Salsa and Chacha are respectively around 2.27 and 5.39 times faster than the existing works of Choudhuri and Maitra (accepted in FSE 2017).

Salsa and ChaCha are two of the most well-known stream ciphers in last two decades. These two ciphers came into the picture when a massively used cipher RC4 was going through severe cryptanalysis and a significant number of observed weaknesses of it showed the requirement of new stream ciphers in the market. Later, ChaCha was adopted by Google as their encryption algorithm, which further increased the importance of research work on these two ciphers. Salsa and ChaCha have gone through differential key recovery attack up to the 8-th and 7-th round respectively. Initially, this attack used an experimentally observed distinguisher by observing a single bit position up to the 4th round for Salsa and 3rd round for ChaCha. Later, Maitra (2016) improved the attack complexity by minimizing the propagation of the difference after the first round using properly chosen IV values. Also, using this distinguisher, Choudhuri et al. (FSE 2016) provided a technique to construct a distinguisher for the next round of both the ciphers by observing multiple bits. Among all these attacks which were mostly based on experimental observations, theoretical works did not get much importance for these two ciphers. In this paper, we aim to theoretically investigate the reason behind these experimentally observed distinguishers for these chosen IV distinguishers, where the difference propagation is minimized up to the first round. We provide a mathematical proof of the observed probabilities for the distinguishers of both the ciphers in the single and multiple bits.