International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Yu Long Chen , KU Leuven and NIST Associate
Yukihito Hiraga , The University of Electro-Communications
Nicky Mouha , FWI and NIST Associate
Yusuke Naito , Mitsubishi Electric Corporation
Yu Sasaki , NTT Social Informatics Laboratories and NIST Associate
Takeshi Sugawara , The University of Electro-Communications
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2025
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 \textsf{AES} as a primitive. Widely used VIL-STPRP modes, such as \textsf{HCTR2}, have birthday-bound security and provide only 64-bit security with \textsf{AES}. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound (BBB) security and to use \textsf{Rijndael-256-256} with \textsf{HCTR2}. This paper pursues the first direction while maintaining compatibility with \textsf{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 \textit{bbb-ddd-AES} recently presented at Eurocrypt 2025. For the first approach, we propose a new mode, \textsf{CHCTR}, that iterates \textsf{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 \textsf{HCTR2}, which allows us to apply the tweak-based key derivation (\textsf{TwKD}) to \textsf{HCTR2} in a provable manner. When the number of BC calls processed by a single tweak is upper-bounded by $2^{n/3}$, \textsf{HCTR2-TwKD} achieves $2n/3$-bit mu security. By benchmarking optimized software implementations, we show that \textsf{CHCTR} with \textsf{AES-256} outperforms \textsf{HCTR2} with \textsf{Rijndael-256-256}, in all the twelve processor models examined. Similarly, \textsf{HCTR2-TwKD} outperforms \textit{bbb-ddd-AES} in general cases, and it is even comparable to \textit{bbb-ddd-AES} rigorously optimized for tweak-repeating use cases using precomputation.
BibTeX
@inproceedings{asiacrypt-2025-36170,
  title={Beyond-Birthday-Bound Security with HCTR2: Cascaded Construction and Tweak-based Key Derivation},
  publisher={Springer-Verlag},
  author={Yu Long Chen and Yukihito Hiraga and Nicky Mouha and Yusuke Naito and Yu Sasaki and Takeshi Sugawara},
  year=2025
}