Paper 2025/2260
Tight Generic PRF Security of HMAC and NMAC
Abstract
HMAC and its variant NMAC are among the most widely used methods for keying a cryptographic hash function to obtain a PRF or a MAC. Yet, even after nearly three decades of research, their generic PRF security still remains poorly understood, where the compression function of the underlying hash function is treated as a black box and accessible to the adversary. Although a series of works have exploited compression function queries to mount generic attacks, proving tight bounds on the generic PRF security of HMAC and NMAC remains a challenging open question until now. In this paper, we establish tight bounds on the generic PRF security of HMAC and NMAC. Our bounds capture the influence of the number of construction queries, the number of compression function queries, and the maximal block length of a message on their security. The proofs are carried out in the multi-user setting and the bounds hold regardless of the number of users. In addition, we present matching attacks to demonstrate that our bounds are essentially tight. Taken together, our results close a longstanding gap in the generic PRF security analysis of HMAC and NMAC.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- HMACNMACGeneric securityProvable security
- Contact author(s)
-
yaobin shen @ xmu edu cn
xiangyang zhang @ xmu edu cn
wanglei_hb @ sjtu edu cn
dwgu @ sjtu edu cn - History
- 2025-12-18: approved
- 2025-12-16: received
- See all versions
- Short URL
- https://ia.cr/2025/2260
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2260,
author = {Yaobin Shen and Xiangyang Zhang and Lei Wang and Dawu Gu},
title = {Tight Generic {PRF} Security of {HMAC} and {NMAC}},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2260},
year = {2025},
url = {https://eprint.iacr.org/2025/2260}
}
