Paper 2021/643

On MILP-based Automatic Search for Bit-Based Division Property for Ciphers with (large) Linear Layers

Muhammad ElSheikh and Amr M. Youssef


With the introduction of the division trail, the bit-based division property (BDP) has become the most efficient method to search for integral distinguishers. The notation of the division trail allows us to automate the search process by modelling the propagation of the DBP as a set of constraints that can be solved using generic Mixed-integer linear programming (MILP) and SMT/SAT solvers. The current models for the basic operations and Sboxes are efficient and accurate. In contrast, the two approaches to model the propagation of the BDP for the non-bit-permutation linear layer are either inaccurate or inefficient. The first approach relies on decomposing the matrix multiplication of the linear layer into COPY and XOR operations. The model obtained by this approach is efficient, in terms of the number of the constraints, but it is not accurate and might add invalid division trails to the search space, which might lead to missing the balanced property of some bits. The second approach employs a one-to-one map between the valid division trails through the primitive matrix represented the linear layer and its invertible sub-matrices. Despite the fact that the current model obtained by this approach is accurate, it is inefficient, i.e., it produces a large number of constraints for large linear layers like the one of Kuznyechik. In this paper, we address this problem by utilizing the one-to-one map to propose a new MILP model and a search procedure for large non-bit-permutation layers. As a proof of the effectiveness of our approach, we improve the previous 3- and 4-round integral distinguishers of Kuznyechik and the 4-round one of PHOTON's internal permutation ($P_{288}$). We also report, for the fist time, a 4-round integral distinguisher for Kalyna block cipher and a 5-round integral distinguisher for PHOTON's internal permutation ($P_{288}$).

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MINOR revision.The 26th Australasian Conference on Information Security and Privacy (ACISP 2021)
Bit-based division propertyintegrallinear layerMILPKuznyechikKalynaPHOTON
Contact author(s)
m_elshei @ encs concordia ca
2021-05-17: received
Short URL
Creative Commons Attribution


      author = {Muhammad ElSheikh and Amr M.  Youssef},
      title = {On MILP-based Automatic Search for Bit-Based Division Property for Ciphers with (large) Linear Layers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/643},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.