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-$\mathcal{IV}$ pairs using certain 2-round criteria and connect that with clever tweaks of existing techniques related to Probabilistically Independent $\mathcal{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 $2^{245.84}$ and data amounting to $2^{99.47}$. Further, the sharpness of our attack can be highlighted by showing that Salsa20/$8$ can be broken with time $2^{186.01}$ and data $2^{99.73}$, which is a significant improvement over the best-known result of Coutinho et al. (Journal of Cryptology, 2023, time $2^{217.14}$ and data $2^{113.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.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in TOSC 2025
- Keywords
- Salsa20Differential-Linear CryptanalysisProbabilistically Neutral BitsProbabilistically Independent Bits
- Contact author(s)
-
sabya ndp @ gmail com
subho @ isical ac in
sarkar santanu bir @ gmail com
sharmanitinkumar685 @ gmail com - History
- 2025-02-20: approved
- 2025-02-19: received
- See all versions
- Short URL
- https://ia.cr/2025/289
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/289, author = {Sabyasachi Dey and Subhamoy Maitra and Santanu Sarkar and Nitin Kumar Sharma}, title = {Significantly Improved Cryptanalysis of Salsa20 With Two-Round Criteria}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/289}, year = {2025}, url = {https://eprint.iacr.org/2025/289} }