Paper 2025/158

Optimizing Key Recovery in Impossible Cryptanalysis and Its Automated Tool

Abstract

Key recovery for impossible differential (ID) cryptanalysis has seen few systematic advancements in nearly a decade, while the recent resurgence of impossible boomerang (IB) attacks has produced several powerful but disparate strategies. This, combined with the high complexity of existing tools for finding IB distinguishers, highlights the need for a unified optimization framework. In this paper, we address these gaps by introducing the Impossible Upper and Lower Boomerang Connectivity Tables (iUBCT/iLBCT), new lightweight tools for finding two-round contradictions. We then modernize key recovery by providing the first formal analysis of probabilistic extensions and by adapting the generic key guessing framework from rectangle cryptanalysis, which enables a systematic search for attacks with optimal complexities, particularly for memory. These techniques are integrated into a new Mixed-Integer Linear Programming (MILP)-based tool, leading to a suite of improved attacks on SKINNY, SKINNYee, Midori, and Deoxys-BC. Our results include the first 30-round attack on SKINNYee, extending the state of the art by one round. For other targets, our framework yields attacks with substantial memory and time reductions. In particular, we reduce the complexity of the best previous ID attack on SKINNY-128-384 by factors of up to $2^{131}$ (memory) and $2^{9}$ (time), and the best previous IB attack on Deoxys-BC-384 by factors of up to $2^{56}$ (memory) and $2^{25}$ (time). Many of these results provide new time-memory-data trade-offs, often achieving complexity reductions at the cost of moderately increased data requirements.