Cryptology ePrint Archive: Report 2013/328

A Proof that the ARX Cipher Salsa20 is Secure against Differential Cryptanalysis

Nicky Mouha and Bart Preneel

Abstract: An increasing number of cryptographic primitives are built using the ARX operations: addition modulo $2^n$, bit rotation and XOR. Because of their very fast performance in software, ARX ciphers are becoming increasingly common. However, not a single ARX cipher has yet been proven to be secure against one of the most common attacks in symmetric-key cryptography: differential cryptanalysis. In this paper, we prove that no differential characteristic exists for 15 rounds of Salsa20 with a higher probability than $2^{-130}$. Thereby, we show that the full 20-round Salsa20 with a 128-bit key is secure against differential cryptanalysis, with a security margin of 5 rounds. Our proof holds both in single-key and related-key settings. Furthermore, our proof technique only involves writing out simple equations for every addition, rotation and XOR operation in the cipher, and applying an off-the-shelf SAT solver. To prove that Salsa20 is secure against differential cryptanalysis requires only about 20 hours of computation on a single CPU core.

Category / Keywords: Differential cryptanalysis, ARX, Salsa20, SAT solver

Date: received 29 May 2013, last revised 31 May 2013

Contact author: Nicky Mouha at esat kuleuven be

Available format(s): PDF | BibTeX Citation

Note: Updated affiliations.

Version: 20130602:170111 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]