Toolkit for the Differential Cryptanalysis of ARX-based Cryptographic Constructions

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

Research output: Contribution to conferenceAbstractpeer-review

Abstract

We propose a software toolkit, intended to automate the differential cryptanalysis of cryptographic constructions based on the operations addition, rotation and xor (ARX). The toolkit consists of several programs, each of which evaluates the probability that xor or additive differences propagate through a certain type of operation. Types of operations that are supported are xor, modular addition and multiplication by a constant.
A subset of the problems to which the proposed toolkit can be applied, have been studied in literature before. In [1], matrix multiplications are used to calculate the differential probability xdp+ of addition modulo 2n, when differences are expressed using xor, and the differential probability adp⊕ of xor when differences are expressed using addition modulo 2n. The time complexity of these computations is linear in the word size n. In our toolkit, we use the same concept of matrix multiplications. The generated matrices are correct by construction, and their size is automatically minimized. The main advantage of our technique, is that it is more general, and can therefore easily be extended to a larger number of cases. The proposed tools can be used to compute xdp+ and adp⊕, as well as xdp+(α, β,...→ γ)–the calculation of xdp+ for more than two inputs, and the differential probability xdp× C of multiplication by a constant C where differences are expressed by xor. The tool is also capable of efficiently counting the number of output differences for each of the mentioned operations. An instance where this problem occurs, is in the cryptanalysis of Threefish-512 [2], where an exponential-in-n time algorithm is proposed. Using the toolkit, this can be solved in linear time in n. The tool also provides a general algorithm to efficiently list the output differences with the highest probability, for a given type of difference and operation.
The cases handled by the toolkit, are encountered in many ARX-based cryptographic algorithms. Examples are the XTEA block cipher [3], the Salsa20 stream cipher family [4], and the hash functions MD5 and SHA-1. Other examples are 6 out of the 14 second-round candidates of NIST’s SHA-3 hash function competition [5]: BLAKE [6], Blue Midnight Wish [7], CubeHash [8], Shabal [9], SIMD [10] and Skein [11]. Our tools can assist in the cryptanalysis of each of these algorithms.
Original languageEnglish
Pages125-126
Number of pages2
Publication statusPublished - 2010

Keywords

  • cosic

Fingerprint

Dive into the research topics of 'Toolkit for the Differential Cryptanalysis of ARX-based Cryptographic Constructions'. Together they form a unique fingerprint.

Cite this