Paper 2024/2053

Optimally Secure TBC Based Accordion Mode

Abstract

The design of tweakable wide block ciphers has advanced significantly over the past two decades. This evolution began with the approach of designing a wide block cipher by Naor and Reingold. Since then, numerous tweakable wide block ciphers have been proposed, many of which build on existing block ciphers and are secure up to the birthday bound for the total number of blocks queried. Although there has been a slowdown in the development of tweakable wide block cipher modes in last couple of years, the latest NIST proposal for accordion modes has reignited interest and momentum in the design and analysis of these ciphers. Although new designs have emerged, their security often falls short of optimal (i.e., $n$-bit) security, where $n$ is the output size of the primitive. In this direction, designing an efficient tweakable wide block cipher with $n$-bit security seems to be an interesting research problem. An optimally secure tweakable wide block cipher mode can easily be turned into a misuse-resistant RUP secure authenticated encryption scheme with optimal security. This paper proposes $\textsf{HCTR+}$, which turns an $n$-bit tweakable block cipher (TBC) with $n$-bit tweak into a variable input length tweakable block cipher. Unlike tweakable $\textsf{HCTR}$, $\textsf{HCTR+}$ ensures $n$-bit security regardless of tweak repetitions. We also propose two TBC-based almost-xor-universal hash functions, named $\textsf{PHASH+}$ and $\textsf{ZHASH+}$, and use them as the underlying hash functions in the $\textsf{HCTR+}$ construction to create two TBC-based $n$-bit secure tweakable wide block cipher modes, $\textsf{PHCTR+}$ and $\textsf{ZHCTR+}$. Experimental results show that both $\textsf{PHCTR+}$ and $\textsf{ZHCTR+}$ exhibit excellent software performance when their underlying TBC is instantiated with $\textsf{Deoxys-BC-128-128}$.