\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
\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}
\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
\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)
+ + 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.
\end{slide}
\begin{slide}
- \head{PRFs are MACs, 2: the distinguisher}
+ \head{PRFs are MACs, \seq: the distinguisher}
\begin{program}
Distinguisher $D^{F(\cdot)}$: \+ \\
\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
$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%
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.
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*}
\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
\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
\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
\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$; \\
\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
\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 =
$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.
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$
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
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}$.
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
\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}
\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
\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
\begin{slide}
\topic{the collision game}
- \head{Universal hashing, 5: the collision game}
+ \head{Universal hashing, \seq: 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$
+ Let $\InSec{uh-set}(H; q)$ be maximum probability achievable for sets $Y$
with $|Y| \le q$. Then
\[ \InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .\]
\end{slide}
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
+ Rearranging and maximizing 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
\begin{slide}
\topic{a MAC}
- \head{Universal hashing, 6: a MAC}
+ \head{Universal hashing, \seq: 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,
+ Suppose that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
+ almost universal hash function, 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]
\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
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}
\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
\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
\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]
\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},
~mdw / doc / ips / blobdiff