New Features of Latin Dances:
Analysis of Salsa, ChaCha, and Rumba
Jean-Philippe Aumasson1, Simon Fischer1, Shahram Khazaei2, Willi Meier1, and Christian Rechberger3
1 FHNW, Windisch, Switzerland
2 EPFL,
Lausanne, Switzerland
3 IAIK, Graz, Austria
Abstract. The stream cipher Salsa20 was introduced by Bernstein in 2005 as a candidate
in the eSTREAM project, accompanied by the reduced versions Salsa20/8 and Salsa20/12. ChaCha is a variant of Salsa20 aiming at bringing better diffusion for similar performance. Variants of Salsa20 with up to 7 rounds (instead of 20) have been broken by differential cryptanalysis, while ChaCha has not been analyzed yet. We introduce a novel method for differential cryptanalysis of Salsa20 and ChaCha, inspired by correlation attacks and related to the notion of neutral bits. This is the first application of neutral bits in stream cipher cryptanalysis. It allows us to break the 256-bit version of Salsa20/8, to bring faster attacks on the 7-round variant, and to break 6- and 7-round ChaCha.
In a second part, we analyze the compression function Rumba, built as the XOR of four Salsa20 instances and returning a 512-bit output. We find collision and preimage attacks for two simplified variants, then we discuss differential attacks
on the original version, and exploit a high-probability differential to reduce complexity of collision search from 2
256 to 2
79 for 3-round Rumba. To prove the correctness of our approach we provide examples of collisions and near-collisions on simplified versions.
1 Introduction
Salsa20 [5] is a stream cipher introduced by Bernstein in 2005 as a candidate in the eSTREAM project [12], that has been selected in April 2007 for the third and ultimate phase of the competition. Three independent cryptanalyses were published [11,13,16], reporting key-recovery attacks for reduced versions with up to 7 rounds, while Salsa20 has a total of 20 rounds. Bernstein also submitted to public evaluation the 8- and 12-round variants Salsa20/8 and Salsa20/12 [6], though they are not formal eSTREAM candidates. Later he introduced ChaCha [4,3,8], a variant of Salsa20 that aims at bringing faster diffusion without slowing down encryption.
The compression function Rumba [7] was presented in 2007 in the context of a study of generalized birthday attacks [17] applied to incremental hashing [2], as the component of a hypothetical iterated hashing scheme. Rumba maps a 1536-bit value to a 512-bit (intermediate) digest, and Bernstein only conjectures collision resistance for this function, letting a further convenient operating mode provide extra security properties as pseudo-randomness.
