International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Forgery Attacks on Several Beyond-Birthday-Bound Secure MACs

Authors:
Yaobin Shen , UCLouvain, Belgium
Fran├žois-Xavier Standaert , UCLouvain, Belgium
Lei Wang , Shanghai Jiao Tong University, China
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: At CRYPTO'18, Datta et al. proposed nPolyMAC and proved the security up to 2^{2n/3} authentication queries and 2^{n} verification queries. At EUROCRYPT'19, Dutta et al. proposed CWC+ and showed the security up to 2^{2n/3} queries. At FSE'19, Datta et al. proposed PolyMAC and its key-reduced variant 2k-PolyMAC, and showed the security up to 2^{2n/3} queries. This security bound was then improved by Kim et al. (EUROCRYPT'20) and Datta et al (FSE'23) respectively to 2^{3n/4} and in the multi-user setting. At FSE'20, Chakraborti et al. proposed PDM*MAC and 1k-PDM*MAC and showed the security up to 2^{2n/3} queries. Recently, Chen et al. proposed nEHtM_p^+ and showed the security up to 2^{2n/3} queries. In this paper, we show forgery attacks on nPolyMAC, CWC+, PolyMAC, 2k-PolyMAC, PDM*MAC, 1k-PDM*MAC and nEHtM_p^+. Our attacks exploit some vulnerability in the underlying polynomial hash function, and (i) require only one authentication query and one verification query; (ii) are nonce-respecting; (iii) succeed with probability 1. Thus, our attacks disprove the provable high security claims of these schemes. We then revisit their security analyses and identify what went wrong. Finally, we propose two solutions that can restore the beyond-birthday-bound security.
BibTeX
@inproceedings{asiacrypt-2023-33544,
  title={Forgery Attacks on Several Beyond-Birthday-Bound Secure MACs},
  publisher={Springer-Verlag},
  author={Yaobin Shen and Fran├žois-Xavier Standaert and Lei Wang},
  year=2023
}