Paper 2025/289

Significantly Improved Cryptanalysis of Salsa20 With Two-Round Criteria

Abstract

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-$$ pairs using certain 2-round criteria and connect that with clever tweaks of existing techniques related to Probabilistically Independent $$ 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 $$ rounds. Specifically, Salsa20/$$, consisting of $$ secret key bits, can be cryptanalyzed with a time complexity of $$ and data amounting to $$. Further, the sharpness of our attack can be highlighted by showing that Salsa20/$$ can be broken with time $$ and data $$, which is a significant improvement over the best-known result of Coutinho et al. (Journal of Cryptology, 2023, time $$ and data $$). 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 $$-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.