You are looking at a specific version 20201211:083414 of this paper. See the latest version.

Paper 2020/1523

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

Yaobin Shen; Lei Wang; Jian Weng

Abstract

Double-block Hash-then-Sum (DbHtS) MACs are a class of MACs that aim for achieving beyond-birthday-bound security, including SUM-ECBC, PMAC_Plus, 3kf9 and LightMAC_Plus. Recently Datta et al. (FSE’19), and then Kim et al. (Eurocrypt’20) proved that DbHtS constructions are secure beyond birthday bound in single-user setting. However, by a generic reduction, their results degrade to (or even worse than) the birthday bound in multi-user setting. In this work, we revisit the security of DbHtS MACs in multi-user setting. We propose a generic framework to prove beyond-birthday-bound security for DbHtS constructions. We demonstrate the usability of this framework with applications to key-reduced variants of DbHtS MACs, including 2k-SUM-ECBC, 2k-PMAC_Plus and 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 beyond-birthday-bound secure in both single-user and multi-user setting without additional domain separation, which are used in prior works to simplify the analysis. Moreover, we find a severe flaw in 2kf9, which is proved to be secure beyond 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 2kf9.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
beyond-birthday-bound securitymulti-user securityDbHtS MACs
Contact author(s)
yb_shen @ sjtu edu cn
History
2022-04-02: last of 4 revisions
2020-12-08: received
See all versions
Short URL
https://ia.cr/2020/1523
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.