X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/41761fdc7bb8f1ed87f5e1116d389158513ee280..2e24ecf52da0f6bd5d5873037c1b535edf32045f:/auth-mac.tex?ds=sidebyside

diff --git a/auth-mac.tex b/auth-mac.tex
index 40f466d..31f2084 100644
--- a/auth-mac.tex
+++ b/auth-mac.tex
@@ -21,7 +21,8 @@
 
 \begin{slide}
   \topic{informal security notion}
-  \head{Strong MACs, 1: informal security notion}
+  \resetseq
+  \head{Strong MACs, \seq: informal security notion}
   
   Our standard notion of security for MACs is \emph{strong unforgeability
     against chosen message attack}, or SUF-CMA, for short
@@ -41,7 +42,7 @@
 
 \begin{slide}
   \topic{strong MACs}
-  \head{Strong MACs, 2: the experiment}
+  \head{Strong MACs, \seq: the experiment}
 
   We perform the following experiment with the adversary.
   \begin{program}
@@ -60,7 +61,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Strong MACs, 3: wrapping up the notation}
+  \head{Strong MACs, \seq: wrapping up the notation}
 
   The \emph{success probability} of an adversary $A$ against the MAC
   $\mathcal{M}$ in the sense of SUF-CMA is
@@ -97,34 +98,20 @@
   \end{itemize}
 \end{slide}
 
