X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/53aa10b5d9431ced4e98673cc872c6627cac1d5f..6278c386d4ce1feeab4adba11c161602ade00414:/auth-mac.tex?ds=sidebyside

diff --git a/auth-mac.tex b/auth-mac.tex
index 8b4eb8a..67489f0 100644
--- a/auth-mac.tex
+++ b/auth-mac.tex
@@ -107,7 +107,7 @@
   
   If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a $(t, q, \epsilon)$-secure
   PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T
-  + q_V + 1$, $t = t' + O(q)$, and $\epsilon \le \epsilon' + (q_V + 1)
+  + q_V + 1$, $t = t' + O(q)$, and $\epsilon' \le \epsilon + (q_V + 1)
   2^{-L}$.  The constant hidden by the $O(\cdot)$ is small and depends on the
   model of computation.
   
@@ -152,7 +152,7 @@
   $A$ does when it's given a random function.  But we know that the
   probability of it successfully guessing the MAC for a message for which it
   didn't query $T$ can be at most $(q_V + 1) 2^{-L}$.  So
-  \[ \Adv{prf}{F}(D) \le \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}. \]
+  \[ \Adv{prf}{F}(D) \ge \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}. \]
   Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields
   \[ \InSec{suf-cma}(F; t, q_T, q_V) \le
      \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}. \]%
@@ -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]
