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 $\mathsf{Sonikku}$ family of expanding primitive based MACs, consisting of three instances: $\mathsf{BabySonic}$, $\mathsf{DarkSonic}$, and $\mathsf{SuperSonic}$. The $\mathsf{Sonikku}$ 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, $\mathsf{BabySonic}$ with $\mathsf{ForkSkinny}$ achieves a speed-up of at least 2.11x (up to 4.36x) compared to state-of-the-art ZMAC with $\mathsf{SKINNY}$ for 128-bit block sizes and queries of 95B or smaller. $\mathsf{DarkSonic}$ and $\mathsf{SuperSonic}$ with $\mathsf{ForkSkinny}$ 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 $\mathsf{SKINNY}$ for both 64- and 128-bit block sizes. Similar to ZMAC and PMAC2x, we then demonstrate the potential of our MAC family by using $\mathsf{SuperSonic}$ to construct a highly efficient, beyond-birthday secure, stateless, and deterministic authenticated encryption scheme, which we call SonicAE.