Is HMAC-SHA256 a PRF?

Question

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.

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.