X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/e09a183984ad92729c40b1ed51d2e9f6388ca9ba..6278c386d4ce1feeab4adba11c161602ade00414:/auth-mac.tex diff --git a/auth-mac.tex b/auth-mac.tex index cd3defa..67489f0 100644 --- a/auth-mac.tex +++ b/auth-mac.tex @@ -384,8 +384,8 @@ 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 @@ -397,8 +397,8 @@ 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$; \\ @@ -485,47 +485,47 @@ 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: @@ -852,7 +852,7 @@ \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. @@ -882,7 +882,7 @@ \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]