Paper 2021/1388

MILES: Modeling Large S-box in MILP Based Differential Characteristic Search

Tarun Yadav and Manoj Kumar

Abstract

Mixed integer linear programming (MILP) based tools are used to estimate the strength of block ciphers against the cryptanalytic attacks. The existing tools use partial difference distribution table (p-DDT) approach to optimize the probability of differential characteristics for large (≥8-bit) S-box based ciphers. We propose to use the full difference distribution table (DDT) with the probability of each possible propagation for MILP modeling of large S-boxes. This requires more than 16 variables to represent the linear inequalities of each propagation and corresponding probabilities. The existing tools (viz. Logic Friday) cannot handle the linear inequalities in more than 16 variables. In this paper, we present a new tool (namely MILES) to minimize the linear inequalities in more than 16 variables. This tool reduces the number of inequalities by minimizing the truth table corresponding to the DDT of S-box. We use our tool to minimize the linear inequalities for 8-bit S-boxes (AES and SKINNY) and get better results than existing tools. We show the application of MILES on 8-bit S-box based lightweight block cipher PIPO. There are 20621 inequalities in 23 variables corresponding to the possible propagations in DDT and these are minimized to 6035 inequalities using MILES. MILP model based on these linear inequalities is used to optimizethe probability of differential characteristics for round-reduced PIPO. For the first time, the MILP problem consisting the inequalities of full DDT for 8-bit S-box is solved to optimize the probability of differential characteristics.