CommitLineData
41761fdc 1\xcalways\section{Message authentication codes}\x
2
3\xcalways\subsection{Definitions and security notions}\x
4
5\begin{slide}
7
8 A MAC is a pair of algorithms $\mathcal{M} = (T, V)$:
9 \begin{itemize}
10 \item The \emph{tagging} algorithm $T\colon \{0, 1\}^k \times \{0, 1\}^* 11 \to \{0, 1\}^L$ is a probabilistic algorithm which, given a key and a
12 string, returns a \emph{tag}. We write $\tau \in T_K(m)$.
13 \item The \emph{verification} algorithm $V\colon \{0, 1\}^k \times \{0, 14 1\}^* \times \{0, 1\}^L \to \{0, 1\}$ is a deterministic algorithm which,
15 given a key, a message and a tag, returns $1$ if the tag is valid, or $0$
16 otherwise; i.e., we require that $V_K(m, \tau) = 1 \iff \tau \in T_K(m)$.
17 \end{itemize}
18 The basic idea is that it's hard for an adversary to \emph{forge} a tag for
19 a message it's not seen before.
20\end{slide}
21
22\begin{slide}
23 \topic{informal security notion}
53aa10b5 24 \resetseq
25 \head{Strong MACs, \seq: informal security notion}
41761fdc 26
27 Our standard notion of security for MACs is \emph{strong unforgeability
28 against chosen message attack}, or SUF-CMA, for short
29 \cite{Abdalla:2001:DHIES, Bellare:2000:AER}. Let $A$ be an adversary which
30 is attempting to attack the MAC $\mathcal{M} = (T, V)$.
31
32 We play a game with the adversary. We invent a key $K \inr \{0, 1\}^k$.
33 The adversary \emph{wins} if, after requesting tags for some messages of
34 its choice, and checking some guesses, it can return a pair $(m, \tau)$
35 such that:
36 \begin{itemize}
37 \item the tag is correct, i.e., $V_K(m, \tau) = 1$; and
38 \item the tag is not one returned by the adversary's tagging oracle for
39 that message.
40 \end{itemize}
41\end{slide}
42
43\begin{slide}
44 \topic{strong MACs}
53aa10b5 45 \head{Strong MACs, \seq: the experiment}
41761fdc 46
47 We perform the following experiment with the adversary.
48 \begin{program}
49 Experiment $\Expt{suf-cma}{\mathcal{M}}(A)$: \+ \\
50 $K \getsr \{0, 1\}^k$; \\
51 $\Xid{T}{list} \gets \emptyset$; \\
52 $(m, \tau) \gets A^{\id{tag}(\cdot), V_K(\cdot, \cdot)}$; \\
53 \IF $V_K(m, \tau) \land (m, \tau) \notin \Xid{T}{list}$
54 \THEN \RETURN $1$; \\
55 \ELSE \RETURN $0$; \- \$\smallskipamount] 56 Oracle \id{tag}(m): \+ \\ 57 \tau \gets T_K(m); \\ 58 \Xid{T}{list} \gets \Xid{T}{list} \cup \{(m, \tau)\}; \\ 59 \RETURN \tau; 60 \end{program} 61\end{slide} 62 63\begin{slide} 53aa10b5 64 \head{Strong MACs, \seq: wrapping up the notation} 41761fdc 65 66 The \emph{success probability} of an adversary A against the MAC 67 \mathcal{M} in the sense of SUF-CMA is 68 \[ \Succ{suf-cma}{\mathcal{M}}(A) = 69 \Pr[\Expt{suf-cma}{\mathcal{M}}(A) = 1].$%
70 The \emph{insecurity} of a MAC $\mathcal{M}$ in the SUF-CMA sense is then
71 $\InSec{suf-cma}(\mathcal{M}; t, q_T, q_V) = 72 \max_A \Succ{suf-cma}{\mathcal{M}}(A)$%
73 where the maximum is taken over all adversaries $A$ running in time $t$ and
74 making $q_T$ tagging and $q_V$ verification queries.
75
76 If $\InSec{suf-cma}(\mathcal{M}; t, q_T, q_V) \le \epsilon$ then we say
77 that $\mathcal{M}$ is a \emph{$(t, q_T, q_V, \epsilon)$-secure MAC in the
78 SUF-CMA sense}.
79\end{slide}
80
81\begin{slide}
82 \topic{other notions}
83 \head{Other security notions for MACs}
84
85 There are a number of weaker security notions in use:
86 \begin{itemize}
87 \item The definition of a \emph{weak MAC} restricts the adversary from
88 returning any message with which it queried its tagging oracle. The
89 strong MAC definition considers this OK, as long as the tag is different
90 from any returned by the oracle for that message.
91 \item Some definitions of MACs don't equip the adversary with a
92 verification oracle. Our definition considers these to be $(t, q_T, 0, 93 \epsilon)$-secure.
94 \item You can have a MAC with a bounded domain $\{0, 1\}^L$ rather than
95 $\{0, 1\}^*$ as shown previously.
96 \item Further quantification is possible, e.g., counting the total number
97 of bytes queried, or the maximum size of a tagging query.
98 \end{itemize}
99\end{slide}
100
41761fdc 101\xcalways\subsection{Basic results}\x
102
103\begin{slide}
104 \topic{PRFs are MACs}
53aa10b5 105 \resetseq
41761fdc 107
108 If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a $(t, q, \epsilon)$-secure
109 PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T e09a1839 110 + q_V + 1$, $t = t' + O(q)$, and $\epsilon' \le \epsilon + (q_V + 1) 41761fdc 111 2^{-L}$. The constant hidden by the $O(\cdot)$ is small and depends on the
112 model of computation.
113
114 Suppose $A$ can break $F$ used as a MAC in time $t$ and with $q_T$ and
115 $q_V$ queries to its tagging and verification oracles respectively.
116
117 If we can construct an adversary which distinguishes $F_K$ from a random
118 function using $A$ as an essential component, then we can prove the
119 result.
120\end{slide}
121
122\begin{slide}
53aa10b5 123 \head{PRFs are MACs, \seq: the distinguisher}
41761fdc 124
125 \begin{program}
126 Distinguisher $D^{F(\cdot)}$: \+ \\
127 $\Xid{T}{list} \gets \emptyset$; \\
128 $(m, \tau) \gets A^{T_F(\cdot), V_F(\cdot, \cdot)}$; \\
129 \IF $m \notin \Xid{T}{list} \land \tau = F(m)$
130 \THEN \RETURN $1$; \\
131 \ELSE \RETURN $0$; \- \$\smallskipamount] 132 Oracle T_F(m): \+ \\ 133 \Xid{T}{list} \gets \Xid{T}{list} \cup \{m\}; \\ 134 \RETURN F(m); \- \\[\smallskipamount] 135 Oracle V_F(m, \tau): \+ \\ 136 \IF \tau = F(m) \THEN \RETURN 1; \\ 137 \ELSE \RETURN 0; 138 \end{program} 139\end{slide} 140 141\begin{slide} 53aa10b5 142 \head{PRFs are MACs, \seq: wrapping up} 41761fdc 143 144 The distinguisher simulates the tagging and verification oracles for the 145 MAC forger, using its supplied oracle. If the forger succeeds, then the 146 distinguisher returns 1; otherwise it returns zero. 147 148 The probability that the distinguisher returns 1 given an instance F_K of 149 the PRF is precisely \Succ{suf-cma}{F}(A). 150 151 The probability that it returns 0 given a random function depends on what 152 A does when it's given a random function. But we know that the 153 probability of it successfully guessing the MAC for a message for which it 154 didn't query T can be at most (q_V + 1) 2^{-L}. So e09a1839 155 \[ \Adv{prf}{F}(D) \ge \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}.$
41761fdc 156 Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields
157 $\InSec{suf-cma}(F; t, q_T, q_V) \le 158 \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}.$%
159\end{slide}
160
53aa10b5 161\begin{slide}
162 \head{PRFs are MACs, \seq: MACs aren't PRFs}
163
164 The converse of our result is not true. Suppose $\mathcal{M} = (T, V)$ is
165 a deterministic MAC. Choose some integer $n$. Then define $\mathcal{M}' = 166 (T', V')$, as follows:
167 $T'_K(x) = 0^n \cat T_K(x); \qquad 168 V'_K(x, \tau) = \begin{cases} 169 1 & if T'_K(x) = \tau \\ 170 0 & otherwise 171 \end{cases}. 172$
173 $T'$ is obviously not a PRF: an adversary checking for the string of $n$
174 zero bits on the output will succeed with advantage $1 - 2^{-qn}$.
175
176 However, $\mathcal{M}'$ is a secure MAC. Suppose $A'$ attacks
177 $\mathcal{M}'$.
178 \begin{program}
179 Adversary $A^{T(\cdot), V(\cdot)}$: \+ \\
180 $(m, \tau') \gets A'^{\id{tag}(\cdot), \id{verify}(\cdot)}$; \\
181 \PARSE $\tau'$ \AS $n\colon z, \tau$; \\
182 \RETURN $(m, \tau)$;
183 \next
184 Oracle $\id{tag}(m)$: \+ \\
185 \RETURN $0^n \cat T(m)$; \- \$\smallskipamount] 186 Oracle \id{verify}(m, \tau'): \+ \\ 187 \PARSE \tau' \AS n\colon z, \tau; \\ 188 \IF z \ne 0^n \THEN \RETURN 0; \\ 189 \ELSE \RETURN V(m, \tau); 190 \end{program} 191\end{slide} 192 41761fdc 193\begin{exercise} 194 \begin{parenum} 195 \item Suppose that F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^L is 196 a (t, q, \epsilon)-secure PRF. Let T^{(\ell)}_K(x) be the leftmost 53aa10b5 197 \ell~bits of F_K(x) for \ell \le L. Demonstrate the security of 198 T^{(\ell)}(\cdot) as a MAC. 41761fdc 199 \item Discuss the merits of truncating MAC tags in practical situations. 200 \end{parenum} 201 \answer% 202 \begin{parenum} 203 \item The follows exactly the same pattern as the PRFs are MACs' proof in 204 the slides: T^{(\ell)} is a (t, q_T, q_V, \epsilon + (q_V + 205 1)2^{-\ell})-secure MAC, where q_T + q_V = q. 206 \item Obviously, truncating tags saves bandwidth. There is a trade-off 207 between tag size and security, as the 2^{-\ell} term shows. Note that 208 this term represents the probability of the adversary guessing the 209 correct tag when it's actually attacking a random function, and 210 therefore, when this occurs, the adversary has one by accident'. 211 Including sequence numbers in packets ensures that replay of accidental 212 forgery (or honest messages) will be detected. Hence, for some 213 applications, setting \ell = 32 or even lower is of no particular harm. 214 Perhaps more significantly, if the PRF isn't actually as good as it ought 215 to be, and (say) leaks key material very slowly, then truncating its 216 output can actually improve security. 217 \end{parenum} 218\end{exercise} 219 220\begin{exercise} 221 A traditional MAC construction is the \emph{CBC-MAC}: it works like this. 222 Suppose F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^l is a PRF. 223 Split a message~x into l-bit blocks x_0, x_1, \ldots, x_{n-1} 224 (applying some sort of padding if you need to). Then we define the CBC-MAC 225 as F^{(n)}_K(x), where 226 \[ F^{(1)}_K(x) = F_K(x); 227 \qquad F^{(i+i)}(x) = F_K(x_i \xor F^{(i)}_K(x)).$%
228 In \cite{Bellare:1994:SCB}, Mihir Bellare, Joe Kilian and Phil Rogaway
229 introduced the world to the concrete-security approach and, almost
230 incidentally, proved that the CBC-MAC is a PRF (and therefore a MAC) for
231 any \emph{fixed sized} input.
232
233 Show that the CBC-MAC is easily broken if you're allowed to choose messages
234 of different lengths.
236 Request tags $\tau$ for the message $x = x_0, x_1, \ldots, x_{n-1}$ and
237 $\tau'$ for $x' = x'_0 \xor \tau, x'_1, \ldots, x'_{n'-1}$. Let $y = x_0, 238 x_1, \ldots, x_{n-1}, x'_0 , x'_1, \ldots, x'_{n'-1}$. Note that
239 $F^{(n)}_K(y) = \tau$, and $F^{(n+1)}_K(y) = F_K(x'_0 \xor F^{(n)}_K(x)) = 240 F^{(1)}_K(x')$. Hence, $F^{(n+n')}_K(y) = \tau'$, and we have a correct
241 forgery.
242\end{exercise}
243
244\begin{slide}
245 \topic{verification oracles}
247
248 We can leave verification oracles out of our analysis. This simplifies
249 analysis, but produces slightly less satisfactory quantitative results.
250
251 Suppose that $\mathcal{M} = (T, V)$ is a $(t, q_T, 0, \epsilon)$-secure
252 MAC. Then, for any $q_V$,
253 $\InSec{suf-cma}(\mathcal{M}; t, q_T, q_V) \le 254 (q_V + 1)\InSec{suf-cma}(\mathcal{M}; t, q_T, 0).$%
255 This bound is \emph{tight}: it's not possible for a general result like
256 this to do better.
257\end{slide}
258
259\begin{proof}
260 Consider an adversary $A$ which uses $q_V$ verification queries. We assume
261 the following properties of $A$'s behaviour:
262 \begin{itemize}
263 \item No verification query contains a message and a tag for that message
264 received from the tagging oracle.
265 \item If a verification query succeeds, the message is not given in a query
266 to the tagging oracle.
267 \item Once a verification query succeeds, all subsequent verification
268 queries also succeed and the adversary returns a correct forgery (e.g.,
53aa10b5 269 by simply repeating the successful query).
41761fdc 270 \end{itemize}
271 It's clear that any adversary can be transformed into one which has these
272 properties and succeeds with probability at least as high.
273
274 Let $V$ be the event that at least one verification query succeeds, and let
275 $S$ be the event that $A$ succeeds. Then
276 \begin{eqnarray*}[rl]
277 \Succ{suf-cma}{\mathcal{M}}(A)
278 &= \Pr[S \mid V] \Pr[V] + \Pr[S \mid \lnot V] \Pr[\lnot V] \\
279 &= \Pr[V] + \Pr[S \mid \lnot V] \Pr[\lnot V].
280 \end{eqnarray*}
281 Now consider these two adversaries:
282 \begin{program}
283 Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$: \+ \\
284 $i \gets 0$; \\
285 $(m, \tau) \gets A^{T(\cdot), \Xid{V}{sim}(\cdot, \cdot)}$; \\
286 \RETURN $(m^*, \tau^*)$; \- \$\smallskipamount] 287 Oracle \Xid{V}{sim}(m, \tau): \+ \\ 288 i \gets i + 1; \\ 289 \IF i < q_V \THEN \RETURN V(m, \tau); \\ 290 (m^*, \tau^*) \gets (m, \tau); \\ 291 \RETURN 1; 292 \next 293 Adversary Z^{T(\cdot), V(\cdot, \cdot)}: \+ \\ 294 \\ 295 (m, \tau) \gets A^{T(\cdot), \Xid{V}{zero}(\cdot, \cdot)}; \\ 296 \RETURN (m, \tau); \- \\[\smallskipamount] 297 Oracle \Xid{V}{zero}(m, \tau): \+ \\ 298 \RETURN 0; 299 \end{program} 300 The adversary A' uses q_V - 1 verification queries. It ignores the 301 output of A, returning instead A's q_V-th verification query. Thus, 302 by our assumptions on the behaviour of A, we have that A' succeeds 303 precisely whenever one of A's verification queries succeeds. Thus: 304 \[ \Pr[V] = \Succ{suf-cma}{\mathcal{M}}(A') 305 \le \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V - 1).$%
306 Similarly, the adversary $Z$ succeeds with precisely the same probability
307 as $A$, given that all of its verification queries failed; i.e.,
308 $\Pr[S \mid \lnot V] \Pr[\lnot V] = \Succ{suf-cma}{\mathcal{M}}(Z) 309 \le \InSec{suf-cma}(\mathcal{M}; t, q_T, 0).$%
310 Because $A$ was chosen arbitrarily, we can maximize:
311 \begin{eqnarray*}[rl]
312 \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V)
313 & \le \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V - 1) +
314 \InSec{suf-cma}(\mathcal{M}; t, q_T, 0) \\
315 & \le (q_V + 1)\InSec{suf-cma}(\mathcal{M}; t, q_T, 0)
316 \end{eqnarray*}
317 as required.
318
319 To show that the bound is tight, consider a random function $F$ used as a
320 MAC, with $L$-bit output. Then we claim that $\InSec{suf-cma}(F; t, q_T, 321 q_V) = (q_V + 1)/2^L$. To save typing, let $e_q = \InSec{suf-cma}(F; t, 322 q_T, q)$. We prove the claim by induction on $q$. Firstly, note that if
323 $q = 0$ then necessarily $e_q = 1/2^L$. Now suppose that $e_{q-1} = 324 q/2^L$. We're now allowed an extra query, so rather than returning the
325 result, we feed it to the verification oracle. If it answers yes' then we
326 return it; otherwise we guess randomly from the remaining $2^L - q$
327 possibilities. Now
328 \begin{eqnarray*}[rl]
53aa10b5 329 e_q &= e_{q-1} + \frac{1 - e_{q-1}}{2^L - q} \\
41761fdc 330 &= \frac{q}{2^L} + \frac{2^L - q}{2^L} \cdot \frac{1}{2^L - q} \\
331 &= \frac{q + 1}{2^L}
332 \end{eqnarray*}
333 as claimed.
334\end{proof}
335
336\xcalways\subsection{The HMAC construction}\x
337
338\begin{slide}
53aa10b5 339 \resetseq
340 \head{The HMAC construction \cite{Bellare:1996:KHF}, \seq: motivation}
341
41761fdc 342 It ought to be possible to construct a decent MAC using a hash function.
343 Many attempts have failed, however. For example, these constructions are
53aa10b5 344 weak if used with standard one-pass Merkle-Damg\aa{}rd iterated hashes.
41761fdc 345 \begin{itemize}
53aa10b5 346 \item Secret prefix: $T_K(m) = H(K \cat m)$. Given $H(K \cat m)$, it's
347 easy to compute $H(K \cat m \cat p \cat m')$ for a padding string $p$ and
348 arbitrary suffix $m'$.
349 \item Secret suffix: $T_K(m) = H(m \cat K)$. Finding a collision $H(m) = 350 H(m')$ yields $H(m \cat K) = H(m' \cat K)$. We saw earlier that
351 adversaries which know collisions \emph{exist} even if we don't know how
352 to describe them.
41761fdc 353 \end{itemize}
354
355 It would be nice to have a construction whose security was provably related
356 to some plausible property of the underlying hash function.
357\end{slide}
358
359\begin{slide}
53aa10b5 360 \head{The HMAC construction, \seq: definition of NMAC}
41761fdc 361
362 Let $H\colon \{0, 1\}^* \to \{0, 1\}^k$ be an iterated hash, constructed
363 from the compression function $F\colon \{0, 1\}^k \times \{0, 1\}^L \to 364 \{0, 1\}^k$. We define a keyed version of $H$. Let $K \in \{0, 1\}^k$;
365 then we compute $H_K(x)$ as follows:
366 \begin{enumerate}
367 \item Pad and split $x$ into the $L$-bit blocks $x_0$, $x_1$, \ldots,
368 $x_{n-1}$ as before.
369 \item Set $I_0 = K$. Let $I_{i+1} = F(I_i \cat x_i)$ for $0 \le i < n$.
370 \item The result $H_K(x) = I_n$.
371 \end{enumerate}
372 The NMAC (nested-MAC) construction requires two independent $k$-bit keys
373 $K_0$ and $K_1$. The construction itself is simply:
374 $\Xid{T}{NMAC}^H_{K_0, K_1}(x) = H_{K_0}(H_{K_1}(x)).$
375 NMAC is deterministic, so verification consists of computing the tag and
376 comparing.
377\end{slide}
378
379\begin{slide}
53aa10b5 380 \head{The HMAC construction, \seq: security of NMAC}
41761fdc 381
382 Consider a function $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^k$.
383 We say that $F$ is \emph{$(t, q, \epsilon)$-weakly collision resistant} if,
384 for any adversary $A$ constrained to run in time $t$ and permitted $q$
385 oracle queries,
386 $\Pr[K \getsr \{0, 1\}^k; 9907b634 387 (x, y) \gets A^{F_K(\cdot)} : 388 x \ne y \land F_K(x) = F_K(y)] \le \epsilon$%
41761fdc 389
390 If $H_K$ is a $(t, q_T, q_V, \epsilon)$-secure MAC on $k$-bit messages, and
391 moreover $(t, q_T + q_V, \epsilon')$-weakly collision resistant, then
392 $\Xid{T}{NMAC}^H$ is a $(t, q_T, q_V, \epsilon + \epsilon')$-secure MAC.
393\end{slide}
394
395\begin{slide}
53aa10b5 396 \head{The HMAC construction, \seq: NMAC security proof}
41761fdc 397
398 Let $A$ be an adversary which forges a $\Xid{T}{NMAC}^H$ tag in time $t$,
399 using $q_T$ tagging queries and $q_V$ verification queries with probability
9907b634 400 $\epsilon$. We construct an adversary $A'$ which forges an $H$-tag for a
401 $k$-bit message in essentially the same time.
41761fdc 402 \begin{program}
403 Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$ \+ \\
404 $K \getsr \{0, 1\}^k$; \\
405 $(m, \tau) \gets A^{T(H_K(\cdot)), V(H_K(\cdot), \cdot)}$; \\
406 \RETURN $(H_K(m), \tau)$;
407 \end{program}
408 $A'$ might fail even though $A$ succeeded only if the message it returns,
409 $H_K(m)$, collides with one of its tagging queries. But since $H_K$ is
410 $(t, q_T + q_V, \epsilon')$-weakly collision resistant, this happens with
411 at most probability $\epsilon'$. Hence, $A'$ succeeds with probability at
412 least $\epsilon - \epsilon'$. Rearrangement yields the required result.
413\end{slide}
414
415\begin{slide}
53aa10b5 416 \head{The HMAC construction, \seq: from NMAC to HMAC}
41761fdc 417
418 Implementing NMAC involves using strange initialization vectors and
419 generally messing about with your hash function. HMAC is an attempt to
420 capture the provable security properties using a plain ol' hash function.
421
422 Suppose $H$ is an iterated hash function with a $k$-bit output and $L$-bit
423 blocks (with $L \ge k$). We set $\id{ipad}$ to be the byte $\hex{36}$
424 repeated $L/8$ times, and $\id{opad}$ to be the byte $\hex{5C}$ repeated
425 $L/8$ times. Select a key $K$ of $L$ bits: if your key is shorter, pad it
426 by appending zero bits; if it's longer, hash it with $H$ and then pad.
427
428 The HMAC tagging function is then defined as
429 $\Xid{T}{HMAC}^H_K(m) = 430 H(K \xor \id{opad} \cat H(K \xor \id{ipad} \cat m)).$%
431\end{slide}
432
433\begin{slide}
53aa10b5 434 \head{The HMAC construction, \seq: comparison with NMAC}
41761fdc 435
436 Comparing the two constructions, we see that
437 $\Xid{T}{HMAC}^H_K = 438 \Xid{T}{NMAC}^{H'}_{F(I \cat K \xor \id{opad}), 439 F(I \cat K \xor \id{ipad})}.$%
440 Here, $I$ is $H$'s initialization vector, $F$ is the compression function;
441 $H'$ denotes a keyed hash function that is like' $H$ but performs padding
442 as if there were an extra initial block of message data for each message.
443
444 The proof of NMAC assumes that the two keys are random and independent.
445 This isn't the case in HMAC, but a little handwaving about pseudorandomness
446 of the compression function makes the problem go away.
447\end{slide}
448
449\begin{exercise}
450 Suppose that $F\colon \{0, 1\}^k \times \{0, 1\}^{t+\ell} \to \{0, 451 1\}^t$ is a PRF. Let $x \in \{0, 1\}^*$ be a message. We define the
452 function $H_K(x)$ as follows:
453 \begin{itemize}
454 \item Pad $x$ to a multiple of $\ell$ bits using some injective
455 mapping. Break the image of $x$ under this mapping into $\ell$-bit
456 blocks $x_0, x_1, \ldots, x_{n-1}$.
457 \item For $0 \le i \le n$, define $H^{(i)}_K(x)$ by
458 $H^{(0)}_K(x) = I; \qquad 459 H^{(i+1)}_K(x) = F_K(H^{(i)}(x) \cat x_i)$%
460 where $I$ is some fixed $t$-bit string (e.g., $I = 0^t$).
461 \item Then set $H_K(x) = H^{(n)}_K(x)$.
462 \end{itemize}
463 We define two (deterministic) MACs $\mathcal{M}^i = (T^i, V^i)$ (for
464 $i \in \{0, 1\}$) using the $H_K$ construction. Verification in each
465 case consists of computing the tag and comparing to the one offered.
466 \begin{eqlines*}
53aa10b5 467 T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K); \\
41761fdc 468 V^i_K(x, \tau) = \begin{cases}
469 1 & if $\tau = T^i_K(x)$ \\
470 0 & otherwise
53aa10b5 471 \end{cases}.
41761fdc 472 \end{eqlines*}
473 Decide whether each of these constructions is secure. A full proof is
474 rather hard: an informal justification would be good.
476 $\mathcal{M}^0$ is secure; $\mathcal{M}^1$ isn't, under the sole
477 assumption that $F$ is a PRF.
478
479 To see that $\mathcal{M}^0$ is secure, it suffices to show that $T^0$
480 is a PRF. This is actually quite involved. Given an adversary $A$
481 attacking $T^1$ as a PRF, we construct an adversary $B$ attacking $F$,
482 which simply computes $H$ as required, using the oracle supplied. To
483 complete the proof, we need to show a bound on the
484 information-theoretic security of $H$ when instantiated using a random
485 function $F$. For the sake of simplicity, we allow the adversary $A$
487 messages. We count the number $q'$ of individual message blocks.
9907b634 488
489 As the game with $A$ progresses, we can construct a directed \emph{graph}
490 of the query results so far. We start with a node labelled $I$. When
491 processing an $H$-query, each time we compute $t' = F(t \cat x_i)$, we add
492 a node $t'$, and an edge $x_i$ from $t$ to $t'$. The `bad' event occurs
493 whenever we add an edge to a previously existing node. We must show,
494 firstly, that the adversary cannot distinguish $H$ from a random function
495 unless the bad event occurs; and, secondly, that the bad event doesn't
496 occur very often.
41761fdc 497
498 The latter is easier: our standard collision bound shows that the bad
9907b634 499 event occurs during the game with probability at most $q'(q' - 1)/2^{t+1}$.
500
41761fdc 501 The former is trickier. This needs a lot more work to make it really
502 rigorous, but we show the idea. Assume that the bad event has not
9907b634 503 occurred. Consider a query $x_0, x_1, \ldots, x_{n-1}$. If it's the same
504 as an earlier query, then $A$ learns nothing (because it could have
505 remembered the answer from last time). If it's a \emph{prefix} of some
506 earlier query, then the answer is the value of some internal node which
507 hasn't been revealed before; however, the value of that internal node was
508 chosen uniformly at random (we claim). Finally, if the query is not a
509 prefix of any previous query, then we add a new edge to our graph. If the
510 bad event doesn't occur, we must add a new node for the result, and the
511 value at that node will be uniformly random, because $F$ is a random
512 function being evaluated at a new point -- this is the only time we add new
513 nodes to the graph, justifying the claim made earlier.
41761fdc 514
515 At the end of all of this, we see that
516 $\InSec{prf}(T^0; t, q) \le 9907b634 517 \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2^{t+1}}$%
41761fdc 518 and hence
519 $\InSec{suf-cma}(\mathcal{M}^0; t, q) \le 9907b634 520 \InSec{prf}(F; t, q') + \frac{2 q'(q' - 1) + 1}{2^{t+1}}.$%
41761fdc 521
522 Now we turn our attention to $T^1$. It's clear that we can't simulate
523 $T^1$ very easily using an oracle for $F$, since we don't know $K$
524 (and indeed there might not be a key $K$). The intuitive reason why
525 $T^1$ is insecure is that $F$ might have leak useful information if
526 its input matches its key. This doesn't affect the strength of $F$ as
527 a PRF because you have to know the key before you can exploit this
528 leakage; but $T^1$ already knows the key, and this can be exploited to
529 break the MAC.
530
531 To show that this is insecure formally, let $F'$ be defined as
532 follows:
533 $F'_K(x) = \begin{cases} 534 K & if x = p \cat K \cat q where 535 |p| = t and |q| = \ell - k \\ 536 F_K(x) & otherwise 537 \end{cases}.$%
538 We choose a simple injective padding scheme: if $x$ is a message then
539 we form $x' = x \cat 1 \cat 0^n$, where $0 \le n < \ell$ and $|x'|$ is
540 a multiple of $\ell$. If $T^1$ is instantiated with this PRF then it
541 is insecure as a MAC: submitting a tagging query for the empty string
542 $\emptystring$ reveals the key $K$, which can be used to construct a
543 forgery.
544
545 To complete the proof, we must show that $F'$ is a PRF. Let $A$ be an
546 adversary attacking $F'$. We consider a series of games; for each
547 $\G{i}$, let $S_i$ be the event that $A$ returns $1$ in that game.
548 Game~$\G0$ is the standard attack game with $A$ given an oracle for a
549 random function; game~$\G1$ is the same, except that $A$ is given an
550 oracle for $F'_K$ for some $K \inr \{0, 1\}^k$. Then
551 $\Adv{prf}{F'}(A) = \Pr[S_1] - \Pr[S_0]$. Let game~$\G2$ be the same
552 as $\G1$, except that if $A$ makes any query of the form $p \cat K 553 \cat q$ with $|p| = t$ and $|q| = \ell - k$ then the game halts
554 immediately, and let $F_2$ be the event that this occurs. By
53aa10b5 555 Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}), then, $|{\Pr[S_2]} - 41761fdc 556 \Pr[S_1]| \le \Pr[F_2]$. Let game~$\G3$ be the same as $\G2$ except
557 that we give $A$ an oracle for $F_K$ rather than $F'_K$. Since $F$
558 and $F'$ differ only on queries of the form $p \cat K \cat q$, we have
559 $\Pr[S_3] = \Pr[S_2]$. But $\Pr[S_3] - \Pr[S_0] = \Adv{prf}{F}(A) \le 560 \InSec{prf}(F; t, q)$. Hence, $\Adv{prf}{F'}(A) \le \InSec{prf}{F}(A) 561 - \Pr[F_2]$.
562
563 Finally, we bound the probability of $F_2$. Fix an integer $n$.
564 Consider an adversary $B$ attacking $F$ which runs as follows. It
565 initially requests $F(0), F(1), \ldots, F(n - 1)$ from its oracle. It
566 then runs $A$, except that, for each oracle query $x$, it parses $x$
567 as $p \cat K' \cat q$ with $|p| = t$, $|K'| = k$ and $|q| = \ell - k$;
568 then, if $F_{K'}(0) = F(0) \land F_{K'}(1) = F(1) \land \cdots \land 569 F_{K'}(n - 1) = F(n - 1)$, $B$ immediately returns $1$, claiming that
53aa10b5 570 its oracle $F$ is the function $F_{K'}$; if this never occurs, $B$
41761fdc 571 returns $0$. Clearly, if $B$ is given an instance $F_K$ of $F$ then
572 it succeeds with probability $\Pr[F_2]$; however, if $F$ is a random
573 function then $B$ returns $1$ with probability at most $q 2^{-nk}$.
574 Hence, $\Adv{prf}{F}(B) \le \Pr[F_2] - q 2^{-nk}$. $B$ issues $q + n$
575 queries, and takes time $t + O(n q)$. Wrapping everything up, we get
576 $\InSec{prf}(F'; t, q) \le 577 2\cdot\InSec{prf}(F; t + O(q n), q + n) + \frac{q}{2^{nk}}.$%
53aa10b5 578 This completes the proof of generic insecurity for $\mathcal{M}^1$.
41761fdc 579\end{exercise}
580
581\xcalways\subsection{Universal hashing}\x
582
583\begin{slide}
584 \topic{almost-universal hash functions}
53aa10b5 585 \resetseq
41761fdc 587
588 Consider a family of hash functions $H\colon \keys H \times \dom H \to 589 \ran H$. We define
590 $\InSec{uh}(H) = 591 \max_{x \ne y} \Pr[K \getsr \keys H : H_K(x) = H_K(y)].$%
592 If $\InSec{uh}(H) \le \epsilon$ then we say that $H$ is
593 \emph{$\epsilon$-almost universal}. Note that the concept of
594 almost-universality is not quantified by running times.
595
596 If $H$ is $1/|{\ran H}|$-almost universal, then we say that $H$ is
597 \emph{universal}. Sometimes it's said that this is the best possible
598 insecurity: this isn't true.
599\end{slide}
600
601\begin{proof}[Counterexample]
602 Here's a function $H\colon \{0, 1, 2\} \times \{0, 1, 2, 3\} \to \{0, 1\}$
603 which is $\frac{1}{3}$-almost universal, though $|{\ran H}| = 2$:
604 \begin{quote} \item
605 \begin{tabular}[C]{c|cccc}
606 & 0 & 1 & 2 & 3 \\ \hlx{vhv}
607 0 & 0 & 1 & 0 & 1 \\
608 1 & 0 & 0 & 1 & 1 \\
609 2 & 0 & 1 & 1 & 0
610 \end{tabular}
611 \end{quote}
612\end{proof}
613
614\begin{slide}
615 \topic{dynamic view}
53aa10b5 616 \head{Universal hashing, \seq: a dynamic view}
41761fdc 617
618 Suppose that $H$ is $\epsilon$-almost universal. Consider this experiment:
619 \begin{program}
620 Experiment $\Expt{uh}{H}(A)$: \+ \\
621 $(x, y) \gets A$; \\
622 $K \getsr \keys H$; \\
623 \IF $x \ne y \land H_K(x) = H_K(y)$ \THEN \RETURN $1$; \\
624 \ELSE \RETURN $0$;
625 \end{program}
626 The adversary may make random decisions before outputting its selection
627 $x$, $y$. We show that $\Pr[\Expt{uh}{H}(A) = 1] \le \InSec{uh}(H) = 628 \epsilon$.
629
630 Let $\rho \in \{0, 1\}^*$ be $A$'s coin tosses: $A$ chooses $x$ and $y$ as
631 functions of $\rho$. For some \emph{fixed} $\rho$,
632 $\Pr[K \getsr \keys H : H_K(x(\rho)) = H_K(y(\rho))] \le 633 \InSec{uh}(H).$%
634\end{slide}
635
636\begin{slide}
53aa10b5 637 \head{Universal hashing, \seq: the dynamic view (cont.)}
41761fdc 638
639 Now we treat $\rho$ as a random variable, selected from some distribution
640 $P$ on the set $\{0, 1\}^*$. We see that
641 \begin{eqnarray*}[Ll]
642 \Pr[\rho \getsr P; K \getsr \keys H : H_K(x(\rho)) = H_K(y(\rho))] \\
643 &= \sum_{\rho \in \{0, 1\}^*}
644 P(\rho) \cdot \Pr[K \getsr \keys H : H_K(x(\rho)) = H_K(y(\rho))] \\
645 &\le \sum_{\rho \in \{0, 1\}^*} P(\rho) \cdot \InSec{uh}(H)
646 = \InSec{uh}(H).
647 \end{eqnarray*}
648 Thus, no adversary can succeed in producing a collision in an
649 $\epsilon$-almost universal hash with probability better than $\epsilon$.
650 But obviously the adversary can ignore its coin tosses and simply return
651 the best colliding pair. Hence the two notions are completely equivalent.
652\end{slide}
653
654\begin{slide}
655 \topic{composition}
53aa10b5 656 \head{Universal hashing, \seq: composition}
41761fdc 657
658 Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is
659 $\epsilon'$-almost universal, and $\dom G = \ran G'$. We define the
660 composition $G \compose G'$ to be the family $H\colon (\keys G \times 661 \keys G') \times \dom G' \to \ran G$ by $H_{k, k'}(m) = 662 G_k(G'_{k'}(m))$.
663
664 Then $H$ is $(\epsilon + \epsilon')$-almost universal. To see this, fix $x 665 \ne y$, and choose $K = (k, k') \inr \keys G \times \keys G'$. Let $x' = 666 G'_{k'}(x)$ and $y' = G'_{k'}(y)$. Following our previous result, we see:
667 \begin{eqnarray*}[rl]
668 \Pr[H_K(x) = H_K(y)]
669 &= \Pr[G_k(G'_{k'}(x)) = G_k(G'_{k'}(y))] \\
670 &= \Pr[G_k(x') = G_k(y')] \\
671 &= \Pr[G_k(x') = G_k(y') \mid x' \ne y'] \Pr[G'_{k'}(x) \ne G'_{k'}(y)]\\
672 &\le \epsilon + \epsilon'.
673 \end{eqnarray*}
674\end{slide}
675
676\begin{slide}
677 \topic{the collision game}
53aa10b5 678 \head{Universal hashing, \seq: the collision game}
41761fdc 679
680 Suppose that, instead of merely a pair $(x, y)$, our adversary was allowed
681 to return a \emph{set} $Y$ of $q$ elements, and measure the probability
682 that $H_K(x) = H_K(y)$ for some $x \ne y$ with $x, y \in Y$, and for $K 683 \inr \keys H$.
684
53aa10b5 685 Let $\InSec{uh-set}(H; q)$ be maximum probability achievable for sets $Y$
41761fdc 686 with $|Y| \le q$. Then
687 $\InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .$
688\end{slide}
689
690\begin{proof}
691 This is rather tedious. We use the dynamic view. Suppose $A$ returns $(x, 692 Y)$ with $|Y| = q$, and succeeds with probability $\epsilon$. Consider
693 \begin{program}
694 Adversary $A'$: \+ \\
695 $(x, Y) \gets A$; \\
696 $y \getsr Y$; \\
697 \RETURN $(x, Y \setminus \{y\})$;
698 \end{program}
699 The worst that can happen is that $A'$ accidentally removes the one
700 colliding element from $Y$. This occurs with probability $2/q$. So
701 $\Succ{uh-set}{H}(A') \ge \frac{q - 2}{q} \Succ{uh-set}{H}(A).$
53aa10b5 702 Rearranging and maximizing gives
41761fdc 703 $\InSec{uh-set}(H; q) \le 704 \frac{q}{q - 2} \cdot \InSec{uh-set}(H; q - 1).$
705 Note that $\InSec{uh-set}(H; 2) = \InSec{uh}(H)$ is our initial notion. A
706 simple inductive argument completes the proof.
707\end{proof}
708
709\begin{slide}
710 \topic{a MAC}
53aa10b5 711 \head{Universal hashing, \seq: a MAC}
41761fdc 712
53aa10b5 713 Suppose that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an
714 almost universal hash function, and $F\colon \{0, 1\}^{k'} \times \{0, 41761fdc 715 1\}^l \to \{0, 1\}^L$ is a PRF\@. Define a MAC $\Xid{\mathcal{M}}{UH}^{H, 716 F} = (\Xid{T}{UH}^{H, F}, \Xid{V}{UH}^{H, F})$ where:
717 \begin{eqnarray*}[rl]
718 \Xid{T}{UH}^{H, F}_{K, K'}(m) &= F_{K'}(H_K(m)) \\
719 \Xid{V}{UH}^{H, F}_{K, K'}(m, \tau) &= \begin{cases}
720 1 & if $\tau = F_{K'}(H_K(m))$ \\
721 0 & otherwise
722 \end{cases}.
723 \end{eqnarray*}
724 We have
725 \begin{eqnarray*}[Ll]
726 \InSec{suf-cma}(\Xid{\mathcal{M}}{UH}^{H, F}; t, q_T, q_V) \\
727 & \le
728 (q_V + 1) \biggl(\InSec{prf}(F; t, q_T + 1) + \frac{1}{2^L} +
729 \frac{q_T(q_T - 1)}{2} \cdot \InSec{uh}(H)\biggr).
730 \end{eqnarray*}
731\end{slide}
732
733\begin{proof}
734 We shall prove the result for $q_V = 0$ and $q_T = q$, and appeal to the
735 earlier result on verification oracles.
736
737 Suppose $A$ attacks the scheme $\Xid{\mathcal{M}}{UH}^{H, F}$ in time $t$,
738 issuing $q$ tagging queries. Consider a distinguisher $D$, constructed
739 from a forger $A$:
740 \begin{program}
741 Distinguisher $D^{F(\cdot)}$: \+ \\
742 $K \getsr \{0, 1\}^k$; \\
743 $\Xid{T}{list} \gets \emptyset$; \\
744 $(m, \tau) \gets A^{\id{tag}(K, \cdot)}$; \\
745 \IF $m \notin \Xid{T}{list} \land \tau = F(H_K(m))$
746 \THEN \RETURN $1$; \\
747 \ELSE \RETURN $0$; \- \$\smallskipamount] 748 Oracle \id{tag}(K, m): \+ \\ 749 \Xid{T}{list} \gets \Xid{T}{list} \cup \{m\}; \\ 750 \RETURN F(H_K(m)); \- \\[\smallskipamount] 751 \end{program} 752 Note that A isn't provided with a verification oracle: that's because we 753 didn't allow it any verification queries. 754 755 We can see immediately that 756 \[ \Pr[K \getsr \{0, 1\}^{k'} : D^{F_K(\cdot)} = 1] = 757 \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A).$%
758
759 We must now find an upper bound for $\Pr[F \getsr \Func{l}{L} : 760 D^{F(\cdot)}]$. Suppose that the adversary returns the pair $(m^*, 761 \tau^*)$, and that its tagging oracle queries and their answers are $(m_i, 762 \tau_i)$ for $0 \le i < q$. Consider the event $C$ that $H_K(m) = 763 H_K(m')$ for some $m \ne m'$, with $m, m' \in \{m^*\} \cup \{\,m_i \mid 0 764 \le i < q\,\}$.
765
766 If $C$ doesn't occur, then $F$ has not been queried before at $H_K(m)$, but
767 there's a $2^{-L}$ probability that the adversary guesses right anyway. If
768 $C$ does occur, then we just assume that the adversary wins, even though it
769 might not have guessed the right tag.
770
771 By our result on the collision game, $\Pr[C] \le q \cdot \InSec{uh}(H)$.
772 Then
773 $\Succ{prf}{F}(D) \ge 774 \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A) - 775 \frac{1}{2^L} - \frac{q(q - 1)}{2} \cdot \InSec{uh}(H).$%
776 The result follows.
777\end{proof}
778
779\begin{slide}
780 \topic{almost XOR-universality}
53aa10b5 781 \resetseq
41761fdc 783
784 Consider a family of hash functions $H\colon \keys H \times \dom H \to 785 \{0, 1\}^L$. Define
786 $\InSec{xuh}(H) = 787 \max_{x \ne y, \delta} 788 \Pr[K \getsr \keys H : H_K(x) \xor H_K(y) = \delta].$%
789 If $\InSec{xuh}(H) < \epsilon$ then we say that $H$ is
790 \emph{$\epsilon$-almost XOR-universal}, or \emph{AXU}. Setting $\delta = 791 0$ shows that
792 \begin{eqnarray*}[rl]
793 \InSec{xuh}(H)
794 & \ge \max_{x \ne y} \Pr[K \getsr \keys H : H_K(x) \xor H_K(y) = 0] \\
795 & = \InSec{uh}(H).
796 \end{eqnarray*}
797
798 We can take a dynamic view of almost XOR-universality using the same
799 technique as for almost universal functions.
800
801 If $H$ is $2^{-L}$-almost XOR universal then we say that $H$ is
53aa10b5 802 \emph{XOR-universal}. This is the best achievable.
41761fdc 803\end{slide}
804
805\begin{proof}
806 Fix some pair $x \ne y$. Choose $\delta \inr \{0, 1\}^L$. Then for any
807 \emph{fixed} $K \in \keys H$, $H_K(x)$ and $H_K(y)$ are fixed, so $H_K(x) 808 \xor H_K(y)$ is fixed, and $\Pr[H_K(x) \xor H_K(y) = \delta] = 2^{-L}$.
809 Using the same trick as for proving the dynamic view:
810 \begin{eqnarray*}[Ll]
811 \Pr[\delta \getsr \{0, 1\}^L; K \getsr \keys H :
812 H_K(x) \xor H_K(y) = \delta] \\
813 & = \sum_{K \in \keys H} \frac{1}{|{\keys H}|}
814 \Pr[\delta \getsr \{0, 1\}^L; K \getsr \keys H :
815 H_K(x) \xor H_K(y) = \delta] \\
816 & = \sum_{K \in \keys H} \frac{1}{|{\keys H}|} 2^{-L} = 2^{-L}.
817 \end{eqnarray*}
818 Since $H$ is arbitrary, this proves the lower bound on the almost
819 XOR-universality.
820\end{proof}
821
822\begin{slide}
823 \topic{composition}
53aa10b5 824 \head{Almost XOR-universality, \seq: composition}
41761fdc 825
826 We extend our result about composition of almost-universal functions.
827 Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is
828 $\epsilon'$-almost universal (it doesn't have to be almost XOR-universal),
829 and $\dom G = \ran G'$.
830
831 Then the composition $H = G \compose G'$ is $(\epsilon + \epsilon')$-almost
832 XOR-universal. The proof is simple, and very similar to the
833 almost-universal case.
834\end{slide}
835
836\begin{slide}
837 \topic{a better MAC}
53aa10b5 838 \head{Almost XOR-universality, \seq: a better MAC}
41761fdc 839
840 The security result for the UH-based MAC contains a factor $q_T$, which
841 it'd be nice to remove. Our new scheme uses an AXU hash $H\colon \keys H 842 \times \{0, 1\}^* \to \{0, 1\}^l$ and a PRF $F\colon \keys F \times \{0, 843 1\}^l \to \{0, 1\}^L$.
844
845 We first present a stateful version $\Xid{\mathcal{M}}{XUH}^{H, F}$.
846 Choose $(K, K') \inr \keys H \times \keys F$, and initialize a counter $i 847 \gets 0$. The tagging and verification algorithms are then:
848 \begin{program}
849 Algorithm $\Xid{T}{XUH}^{H, F}_{K, K'}(m)$: \+ \\
850 $\tau \gets (i, H_K(m) \xor F_{K'}(i))$; \\
851 $i \gets i + 1$; \\
852 \RETURN $\tau$;
853 \next
854 Algorithm $\Xid{V}{XUH}^{H, F}_{K, K'}(m, \tau)$: \+ \\
855 $(s, \sigma) \gets \tau$; \\
856 \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\
857 \ELSE \RETURN $0$;
858 \end{program}
859 Note that verification is stateless.
860\end{slide}
861
862\begin{slide}
53aa10b5 863 \head{Almost XOR-universality, \seq: security of AXU-based MACs}
41761fdc 864
865 For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have
866 \begin{eqnarray*}[Ll]
867 \InSec{suf-cma}(\Xid{\mathcal{M}}{XUH}^{H, F}; t, q_T, q_V) \\
868 & \le (q_V + 1)(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L}).
869 \end{eqnarray*}
870\end{slide}
871
872\begin{slide}
53aa10b5 873 \head{Almost XOR-universality, \seq: randomized AXU-based MAC}
41761fdc 874
875 We can avoid statefulness by using randomization. This new scheme is
876 $\Xid{\mathcal{M}}{XUH$\$$}^{H, F} = (\Xid{T}{XUH\$$}^{H, F},
877 \Xid{V}{XUH$\$$}^{H, F}): 878 \begin{program} 879 Algorithm \Xid{T}{XUH\$$}^{H, F}_{K, K'}(m)$: \+ \\
880 $s \getsr \{0, 1\}^l$; \\
881 $\tau \gets (s, H_K(m) \xor F_{K'}(s))$; \\
882 \RETURN $\tau$;
883 \next
884 Algorithm $\Xid{V}{XUH$\$$}^{H, F}_{K, K'}(m, \tau): \+ \\ 885 (s, \sigma) \gets \tau; \\ 886 \IF \sigma = H_K(m) \xor F_{K'}(i) \THEN \RETURN 1; \\ 887 \ELSE \RETURN 0; 888 \end{program} 889 \begin{eqnarray*}[Ll] 890 \InSec{suf-cma}(\Xid{\mathcal{M}}{XUH\$$}^{H, F}; t, q_T, q_V) \\
891 & \le (q_V + 1)
892 \Bigl(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L} +
893 \frac{q_T(q_T - 1)}{2^{l+1}}\Bigr).
894 \end{eqnarray*}
895\end{slide}
896
897\begin{proof}
898 We prove the result with $q_V = 0$ and $q_T = q$, and appeal to the result
899 on verification oracles. Let $m_i$ be the message specified in the $i$-th
900 tagging query ($0 \le i < q$), and let $(s_i, \sigma_i) = (s_i, H_K(m) \xor 901 F_{K'}(s_i))$ be the tag returned. We call the $s_i$ the \emph{nonce}.
902
903 We prove the result for the stateless scheme. The bound $q \le 2^l$
904 ensures that the nonces are all distinct (we have $s_i = i$). The security
905 bound for the randomized version merely has as an extra term upper bound
906 for the probability of a nonce collision.
907
908 Let $A$ be an adversary attacking the MAC in time $t$, and using $q$
909 tagging queries. Then we present the following pair of adversaries:
910 \begin{program}
911 Distinguisher $D^{F(\cdot)}$: \+ \\
912 $i \gets 0$; \\
913 $\Xid{T}{list} \gets \emptyset$; \\
914 $K \getsr \keys H$; \\
915 $(m, \tau) \gets A^{\id{tag}}$; \\
916 $(s, \sigma) \gets \tau$; \\
917 \IF $(m, \tau) \notin \Xid{T}{list} \land 918 \sigma = H_K(m) \xor F(s)$
919 \THEN \RETURN $1$; \\
920 \ELSE \RETURN $0$; \- \$\smallskipamount] 921 Oracle \id{tag}(m): \+ \\ 922 \tau \gets (i, H_K(m) \xor F(i)); \\ 923 \Xid{T}{list} \gets \Xid{T}{list} \cup \{(m, \tau)\}; \\ 924 i \gets i + 1; 925 \RETURN \tau; 926 \next 927 Collision-finder C: \+ \\ 928 i \gets 0; \\ 929 (m, \tau) \gets A^{\id{tag}}; \\ 930 (s, \sigma) \gets \tau; \\ 931 \IF s \ge i \lor m = m_s \THEN \ABORT; \\ 932 \RETURN (m, m_s, \sigma \xor \sigma_s); \- \\[\smallskipamount] 933 Oracle \id{tag}(m): \+ \\ 934 m_i \gets m; \\ 935 \sigma_i \getsr \{0, 1\}^L; \\ 936 \tau \gets (i, \sigma_i); \\ 937 i \gets i + 1; \\ 938 \RETURN \tau; 939 \end{program} 940 941 We need to find a lower bound on the advantage of D. If F is chosen 942 from the PRF then D returns 1 precisely when A finds a valid 943 forgery. We now examine the setting in which F is a random function. 944 945 Let S be the event that A succeeds in returning a valid forgery when 946 F is random, and let N be the event that the nonce s returned by A 947 is not equal to any nonce s_i returned by the tagging oracle. Suppose 948 N occurs: then the random function F has never been queried before at 949 F, and \Pr[F(s) = \sigma \xor H_K(m)] is precisely 2^{-L}. 950 951 So suppose instead that N doesn't occur. Then, since the s_i are 952 distinct, there is a unique i such that s = s_i. For A to win, we 953 must have m \ne m_i (for if m = m_i then the only valid tag is 954 H_K(m_i) \xor F(s_i) = \sigma_i, which was already returned by the 955 tagging oracle). If A's forgery is successful then 956 \[ \sigma = H_K(m) \xor F(s) 957 \qquad \text{and} \qquad 958 \sigma_i = H_K(m_i) \xor F(s_i)$%
959 but $s = s_i$, whence
960 $H_K(m_i) \xor H_K(m) = \sigma \xor \sigma_i.$
961 Since the $s_i$ are distinct and $F$ is a random function, the $\sigma_i$
962 are independent uniformly-distributed random strings from $\{0, 1\}^L$.
963 Hence the collision-finder $C$ succeeds with probability $\Pr[S \land 964 \lnot N] \le \InSec{xuh}(H)$.
965
966 Wrapping up, we have
967 \begin{eqnarray*}[rl]
969 & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
970 (\Pr[S \mid N] \Pr[N] + \Pr[S \mid \lnot N] \Pr[\lnot N]) \\
971 & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) -
972 (2^{-L} + \InSec{xuh}(H)).
973 \end{eqnarray*}
974 Maximizing and rearranging yields the required result.
975\end{proof}
976
977\begin{remark*}
978 Note that our bound has a $2^{-L}$ term in it that's missing from
979 \cite{Goldwasser:1999:LNC}. We believe that their proof is wrong in its
980 handling of the XOR-collision probability.
981\end{remark*}
982
983\endinput
984
985%%% Local Variables:
986%%% mode: latex
987%%% TeX-master: "ips"
988%%% End: