An Automated Model to Search For Differential Meet-In-The-Middle Attack: Applications to AndRX Ciphers

Differential meet-in-the-middle (MITM) cryptanalysis, recently introduced by Boura et al., has emerged as a powerful and versatile technique for assessing the security of modern block cipher designs. Since its introduction, this method has been effectively applied to a variety of block ciphers, including different variants of \cipher{SKINNY}, \cipher{CRAFT}, and \cipher{AES}. However, identifying such attacks manually-especially on bit-oriented ciphers with large block sizes-can be a complex and error-prone process, which underscores the growing importance of automated solutions in this domain. In this work, we present, for the first time to the best of our knowledge, a novel and efficient automated tool for constructing optimized differential MITM attacks on bit-oriented block ciphers, with a particular focus on AndRX designs. Our framework begins by modeling an efficient constraint programming (CP) model to search for single-key optimal differential trails in AndRX ciphers. Building on this, we propose a unified bitwise CP model to automatically construct optimized differential MITM attacks within the same design framework. Furthermore, we incorporate two dedicated optimization strategies-namely, the \textit{equivalent subkey technique} and the \textit{selective key guessing technique}-both of which are tailored to the structural properties of AndRX ciphers and significantly enhance key recovery efficiency. Additionally, we also apply two additional optimization techniques: the \textit{parallel partitioning technique} and \textit{reducing data with imposed conditions techniques} to further enhance the differential MITM attack on AndRX ciphers. To demonstrate the practical effectiveness of our tool, we apply it to all versions of \cipher{SIMON} and \cipher{Simeck}, two widely studied representatives of the AndRX family, and report improved cryptanalytic results. All of these results improve the number of attacked rounds compared to the best-known classical meet-in-the-middle (MITM) and Demirci-Selçuk MITM (DS-MITM) attacks on the corresponding versions of \cipher{SIMON} and \cipher{Simeck}. These findings highlight the strength and flexibility of our automated tool. Notably, our automated framework for constructing differential MITM attacks works at the bit level and is generic in design, allowing it to be applied to a wide range of bit-oriented block ciphers beyond the AndRX family.