A multi-step key recovery attack on reduced round Salsa and ChaCha

Abstract

This paper develops a significantly enhanced attack on the ciphers Salsa and ChaCha. The existing attacks against these ciphers are mainly differential attacks. In this work, we produce an attack on 7.5-round Salsa and 6.5-round ChaCha20. These are the maiden key-recovery attacks on those versions of the two ciphers, in which we recover the key in multiple steps using several distinguishers. In comparison to the previous best-known attack against 7-round Salsa, the new attack method offers an improvement of $2^{7.5}$ times, while on 7.5-round Salsa20 and 6.5-round ChaCha20 our attack is the only existing one.

Keywords:

• ARX
• ChaCha
• differential cryptanalysis
• key recovery attack
• Salsa

Disclosure statement

No potential conflict of interest was reported by the author(s).

Table 1. Notations used in this article.

Table 2. Complexities of certain previous key recovery attacks on 256-bit Salsa20/7 and our results.

Table 3. Distinguishers for the attack against 7-round Salsa.

Table 4. Complexity details for the attack against Salsa20/7.

Table 5. Distinguishers for the attack against Salsa20/7.5.

Table 6. Distinguishers for the attack against ChaCha20/6.5.

Notes

1 The C++ source code of the backward bias determination is uploaded in GitHub (Garai 2023).

Additional information

Funding

Human Resource Development Centre, Council of Scientific and Industrial Research.

Notes on contributors

Hirendra Kumar Garai

Hirendra Kumar Garai earned his Master of Science (M.Sc.) in Mathematics from Visva-Bharati University, India in 2018. Presently, he is in his fourth year as a doctoral student at BITS Pilani, Hyderabad Campus, India. His research primarily centers on symmetric key cryptanalysis.

Sabyasachi Dey

Sabyasachi Dey got his Ph.D. in mathematics from the Indian Institute of Technology Madras in Chennai, India, in 2018. Presently, he is an Assistant Professor at the Birla Institute of Technology and Science (BITS) in Pilani, India. Symmetric key cryptology is one of his main research interests.