Usage of mixed integer linear programming in cryptanalysis of block ciphers

Abstract

Cryptanalysis of block ciphers remains a fundamental area of research in symmetric cryptography, especially as lightweight cryptographic algorithms continue to be deployed in resource-constrained sytems like IoT devices and RFID systems, and embedded applications. These environments often impose strict limitations on hardware resources, energy consumption, and memory footprint, rendering standard algorithms like AES inefficient or impractical. As a result, alternative lightweight ciphers—such as the ITUbee block cipher—have been proposed to meet these requirements. However, the adoption of new algorithms necessitates rigorous and comprehensive security evaluations. Among the most influential cryptanalytic methods are differential cryptanalysis and linear cryptanalysis, which target structural properties of the cipher to exploit non-random behavior. Additionally, related-key differential attacks provide an extended model that considers adversaries with control over key differences, making them particularly relevant in analyzing ciphers with simple or predictable key schedules. For any cipher, resistance against these attacks is essential. Manual analysis of differential, linear and related-key differential characteristics becomes increasingly infeasible as cipher complexity grows. Changes to components such as the S-box, Feistel structure, or matrix-based linear layer often require re-analysis from scratch. This has motivated the development of automated cryptanalysis techniques, where MILP become a leading approach. MILP enables the systematic formulation of cryptanalytic problems using linear constraints, allowing modeling of S-box, XOR operations, MDS matrices and propagation probabilities. In recent years, MILP modeling of cryptographic attacks applied to many different block ciphers to prove the security of the cipher against cryptographic attacks. In traditional cryptanalysis methods (pattern search methods, brute force method, tree-search method etc. )searching all possible patterns is impossible for most cipher because of the computational costs. Unlike the traditional methods, MILP is very efficient tool for searching possible patterns for most of the ciphers(Especially for used for lightweight ciphers because of small structures like s-box). In this thesis, we begin by presenting an overview of symmetric encryption algorithms, including Substitution-Permutation Networks, Feistel structures, ARX ciphers, and sponge constructions. We then provide a comprehensive discussion of cryptanalytic techniques, with particular emphasis on linear, differential, and related-key differential cryptanalysis. Subsequently, we introduce the fundamentals of Linear Programming and Mixed-Integer Linear Programming , and formally define key concepts such as the branch number and the H-representation of block cipher components. We describe two algorithms—Greedy and New-Reduction—developed for minimizing the number of constraints required to represent cryptographic components within MILP models. Following this, we detail the MILP-based modeling of essential cipher operations, including XOR, linear transformations, S-boxes, and three-forked branches. The ITUbee block cipher is then examined in detail, and the previously introduced methods are applied to this cipher. We construct MILP models to assess the security of the ITUbee algorithm against differential, linear, and related-key differential attacks. These models are used to derive corresponding cryptanalytic characteristics. While the original designers of ITUbee claimed theoretical resistance to linear and differential attacks, our MILP-based analysis confirms that such attacks are ineffective beyond three rounds. Furthermore, While the designers suggested security after 10 rounds, our models shows that there is no practical related-key differential characteristics after 8 rounds. The obtained characteristics are presented within the thesis, and all MILP models are provided in the appendix for reference.