The Additive Differential Probability of ARX

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

doi:10.1007/978-3-642-21702-9_20

The Additive Differential Probability of ARX

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

We analyze adp^ARX, 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 adp^ARXwith 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 adp^ARXcan 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 adp^ARX. 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 language	English
Title of host publication	Fast Software Encryption
Editors	Antoine Joux
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	342-358
Number of pages	17
ISBN (Print)	978-3-642-21702-9
DOIs	https://doi.org/10.1007/978-3-642-21702-9_20
Publication status	Published - 2011
Event	18th International Workshop on Fast Software Encryption - Copenhagen, Denmark Duration: 13 Feb 2011 → 16 Feb 2011 http://fse2011.mat.dtu.dk/

Conference

Conference	18th International Workshop on Fast Software Encryption
Abbreviated title	FSE 2011
Country/Territory	Denmark
City	Copenhagen
Period	13/02/11 → 16/02/11
Internet address	http://fse2011.mat.dtu.dk/

Access to Document

10.1007/978-3-642-21702-9_20

https://link.springer.com/chapter/10.1007%2F978-3-642-21702-9_20

Cite this

@inproceedings{088e2f419f9b4f98b945d88aa43eff0b,

title = "The Additive Differential Probability of ARX",

abstract = "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.",

author = "Vesselin Velichkov and Nicky Mouha and {De Canni{\`e}re}, Christophe and Bart Preneel",

year = "2011",

doi = "10.1007/978-3-642-21702-9_20",

language = "English",

isbn = "978-3-642-21702-9",

pages = "342--358",

editor = "Antoine Joux",

booktitle = "Fast Software Encryption",

publisher = "Springer",

address = "United Kingdom",

note = "18th International Workshop on Fast Software Encryption, FSE 2011 ; Conference date: 13-02-2011 Through 16-02-2011",

url = "http://fse2011.mat.dtu.dk/",

}

TY - GEN

T1 - The Additive Differential Probability of ARX

AU - Velichkov, Vesselin

AU - Mouha, Nicky

AU - De Cannière, Christophe

AU - Preneel, Bart

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-21702-9_20

DO - 10.1007/978-3-642-21702-9_20

M3 - Conference contribution

SN - 978-3-642-21702-9

SP - 342

EP - 358

BT - Fast Software Encryption

A2 - Joux, Antoine

PB - Springer

CY - Berlin, Heidelberg

T2 - 18th International Workshop on Fast Software Encryption

Y2 - 13 February 2011 through 16 February 2011

ER -

The Additive Differential Probability of ARX

Abstract / Description of output

Conference

Access to Document

Fingerprint

Cite this