In the abstract of The Exact PRF-Security of NMAC and HMAC, Gazi, Pietrzak, and Rybar state:

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.

This implies that HMAC-SHA1 and HMAC-MD5 are not PRFs. However, I'm not sure whether SHA-2 (particularly, SHA-256) is considered to satisfy (2) from their abstract, and thus whether HMAC-SHA2 (particularly, HMAC-SHA256) is a PRF. I'm further confused by result from Bellare, 2006 which seems to contract the more recent paper by proving that collision resistance of the underlying function is not necessary in order for an HMAC to be a PRF.

  • 1
    $\begingroup$ Note that the quoted text only states that the original authors (back in 1996) required collision resistance to prove PRF security. $\endgroup$ – SEJPM Feb 11 at 8:30
  • $\begingroup$ That depends on the instantiation, there is a distinguisher for some $\endgroup$ – kelalaka Feb 11 at 8:51
  • $\begingroup$ By "instantiation", I assume you are referring to the underlying CRHF? Is there a distinguisher for SHA-2/SHA-256? $\endgroup$ – joshlf Feb 11 at 16:28
  • $\begingroup$ To prove a PRF is not an easy task, disproving is the easier way. As long as one is not showing, assume that it is. $\endgroup$ – kelalaka Feb 11 at 20:56
  • $\begingroup$ Understood; do you know if it is currently assumed by most cryptographers that SHA-256 is a PRF? $\endgroup$ – joshlf Feb 12 at 21:10

TLDR: (2) is a sufficient condition, but probably not a necessary condition. Most people would probably believe that HMAC-SHA-1 is indeed a PRF, although SHA-1 is not WCR.

The 2006 paper by Bellare claims to prove that e.g. HMAC-SHA-1 is a PRF, if the inner compression function of SHA-1 is a PRF. No known attacks break the pseudorandomness of the inner function, so taken at face value, we would conclude that HMAC-SHA-1 is a PRF. However, reading that paper closely, this is proven for NMAC, and other two-keyed constructions. The proof for standard HMAC requires a related-key assumption (see Setion 5). This assumption is also pretty mild, and not even close to be broken by any known attack.

So to conclude: In practice, HMAC-SHA-1 is probably a PRF. The 2006 Bellare paper identifies relatively mild assumptions under which this holds, but if you want to precisely identify these assumptions, read Section 5 of that paper carefully.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.