International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Revisiting the Security of DbHtS MACs: Beyond-Birthday-Bound in the Multi-User Setting

Authors:
Yaobin Shen , Shanghai Jiao Tong Univeristy
Lei Wang , Shanghai Jiao Tong University
Dawu Gu , Shanghai Jiao Tong University
Jian Weng , Jinan University
Download:
DOI: 10.1007/978-3-030-84252-9_11 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2021
Abstract: Double-block Hash-then-Sum (\textsf{DbHtS}) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including \textsf{SUM-ECBC}, \textsf{PMAC\_Plus}, \textsf{3kf9} and \textsf{LightMAC\_Plus}. Recently Datta et al. (FSE'19), and then Kim et al. (Eurocrypt'20) prove that \textsf{DbHtS} constructions are secure beyond the birthday bound in the single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in the multi-user setting. In this work, we revisit the security of \textsf{DbHtS} MACs in the multi-user setting. We propose a generic framework to prove beyond-birthday-bound security for \textsf{DbHtS} constructions. We demonstrate the usability of this framework with applications to key-reduced variants of \textsf{DbHtS} MACs, including \textsf{2k-SUM-ECBC}, \textsf{2k-PMAC\_Plus} and \textsf{2k-LightMAC\_Plus}. Our results show that the security of these constructions will not degrade as the number of users grows. On the other hand, our results also indicate that these constructions are secure beyond the birthday bound in both single-user and multi-user setting without additional domain separation, which is used in the prior work to simplify the analysis. Moreover, we find a critical flaw in \textsf{2kf9}, which is proved to be secure beyond the birthday bound by Datta et al. (FSE'19). We can successfully forge a tag with probability 1 without making any queries. We go further to show attacks with birthday-bound complexity on several variants of \textsf{2kf9}.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31103,
  title={Revisiting the Security of DbHtS MACs: Beyond-Birthday-Bound in the Multi-User Setting},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-84252-9_11},
  author={Yaobin Shen and Lei Wang and Dawu Gu and Jian Weng},
  year=2021
}