Milp Modeling of Matrix Multiplication: Cryptanalysis of Klein and Prince

Abstract

Mixed-integer linear programming (MILP) techniques are widely used in cryptanalysis, aiding in the discovery of optimal linear and differential characteristics. This paper delves into the analysis of block ciphers KLEIN and PRINCE using MILP, specifically calculating the best linear and differential characteristics for reduced-round versions. Both ciphers employ matrix multiplication in their diffusion layers, which we model using multiple XOR operations. To this end, we propose two novel MILP models for multiple XOR operations, which use fewer variables and constraints, proving to be more efficient than standard methods for XOR modeling. For differential cryptanalysis, we identify characteristics with a probability of 2−59 for 7 rounds of KLEIN and a probability of 2−56 for 7 rounds of PRINCE. In linear cryptanalysis, we identify characteristics with a bias of 2−27 for 6 rounds of KLEIN and a bias of 2−29 for 7 rounds of PRINCE. These results establish the best single-key differential and linear distinguishers for these ciphers in the literature. © TÜBİTAK.