Paper 2026/2811

More Keys, Less Commitment: Key-Committing Attacks on BBB Accordions via Encode-then-Encipher and a Key-Committing Transform

Abstract

Cryptographic accordions with beyond-birthday-bound (BBB) security are being actively studied in connection with NIST’s ongoing standardization effort. We show that BBB security of an accordion does not necessarily strengthen key commitment of AE built from it: in many BBB accordions, additional keys introduced for BBB security give an adversary extra degrees of freedom. Exploiting this observation, we present $O(1)$ key-committing attacks on a broad range of AE schemes built from BBB accordions, mostly via the Encode-then-Encipher (EtE) paradigm, including CHCTR2, eCTR-based accordions, THCTR, HCTR+, TCT2, and bbb-ddd-AES under a natural polynomial-hash instantiation. To address this issue, we propose CACH, a black-box transform from BBB-secure accordions to robust AE (RAE) with key-committing security. CACH achieves BBB multi-user RAE security and achieves $t/2$-bit key-committing security with a $t$-bit tag for $n \le t \le 2n$ in the ideal-cipher model. CACH uses only AES-based components and supports all AES key sizes, making it compatible with NIST’s design goals. We instantiate CACH with CHCTR2. CACH-CHCTR2 with AES-256 outperforms EtE-HCTR2 with Rijndael-256 and EtE-CHCTR2 for short messages.