International Association
for Cryptologic Research

HMAC and its variant NMAC are the most popular approaches to

deriving a MAC (and more generally, a PRF) from a cryptographic hash

function. Despite nearly two decades of research, their exact

security still remains far from understood in many different

contexts. Indeed, recent works have re-surfaced interest for {\\em

generic} attacks, i.e., attacks that treat the compression

function of the underlying hash function as a black box.

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.