Generic security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question.
In this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing.
While our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions.
Category / Keywords: secret-key cryptography / message authentication codes, HMAC, generic attacks, provable security Original Publication (with major differences): IACR-ASIACRYPT-2015 Date: received 11 Sep 2015, last revised 11 Sep 2015 Contact author: peter gazi at ist ac at Available format(s): PDF | BibTeX Citation Version: 20150913:192230 (All versions of this report) Short URL: ia.cr/2015/881 Discussion forum: Show discussion | Start new discussion