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?
$\begingroup$ $\endgroup$
3 
- $\begingroup$ Collision resistance $\implies$ 2nd-preimage resistance of hash functions. That is $p \implies q$. See the law of contraposition $\neg q \implies \neg p$ $\endgroup$kelalaka– kelalaka2020-10-12 20:05:54 +00:00Commented Oct 12, 2020 at 20:05
- 1$\begingroup$ @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? $\endgroup$Keshav Srinivasan– Keshav Srinivasan2020-10-12 20:18:59 +00:00Commented Oct 12, 2020 at 20:18
- 1$\begingroup$ 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). $\endgroup$Ilmari Karonen– Ilmari Karonen2020-10-13 11:54:50 +00:00Commented Oct 13, 2020 at 11:54
Add a comment |
1 Answer
$\begingroup$ $\endgroup$
Even collision resistance is not sufficient to make HMAC unforgeable, so neither is second-preimage resistance.
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$.
