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, 2021 at 8:30
  • $\begingroup$ That depends on the instantiation, there is a distinguisher for some $\endgroup$
    – kelalaka
    Feb 11, 2021 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, 2021 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, 2021 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, 2021 at 21:10

1 Answer 1


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 and acknowledge you have read our privacy policy.

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