X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/41761fdc7bb8f1ed87f5e1116d389158513ee280..9907b634a7bc6c9db6381a578e192178a28e9799:/auth-mac.tex diff --git a/auth-mac.tex b/auth-mac.tex index 40f466d..60e0034 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,32 +98,16 @@ \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) + + 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. @@ -135,7 +120,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 +139,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 +152,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 +266,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 +326,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 +336,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 +357,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 +377,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 +393,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 +413,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 +431,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 +464,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,38 +485,39 @@ 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$ @@ -528,7 +552,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 +567,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 +575,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 @@ -588,7 +613,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 +634,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 +653,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 @@ -650,14 +675,14 @@ \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} @@ -674,7 +699,7 @@ 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 @@ -683,10 +708,10 @@ \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] @@ -753,7 +778,8 @@ \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 +799,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 +821,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 @@ -809,7 +835,7 @@ \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 @@ -834,7 +860,7 @@ \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 +870,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},