Paper 2026/1963

Impossible Polytopic Attack Revisited: Low-Data Distinguishers and Attacks

Abstract

Block ciphers including several variants of the well-known \textsf{AES}, the newly proposed tweakable block cipher \textsf{Deoxys-BC} (standardized by ISO/IEC and renamed Deoxys-TBC), and \textsf{ChiLow} (EUROCRYPT 2025) adopt key sizes larger than their block sizes. These designs offer security higher than the block size. This paper evaluates the security of such ciphers by revisiting the Impossible Polytopic Attack (\ipa{}, proposed by Tyge Tiessen at EUROCRYPT 2016). We show that \ipa{} can build longer-round distinguishers, enabling attacks on more rounds. Moreover, the attack is applicable under the known-plaintext (KP) setting. Towards this end, we first formalize the distinguisher from Tiessen’s original work and establish a generic framework for distinguisher construction. We further propose two novel methods to lower the corresponding construction complexity. Moreover, we develop two dedicated key-recovery techniques, namely the plaintext‑grouping technique and the partition-guess-filter technique. The former allows cryptanalysis on more rounds of target ciphers, while the latter substantially lowers the overall attack complexity. Finally, we build the first framework for \ipa{}. We apply our method to the chosen-plaintext/ciphertext (CP/CC) and KP scenarios under the single-key setting. As a result, we obtain new distinguishers and attacks against \textsf{AES}, \textsf{Deoxys-BC}, \textsf{Joltik-BC}, \textsf{LED-128}, and \textsf{ChiLow-32}. Notably, 10-round attacks are constructed on \textsf{Deoxys-BC-384} and \textsf{Joltik-BC-192}. Compared with impossible differential attacks, which are closely related and extensively studied, the proposed results outperform such attacks by one round. Furthermore, a novel full-round attack on \textsf{ChiLow-32} is constructed under the KP setting, achieving the state-of-the-art attack with optimal data complexity and overall complexity.