Significantly Improved Cryptanalysis of Salsa20 with Two-Round Criteria

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.