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.
\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]