for any adversary $A$ constrained to run in time $t$ and permitted $q$
oracle queries,
\[ \Pr[K \getsr \{0, 1\}^k;
- (x, y) \gets A^{F_K(\cdot)}] \le \epsilon :
- x \ne y \land F_K(x) = F_K(y) \]%
+ (x, y) \gets A^{F_K(\cdot)} :
+ x \ne y \land F_K(x) = F_K(y)] \le \epsilon \]%
If $H_K$ is a $(t, q_T, q_V, \epsilon)$-secure MAC on $k$-bit messages, and
moreover $(t, q_T + q_V, \epsilon')$-weakly collision resistant, then
Let $A$ be an adversary which forges a $\Xid{T}{NMAC}^H$ tag in time $t$,
using $q_T$ tagging queries and $q_V$ verification queries with probability
- $\epsilon$. We construct an adversary $A'$ which forces a $H$ tag for a
- $k$-bit in essentially the same time.
+ $\epsilon$. We construct an adversary $A'$ which forges an $H$-tag for a
+ $k$-bit message in essentially the same time.
\begin{program}
Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$ \+ \\
$K \getsr \{0, 1\}^k$; \\
function $F$. For the sake of simplicity, we allow the adversary $A$
to query on \emph{padded} messages, rather than the raw unpadded
messages. We count the number $q'$ of individual message blocks.
-
- As the game with $A$ progresses, we can construct a directed
- \emph{graph} of the query results so far. We start with a node
- labelled $I$. When processing an $H$-query, each time we compute $t'
- = F(t \cat x_i)$, we add a node $t'$, and an edge $x_i$ from $t$ to
- $t'$. The `bad' event occurs whenever we add an edge to a previously
- existing node. We must show, firstly, that the
- adversary cannot distinguish $H$ from a random function unless the bad
- event occurs; and, secondly, that the bad event doesn't occur very
- often.
+
+ As the game with $A$ progresses, we can construct a directed \emph{graph}
+ of the query results so far. We start with a node labelled $I$. When
+ processing an $H$-query, each time we compute $t' = F(t \cat x_i)$, we add
+ a node $t'$, and an edge $x_i$ from $t$ to $t'$. The `bad' event occurs
+ whenever we add an edge to a previously existing node. We must show,
+ firstly, that the adversary cannot distinguish $H$ from a random function
+ unless the bad event occurs; and, secondly, that the bad event doesn't
+ occur very often.
The latter is easier: our standard collision bound shows that the bad
- event occurs during the game with probability at most $q'(q' - 1)/2$.
-
+ event occurs during the game with probability at most $q'(q' - 1)/2^{t+1}$.
+
The former is trickier. This needs a lot more work to make it really
rigorous, but we show the idea. Assume that the bad event has not
- occurred. Consider a query $x_0, x_1, \ldots, x_{n-1}$. If it's the
- same as an earlier query, then $A$ learns nothing (because it could
- have remembered the answer from last time). If it's \emph{not} a
- prefix of some previous query, then we must add a new edge to our
- graph; then either the bad event occurs or we create a new node for
- the result, and because $F$ is a random function, the answer is
- uniformly random. Finally, we consider the case where the query is a
- prefix of some earlier query, or queries. But these were computed at
- random at the time.
+ occurred. Consider a query $x_0, x_1, \ldots, x_{n-1}$. If it's the same
+ as an earlier query, then $A$ learns nothing (because it could have
+ remembered the answer from last time). If it's a \emph{prefix} of some
+ earlier query, then the answer is the value of some internal node which
+ hasn't been revealed before; however, the value of that internal node was
+ chosen uniformly at random (we claim). Finally, if the query is not a
+ prefix of any previous query, then we add a new edge to our graph. If the
+ bad event doesn't occur, we must add a new node for the result, and the
+ value at that node will be uniformly random, because $F$ is a random
+ function being evaluated at a new point -- this is the only time we add new
+ nodes to the graph, justifying the claim made earlier.
At the end of all of this, we see that
\[ \InSec{prf}(T^0; t, q) \le
- \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2} \]%
+ \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2^{t+1}} \]%
and hence
\[ \InSec{suf-cma}(\mathcal{M}^0; t, q) \le
- \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2} + \frac{1}{2^t}. \]%
+ \InSec{prf}(F; t, q') + \frac{2 q'(q' - 1) + 1}{2^{t+1}}. \]%
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} \Pr[N] + \InSec{xuh}(H) \Pr[\bar{N}]) \\
& \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
- (2^{-L} + \InSec{xuh}(H)).
+ \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