Paper 2019/476

On MILP-Based Automatic Search for Differential Trails Through Modular Additions with Application to Bel-T

Muhammad ElSheikh, Ahmed Abdelkhalek, and Amr M. Youssef


Using modular addition as a source of nonlinearity is frequently used in many symmetric-key structures such as ARX and Lai--Massey schemes. At FSE'16, Fu \etal proposed a Mixed Integer Linear Programming (MILP)-based method to handle the propagation of differential trails through modular additions assuming that the two inputs to the modular addition and the consecutive rounds are independent. However, this assumption does not necessarily hold. In this paper, we study the propagation of the XOR difference through the modular addition at the bit level and show the effect of the carry bit. Then, we propose a more accurate MILP model to describe the differential propagation through the modular addition taking into account the dependency between the consecutive modular additions. The proposed MILP model is utilized to launch a differential attack against Bel-T-256, which is a member of the Bel-T block cipher family that has been adopted recently as a national standard of the Republic of Belarus. In particular, we employ the concept of partial Differential Distribution Table to model the 8-bit S-Box of Bel-T using a MILP approach in order to automate finding a differential characteristic of the cipher. Then, we present a $4\frac{1}{7}$-round (out of 8) differential attack which utilizes a $3$-round differential characteristic that holds with probability $2^{-111}$. The data, time and memory complexities of the attack are $2^{114}$ chosen plaintexts, $ 2^{237.14} $ $4\frac{1}{7}$-round encryptions, and $2^{224}$ 128-bit blocks, respectively.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. 11th International Conference on Cryptology, AFRICACRYPT 2019
Differential cryptanalysisMILPModular AdditionARXBel-T
Contact author(s)
m_elshei @ encs concordia ca
2019-05-10: received
Short URL
Creative Commons Attribution


      author = {Muhammad ElSheikh and Ahmed Abdelkhalek and Amr M.  Youssef},
      title = {On MILP-Based Automatic Search for Differential Trails Through Modular Additions with Application to Bel-T},
      howpublished = {Cryptology ePrint Archive, Paper 2019/476},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.