41761fdc |
1 | \xcalways\section{Message authentication codes}\x |
2 | |
3 | \xcalways\subsection{Definitions and security notions}\x |
4 | |
5 | \begin{slide} |
6 | \head{Definition of a MAC} |
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? |
112 | \answer% |
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} |
121 | \head{PRFs are MACs, 1} |
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} |
184 | \answer% |
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. |
218 | \answer% |
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} |
229 | \head{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. |
452 | \answer% |
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$ |
463 | to query on \emph{padded} messages, rather than the raw unpadded |
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} |
561 | \head{Universal hashing, 1: definition} |
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} |
631 | \head{Universal hashing, 4: 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} |
756 | \head{Almost XOR-universality, 1: definition} |
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} |
798 | \head{Almost XOR-universality, 2: 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] |
942 | \Adv{prf}{F}(D) |
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: |