Now we turn our attention to $T^1$. It's clear that we can't simulate
$T^1$ very easily using an oracle for $F$, since we don't know $K$
(and indeed there might not be a key $K$). The intuitive reason why
- $T^1$ is insecure is that $F$ might have leak useful information if
- its input matches its key. This doesn't affect the strength of $F$ as
- a PRF because you have to know the key before you can exploit this
- leakage; but $T^1$ already knows the key, and this can be exploited to
- break the MAC.
+ $T^1$ is insecure is that $F$ might leak useful information if its input
+ matches its key. This doesn't affect the strength of $F$ as a PRF
+ because you have to know the key before you can exploit this leakage; but
+ $T^1$ already knows the key, and this can be exploited to break the MAC.
To show that this is insecure formally, let $F'$ be defined as
follows:
\next
Algorithm $\Xid{V}{XUH}^{H, F}_{K, K'}(m, \tau)$: \+ \\
$(s, \sigma) \gets \tau$; \\
- \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\
+ \IF $\sigma = H_K(m) \xor F_{K'}(s)$ \THEN \RETURN $1$; \\
\ELSE \RETURN $0$;
\end{program}
Note that verification is stateless.
For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
\begin{eqnarray*}[Ll]
\InSec{suf-cma}(\Xid{\mathcal{M}}{XUH}^{H, F}; t, q_T, q_V) \\
- & \le (q_V + 1)(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L}).
+ & \le (q_V + 1)(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H)).
\end{eqnarray*}
\end{slide}
\next
Algorithm $\Xid{V}{XUH$\$$}^{H, F}_{K, K'}(m, \tau)$: \+ \\
$(s, \sigma) \gets \tau$; \\
- \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\
+ \IF $\sigma = H_K(m) \xor F_{K'}(s)$ \THEN \RETURN $1$; \\
\ELSE \RETURN $0$;
\end{program}
\begin{eqnarray*}[Ll]
\InSec{suf-cma}(\Xid{\mathcal{M}}{XUH$\$$}^{H, F}; t, q_T, q_V) \\
& \le (q_V + 1)
- \Bigl(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L} +
+ \Bigl(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) +
\frac{q_T(q_T - 1)}{2^{l+1}}\Bigr).
\end{eqnarray*}
\end{slide}
$F$ is random, and let $N$ be the event that the nonce $s$ returned by $A$
is not equal to any nonce $s_i$ returned by the tagging oracle. Suppose
$N$ occurs: then the random function $F$ has never been queried before at
- $F$, and $\Pr[F(s) = \sigma \xor H_K(m)]$ is precisely $2^{-L}$.
+ $F$, and $\Pr[S \mid N] = \Pr[F(s) = \sigma \xor H_K(m)]$ is precisely
+ $2^{-L}$.
So suppose instead that $N$ doesn't occur. Then, since the $s_i$ are
distinct, there is a unique $i$ such that $s = s_i$. For $A$ to win, we
\[ H_K(m_i) \xor H_K(m) = \sigma \xor \sigma_i. \]
Since the $s_i$ are distinct and $F$ is a random function, the $\sigma_i$
are independent uniformly-distributed random strings from $\{0, 1\}^L$.
- Hence the collision-finder $C$ succeeds with probability $\Pr[S \land
- \lnot N] \le \InSec{xuh}(H)$.
+ Hence the collision-finder $C$ succeeds with probability $\Pr[S \mid
+ \bar{N}] \le \InSec{xuh}(H)$.
Wrapping up, we have
\begin{eqnarray*}[rl]
\Adv{prf}{F}(D)
& \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
- (\Pr[S \mid N] \Pr[N] + \Pr[S \mid \lnot N] \Pr[\lnot N]) \\
+ (\Pr[S \mid N] \Pr[N] + \Pr[S \mid \bar{N}] \Pr[\bar{N}]) \\
& \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
- (2^{-L} + \InSec{xuh}(H)).
+ (2^{-L} \Pr[N] + \InSec{xuh}(H) \Pr[\bar{N}]) \\
+ & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
+ \InSec{xuh}(H).
\end{eqnarray*}
Maximizing and rearranging yields the required result.
\end{proof}
-\begin{remark*}
- Note that our bound has a $2^{-L}$ term in it that's missing from
- \cite{Goldwasser:1999:LNC}. We believe that their proof is wrong in its
- handling of the XOR-collision probability.
-\end{remark*}
-
\endinput
%%% Local Variables:
~mdw / doc / ips / blobdiff