Paper 2022/720

A Model Set Method to Search Integral Distinguishers Based on Division Property for Block Ciphers

Abstract

In this paper, we focus on constructing an automatic search model that greatly improves efficiency with little loss of accuracy and obtains some better results in the construction of integral distinguishers for block ciphers. First, we define a new notion named BDPT Trail, which divides BDPT propagation into three parts: the division trail for K, division trail for L, and Key-Xor operation. Secondly, we improve the insufficiency of the previous methods of calculating division trails and propose an effective algorithm that can obtain more valid division trails for L of the S-box operation. Third, we propose a new algorithm that models each Key-Xor operation based on the MILP technique for the first time. Based on this, we can accurately characterize the Key-Xor operation by solving these MILP models. After that, by selecting the appropriate initial BDPT and stopping rules, we construct an automatic search model. As a result, our automatic search model is applied to search for integral distinguishers for some block ciphers. For GIFT-64, we find a 11-round integral distinguisher, which is one more round than the previous best results. For Rectangle, we find a better $10$-round integral distinguisher with 9 balanced bits, which has eight more bits than the previous best results. For Simon64, we can find more balanced bits than the previous longest distinguishers.