Abstract

Symmetric-key cryptographic primitives, such as block ciphers, play a pivotal role in achieving confidentiality, integrity, and authentication – which are the core services of information security. Since symmetric-key primitives do not rely on well-defined hard mathematical problems, unlike public-key primitives, there are no formal mathematical proofs for the security of symmetric-key primitives. Consequently, their security is guaranteed only by measuring their immunity against a set of predefined cryptanalysis techniques, e.g., differential, linear, impossible differential, and integral cryptanalysis.

The attacks based on cryptanalysis techniques usually include searching in an exponential space of patterns, and for a long time, cryptanalysts have performed this task manually. As a result, it has been hard, time-consuming, and an error-prone task. Indeed, the need for automatic tools becomes more pressing. This thesis is dedicated to investigating the security of symmetric-key cryptographic primitives, precisely block ciphers. One of our main goals is to utilize Mixed Integer Linear Programming (MILP) to automate the evaluation and the validation of block cipher security against a wide range of cryptanalysis techniques. Our contributions can be summarized as follows.

First, we investigate the security of two recently proposed block ciphers, CRAFT and SPARX-128/256 against two variants of differential cryptanalysis. We utilize the simple key schedule of CRAFT to construct several repeatable 2-round related-key differential characteristics with the maximum differential probability. Consequently, we are able to mount a practical key recovery attack on full-round CRAFT in the related-key setting. In addition, we use impossible differential cryptanalysis to assess SPARX-128/256 that is provable secure against single-trail differential and linear cryptanalysis. As a result, we can attack 24 rounds similar to the internal attack presented by the designers. However, our attack is better than the integral attack regarding the time and memory complexities.

Next, we tackle the limitation of the current Mixed Integer Linear Programming (MILP) model to automate the search for differential distinguishers through modular additions. The current model assumes that the inputs to the modular addition and the consecutive rounds are independent. However, we show that this assumption does not necessarily hold and the current model might lead to invalid attacks. Accordingly, we propose a more accurate MILP model that takes into account the dependency between consecutive modular additions. As a proof of the validity and efficiency of our model, we use it to analyze the security of Bel-T cipher—the standard of the Republic of Belarus.

Afterwards, we shift focus to another equally important cryptanalysis technique, i.e., integral cryptanalysis using the bit-based division property (BDP). We present MILP models to automate the search for the BDP through modular additions with a constant and modular subtractions. Consequently, we assess the security of Bel-T block cipher against the integral attacks. Next, we analyze the security of the tweakable block cipher T-TWINE. We present key recovery attacks on 27 and 28 rounds of T-TWINE-80 and T-TWINE-128, respectively.

Finally, we address the limitation of the current MILP model for the propagation of the bit-based division property through large non-bit-permutation linear layers. The current models are either inaccurate, which might lead to missing some balanced bits, or inefficient in terms of the number of constraints. As a proof of the effectiveness of our approach, we improve the previous 3- and 4-round integral distinguishers of the Russian encryption standard—Kuznyechik, and the 4-round one of PHOTON’s internal permutation (P288). We also report a 4-round integral distinguisher for the Ukrainian standard Kalyna and a 5-round integral distinguisher for PHOTON’s internal permutation (P288).