Paper 2026/085

Beyond-Birthday-Bound Security with HCTR2: Cascaded Construction and Tweak-based Key Derivation

Abstract

The block cipher (BC) mode for realizing a variable-input-length strong tweakable pseudorandom permutation (VIL-STPRP), also known as the accordion mode, is a rapidly growing research field driven by NIST's standardization project, which considers AES as a primitive. Widely used VIL-STPRP modes, such as HCTR2, have birthday-bound security and provide only 64-bit security with AES. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound (BBB) security and to use Rijndael-256-256 with HCTR2. This paper pursues the first direction while maintaining compatibility with HCTR2. In particular, we provide two solutions to achieve BBB security for two different approaches: (i) general cases without any conditions on the tweak and (ii) under the condition that the same tweak is not repeated too often as adopted in bbb-ddd-AES recently presented at Eurocrypt 2025. For the first approach, we propose a new mode, CHCTR, that iterates HCTR2 with two independent keys, which achieves $2n/3$-bit security in the multi-user (mu) setting and satisfies NIST's requirements. For the second approach, we prove mu security of HCTR2, which allows us to apply the tweak-based key derivation (TwKD) to HCTR2 in a provable manner. When the number of BC calls processed by a single tweak is upper-bounded by $2^{n/3}$, HCTR2-TwKD achieves $2n/3$-bit mu security. By benchmarking optimized software implementations, we show that CHCTR with AES-256 outperforms HCTR2 with Rijndael-256-256, in all the twelve processor models examined. Similarly, HCTR2-TwKD outperforms bbb-ddd-AES in general cases, and it is even comparable to bbb-ddd-AES rigorously optimized for tweak-repeating use cases using precomputation.

Note: Corrected a typo in the evaluation of Pr[collX] in Section 11.5.