Automatic Search for Value-Constraint DS-MITM Attacks with Table Lookups

Demirci-Selçuk meet-in-the-middle (DS-MITM) attacks are effective against many primitives and are responsible for some state-of-the-art attacks on widespread standards, such as round-reduced AES. As with other types of attacks, the community has proposed automatic tools to help cryptographers find distinguishers and attacks. The tools developed by Shi et al. at ASIACRYPT 2018 and EUROCRYPT 2023 can already capture some of the improvements to the basic technique, such as differential enumeration and key dependencies. However, recent works have proposed further technical refinements to DS-MITM attacks, such as value constraints, which have led to improved attacks on round-reduced AES but still lack automation support. In this work, we extend the earlier modelling approaches of DS-MITM attacks by proposing a framework that integrates value constraints and table lookups. We apply our framework not only to SPNs, such as variants of Rijndael, SKINNY, and Vistrutah, but also to the Type-II Feistel design TWINE and the bit-oriented balanced Feistel cipher SIMON. We show improved DS-MITM attacks on these variants, including the first 10-round DS-MITM attack on Rijndael-256-256, demonstrating the effectiveness of the technique and our framework.