International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Wonseok Choi , Purdue University, West Lafayette, IN, USA
Jooyoung Lee , KAIST, Daejeon, Korea
Yeongmin Lee , DESILO Inc., Seoul, Korea
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2024
Abstract: In this paper, we study the security of MAC constructions among those classified by Chen {\it et al.} in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$~(or $\ewcdm$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen {\it et al.}) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular, $F^{\text{SoP}}_{B_2}$ and $F^{\text{SoP}}_{B_3}$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called \emph{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 $\xi_{\max}$ including inequalities. We also present matching attacks on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and $O(1)$ verification query without using repeated nonces.
BibTeX
@inproceedings{asiacrypt-2024-34530,
  title={Toward Full n-bit Security and Nonce Misuse Resistance of Block Cipher-based MACs},
  publisher={Springer-Verlag},
  author={Wonseok Choi and Jooyoung Lee and Yeongmin Lee},
  year=2024
}