-%% IFF systems
-\begin{exercise}
-  %% A nice open-ended question.  Need to sort out IFF details (e.g.,
-  %% aircraft numbering or whatever.
-  An \emph{identify friend-or-foe} (IFF) system works as follows.  Each
-  `friendly' aircraft knows a common secret key.  When a new aircraft is
-  detected, a \emph{challenge} $x$ is sent.  If a correct \emph{response} is
-  returned, the new aircraft is presumed friendly; otherwise it is attacked.
-  Discuss the security requirements of IFF systems and construct a formal
-  model.  Decide which primitive is best suited to the job and relate the
-  security notions.  What sorts of resource constraints can be imposed on
-  adversaries attacking an IFF system?
-  \answer%
-  No prizes for guessing that a MAC is what's wanted, this being the MAC
-  section.  
-\end{exercise}
-
 \xcalways\subsection{Basic results}\x
 
 \begin{slide}
   \topic{PRFs are MACs}
-  \head{PRFs are MACs, 1}
+  \resetseq
+  \head{PRFs are MACs, \seq}
   
-  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)
-  2^{-L}$.  The constant hidden by the $O(\cdot)$ is small and depends on the
-  model of computation.
+  If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a PRF then it's also a MAC.
+  Quantitatively:
+  \[ \InSec{suf-cma}(F; t, q_T, q_V) \le
+       \InSec{prf}(F; t + O(q), q_T + q_V) +
+       \frac(q_V + 1}{2^L}. \]
+  The constant hidden by the $O(\cdot)$ is small and depends on the model of
+  computation.
   
   Suppose $A$ can break $F$ used as a MAC in time $t$ and with $q_T$ and
   $q_V$ queries to its tagging and verification oracles respectively.
@@ -135,7 +122,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{PRFs are MACs, 2: the distinguisher}
+  \head{PRFs are MACs, \seq: the distinguisher}
 
   \begin{program}
     Distinguisher $D^{F(\cdot)}$: \+ \\
@@ -154,7 +141,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{PRFs are MACs, 3: wrapping up}
+  \head{PRFs are MACs, \seq: wrapping up}
 
   The distinguisher simulates the tagging and verification oracles for the
   MAC forger, using its supplied oracle.  If the forger succeeds, then the
@@ -167,18 +154,50 @@
   $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}. \]%
 \end{slide}
 
+\begin{slide}
+  \head{PRFs are MACs, \seq: MACs aren't PRFs}
+  
+  The converse of our result is not true.  Suppose $\mathcal{M} = (T, V)$ is
+  a deterministic MAC.  Choose some integer $n$.  Then define $\mathcal{M}' =
+  (T', V')$, as follows:
+  \[ T'_K(x) = 0^n \cat T_K(x); \qquad
+     V'_K(x, \tau) = \begin{cases}
+       1 & if $T'_K(x) = \tau$ \\
+       0 & otherwise
+     \end{cases}.
+  \]
+  $T'$ is obviously not a PRF: an adversary checking for the string of $n$
+  zero bits on the output will succeed with advantage $1 - 2^{-qn}$.
+  
+  However, $\mathcal{M}'$ is a secure MAC.  Suppose $A'$ attacks
+  $\mathcal{M}'$.
+  \begin{program}
+    Adversary $A^{T(\cdot), V(\cdot)}$: \+ \\
+      $(m, \tau') \gets A'^{\id{tag}(\cdot), \id{verify}(\cdot)}$; \\
+      \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
+      \RETURN $(m, \tau)$;
+  \next
+    Oracle $\id{tag}(m)$: \+ \\
+      \RETURN $0^n \cat T(m)$; \- \\[\smallskipamount]
+    Oracle $\id{verify}(m, \tau')$: \+ \\
+      \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
+      \IF $z \ne 0^n$ \THEN \RETURN $0$; \\
+      \ELSE \RETURN $V(m, \tau)$;
+  \end{program}
+\end{slide}
+
 \begin{exercise}
   \begin{parenum}
   \item Suppose that $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^L$ is
     a $(t, q, \epsilon)$-secure PRF.  Let $T^{(\ell)}_K(x)$ be the leftmost
-    $\ell$~bits of $F_K(x)$.  Demonstrate the security of $T^{(\ell)}(\cdot)$
-    as a MAC.
+    $\ell$~bits of $F_K(x)$ for $\ell \le L$.  Demonstrate the security of
+    $T^{(\ell)}(\cdot)$ as a MAC.
   \item Discuss the merits of truncating MAC tags in practical situations.
   \end{parenum}
   \answer%
@@ -249,7 +268,7 @@
     to the tagging oracle.
   \item Once a verification query succeeds, all subsequent verification
     queries also succeed and the adversary returns a correct forgery (e.g.,
-    by simply repeating the succeessful query).
+    by simply repeating the successful query).
   \end{itemize}
   It's clear that any adversary can be transformed into one which has these
   properties and succeeds with probability at least as high.
@@ -309,7 +328,7 @@
   return it; otherwise we guess randomly from the remaining $2^L - q$
   possibilities.  Now
   \begin{eqnarray*}[rl]
-    e_q &= e_{q-1} + (1 - e_{q-1}) \frac{1}{2^L - q} \\
+    e_q &= e_{q-1} + \frac{1 - e_{q-1}}{2^L - q} \\
         &= \frac{q}{2^L} + \frac{2^L - q}{2^L} \cdot \frac{1}{2^L - q} \\
         &= \frac{q + 1}{2^L}
   \end{eqnarray*}
@@ -319,14 +338,20 @@
 \xcalways\subsection{The HMAC construction}\x
 
 \begin{slide}
-  \head{The HMAC construction \cite{Bellare:1996:KHF}, 1: motivation}
-
+  \resetseq
+  \head{The HMAC construction \cite{Bellare:1996:KHF}, \seq: motivation}
+  
   It ought to be possible to construct a decent MAC using a hash function.
   Many attempts have failed, however.  For example, these constructions are
-  weak if used with Merkle-Damg\aa{}rd iterated hashes:
+  weak if used with standard one-pass Merkle-Damg\aa{}rd iterated hashes.
   \begin{itemize}
-  \item Secret prefix: $T_K(m) = H(K \cat m)$.
-  \item Secret suffix: $T_K(m) = H(m \cat K)$.
+  \item Secret prefix: $T_K(m) = H(K \cat m)$.  Given $H(K \cat m)$, it's
+    easy to compute $H(K \cat m \cat p \cat m')$ for a padding string $p$ and
+    arbitrary suffix $m'$.
+  \item Secret suffix: $T_K(m) = H(m \cat K)$.  Finding a collision $H(m) =
+    H(m')$ yields $H(m \cat K) = H(m' \cat K)$.  We saw earlier that
+    adversaries which know collisions \emph{exist} even if we don't know how
+    to describe them.
   \end{itemize}
 
   It would be nice to have a construction whose security was provably related
@@ -334,7 +359,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 2: definition of NMAC}
+  \head{The HMAC construction, \seq: definition of NMAC}
  
   Let $H\colon \{0, 1\}^* \to \{0, 1\}^k$ be an iterated hash, constructed
   from the compression function $F\colon \{0, 1\}^k \times \{0, 1\}^L \to
@@ -354,15 +379,15 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 3: security of NMAC}
+  \head{The HMAC construction, \seq: security of NMAC}
 
   Consider a function $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^k$.
   We say that $F$ is \emph{$(t, q, \epsilon)$-weakly collision resistant} if,
   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
@@ -370,12 +395,12 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 4: NMAC security proof}
+  \head{The HMAC construction, \seq: NMAC security proof}
 
   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$; \\
@@ -390,7 +415,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 5: from NMAC to HMAC}
+  \head{The HMAC construction, \seq: from NMAC to HMAC}
 
   Implementing NMAC involves using strange initialization vectors and
   generally messing about with your hash function.  HMAC is an attempt to
@@ -408,7 +433,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{The HMAC construction, 6: comparison with NMAC}
+  \head{The HMAC construction, \seq: comparison with NMAC}
 
   Comparing the two constructions, we see that
   \[ \Xid{T}{HMAC}^H_K =
@@ -441,11 +466,11 @@
   $i \in \{0, 1\}$) using the $H_K$ construction.  Verification in each
   case consists of computing the tag and comparing to the one offered.
   \begin{eqlines*}
-    T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K)
+    T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K); \\
     V^i_K(x, \tau) = \begin{cases}
       1 & if $\tau = T^i_K(x)$ \\
       0 & otherwise
-    \end{cases}
+    \end{cases}.
   \end{eqlines*}
   Decide whether each of these constructions is secure.  A full proof is
   rather hard: an informal justification would be good.
@@ -462,47 +487,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
-  occured. 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:
@@ -528,7 +553,7 @@
   as $\G1$, except that if $A$ makes any query of the form $p \cat K
   \cat q$ with $|p| = t$ and $|q| = \ell - k$ then the game halts
   immediately, and let $F_2$ be the event that this occurs.  By
-  Lemma~\ref{lem:shoup} (page~\pageref{lem:shoup}), then, $|{\Pr[S_2]} -
+  Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}), then, $|{\Pr[S_2]} -
   \Pr[S_1]| \le \Pr[F_2]$.  Let game~$\G3$ be the same as $\G2$ except
   that we give $A$ an oracle for $F_K$ rather than $F'_K$.  Since $F$
   and $F'$ differ only on queries of the form $p \cat K \cat q$, we have
@@ -543,7 +568,7 @@
   as $p \cat K' \cat q$ with $|p| = t$, $|K'| = k$ and $|q| = \ell - k$;
   then, if $F_{K'}(0) = F(0) \land F_{K'}(1) = F(1) \land \cdots \land
   F_{K'}(n - 1) = F(n - 1)$, $B$ immediately returns $1$, claiming that
-  its oracle $F$ is the function $F_{K'}$; if this never occirs, $B$
+  its oracle $F$ is the function $F_{K'}$; if this never occurs, $B$
   returns $0$.  Clearly, if $B$ is given an instance $F_K$ of $F$ then
   it succeeds with probability $\Pr[F_2]$; however, if $F$ is a random
   function then $B$ returns $1$ with probability at most $q 2^{-nk}$.
@@ -551,14 +576,15 @@
   queries, and takes time $t + O(n q)$.  Wrapping everything up, we get
   \[ \InSec{prf}(F'; t, q) \le 
      2\cdot\InSec{prf}(F; t + O(q n), q + n) + \frac{q}{2^{nk}}. \]%
-  This completes the proof of generic insecurty for $\mathcal{M}^1$.
+  This completes the proof of generic insecurity for $\mathcal{M}^1$.
 \end{exercise}
 
 \xcalways\subsection{Universal hashing}\x
 
 \begin{slide}
   \topic{almost-universal hash functions}
-  \head{Universal hashing, 1: definition}
+  \resetseq
+  \head{Universal hashing, \seq: definition}
   
   Consider a family of hash functions $H\colon \keys H \times \dom H \to
   \ran H$.  We define
@@ -567,6 +593,9 @@
   If $\InSec{uh}(H) \le \epsilon$ then we say that $H$ is
   \emph{$\epsilon$-almost universal}.  Note that the concept of
   almost-universality is not quantified by running times.
+
+  Such families definitely exist: we don't need to make intractability
+  assumptions.  We'll see some examples later.
   
   If $H$ is $1/|{\ran H}|$-almost universal, then we say that $H$ is
   \emph{universal}.  Sometimes it's said that this is the best possible
@@ -588,7 +617,7 @@
 
 \begin{slide}
   \topic{dynamic view}
-  \head{Universal hashing, 2: a dynamic view}
+  \head{Universal hashing, \seq: a dynamic view}
   
   Suppose that $H$ is $\epsilon$-almost universal.  Consider this experiment:
   \begin{program}
@@ -609,7 +638,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Universal hashing, 3: the dynamic view (cont.)}
+  \head{Universal hashing, \seq: the dynamic view (cont.)}
   
   Now we treat $\rho$ as a random variable, selected from some distribution
   $P$ on the set $\{0, 1\}^*$.  We see that
@@ -628,7 +657,7 @@
 
 \begin{slide}
   \topic{composition}
-  \head{Universal hashing, 4: composition}
+  \head{Universal hashing, \seq: composition}
   
   Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is
   $\epsilon'$-almost universal, and $\dom G = \ran G'$.  We define the
@@ -649,111 +678,60 @@
 \end{slide}
 
 \begin{slide}
-  \topic{the collision game}
-  \head{Universal hashing, 5: the collision game}
-  
-  Suppose that, instead of merely a pair $(x, y)$, our adversary was allowed
-  to return a \emph{set} $Y$ of $q$ elements, and measure the probability
-  that $H_K(x) = H_K(y)$ for some $x \ne y$ with $x, y \in Y$, and for $K
-  \inr \keys H$.
-  
-  Let $\InSec{uh-set}(H; q)$ be maximum probability acheivable for sets $Y$
-  with $|Y| \le q$.  Then
-  \[ \InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .\]
+  \topic{domain and range extension of a PRF}
+  \head{Universal hashing, \seq: PRF domain extension}
+
+  Suppose that $F\colon \keys F \times \{0, 1\}^L \to \{0, 1\}^l$ is a PRF.
+  We'd like to have a PRF for a bigger domain $\{0, 1\}^n$.
+
+  If $H\colon \{0, 1\}^k \times \{0, 1\}^n \to \{0, 1\}^L$ is an
+  almost-universal hash function.  Then we can define $F'$ by
+  \[ F'_{K, h}(x) = F_K(H_h(x)). \]
+  Now we can prove that
+  \[ \InSec{prf}(F'; t, q) \le
+       \InSec{prf}(F; t, q) +
+       \frac{q(q - 1)}{2} \InSec{ah}(H). \]
+  Immediately this tells us that $F'$ is a MAC for $n$-bit messages.
 \end{slide}
 
 \begin{proof}
-  This is rather tedious.  We use the dynamic view.  Suppose $A$ returns $(x,
-  Y)$ with $|Y| = q$, and succeeds with probability $\epsilon$.  Consider
+  Suppose $A$ attacks $F'$.  Consider the distinguisher $B$ which attacks
+  $F$:
   \begin{program}
-    Adversary $A'$: \+ \\
-      $(x, Y) \gets A$; \\
-      $y \getsr Y$; \\
-      \RETURN $(x, Y \setminus \{y\})$;
+    Distinguisher $B^{F(\cdot)}$: \+ \\
+      $h \getsr \{0, 1\}^k$; \\
+      \RETURN $A^{F(H_h(\cdot))}()$;
   \end{program}
-  The worst that can happen is that $A'$ accidentally removes the one
-  colliding element from $Y$.  This occurs with probability $2/q$.  So
-  \[ \Succ{uh-set}{H}(A') \ge \frac{q - 2}{q} \Succ{uh-set}{H}(A). \]
-  Rearranging and maximzing gives
-  \[ \InSec{uh-set}(H; q) \le
-     \frac{q}{q - 2} \cdot \InSec{uh-set}(H; q - 1). \]
-  Note that $\InSec{uh-set}(H; 2) = \InSec{uh}(H)$ is our initial notion.  A
-  simple inductive argument completes the proof.
+  Suppose $F$ is an oracle for $F_K(\cdot)$.  Then $A$ plays its standard
+  attack game and all is well.  Conversely, suppose $F$ is a random
+  function.  Then the only way $A$ can distinguish its oracle $F(H_h(\cdot))$
+  from a random function is if it issues two queries $x_i \ne x_j$ such that
+  $H_h(x_i) = H_h(x_j)$.  But for each pair $(i, j)$ this happens with
+  probability at most $\InSec{ah}(H)$.  The stated bound follows.
 \end{proof}
 
-\begin{slide}
-  \topic{a MAC}
-  \head{Universal hashing, 6: a MAC}
-  
-  Suppse that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
-  almost universal hash fucntion, and $F\colon \{0, 1\}^{k'} \times \{0,
-  1\}^l \to \{0, 1\}^L$ is a PRF\@.  Define a MAC $\Xid{\mathcal{M}}{UH}^{H,
-    F} = (\Xid{T}{UH}^{H, F}, \Xid{V}{UH}^{H, F})$ where:
-  \begin{eqnarray*}[rl]
-    \Xid{T}{UH}^{H, F}_{K, K'}(m) &= F_{K'}(H_K(m)) \\
-    \Xid{V}{UH}^{H, F}_{K, K'}(m, \tau) &= \begin{cases}
-      1 & if $\tau = F_{K'}(H_K(m))$ \\
-      0 & otherwise
-    \end{cases}.
-  \end{eqnarray*}
-  We have
-  \begin{eqnarray*}[Ll]
-     \InSec{suf-cma}(\Xid{\mathcal{M}}{UH}^{H, F}; t, q_T, q_V) \\
-     & \le
-     (q_V + 1) \biggl(\InSec{prf}(F; t, q_T + 1) + \frac{1}{2^L} +
-                      \frac{q_T(q_T - 1)}{2} \cdot \InSec{uh}(H)\biggr).
-  \end{eqnarray*}
-\end{slide}
-
-\begin{proof}
-  We shall prove the result for $q_V = 0$ and $q_T = q$, and appeal to the
-  earlier result on verification oracles.
-  
-  Suppose $A$ attacks the scheme $\Xid{\mathcal{M}}{UH}^{H, F}$ in time $t$,
-  issuing $q$ tagging queries.  Consider a distinguisher $D$, constructed
-  from a forger $A$:
-  \begin{program}
-    Distinguisher $D^{F(\cdot)}$: \+ \\
-      $K \getsr \{0, 1\}^k$; \\
-      $\Xid{T}{list} \gets \emptyset$; \\
-      $(m, \tau) \gets A^{\id{tag}(K, \cdot)}$; \\
-      \IF $m \notin \Xid{T}{list} \land \tau = F(H_K(m))$
-      \THEN \RETURN $1$; \\
-      \ELSE \RETURN $0$; \- \\[\smallskipamount]
-    Oracle $\id{tag}(K, m)$: \+ \\
-      $\Xid{T}{list} \gets \Xid{T}{list} \cup \{m\}$; \\
-      \RETURN $F(H_K(m))$; \- \\[\smallskipamount]
-  \end{program}
-  Note that $A$ isn't provided with a verification oracle: that's because we
-  didn't allow it any verification queries.
-
-  We can see immediately that
-  \[ \Pr[K \getsr \{0, 1\}^{k'} : D^{F_K(\cdot)} = 1] =
-     \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A). \]%
-  
-  We must now find an upper bound for $\Pr[F \getsr \Func{l}{L} :
-  D^{F(\cdot)}]$.  Suppose that the adversary returns the pair $(m^*,
-  \tau^*)$, and that its tagging oracle queries and their answers are $(m_i,
-  \tau_i)$ for $0 \le i < q$.  Consider the event $C$ that $H_K(m) =
-  H_K(m')$ for some $m \ne m'$, with $m, m' \in \{m^*\} \cup \{\,m_i \mid 0
-  \le i < q\,\}$.
-  
-  If $C$ doesn't occur, then $F$ has not been queried before at $H_K(m)$, but
-  there's a $2^{-L}$ probability that the adversary guesses right anyway.  If
-  $C$ does occur, then we just assume that the adversary wins, even though it
-  might not have guessed the right tag.
-  
-  By our result on the collision game, $\Pr[C] \le q \cdot \InSec{uh}(H)$.
-  Then
-  \[ \Succ{prf}{F}(D) \ge
-     \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A) -
-       \frac{1}{2^L} - \frac{q(q - 1)}{2} \cdot \InSec{uh}(H). \]%
-  The result follows.
-\end{proof}
+\begin{exercise}
+  Show how to extend the \emph{range} of a PRF.  Specifically, suppose you're
+  given a PRF $F\colon \keys{F} \times \{0, 1\}^L \to \{0, 1\}^t$, but want
+  an $l$-bit output.  Show how to achieve this.
+\answer
+  There are two obvious techniques.
+  \begin{enumerate}
+  \item Suppose we have a PRG $G\colon \{0, 1\}^t \to \{0, 1\}^l$.  Then we
+    can easily use $G \compose F$; it's easy to see how this is secure.
+    Indeed, we can use $F$ itself as a PRG, by defining $G(x) = F_x(0) \cat
+    F_x(1) \cat \cdots$.
+  \item Let $m = \lceil \log_2 (l/t) \rceil$.  Use the construction from the
+    slide to build a PRF $F'$ with domain $\{0, 1\}^{L+m}$.  Then we define
+    $F''_K(x) = F'_K(x \cat 0) \cat F'_K(x \cat 1) \cat \cdots \cat F'_K(x
+    \cat m - 1)$.
+  \end{enumerate}
+\end{exercise}
 
 \begin{slide}
   \topic{almost XOR-universality}
-  \head{Almost XOR-universality, 1: definition}
+  \resetseq
+  \head{Almost XOR-universality, \seq: definition}
   
   Consider a family of hash functions $H\colon \keys H \times \dom H \to
   \{0, 1\}^L$.  Define
@@ -773,7 +751,7 @@
   technique as for almost universal functions.
   
   If $H$ is $2^{-L}$-almost XOR universal then we say that $H$ is
-  \emph{XOR-universal}.  This is the best acheivable.
+  \emph{XOR-universal}.  This is the best achievable.
 \end{slide}
 
 \begin{proof}
@@ -795,7 +773,7 @@
 
 \begin{slide}
   \topic{composition}
-  \head{Almost XOR-universality, 2: composition}
+  \head{Almost XOR-universality, \seq: composition}
   
   We extend our result about composition of almost-universal functions.
   Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is
@@ -808,8 +786,62 @@
 \end{slide}
 
 \begin{slide}
+  \head{Almost XOR-universality, \seq: examples of AXU hash functions}
+
+  Let $\F = \gf{2^l}$ be a finite field.  Given a message $m = (m_0, \ldots,
+  m_{n-1} \in \F^n$, we can hash it in several ways.
+  \begin{itemize}
+  \item Inner-product: choose $k = (k_0, \ldots, k_{n-1}) \in \F^n$.
+    \[ \Xid{H}{ip}_{k}(m) = m \cdot k = \sum_{0\le i<n} k_i m_i. \]
+    This hash is XOR-universal: $\InSec{axu}(\Xid{H}{ip}) = 1/2^l$.
+  \item Polynomial evaluation: choose $x \in \F$.
+    \[ \Xid{H}{pe}_{x}(m) = \sum_{0\le i<n} m_i x^{i+1}. \]
+    Here we have only $\InSec{axu}(\Xid{H}{pe}) = n/2^l$.
+  \end{itemize}
+\end{slide}
+
+\begin{proof}
+  \begin{itemize}
+  \item Suppose we have messages $m \ne m'$ and $\delta \in \F$.  Then $m
+    \cdot k + m' \cdot k = \delta$.  We must have some $m_j \ne m'_j$.  It
+    follows that
+    \[ k_j = \biggl( \delta + \sum_{\begin{script}
+               0\le i<n \\
+               i \ne j
+             \end{script}
+             k_i (m_i + m'_i)
+             \biggr) \biggm/ (m'_i - m_j) \]
+    But we choose $k$ uniformly at random, so the probability that this holds
+    is $2^{-l}$.
+  \item Again, we have distinct messages and some $\delta \in \F$.  We have a
+    polynomial equation
+    \[ \delta + \sum_{0\le i <n} (m_i - m'_i) x^{i+1} = 0 \]
+    Since there is some $m_j \ne m'_j$, this has degree at most $n$, so
+    there are at most $n$ distinct roots $x \in \F$.  But we choose $x$
+    uniformly at random, so $x$ is one of these roots with probability at
+    most $n/2^l$.
+  \end{itemize}
+\end{proof}
+
+\begin{exercise}
+  Suppose $H$ is an $\epsilon$-AXU hash function with $l$-bit output.  Let
+  $G_h(x)$ be the first $t$ bits of $H_h(x)$.  Show that $G$ is
+  $2^{l-t}\epsilon$-AXU.
+\answer
+  Let $m \ne m'$ be distinct messages and let $\delta \in \{0, 1\}^t$ be some
+  XOR difference.  Then
+  \begin{eqnarray*}
+    \Pr[h \gets \keys{G} : G_h(m) \xor G_h(m') = \delta]
+    &= \sum_{\delta' \in \{0, 1\}^{l-t}}
+         \Pr[h \gets \keys{H} : H_h(m) \xor H_h(m') = \delta \cat \delta']
+    &\le \sum_{\delta' \in \{0, 1\}^{l-t}} \InSec{axu}(H)
+    &= 2^{l-t} \InSec{axu}(H).
+  \end{eqnarray*}
+\end{exercise}
+
+\begin{slide}
   \topic{a better MAC}
-  \head{Almost XOR-universality, 3: a better MAC}
+  \head{Almost XOR-universality, \seq: a better MAC}
 
   The security result for the UH-based MAC contains a factor $q_T$, which
   it'd be nice to remove.  Our new scheme uses an AXU hash $H\colon \keys H
@@ -827,14 +859,14 @@
   \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.
 \end{slide}
 
 \begin{slide}
-  \head{Almost XOR-universality, 4: security of AXU-based MACs}
+  \head{Almost XOR-universality, \seq: security of AXU-based MACs}
   
   For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
   \begin{eqnarray*}[Ll]
@@ -844,7 +876,7 @@
 \end{slide}
 
 \begin{slide}
-  \head{Almost XOR-universality, 5: randomized AXU-based MAC}
+  \head{Almost XOR-universality, \seq: randomized AXU-based MAC}
   
   We can avoid statefulness by using randomization.  This new scheme is
   $\Xid{\mathcal{M}}{XUH$\$$}^{H, F} = (\Xid{T}{XUH$\$$}^{H, F},
@@ -857,7 +889,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]
