Improved Automatic Search Tool for Bit-Oriented Block Ciphers and Its Applications

摘要

The tool based on Mixed-integer Linear Programming (MILP) is simple and effective that frequently used in searching some different types of distinguishers recently. In this paper, we mainly focus on the automatic search method using MILP and the optimizer Gurobi for bit-oriented block ciphers. We introduce the OPB file format to construct MILP models for the bit-oriented block ciphers. Compared to the LP file format, it is more concise and suitable to deal with boolean variables. And we modify the high-level strategy to reduce the solution time by setting parameter MIP-Focus provided by the optimizer Gurobi. Moreover, the new simple linear inequalities of differential pattern propagation of modular addition are given without considering the differential probability in the impossible differential search. As applications, we give the exact lower bounds of the number of differential active s-boxes for 5～12 rounds LBlock in the related-key model and all of impossible differentials limited the input and output differences to only 1 active bit for the full versions of SPECK.