Return to Answer

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys. Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]|$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$. Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$. (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$. We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$: \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} where $A$ is a PRF-distinguisher for $F$. As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

1. Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$. Then \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_F(A) &= |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]| \\ &= |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]|. \end{align*} If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.

2. Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

   From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^{|m| - i + 1}$ the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

   But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either. The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted. Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

   Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$. Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] = \Pr[A'(U) = 1]$, so that \begin{align*} \Pr[A'(f \circ H_{k_1}) = 1] &= \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| C]\,\Pr[C] \\ &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C]\,\Pr[\lnot C] \\ &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] \\ &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1], \end{align*} and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.

3. Summing up, \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]| \\ &\quad + |\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} QED.

_{This follows the structure of the proof of Lemma 3.3 in:}

_{Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119}

_{Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.}

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys. Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = \lvert\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]\rvert$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$. Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$. (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$. We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$: \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= \lvert\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]\rvert \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} where $A$ is a PRF-distinguisher for $F$. As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

1. Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$. Then \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_F(A) &= \lvert\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]\rvert \\ &= \lvert\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]\rvert. \end{align*} If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.

2. Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

   From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^{|m| - i + 1}$ the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

   But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either. The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted. Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

   Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$. Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C] = \Pr[A'(U) = 1]$, so that \begin{align*} \Pr[A'(f \circ H_{k_1}) = 1] &= \Pr[A'(f \circ H_{k_1}) = 1 \mid C]\,\Pr[C] \\ &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C]\,\Pr[\lnot C] \\ &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C] \\ &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1], \end{align*} and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.

3. Summing up, \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= \lvert\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]\rvert \\ &\leq \lvert\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]\rvert \\ &\quad + \lvert\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]\rvert \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} QED.

_{This follows the structure of the proof of Lemma 3.3 in:}

_{Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119}

_{Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.}

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys. Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]|$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$. Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$. (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$. We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$: \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} where $A$ is a PRF-distinguisher for $F$. As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

1. Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$. Then \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_F(A) &= |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]| \\ &= |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]|. \end{align*} If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.

2. Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

   From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^i$, the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

   But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either. The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted. Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

   Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$. Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] = \Pr[A'(U) = 1]$, so that \begin{align*} \Pr[A'(f \circ H_{k_1}) = 1] &= \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| C]\,\Pr[C] \\ &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C]\,\Pr[\lnot C] \\ &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] \\ &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1], \end{align*} and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.

3. Summing up, \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]| \\ &\quad + |\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} QED.

_{This follows the structure of the proof of Lemma 3.3 in:}

_{Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119}

_{Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.}

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys. Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]|$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$. Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$. (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$. We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$: \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} where $A$ is a PRF-distinguisher for $F$. As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

1. Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$. Then \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_F(A) &= |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]| \\ &= |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]|. \end{align*} If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.

2. Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

   From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^{|m| - i + 1}$ the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

   But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either. The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted. Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

   Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$. Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] = \Pr[A'(U) = 1]$, so that \begin{align*} \Pr[A'(f \circ H_{k_1}) = 1] &= \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| C]\,\Pr[C] \\ &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C]\,\Pr[\lnot C] \\ &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] \\ &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1], \end{align*} and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.

3. Summing up, \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]| \\ &\quad + |\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} QED.

_{This follows the structure of the proof of Lemma 3.3 in:}

_{Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119}

_{Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.}

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys. Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]|$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$. Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$. (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$. We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$: \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} where $A$ is a PRF-distinguisher for $F$. As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

1. Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$. Then \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_F(A) &= |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]| \\ &= |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]|. \end{align*} If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.

2. Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$. Among them, the event $C$ of a collision in $H_{k_1}$ has probability \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} In the event $\lnot C$ that the queries do not collide, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$. Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] = \Pr[A'(U) = 1]$, so that \begin{align*} \Pr[A'(f \circ H_{k_1}) = 1] &= \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| C]\,\Pr[C] \\ &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C]\,\Pr[\lnot C] \\ &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] \\ &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1], \end{align*} and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.

3. Summing up, \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]| \\ &\quad + |\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} QED.

_{This follows the structure of the proof of Lemma 3.3 in:}

_{Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119}

_{Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.}

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys. Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]|$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$. Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$. (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$. We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$: \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} where $A$ is a PRF-distinguisher for $F$. As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

1. Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$. Then \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_F(A) &= |\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]| \\ &= |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]|. \end{align*} If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.

2. Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

   From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^i$, the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

   But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either. The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted. Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

   Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability \begin{multline*} \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\ \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)] \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon, \end{multline*} In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$. Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] = \Pr[A'(U) = 1]$, so that \begin{align*} \Pr[A'(f \circ H_{k_1}) = 1] &= \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| C]\,\Pr[C] \\ &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C]\,\Pr[\lnot C] \\ &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mathrel| \lnot C] \\ &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1], \end{align*} and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.

3. Summing up, \begin{align*} \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A') &= |\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]| \\ &\leq |\Pr[A'(F_{k_2} \circ H_{k_1}) = 1] - \Pr[A'(f \circ H_{k_1}) = 1]| \\ &\quad + |\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]| \\ &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon, \end{align*} QED.

_{This follows the structure of the proof of Lemma 3.3 in:}

_{Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119}

_{Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.}