Automatic Tool for Searching for Differential Characteristics in ARX Ciphers and Applications

Motivated by the algorithm of differential probability calculation of Lipmaa and Moriai, we revisit the differential properties of modular addition. We propose an efficient approach to generate the input-output difference tuples with non-zero probabilities. A novel concept of combinational DDT and the corresponding construction algorithm are introduced to make it possible to obtain all valid output differences for fixed input differences. According to the upper bound of differential probability of modular addition, combining the optimization strategies with branch and bound search algorithm, we can reduce the search space of the first round and prune the invalid difference branches of the middle rounds. Applying this tool, the provable optimal differential trails covering more rounds for SPECK32/48/64 with tight probabilities can be found, and the differentials with larger probabilities are also obtained. In addition, the optimal differential trails cover more rounds than exisiting results for SPARX variants are obtained. A 12-round differential with a probability of 2-54.83 for SPARX-64, and a 11-round differential trail with a probability of 2-53 for SPARX-128 are found. For CHAM-64/128 and CHAM-128/*, the 39/63-round differential characteristics we find cover 3/18 rounds more than the known results respectively.