Paper 2024/1008

Multi-round Dependency Identification: Theoretical Construction and Automatic Search of Impossible Boomerang Distinguishers

Abstract

The impossible boomerang (IB) attack is one of the most powerful cryptanalytic techniques for block ciphers, with notable successes against AES. However, constructing IB distinguishers—the core component of IB attack—remains a fundamental challenge: existing methods are restricted to specific cipher structures, cannot detect contradictions spanning more than two rounds, and lack a unified framework across attack settings. To solve these issues, this paper introduces three hierarchically complementary methods for constructing IB distinguishers: (1) a GEBCT-based method breaking the 2-round contradiction barrier; (2) a state-based method proven exactly equivalent to the definition of IB distinguishers (the most precise available); and (3) a structural method for fast security evaluation. We prove their inclusion relations, unify all prior methods, and connect the state-based method to the Quasidifferential Framework within IB distinguishers. Furthermore, we develop a unified SAT/SMT-based framework that automatically searches distinguishers under single-key, two-related-key, and four-related-key settings. We evaluate on seven representative block ciphers covering almost major design paradigms: We present the first IB distinguishers for ARX cipher SPECK (ISO/IEC standard) and CHAM, bit-permutation cipher GIFT-64 (CHES'17, an example with 5-round contradictions), and key-dependent Sbox cipher PRINTcipher48 (CHES'20). We obtain the first 5-round related-key IB distinguishers for AES-128 (NIST's standard with nonlinear key schedule, first automatically searched), and 1-round improvements over prior IB distinguishers for tweakable cipher SKINNY-64/192 (CRYPTO'16) and SKINNYee (CRYPTO'22). All IB distinguishers outperform the best impossible differentials by 1--4 rounds, including a PRINTcipher48 result that disproves the long-standing claim about single-key IB distinguisher limitations. Finally, we present a 31-round related-key IB attack on SKINNYee, the best result to date.