Paper 2024/1980

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

Abstract

Message authentication codes (MACs) are fundamental symmetric key cryptographic functions used to generate a short, secret-key-dependent tag for a given message. This tag ensures both message authenticity and integrity, as computing a valid tag without the secret key is computationally infeasible, thereby revealing any unauthorized modification. Existing MACs often rely on block ciphers (BCs) and tweakable block ciphers (TBCs). The design of these MACs involves various trade-offs regarding properties such as data processing rate, the number of secret keys, achievable security definitions and concrete margins, the necessity for pre- or post-processing, parallelization capabilities, internal state size, and performance optimization for diverse message lengths. This work introduces $\mathsf{Sonikku}$, a new family of MACs based on expanding primitives, comprising three distinct instances: $\mathsf{BabySonic}$, $\mathsf{DarkSonic}$, and $\mathsf{SuperSonic}$. The $\mathsf{Sonikku}$ MACs offer a compelling combination of advantages: 1) superior speed compared to state-of-the-art TBC-based MACs; 2) security beyond the birthday bound related to the input block size; 3) a smaller internal state than comparable contemporary MACs; and 4) design flexibility considering diverse trade-offs, including pre/post-processing-free operation, parallel processing, a small resource footprint, and suitability for both short and long messages. These characteristics make them highly attractive for widespread applications, including resource-constrained environments like IoT and embedded devices. Performance evaluations on a Cortex-M4 32-bit microcontroller demonstrate that $\mathsf{BabySonic}$ instantiated with $\mathsf{ForkSkinny}$ achieves a significant speed-up of at least 2.11x (and up to 4.36x) compared to the state-of-the-art ZMAC instantiated with $\mathsf{SKINNY}$ for 128-bit block sizes and messages up to 95 bytes. Similarly, $\mathsf{DarkSonic}$ and $\mathsf{SuperSonic}$ instantiated with $\mathsf{ForkSkinny}$ exhibit speed improvements of at least 1.93x for short messages (up to 95 bytes) and 1.48x for larger messages (up to 64KB), respectively, when benchmarked against ZMAC instantiated with $\mathsf{SKINNY}$ for both 64- and 128-bit block sizes. Building upon the approach of ZMAC and PMAC2x, we further illustrate the potential of the $\mathsf{Sonikku}$ family by employing $\mathsf{SuperSonic}$ to construct SonicAE, a highly efficient, beyond-birthday secure, stateless, and deterministic authenticated encryption scheme.