Paper 2022/752

Provably Minimum Data Complexity Integral Distinguisher Based on Conventional Division Property

Abstract

Division property is an effective method for finding integral distinguishers for block ciphers, performing cube attacks on stream ciphers, and studying the algebraic degree of boolean functions. One of the main problems in this field is how to provably find the smallest input multiset leading to a balanced output. In this paper, we propose a new method based on division property for finding integral distinguishers with a provably minimum data complexity on permutation functions and block ciphers, in the conventional division property model. The new method is based on efficiently analyzing the algebraic normal form of the target output boolean function. We examine the proposed method on LBlock, TWINE, SIMON, Present, Gift, and Clyde-128 block ciphers. Although in most cases, the results are compliant with the distinguishers reported in the previous work, the proposed method proves the optimality of these results, in the conventional division property model. However, the proposed method can find distinguishers for 8-round Clyde-128 with a data complexity less than the previously reported one, based on conventional division property. The new method is also capable of determining the maximum number of balanced output bits in an integral distinguisher with a specified number of active bits. We propose an algorithm to exploit this capability and apply it to the studied ciphers. As a result, we determine the maximum number of balanced bits on integral distinguishers with minimum and non-minimum data complexities on the studied ciphers and report improved results on Gift-64, Present and SIMON64 in the conventional model.