Paper 2024/1980

Sonikku: Gotta Speed, Keed! A Family of Fast and Secure MACs

Abstract

A message authentication code (MAC) is a symmetric-key cryptographic function used to authenticate a message by assigning it a tag. This tag is a short string that is difficult to reproduce without knowing the key. The tag ensures both the authenticity and integrity of the message, enabling the detection of any modifications. A significant number of existing message authentication codes (MACs) are based on block ciphers (BCs) and tweakable block ciphers (TBCs). These MACs offer various trade-offs in properties, such as data processing rate per primitive call, use of single or multiple keys, security levels, pre- or post-processing, parallelizability, state size, and optimization for short/long queries. In this work, we propose the $$ family of expanding primitive based MACs, consisting of three instances: $$, $$, and $$. The $$ MACs are -- 1) faster than the state-of-the-art TBC-based MACs; 2) secure beyond the birthday bound in the input block size; 3) smaller in state size compared to state-of-the-art MACs; and 4) optimized with diverse trade-offs such as pre/post-processing-free execution, parallelization, small footprint, and suitability for both short and long queries. These attributes make them favorable for common applications as well as ``IoT'' and embedded devices where processing power is limited. On a Cortex-M4 32-bit microcontroller, $$ with $$ achieves a speed-up of at least 2.11x (up to 4.36x) compared to state-of-the-art ZMAC with $$ for 128-bit block sizes and queries of 95B or smaller. $$ and $$ with $$ achieve a speed-up of at least 1.93x for small queries of 95B or smaller and 1.48x for large queries up to 64KB, respectively, against ZMAC with $$ for both 64- and 128-bit block sizes. Similar to ZMAC and PMAC2x, we then demonstrate the potential of our MAC family by using $$ to construct a highly efficient, beyond-birthday secure, stateless, and deterministic authenticated encryption scheme, which we call SonicAE.