SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications - Bin HU; Xiao TAN; Senpeng WANG (Tongxin xuebao)
To improve the efficiency of automatic search, an algorithm for searching the optimal differential characteristics based on SAT model was proposed by combining the divide-and-conquer strategy.The search space was divided into disjoint subsets by using the information from Matsui boundary conditions of arbitrary continuous rounds.By analyzing the relationships between satisfiability of differential models based on SAT, a descending branch search chain model was proposed.Furthermore, at the model optimization level, the number of subsets that need to be searched and partitioned was decreased.At the level of algorithm implementation, the search space was reduced by utilizing the parallel technology.Finally, the accelerated algorithm was applied to SPECK family of ARX cryptographic algorithms.The 20, 14, 11-round optimal differential characteristics of SPECK-48, SPECK-96, SPECK-128 are obtained, which increase the previous best results by 1, 4, 2 rounds respectively.