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