Paper 2024/731

Toward Full $n$-bit Security and Nonce Misuse Resistance of Block Cipher-based MACs

Abstract

In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F_{B_2}^{\text{EDM}}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F_{B_3}^{\text{EDM}}$, $F_{B_2}^{\text{SoP}}$, $F_{B_3}^{\text{SoP}}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $$-bit security. In particular, $$ and $$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called multi-xor-collision resistance). To do this, we develop a new tool, namely extended Mirror theory based on two independent permutations to a wide range of $$ including inequalities. We also present matching attacks on $$ and $$ using $$ MAC queries and $$ verification query without using repeated nonces.