# Is an HMAC based on a second-preimage resistant hash function always unforgeable?

If hash function is collision-resistant, then its associated HMAC is always unforgeable. But suppose that a hash function is only second-preimage resistant, not necessarily collision-resistant. Then my question is, its associated HMAC always unforgeable?

• Collision resistance $\implies$ 2nd-preimage resistance of hash functions. That is $p \implies q$. See the law of contraposition $\neg q \implies \neg p$ – kelalaka Oct 12 '20 at 20:05
• @kelalaka Yes, collision resistance implies second preimage resistance. But second preimage resistance does not imply collision resistance. So I'm asking. If a hash function is second preimage resistant, is its associated HMAC unforgeable? – Keshav Srinivasan Oct 12 '20 at 20:18
• AFAIK, collision resistance alone is not sufficient to prove the security of HMAC. The original Bellare et al. 1996 paper proves the unforgeability of HMAC assuming both collision resistance and the unforgeability of the compression function of the hash when viewed as a MAC acting on fixed-length messages (and the later 2006 paper removes the collision resistance assumption, under slightly stronger assumptions about the compression function). – Ilmari Karonen Oct 13 '20 at 11:54

Let $$H : \{0,1\}^* \to \{0,1\}^n$$ be a collision resistant hash function. We define the hash function $$H' : \{0,1\}^* \to \{0,1\}^{n+1}$$ as $$H'(m\Vert b) = H(m)\Vert b,$$ where $$|b|=1$$.
Since for any $$m_0\Vert b_0$$ and $$m_1\Vert b_1$$, it holds that $$H'(m_0\Vert b_0) = H'(m_1\Vert b_1)$$ if and only if $$b_0=b_1$$ and $$H(m_0)=H(m_1)$$, it is easy to see that any collision in $$H'$$ implies a collision in $$H$$. Thus $$H'$$ must remain collision resistant.
However, HMAC instantiated with $$H'$$ is easily forgeable.
\begin{align} \mathsf{HMAC}(K,m\Vert b) =& H'\Bigl((K\oplus \mathsf{opad})\Vert H'\bigl((K\oplus \mathsf{ipad})\Vert m\Vert b\bigr)\Bigr)\\ =&H'\Bigl((K\oplus \mathsf{opad})\Vert H\bigl((K\oplus \mathsf{ipad})\Vert m\bigr)\Vert b\Bigr)\\ =&H\Bigl((K\oplus \mathsf{opad})\Vert H\bigl((K\oplus \mathsf{ipad})\Vert m\bigr)\Bigr)\Vert b\\ \end{align}
I.e., an adversary can take the tag $$t$$ for some arbitrary message $$m$$, and present $$(m\oplus 0\dots01,t\oplus 0\dots01)$$ as a valid forgery with probability $$1$$.