International Association
for Cryptologic Research

In this paper, we present 4 major contributions to ARX ciphers and in particular, to the Salsa/ChaCha family of stream ciphers: (a) We propose an improved differential-linear distinguisher against ChaCha. To do so, we propose a new way to approach the derivation of linear approximations by viewing the algorithm in terms of simpler subrounds. Using this idea, we show that it is possible to derive almost all linear approximations from previous works from just 3 simple rules. Furthermore, we show that with one extra rule, it is possible to improve the linear approximations proposed by Coutinho and Souza at Eurocrypt 2021 (Coutinho and Neto, in: Canteaut, Standaert (eds) Advances in cryptology—EUROCRYPT 2021—40th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, October 17–21, 2021, proceedings, Part I. Lecture notes in computer science, vol 12696, Springer, 2021). (b) We propose a technique called Bidirectional Linear Expansions (BLE) to improve attacks against Salsa. While previous works only considered linear expansions moving forward into the rounds, BLE explores the expansion of a single bit in both forward and backward directions. Applying BLE, we propose the first differential-linear distinguishers reaching 7 and 8 rounds of Salsa and we improve Probabilistic Neutral Bit (PNB) key-recovery attacks against 8 rounds of Salsa. (c) At Eurocrypt 2022 (Dey et al in Revamped differential-linear cryptanalysis on reduced round chacha, Springer, 2022), Dey et al. proposed a technique to combine two input–output positions in a PNB attack. In this paper, we generalize this technique for an arbitrary number of input–output positions. Combining this approach with BLE, we are able to improve key recovery attacks against 7 rounds of Salsa. (d) Using all the knowledge acquired studying the cryptanalysis of these ciphers, we propose some modifications in order to provide better diffusion per round and higher resistance to cryptanalysis, leading to a new stream cipher named Forró. We show that Forró has higher security margin; this allows us to reduce the total number of rounds while maintaining the security level, thus creating a faster cipher in many platforms, especially in constrained devices. (e) Finally, we developed CryptDances , a new tool for the cryptanalysis of Salsa, ChaCha, and Forró designed to be used in high performance environments with several GPUs. With CryptDances it is possible to compute differential correlations, to derive new linear approximations for ChaCha automatically, to automate the computation of the complexity of PNB attacks, among other features. We make CryptDances available for the community at https://github.com/murcoutinho/cryptDances .