Paper 2025/1830

A New Approach to Improved PNB-based Attacks on Reduced-round ChaCha and Salsa

Anup Kumar Kundu, Indian Statistical Institute

Sucheta Chakrabarti, Indian Statistical Institute

Abstract

ChaCha and Salsa are two ARX based stream ciphers which are widely used in data encryption including TLS v1.3 standard, VPN software etc. Exploiting Probabilistic Neutral Bits (PNB) is one of the most significant cryptanalysis strategies for reduced-round versions of these ciphers. The seminal work using PNB by Aumasson et al. (FSE 2008) claims that the PNB set mostly depends on the output bit difference occurring in the intermediate round. The subsequent works mainly relied on the differential or differential-linear cryptanalysis, or multiple distinct input-output differentials for which the bias is higher than a threshold in the intermediate round. In this paper, we propose a new PNB set construction based on multiple output bit differences with respect to a single input bit difference only. We exploit the differentials to mount key recovery attacks using a multi-step procedure depending on our new PNB set. Our attack achieves a time complexity of $2^{167.90}$ for ChaCha20/7 and $2^{183.54}$ for Salsa20/8 in 256-bit versions, beating all the existing PNB-based attacks on ChaCha20/7 and Salsa20/8 by a significant margin. Further, both our time and data complexities for ChaCha20/7.5 are better than the latest published works by Flórez-Gutiérrez and Todo (Eurocrypt 2025 and Asiacrypt 2025). For 128-bit versions, our attack procedure results in a time complexity of $2^{115.24}$ for ChaCha20/6.5 and $2^{98.40}$ for Salsa20/7.5 respectively. We have also verified our attack experimentally on a published toy version of ChaCha (FSE 2023).

Note: Updated to include comparison with recent results.

@misc{cryptoeprint:2025/1830,
      author = {Goutam Paul and Anup Kumar Kundu and Sucheta Chakrabarti},
      title = {A New Approach to Improved {PNB}-based Attacks on Reduced-round {ChaCha} and Salsa},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1830},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1830}
}