Enhancing the MILP/MIQCP-Based Automatic Search for Differential-Linear Distinguishers of IoT-Friendly Block Ciphers Simon and Simeck

<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simon}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simeck}$ </tex-math></inline-formula> are two famous lightweight block cipher families, both of which have good implementation performance benefiting from their extremely simple round functions. So, they are suitable and friendly in use for the Internet of Things devices that require high security but low-latency and low-energy. In this article, we aim to improve the mixed-integer linear programming/mixed-integer quadratic constraint programming (MILP/MIQCP)-based method, to find better differential-linear (DL) distinguishers for the above ciphers, which can be exploited to mount distinguishing or key-recovery attacks. In particular, first, we give the completely precise mixed-integer linear programming (MILP) model to describe the linear part, and utilize the general expressions of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Gurobi}$ </tex-math></inline-formula> optimizer to model middle part in a quite easy way. Second, to explore DL trails in a reasonable time, we propose two heuristic strategies to speed up the searching process. Lastly, we introduce the transforming technique, which exploits the clustering effect on DL trails, to improve the estimated correlation of the DL approximation. By applying our enhanced method, we improve the DL distinguisher correlation from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{-59.75}$ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{-59.62}$ </tex-math></inline-formula> for 32-round <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simon128}$ </tex-math></inline-formula>, and extend the number of longest rounds of valid DL distinguishers for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simon32/48/64/96}$ </tex-math></inline-formula> from <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$11/16/16/25$ </tex-math></inline-formula> to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$14/17/21/26$ </tex-math></inline-formula>. For <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simeck}$ </tex-math></inline-formula>, we do not outperform the currently best work, but refresh Zhou et al.’s results (the first work to automate finding DL distinguishers for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simon/Simeck}$ </tex-math></inline-formula> using MILP/MIQCP). Our work not only provides a new insight on the automatic DL cryptanalysis, but also further confirms that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simon}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\textsf {Simeck}$ </tex-math></inline-formula> are sufficiently strong to resist the DL attacks.