Extending the Applicability of the Mixed-Integer Programming Technique in Automatic Differential Cryptanalysis

We focus on extending the applicability of the mixed-integer programming (MIP) based method in differential cryptanalysis such that more work can be done automatically. Firstly, we show how to use the MIP-based technique to obtain almost all high probability 2-round iterative related-key differential characteristics of PRIDE (a block cipher proposed in CRYPTO 2014) automatically by treating the \(g_i^{(j)}(\cdot )\) function with a special kind of modulo addition operations in the key schedule algorithm of PRIDE as an \(8 \times 8\) S-box and partially modelling its differential behavior with linear inequalities. Note that some of the characteristics presented in this paper has not been found before, and all the characteristics we found can be used to attack the full-round PRIDE in the related-key model. Secondly, we show how to construct MIP models whose feasible regions are exactly the sets of all possible differential characteristics of SIMON (a family of lightweight block ciphers designed by the U.S. National Security Agency). With this method, there is no need to filter out invalid characteristics due to the dependent inputs of the AND operations. Finally, we present an MIP-based method which can be used to automatically analyze how the differences at the beginning and end of a differential distinguisher propagate upwards and downward. Note that how the differences at the ends of a differential distinguisher propagate, together with the probability of the differential distinguisher, determine how many outer rounds can be added to the distinguisher, which key bits can be recovered without exhaustive search, and how to identify wrong pairs in the filtering process. We think this work serves to further strengthens the position of the MIP as a promising tool in automatic differential cryptanalysis.