**The Exact PRF-Security of NMAC and HMAC**

*Peter Gaži and Krzysztof Pietrzak and Michal Rybár*

**Abstract: **NMAC is a mode of operation which turns a fixed input-length
keyed hash function f into a variable input-length function.
A~practical single-key variant of NMAC called HMAC is a very
popular and widely deployed message authentication code
(MAC). Security proofs and attacks for NMAC can typically
be lifted to HMAC.

NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto'96], who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable guarantees for NMAC, Bellare [Crypto'06] showed its security based solely on the assumption that f is a PRF, albeit via a non-uniform reduction.

Our first contribution is a simpler and uniform proof: If f is an \eps-secure PRF (against q queries) and a \delta-non-adaptively secure PRF (against q queries), then NMAC^f is an (\eps+lq\delta)-secure PRF against q queries of length at most l blocks each.

We then show that this \eps+lq\delta bound is basically tight. For the most interesting case where lq\delta>=\eps we prove this by constructing an f for which an attack with advantage lq\delta exists. This also violates the bound O(l\eps) on the PRF-security of NMAC recently claimed by Koblitz and Menezes.

Finally, we analyze the PRF-security of a modification of NMAC called NI [An and Bellare, Crypto'99] that differs mainly by using a compression function with an additional keying input. This avoids the constant rekeying on multi-block messages in NMAC and allows for a security proof starting by the standard switch from a PRF to a random function, followed by an information-theoretic analysis. We carry out such an analysis, obtaining a tight lq^2/2^c bound for this step, improving over the trivial bound of l^2q^2/2^c. The proof borrows combinatorial techniques originally developed for proving the security of CBC-MAC [Bellare et al., Crypto'05]. We also analyze a variant of NI that does not include the message length in the last call to the compression function, proving a l^{1+o(1)}q^2/2^c bound in this case.

**Category / Keywords: **secret-key cryptography / Message authentication codes, pseudorandom functions, NMAC, HMAC, NI.

**Original Publication**** (with major differences): **IACR-CRYPTO-2014

**Date: **received 24 Jul 2014, last revised 13 Aug 2014

**Contact author: **peter gazi at ist ac at

**Available format(s): **PDF | BibTeX Citation

**Note: **A preliminary version of this paper appears in the proceedings of CRYPTO 2014, this is the full version.

**Version: **20140813:065637 (All versions of this report)

**Short URL: **ia.cr/2014/578

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]