Paper 2026/1424

Repeated Masks, Predictable Splices: Breaking AESpolyW and Its AEAD Applications

Abstract

AESpolyW, presented at the 2026 IEEE Symposium on Security and Privacy, is a wide-block encryption mode that preserves the length of each message. Its design lets operations of the Advanced Encryption Standard (AES) overlap with hash computations based on polynomial evaluation. Our attacks splice ciphertexts by copying blocks from one ciphertext to the same positions in another. On five-block messages, two encryption queries and one decryption query at a fixed public parameter, called a tweak, distinguish AESpolyW from a random permutation at that tweak. The two probabilities of reporting AESpolyW differ by more than \(1-2^{-3n}\), where \(n\) is the block size in bits. When AESpolyW decrypts the splice, an internal block-cipher inversion takes an output from an earlier encryption. The published proof treats such reuse as unlikely. The splice also works across distinct tweaks. We also attack three AESpolyW-based schemes for authenticated encryption with associated data (AEAD). All three use encode-then-encipher, adding a zero block before encryption and checking it after decryption. The zero block goes at the end, after the first block, or at the beginning. The tweak \(T=A\|\nu\) concatenates one block of associated data \(A\), which is authenticated without encryption, and one block of nonce \(\nu\), a public value intended for one-time use per key. Two encryptions at distinct nonces suffice to forge a new ciphertext that passes verification with probability one. In the experiment for indistinguishability under chosen-ciphertext attack (IND-CCA), we use one auxiliary encryption at a nonce distinct from the challenge nonce and at most one decryption. This identifies which of two chosen plaintexts was encrypted in the challenge with probability one.