A Unified Key Recovery Framework for Impossible Boomerang Attacks: Applications to Full-Round-ARADI and SKINNYe v2

The impossible boomerang attack is a powerful cryptanalytic technique, but existing key recovery methods face several limitations that restrict its applicability. Specifically, the key pre-guessing is coarse-grained, S-box details are ignored in the differential propagation, the complexity estimation and the key guessing order determination remain rudimentary. To overcome these issues, we introduce three key improvement measures. First, we propose a flexible partial key and difference pre-guessing technique based on directed graphs, enabling selective identification of required keys and differences for generating partial pairs and quartets. Second, we propose a pre-sieving technique to early eliminate invalid quartets by exploiting cipher-specific details. Third, we introduce an automatic key-guessing strategy based on the same directed graphs to efficiently determine valid guessing orders. We integrate these techniques to develop a unified key recovery framework for impossible boomerang attacks, accompanied by a formal and precise characterization of the overall complexity. This is the first framework to support flexible key and difference pre-guessing while incorporating block cipher details during key recovery for impossible boomerang attacks. Crucially, it enables the automatic generation of detailed recovery steps, a capability missing in prior work. As applications, under the four related-key/tweakey setting, we apply the framework to ARADI, a low-latency cipher proposed by the National Security Agency (NSA), and SKINNYe v2, a threshold-implementation-friendly cipher proposed at EUROCRYPT 2020. For ARADI, we achieve the first full-round attack with 2¹³⁰ data, 2^253.78 time, and 2^235.75 memory complexity. For SKINNYe v2, we present the first 34-round impossible boomerang attack with 2⁶⁶ data, 2^253.75 time, and 2^239.75 memory complexity. These results demonstrate the framework’s significance and its substantial improvement in advancing the impossible boomerang attack.