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