The Additive Differential Probability of ARX

Vesselin Velichkov, Nicky Mouha, Christophe De Cannière, Bart Preneel

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We analyze adpARX, the probability with which additive differences propagate through the following sequence of operations: modular addition, bit rotation and XOR (ARX). We propose an algorithm to evaluate adpARX with a linear time complexity in the word size. This algorithm is based on the recently proposed concept of S-functions. Because of the bit rotation operation, it was necessary to extend the S-functions framework. We show that adpARX can differ significantly from the multiplication of the differential probability of each component. To the best of our knowledge, this paper is the first to propose an efficient algorithm to calculate adpARX. Accurate calculations of differential probabilities are necessary to evaluate the resistance of cryptographic primitives against differential cryptanalysis. Our method can be applied to find more accurate differential characteristics for ARX-based constructions.
Original languageEnglish
Title of host publicationFast Software Encryption
EditorsAntoine Joux
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages17
ISBN (Print)978-3-642-21702-9
Publication statusPublished - 2011
Event18th International Workshop on Fast Software Encryption - Copenhagen, Denmark
Duration: 13 Feb 201116 Feb 2011


Conference18th International Workshop on Fast Software Encryption
Abbreviated titleFSE 2011
Internet address

Cite this