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

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 language | English |
---|---|

Pages | 125-126 |

Number of pages | 2 |

Publication status | Published - 2010 |

## Keywords

- cosic