Skip to main content
typo
Source Link
Maeher
  • 7.2k
  • 1
  • 37
  • 46

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}$$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$.

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$.

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$.

Source Link
Maeher
  • 7.2k
  • 1
  • 37
  • 46

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$.