International Association
for Cryptologic Research

Over the past decade and a half, cryptanalytic techniques for Salsa20 have been increasingly refined, largely following the overarching concept of Probabilistically Neutral Bits (PNBs) by Aumasson et al. (FSE 2008). In this paper, we present a novel criterion for choosing key-IV pairs using certain 2-round criteria and connect that with clever tweaks of existing techniques related to Probabilistically Independent IV bits (earlier used for ARX ciphers, but not for Salsa20) and well-studied PNBs. Through a detailed examination of the matrix after initial rounds of Salsa20, we introduce the first-ever cryptanalysis of Salsa20 exceeding 8 rounds. Specifically, Salsa20/8.5, consisting of 256 secret key bits, can be cryptanalyzed with a time complexity of 2245.84 and data amounting to 299.47. Further, the sharpness of our attack can be highlighted by showing that Salsa20/8 can be broken with time 2186.01 and data 299.73, which is a significant improvement over the best-known result of Coutinho et al. (Journal of Cryptology, 2023, time 2217.14 and data 2113.14). Here, the refinements related to backward biases for PNBs are also instrumental in achieving the improvements. We also provide certain instances of how these ideas improve the cryptanalysis on 128-bit versions. In the process, a few critical points are raised on some existing state-of-the-art works in this direction, and in those cases, their estimates of time and data are revisited to note the correct complexities, revising the incorrect numbers.

In this paper we present several analyses on ChaCha, a software stream cipher. First, we consider a divide-and-conquer approach on the secret key bits by partitioning them. The partitions are based on multiple input-output differentials to obtain a significantly improved attack on 6-round ChaCha256 with a complexity of 299.48. It is 240 times faster than the currently best known attack. This is the first time an attack on a round reduced ChaCha with a complexity smaller than 2k/2, where the secret key is of k bits, has been successful.Further, all the attack complexities related to ChaCha are theoretically estimated in general and there are several questions in this regard as pointed out by Dey, Garai, Sarkar and Sharma in Eurocrypt 2022. In this regard, we propose a toy version of ChaCha, with a 32-bit secret key, on which the attacks can be implemented completely to verify whether the theoretical estimates are justified. This idea is implemented for our proposed attack on 6 rounds. Finally, we show that it is possible to estimate the success probabilities of these kinds of PNB-based differential attacks more accurately. Our methodology explains how different cryptanalytic results can be evaluated with better accuracy rather than claiming that the success probability is significantly better than 50%.