International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba

Authors:
Jean-Philippe Aumasson
Simon Fischer
Shahram Khazaei
Willi Meier
Christian Rechberger
Download:
URL: http://eprint.iacr.org/2007/472
Search ePrint
Search Google
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. In this paper, 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, and it allows us to present the first break 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, constructed 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. We give examples of collisions over three rounds for a version without feedforward, and near-collisions of weight 16 for three rounds of the original compression function, and of weight 129 for four rounds.
BibTeX
@misc{eprint-2007-13752,
  title={New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Cryptanalysis, Stream Cipher, eSTREAM, Salsa20},
  url={http://eprint.iacr.org/2007/472},
  note={Extended version of a paper accepted for FSE 2008 simon.fischer@fhnw.ch 13865 received 18 Dec 2007},
  author={Jean-Philippe Aumasson and Simon Fischer and Shahram Khazaei and Willi Meier and Christian Rechberger},
  year=2007
}