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