Differential and Linear Cryptanalysis of Lightweight Block Ciphers with MILP Approach

İlter, Murat Burhan
The security of block ciphers can be evaluated using cryptanalysis methods. The use of Mixed-Integer Linear Programming (MILP) has gained prominence due to its effectiveness in analyzing the security aspects of block ciphers. In this thesis, we explore the application of MILP techniques for conducting comprehensive differential and linear cryptanalysis. Our research specifically addresses fundamental challenges in the realm of differential and linear cryptanalysis. In this work, we study the cipher resistance against differential and linear attacks taking into account that ciphers need to be resistant to these attacks. In this context, aiming to identify the best differential and linear characteristics of a block cipher is a challenging problem. To tackle these challenges, our work introduces innovative MILP modeling methods for equations involving multiple xor operations. These models, denoted as Model 1 and Model 2, offer alternatives with fewer variables and constraints, respectively. Model 1 and Model 2 generally provide shorter solution times compared to the standard xor model. Importantly, these proposed models have broad applicability beyond differential and linear cryptanalysis, enhancing their utility in various cryptanalysis methods. We model well-known ciphers such as KLEIN, PRINCE, FUTURE, and IVLBC with MILP. The resulting models enable us to precisely determine the exact minimum number of active S-boxes, and the best differential and linear characteristics. Applying our developed MILP models provides improvements in the best single-key differential and linear characteristics for the examined ciphers.
Citation Formats
M. B. İlter, “Differential and Linear Cryptanalysis of Lightweight Block Ciphers with MILP Approach,” Ph.D. - Doctoral Program, Middle East Technical University, 2023.