Paper 2013/328

Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20

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, there is currently no rigorous understanding of the security of ARX ciphers against one of the most common attacks in symmetric-key cryptography: differential cryptanalysis. In this paper, we introduce a tool to search for optimal differential characteristics for ARX ciphers. Our technique is very easy to use, as it only involves writing out simple equations for every addition, rotation and XOR operation in the cipher, and applying an off-the-shelf SAT solver. As is commonly done for ARX ciphers, our analysis assumes that the probability of a characteristic can be computed by multiplying the probabilities of each operation, and that the probability of the best characteristic is a good estimate for the probability of the corresponding differential. Using extensive experiments for Salsa20, we find that these assumptions are not always valid. To overcome these issues, we propose a method to accurately estimate the probability of ARX differentials.

Note: Updated affiliations.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown status
Keywords
Differential cryptanalysisARXEvaluation ToolSAT solverSalsa20
Contact author(s)
Nicky Mouha @ esat kuleuven be
History
2013-11-13: revised
2013-06-02: received
See all versions
Short URL
https://ia.cr/2013/328
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/328,
      author = {Nicky Mouha and Bart Preneel},
      title = {Towards Finding Optimal Differential Characteristics for ARX: Application to Salsa20},
      howpublished = {Cryptology ePrint Archive, Paper 2013/328},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/328}},
      url = {https://eprint.iacr.org/2013/328}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.