Commit | Line | Data |
---|---|---|

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} | |

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 |

106 | \head{PRFs are MACs, \seq} | |

41761fdc | 107 | |

108 | If $F_K\colon \{0, 1\}^* \to \{0, 1\}^L$ is a $(t, q, \epsilon)$-secure | |

109 | PRF, then it's also a $(t', q_T, q_V, \epsilon')$-secure MAC, with $q = q_T | |

e09a1839 | 110 | + q_V + 1$, $t = t' + O(q)$, and $\epsilon' \le \epsilon + (q_V + 1) |

41761fdc | 111 | 2^{-L}$. The constant hidden by the $O(\cdot)$ is small and depends on the |

112 | model of computation. | |

113 | ||

114 | Suppose $A$ can break $F$ used as a MAC in time $t$ and with $q_T$ and | |

115 | $q_V$ queries to its tagging and verification oracles respectively. | |

116 | ||

117 | If we can construct an adversary which distinguishes $F_K$ from a random | |

118 | function using $A$ as an essential component, then we can prove the | |

119 | result. | |

120 | \end{slide} | |

121 | ||

122 | \begin{slide} | |

53aa10b5 | 123 | \head{PRFs are MACs, \seq: the distinguisher} |

41761fdc | 124 | |

125 | \begin{program} | |

126 | Distinguisher $D^{F(\cdot)}$: \+ \\ | |

127 | $\Xid{T}{list} \gets \emptyset$; \\ | |

128 | $(m, \tau) \gets A^{T_F(\cdot), V_F(\cdot, \cdot)}$; \\ | |

129 | \IF $m \notin \Xid{T}{list} \land \tau = F(m)$ | |

130 | \THEN \RETURN $1$; \\ | |

131 | \ELSE \RETURN $0$; \- \\[\smallskipamount] | |

132 | Oracle $T_F(m)$: \+ \\ | |

133 | $\Xid{T}{list} \gets \Xid{T}{list} \cup \{m\}$; \\ | |

134 | \RETURN $F(m)$; \- \\[\smallskipamount] | |

135 | Oracle $V_F(m, \tau)$: \+ \\ | |

136 | \IF $\tau = F(m)$ \THEN \RETURN $1$; \\ | |

137 | \ELSE \RETURN $0$; | |

138 | \end{program} | |

139 | \end{slide} | |

140 | ||

141 | \begin{slide} | |

53aa10b5 | 142 | \head{PRFs are MACs, \seq: wrapping up} |

41761fdc | 143 | |

144 | The distinguisher simulates the tagging and verification oracles for the | |

145 | MAC forger, using its supplied oracle. If the forger succeeds, then the | |

146 | distinguisher returns 1; otherwise it returns zero. | |

147 | ||

148 | The probability that the distinguisher returns 1 given an instance $F_K$ of | |

149 | the PRF is precisely $\Succ{suf-cma}{F}(A)$. | |

150 | ||

151 | The probability that it returns 0 given a random function depends on what | |

152 | $A$ does when it's given a random function. But we know that the | |

153 | probability of it successfully guessing the MAC for a message for which it | |

154 | didn't query $T$ can be at most $(q_V + 1) 2^{-L}$. So | |

e09a1839 | 155 | \[ \Adv{prf}{F}(D) \ge \Succ{suf-cma}{F}(A) - (q_V + 1) 2^{-L}. \] |

41761fdc | 156 | Let $q = q_T + q_V + 1$; then counting, rearranging, maximizing yields |

157 | \[ \InSec{suf-cma}(F; t, q_T, q_V) \le | |

158 | \InSec{prf}(F; t + O(q), q) + (q_V + 1)2^{-L}. \]% | |

159 | \end{slide} | |

160 | ||

53aa10b5 | 161 | \begin{slide} |

162 | \head{PRFs are MACs, \seq: MACs aren't PRFs} | |

163 | ||

164 | The converse of our result is not true. Suppose $\mathcal{M} = (T, V)$ is | |

165 | a deterministic MAC. Choose some integer $n$. Then define $\mathcal{M}' = | |

166 | (T', V')$, as follows: | |

167 | \[ T'_K(x) = 0^n \cat T_K(x); \qquad | |

168 | V'_K(x, \tau) = \begin{cases} | |

169 | 1 & if $T'_K(x) = \tau$ \\ | |

170 | 0 & otherwise | |

171 | \end{cases}. | |

172 | \] | |

173 | $T'$ is obviously not a PRF: an adversary checking for the string of $n$ | |

174 | zero bits on the output will succeed with advantage $1 - 2^{-qn}$. | |

175 | ||

176 | However, $\mathcal{M}'$ is a secure MAC. Suppose $A'$ attacks | |

177 | $\mathcal{M}'$. | |

178 | \begin{program} | |

179 | Adversary $A^{T(\cdot), V(\cdot)}$: \+ \\ | |

180 | $(m, \tau') \gets A'^{\id{tag}(\cdot), \id{verify}(\cdot)}$; \\ | |

181 | \PARSE $\tau'$ \AS $n\colon z, \tau$; \\ | |

182 | \RETURN $(m, \tau)$; | |

183 | \next | |

184 | Oracle $\id{tag}(m)$: \+ \\ | |

185 | \RETURN $0^n \cat T(m)$; \- \\[\smallskipamount] | |

186 | Oracle $\id{verify}(m, \tau')$: \+ \\ | |

187 | \PARSE $\tau'$ \AS $n\colon z, \tau$; \\ | |

188 | \IF $z \ne 0^n$ \THEN \RETURN $0$; \\ | |

189 | \ELSE \RETURN $V(m, \tau)$; | |

190 | \end{program} | |

191 | \end{slide} | |

192 | ||

41761fdc | 193 | \begin{exercise} |

194 | \begin{parenum} | |

195 | \item Suppose that $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^L$ is | |

196 | a $(t, q, \epsilon)$-secure PRF. Let $T^{(\ell)}_K(x)$ be the leftmost | |

53aa10b5 | 197 | $\ell$~bits of $F_K(x)$ for $\ell \le L$. Demonstrate the security of |

198 | $T^{(\ell)}(\cdot)$ as a MAC. | |

41761fdc | 199 | \item Discuss the merits of truncating MAC tags in practical situations. |

200 | \end{parenum} | |

201 | \answer% | |

202 | \begin{parenum} | |

203 | \item The follows exactly the same pattern as the `PRFs are MACs' proof in | |

204 | the slides: $T^{(\ell)}$ is a $(t, q_T, q_V, \epsilon + (q_V + | |

205 | 1)2^{-\ell})$-secure MAC, where $q_T + q_V = q$. | |

206 | \item Obviously, truncating tags saves bandwidth. There is a trade-off | |

207 | between tag size and security, as the $2^{-\ell}$ term shows. Note that | |

208 | this term represents the probability of the adversary guessing the | |

209 | correct tag when it's actually attacking a random function, and | |

210 | therefore, when this occurs, the adversary has one `by accident'. | |

211 | Including sequence numbers in packets ensures that replay of accidental | |

212 | forgery (or honest messages) will be detected. Hence, for some | |

213 | applications, setting $\ell = 32$ or even lower is of no particular harm. | |

214 | Perhaps more significantly, if the PRF isn't actually as good as it ought | |

215 | to be, and (say) leaks key material very slowly, then truncating its | |

216 | output can actually improve security. | |

217 | \end{parenum} | |

218 | \end{exercise} | |

219 | ||

220 | \begin{exercise} | |

221 | A traditional MAC construction is the \emph{CBC-MAC}: it works like this. | |

222 | Suppose $F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^l$ is a PRF. | |

223 | Split a message~$x$ into $l$-bit blocks $x_0, x_1, \ldots, x_{n-1}$ | |

224 | (applying some sort of padding if you need to). Then we define the CBC-MAC | |

225 | as $F^{(n)}_K(x)$, where | |

226 | \[ F^{(1)}_K(x) = F_K(x); | |

227 | \qquad F^{(i+i)}(x) = F_K(x_i \xor F^{(i)}_K(x)). \]% | |

228 | In \cite{Bellare:1994:SCB}, Mihir Bellare, Joe Kilian and Phil Rogaway | |

229 | introduced the world to the concrete-security approach and, almost | |

230 | incidentally, proved that the CBC-MAC is a PRF (and therefore a MAC) for | |

231 | any \emph{fixed sized} input. | |

232 | ||

233 | Show that the CBC-MAC is easily broken if you're allowed to choose messages | |

234 | of different lengths. | |

235 | \answer% | |

236 | Request tags $\tau$ for the message $x = x_0, x_1, \ldots, x_{n-1}$ and | |

237 | $\tau'$ for $x' = x'_0 \xor \tau, x'_1, \ldots, x'_{n'-1}$. Let $y = x_0, | |

238 | x_1, \ldots, x_{n-1}, x'_0 , x'_1, \ldots, x'_{n'-1}$. Note that | |

239 | $F^{(n)}_K(y) = \tau$, and $F^{(n+1)}_K(y) = F_K(x'_0 \xor F^{(n)}_K(x)) = | |

240 | F^{(1)}_K(x')$. Hence, $F^{(n+n')}_K(y) = \tau'$, and we have a correct | |

241 | forgery. | |

242 | \end{exercise} | |

243 | ||

244 | \begin{slide} | |

245 | \topic{verification oracles} | |

246 | \head{Verification oracles} | |

247 | ||

248 | We can leave verification oracles out of our analysis. This simplifies | |

249 | analysis, but produces slightly less satisfactory quantitative results. | |

250 | ||

251 | Suppose that $\mathcal{M} = (T, V)$ is a $(t, q_T, 0, \epsilon)$-secure | |

252 | MAC. Then, for any $q_V$, | |

253 | \[ \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V) \le | |

254 | (q_V + 1)\InSec{suf-cma}(\mathcal{M}; t, q_T, 0). \]% | |

255 | This bound is \emph{tight}: it's not possible for a general result like | |

256 | this to do better. | |

257 | \end{slide} | |

258 | ||

259 | \begin{proof} | |

260 | Consider an adversary $A$ which uses $q_V$ verification queries. We assume | |

261 | the following properties of $A$'s behaviour: | |

262 | \begin{itemize} | |

263 | \item No verification query contains a message and a tag for that message | |

264 | received from the tagging oracle. | |

265 | \item If a verification query succeeds, the message is not given in a query | |

266 | to the tagging oracle. | |

267 | \item Once a verification query succeeds, all subsequent verification | |

268 | queries also succeed and the adversary returns a correct forgery (e.g., | |

53aa10b5 | 269 | by simply repeating the successful query). |

41761fdc | 270 | \end{itemize} |

271 | It's clear that any adversary can be transformed into one which has these | |

272 | properties and succeeds with probability at least as high. | |

273 | ||

274 | Let $V$ be the event that at least one verification query succeeds, and let | |

275 | $S$ be the event that $A$ succeeds. Then | |

276 | \begin{eqnarray*}[rl] | |

277 | \Succ{suf-cma}{\mathcal{M}}(A) | |

278 | &= \Pr[S \mid V] \Pr[V] + \Pr[S \mid \lnot V] \Pr[\lnot V] \\ | |

279 | &= \Pr[V] + \Pr[S \mid \lnot V] \Pr[\lnot V]. | |

280 | \end{eqnarray*} | |

281 | Now consider these two adversaries: | |

282 | \begin{program} | |

283 | Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$: \+ \\ | |

284 | $i \gets 0$; \\ | |

285 | $(m, \tau) \gets A^{T(\cdot), \Xid{V}{sim}(\cdot, \cdot)}$; \\ | |

286 | \RETURN $(m^*, \tau^*)$; \- \\[\smallskipamount] | |

287 | Oracle $\Xid{V}{sim}(m, \tau)$: \+ \\ | |

288 | $i \gets i + 1$; \\ | |

289 | \IF $i < q_V$ \THEN \RETURN $V(m, \tau)$; \\ | |

290 | $(m^*, \tau^*) \gets (m, \tau)$; \\ | |

291 | \RETURN $1$; | |

292 | \next | |

293 | Adversary $Z^{T(\cdot), V(\cdot, \cdot)}$: \+ \\ | |

294 | \\ | |

295 | $(m, \tau) \gets A^{T(\cdot), \Xid{V}{zero}(\cdot, \cdot)}$; \\ | |

296 | \RETURN $(m, \tau)$; \- \\[\smallskipamount] | |

297 | Oracle $\Xid{V}{zero}(m, \tau)$: \+ \\ | |

298 | \RETURN $0$; | |

299 | \end{program} | |

300 | The adversary $A'$ uses $q_V - 1$ verification queries. It ignores the | |

301 | output of $A$, returning instead $A$'s $q_V$-th verification query. Thus, | |

302 | by our assumptions on the behaviour of $A$, we have that $A'$ succeeds | |

303 | precisely whenever one of $A$'s verification queries succeeds. Thus: | |

304 | \[ \Pr[V] = \Succ{suf-cma}{\mathcal{M}}(A') | |

305 | \le \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V - 1). \]% | |

306 | Similarly, the adversary $Z$ succeeds with precisely the same probability | |

307 | as $A$, given that all of its verification queries failed; i.e., | |

308 | \[ \Pr[S \mid \lnot V] \Pr[\lnot V] = \Succ{suf-cma}{\mathcal{M}}(Z) | |

309 | \le \InSec{suf-cma}(\mathcal{M}; t, q_T, 0). \]% | |

310 | Because $A$ was chosen arbitrarily, we can maximize: | |

311 | \begin{eqnarray*}[rl] | |

312 | \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V) | |

313 | & \le \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V - 1) + | |

314 | \InSec{suf-cma}(\mathcal{M}; t, q_T, 0) \\ | |

315 | & \le (q_V + 1)\InSec{suf-cma}(\mathcal{M}; t, q_T, 0) | |

316 | \end{eqnarray*} | |

317 | as required. | |

318 | ||

319 | To show that the bound is tight, consider a random function $F$ used as a | |

320 | MAC, with $L$-bit output. Then we claim that $\InSec{suf-cma}(F; t, q_T, | |

321 | q_V) = (q_V + 1)/2^L$. To save typing, let $e_q = \InSec{suf-cma}(F; t, | |

322 | q_T, q)$. We prove the claim by induction on $q$. Firstly, note that if | |

323 | $q = 0$ then necessarily $e_q = 1/2^L$. Now suppose that $e_{q-1} = | |

324 | q/2^L$. We're now allowed an extra query, so rather than returning the | |

325 | result, we feed it to the verification oracle. If it answers `yes' then we | |

326 | return it; otherwise we guess randomly from the remaining $2^L - q$ | |

327 | possibilities. Now | |

328 | \begin{eqnarray*}[rl] | |

53aa10b5 | 329 | e_q &= e_{q-1} + \frac{1 - e_{q-1}}{2^L - q} \\ |

41761fdc | 330 | &= \frac{q}{2^L} + \frac{2^L - q}{2^L} \cdot \frac{1}{2^L - q} \\ |

331 | &= \frac{q + 1}{2^L} | |

332 | \end{eqnarray*} | |

333 | as claimed. | |

334 | \end{proof} | |

335 | ||

336 | \xcalways\subsection{The HMAC construction}\x | |

337 | ||

338 | \begin{slide} | |

53aa10b5 | 339 | \resetseq |

340 | \head{The HMAC construction \cite{Bellare:1996:KHF}, \seq: motivation} | |

341 | ||

41761fdc | 342 | It ought to be possible to construct a decent MAC using a hash function. |

343 | Many attempts have failed, however. For example, these constructions are | |

53aa10b5 | 344 | weak if used with standard one-pass Merkle-Damg\aa{}rd iterated hashes. |

41761fdc | 345 | \begin{itemize} |

53aa10b5 | 346 | \item Secret prefix: $T_K(m) = H(K \cat m)$. Given $H(K \cat m)$, it's |

347 | easy to compute $H(K \cat m \cat p \cat m')$ for a padding string $p$ and | |

348 | arbitrary suffix $m'$. | |

349 | \item Secret suffix: $T_K(m) = H(m \cat K)$. Finding a collision $H(m) = | |

350 | H(m')$ yields $H(m \cat K) = H(m' \cat K)$. We saw earlier that | |

351 | adversaries which know collisions \emph{exist} even if we don't know how | |

352 | to describe them. | |

41761fdc | 353 | \end{itemize} |

354 | ||

355 | It would be nice to have a construction whose security was provably related | |

356 | to some plausible property of the underlying hash function. | |

357 | \end{slide} | |

358 | ||

359 | \begin{slide} | |

53aa10b5 | 360 | \head{The HMAC construction, \seq: definition of NMAC} |

41761fdc | 361 | |

362 | Let $H\colon \{0, 1\}^* \to \{0, 1\}^k$ be an iterated hash, constructed | |

363 | from the compression function $F\colon \{0, 1\}^k \times \{0, 1\}^L \to | |

364 | \{0, 1\}^k$. We define a keyed version of $H$. Let $K \in \{0, 1\}^k$; | |

365 | then we compute $H_K(x)$ as follows: | |

366 | \begin{enumerate} | |

367 | \item Pad and split $x$ into the $L$-bit blocks $x_0$, $x_1$, \ldots, | |

368 | $x_{n-1}$ as before. | |

369 | \item Set $I_0 = K$. Let $I_{i+1} = F(I_i \cat x_i)$ for $0 \le i < n$. | |

370 | \item The result $H_K(x) = I_n$. | |

371 | \end{enumerate} | |

372 | The NMAC (nested-MAC) construction requires two independent $k$-bit keys | |

373 | $K_0$ and $K_1$. The construction itself is simply: | |

374 | \[ \Xid{T}{NMAC}^H_{K_0, K_1}(x) = H_{K_0}(H_{K_1}(x)). \] | |

375 | NMAC is deterministic, so verification consists of computing the tag and | |

376 | comparing. | |

377 | \end{slide} | |

378 | ||

379 | \begin{slide} | |

53aa10b5 | 380 | \head{The HMAC construction, \seq: security of NMAC} |

41761fdc | 381 | |

382 | Consider a function $F\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^k$. | |

383 | We say that $F$ is \emph{$(t, q, \epsilon)$-weakly collision resistant} if, | |

384 | for any adversary $A$ constrained to run in time $t$ and permitted $q$ | |

385 | oracle queries, | |

386 | \[ \Pr[K \getsr \{0, 1\}^k; | |

387 | (x, y) \gets A^{F_K(\cdot)}] \le \epsilon : | |

388 | x \ne y \land F_K(x) = F_K(y) \]% | |

389 | ||

390 | If $H_K$ is a $(t, q_T, q_V, \epsilon)$-secure MAC on $k$-bit messages, and | |

391 | moreover $(t, q_T + q_V, \epsilon')$-weakly collision resistant, then | |

392 | $\Xid{T}{NMAC}^H$ is a $(t, q_T, q_V, \epsilon + \epsilon')$-secure MAC. | |

393 | \end{slide} | |

394 | ||

395 | \begin{slide} | |

53aa10b5 | 396 | \head{The HMAC construction, \seq: NMAC security proof} |

41761fdc | 397 | |

398 | Let $A$ be an adversary which forges a $\Xid{T}{NMAC}^H$ tag in time $t$, | |

399 | using $q_T$ tagging queries and $q_V$ verification queries with probability | |

400 | $\epsilon$. We construct an adversary $A'$ which forces a $H$ tag for a | |

401 | $k$-bit in essentially the same time. | |

402 | \begin{program} | |

403 | Adversary $A'^{T(\cdot), V(\cdot, \cdot)}$ \+ \\ | |

404 | $K \getsr \{0, 1\}^k$; \\ | |

405 | $(m, \tau) \gets A^{T(H_K(\cdot)), V(H_K(\cdot), \cdot)}$; \\ | |

406 | \RETURN $(H_K(m), \tau)$; | |

407 | \end{program} | |

408 | $A'$ might fail even though $A$ succeeded only if the message it returns, | |

409 | $H_K(m)$, collides with one of its tagging queries. But since $H_K$ is | |

410 | $(t, q_T + q_V, \epsilon')$-weakly collision resistant, this happens with | |

411 | at most probability $\epsilon'$. Hence, $A'$ succeeds with probability at | |

412 | least $\epsilon - \epsilon'$. Rearrangement yields the required result. | |

413 | \end{slide} | |

414 | ||

415 | \begin{slide} | |

53aa10b5 | 416 | \head{The HMAC construction, \seq: from NMAC to HMAC} |

41761fdc | 417 | |

418 | Implementing NMAC involves using strange initialization vectors and | |

419 | generally messing about with your hash function. HMAC is an attempt to | |

420 | capture the provable security properties using a plain ol' hash function. | |

421 | ||

422 | Suppose $H$ is an iterated hash function with a $k$-bit output and $L$-bit | |

423 | blocks (with $L \ge k$). We set $\id{ipad}$ to be the byte $\hex{36}$ | |

424 | repeated $L/8$ times, and $\id{opad}$ to be the byte $\hex{5C}$ repeated | |

425 | $L/8$ times. Select a key $K$ of $L$ bits: if your key is shorter, pad it | |

426 | by appending zero bits; if it's longer, hash it with $H$ and then pad. | |

427 | ||

428 | The HMAC tagging function is then defined as | |

429 | \[ \Xid{T}{HMAC}^H_K(m) = | |

430 | H(K \xor \id{opad} \cat H(K \xor \id{ipad} \cat m)). \]% | |

431 | \end{slide} | |

432 | ||

433 | \begin{slide} | |

53aa10b5 | 434 | \head{The HMAC construction, \seq: comparison with NMAC} |

41761fdc | 435 | |

436 | Comparing the two constructions, we see that | |

437 | \[ \Xid{T}{HMAC}^H_K = | |

438 | \Xid{T}{NMAC}^{H'}_{F(I \cat K \xor \id{opad}), | |

439 | F(I \cat K \xor \id{ipad})}. \]% | |

440 | Here, $I$ is $H$'s initialization vector, $F$ is the compression function; | |

441 | $H'$ denotes a keyed hash function that is `like' $H$ but performs padding | |

442 | as if there were an extra initial block of message data for each message. | |

443 | ||

444 | The proof of NMAC assumes that the two keys are random and independent. | |

445 | This isn't the case in HMAC, but a little handwaving about pseudorandomness | |

446 | of the compression function makes the problem go away. | |

447 | \end{slide} | |

448 | ||

449 | \begin{exercise} | |

450 | Suppose that $F\colon \{0, 1\}^k \times \{0, 1\}^{t+\ell} \to \{0, | |

451 | 1\}^t$ is a PRF. Let $x \in \{0, 1\}^*$ be a message. We define the | |

452 | function $H_K(x)$ as follows: | |

453 | \begin{itemize} | |

454 | \item Pad $x$ to a multiple of $\ell$ bits using some injective | |

455 | mapping. Break the image of $x$ under this mapping into $\ell$-bit | |

456 | blocks $x_0, x_1, \ldots, x_{n-1}$. | |

457 | \item For $0 \le i \le n$, define $H^{(i)}_K(x)$ by | |

458 | \[ H^{(0)}_K(x) = I; \qquad | |

459 | H^{(i+1)}_K(x) = F_K(H^{(i)}(x) \cat x_i) \]% | |

460 | where $I$ is some fixed $t$-bit string (e.g., $I = 0^t$). | |

461 | \item Then set $H_K(x) = H^{(n)}_K(x)$. | |

462 | \end{itemize} | |

463 | We define two (deterministic) MACs $\mathcal{M}^i = (T^i, V^i)$ (for | |

464 | $i \in \{0, 1\}$) using the $H_K$ construction. Verification in each | |

465 | case consists of computing the tag and comparing to the one offered. | |

466 | \begin{eqlines*} | |

53aa10b5 | 467 | T^0_K(x) = H_K(x); \qquad T^1_K(x) = H_K(x \cat K); \\ |

41761fdc | 468 | V^i_K(x, \tau) = \begin{cases} |

469 | 1 & if $\tau = T^i_K(x)$ \\ | |

470 | 0 & otherwise | |

53aa10b5 | 471 | \end{cases}. |

41761fdc | 472 | \end{eqlines*} |

473 | Decide whether each of these constructions is secure. A full proof is | |

474 | rather hard: an informal justification would be good. | |

475 | \answer% | |

476 | $\mathcal{M}^0$ is secure; $\mathcal{M}^1$ isn't, under the sole | |

477 | assumption that $F$ is a PRF. | |

478 | ||

479 | To see that $\mathcal{M}^0$ is secure, it suffices to show that $T^0$ | |

480 | is a PRF. This is actually quite involved. Given an adversary $A$ | |

481 | attacking $T^1$ as a PRF, we construct an adversary $B$ attacking $F$, | |

482 | which simply computes $H$ as required, using the oracle supplied. To | |

483 | complete the proof, we need to show a bound on the | |

484 | information-theoretic security of $H$ when instantiated using a random | |

485 | function $F$. For the sake of simplicity, we allow the adversary $A$ | |

486 | to query on \emph{padded} messages, rather than the raw unpadded | |

487 | messages. We count the number $q'$ of individual message blocks. | |

488 | ||

489 | As the game with $A$ progresses, we can construct a directed | |

490 | \emph{graph} of the query results so far. We start with a node | |

491 | labelled $I$. When processing an $H$-query, each time we compute $t' | |

492 | = F(t \cat x_i)$, we add a node $t'$, and an edge $x_i$ from $t$ to | |

493 | $t'$. The `bad' event occurs whenever we add an edge to a previously | |

494 | existing node. We must show, firstly, that the | |

495 | adversary cannot distinguish $H$ from a random function unless the bad | |

496 | event occurs; and, secondly, that the bad event doesn't occur very | |

497 | often. | |

498 | ||

499 | The latter is easier: our standard collision bound shows that the bad | |

500 | event occurs during the game with probability at most $q'(q' - 1)/2$. | |

501 | ||

502 | The former is trickier. This needs a lot more work to make it really | |

503 | rigorous, but we show the idea. Assume that the bad event has not | |

53aa10b5 | 504 | occurred. Consider a query $x_0, x_1, \ldots, x_{n-1}$. If it's the |

41761fdc | 505 | same as an earlier query, then $A$ learns nothing (because it could |

506 | have remembered the answer from last time). If it's \emph{not} a | |

507 | prefix of some previous query, then we must add a new edge to our | |

508 | graph; then either the bad event occurs or we create a new node for | |

509 | the result, and because $F$ is a random function, the answer is | |

510 | uniformly random. Finally, we consider the case where the query is a | |

511 | prefix of some earlier query, or queries. But these were computed at | |

512 | random at the time. | |

513 | ||

514 | At the end of all of this, we see that | |

515 | \[ \InSec{prf}(T^0; t, q) \le | |

516 | \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2} \]% | |

517 | and hence | |

518 | \[ \InSec{suf-cma}(\mathcal{M}^0; t, q) \le | |

519 | \InSec{prf}(F; t, q') + \frac{q'(q' - 1)}{2} + \frac{1}{2^t}. \]% | |

520 | ||

521 | Now we turn our attention to $T^1$. It's clear that we can't simulate | |

522 | $T^1$ very easily using an oracle for $F$, since we don't know $K$ | |

523 | (and indeed there might not be a key $K$). The intuitive reason why | |

524 | $T^1$ is insecure is that $F$ might have leak useful information if | |

525 | its input matches its key. This doesn't affect the strength of $F$ as | |

526 | a PRF because you have to know the key before you can exploit this | |

527 | leakage; but $T^1$ already knows the key, and this can be exploited to | |

528 | break the MAC. | |

529 | ||

530 | To show that this is insecure formally, let $F'$ be defined as | |

531 | follows: | |

532 | \[ F'_K(x) = \begin{cases} | |

533 | K & if $x = p \cat K \cat q$ where | |

534 | $|p| = t$ and $|q| = \ell - k$ \\ | |

535 | F_K(x) & otherwise | |

536 | \end{cases}. \]% | |

537 | We choose a simple injective padding scheme: if $x$ is a message then | |

538 | we form $x' = x \cat 1 \cat 0^n$, where $0 \le n < \ell$ and $|x'|$ is | |

539 | a multiple of $\ell$. If $T^1$ is instantiated with this PRF then it | |

540 | is insecure as a MAC: submitting a tagging query for the empty string | |

541 | $\emptystring$ reveals the key $K$, which can be used to construct a | |

542 | forgery. | |

543 | ||

544 | To complete the proof, we must show that $F'$ is a PRF. Let $A$ be an | |

545 | adversary attacking $F'$. We consider a series of games; for each | |

546 | $\G{i}$, let $S_i$ be the event that $A$ returns $1$ in that game. | |

547 | Game~$\G0$ is the standard attack game with $A$ given an oracle for a | |

548 | random function; game~$\G1$ is the same, except that $A$ is given an | |

549 | oracle for $F'_K$ for some $K \inr \{0, 1\}^k$. Then | |

550 | $\Adv{prf}{F'}(A) = \Pr[S_1] - \Pr[S_0]$. Let game~$\G2$ be the same | |

551 | as $\G1$, except that if $A$ makes any query of the form $p \cat K | |

552 | \cat q$ with $|p| = t$ and $|q| = \ell - k$ then the game halts | |

553 | immediately, and let $F_2$ be the event that this occurs. By | |

53aa10b5 | 554 | Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}), then, $|{\Pr[S_2]} - |

41761fdc | 555 | \Pr[S_1]| \le \Pr[F_2]$. Let game~$\G3$ be the same as $\G2$ except |

556 | that we give $A$ an oracle for $F_K$ rather than $F'_K$. Since $F$ | |

557 | and $F'$ differ only on queries of the form $p \cat K \cat q$, we have | |

558 | $\Pr[S_3] = \Pr[S_2]$. But $\Pr[S_3] - \Pr[S_0] = \Adv{prf}{F}(A) \le | |

559 | \InSec{prf}(F; t, q)$. Hence, $\Adv{prf}{F'}(A) \le \InSec{prf}{F}(A) | |

560 | - \Pr[F_2]$. | |

561 | ||

562 | Finally, we bound the probability of $F_2$. Fix an integer $n$. | |

563 | Consider an adversary $B$ attacking $F$ which runs as follows. It | |

564 | initially requests $F(0), F(1), \ldots, F(n - 1)$ from its oracle. It | |

565 | then runs $A$, except that, for each oracle query $x$, it parses $x$ | |

566 | as $p \cat K' \cat q$ with $|p| = t$, $|K'| = k$ and $|q| = \ell - k$; | |

567 | then, if $F_{K'}(0) = F(0) \land F_{K'}(1) = F(1) \land \cdots \land | |

568 | F_{K'}(n - 1) = F(n - 1)$, $B$ immediately returns $1$, claiming that | |

53aa10b5 | 569 | its oracle $F$ is the function $F_{K'}$; if this never occurs, $B$ |

41761fdc | 570 | returns $0$. Clearly, if $B$ is given an instance $F_K$ of $F$ then |

571 | it succeeds with probability $\Pr[F_2]$; however, if $F$ is a random | |

572 | function then $B$ returns $1$ with probability at most $q 2^{-nk}$. | |

573 | Hence, $\Adv{prf}{F}(B) \le \Pr[F_2] - q 2^{-nk}$. $B$ issues $q + n$ | |

574 | queries, and takes time $t + O(n q)$. Wrapping everything up, we get | |

575 | \[ \InSec{prf}(F'; t, q) \le | |

576 | 2\cdot\InSec{prf}(F; t + O(q n), q + n) + \frac{q}{2^{nk}}. \]% | |

53aa10b5 | 577 | This completes the proof of generic insecurity for $\mathcal{M}^1$. |

41761fdc | 578 | \end{exercise} |

579 | ||

580 | \xcalways\subsection{Universal hashing}\x | |

581 | ||

582 | \begin{slide} | |

583 | \topic{almost-universal hash functions} | |

53aa10b5 | 584 | \resetseq |

585 | \head{Universal hashing, \seq: definition} | |

41761fdc | 586 | |

587 | Consider a family of hash functions $H\colon \keys H \times \dom H \to | |

588 | \ran H$. We define | |

589 | \[ \InSec{uh}(H) = | |

590 | \max_{x \ne y} \Pr[K \getsr \keys H : H_K(x) = H_K(y)]. \]% | |

591 | If $\InSec{uh}(H) \le \epsilon$ then we say that $H$ is | |

592 | \emph{$\epsilon$-almost universal}. Note that the concept of | |

593 | almost-universality is not quantified by running times. | |

594 | ||

595 | If $H$ is $1/|{\ran H}|$-almost universal, then we say that $H$ is | |

596 | \emph{universal}. Sometimes it's said that this is the best possible | |

597 | insecurity: this isn't true. | |

598 | \end{slide} | |

599 | ||

600 | \begin{proof}[Counterexample] | |

601 | Here's a function $H\colon \{0, 1, 2\} \times \{0, 1, 2, 3\} \to \{0, 1\}$ | |

602 | which is $\frac{1}{3}$-almost universal, though $|{\ran H}| = 2$: | |

603 | \begin{quote} \item | |

604 | \begin{tabular}[C]{c|cccc} | |

605 | & 0 & 1 & 2 & 3 \\ \hlx{vhv} | |

606 | 0 & 0 & 1 & 0 & 1 \\ | |

607 | 1 & 0 & 0 & 1 & 1 \\ | |

608 | 2 & 0 & 1 & 1 & 0 | |

609 | \end{tabular} | |

610 | \end{quote} | |

611 | \end{proof} | |

612 | ||

613 | \begin{slide} | |

614 | \topic{dynamic view} | |

53aa10b5 | 615 | \head{Universal hashing, \seq: a dynamic view} |

41761fdc | 616 | |

617 | Suppose that $H$ is $\epsilon$-almost universal. Consider this experiment: | |

618 | \begin{program} | |

619 | Experiment $\Expt{uh}{H}(A)$: \+ \\ | |

620 | $(x, y) \gets A$; \\ | |

621 | $K \getsr \keys H$; \\ | |

622 | \IF $x \ne y \land H_K(x) = H_K(y)$ \THEN \RETURN $1$; \\ | |

623 | \ELSE \RETURN $0$; | |

624 | \end{program} | |

625 | The adversary may make random decisions before outputting its selection | |

626 | $x$, $y$. We show that $\Pr[\Expt{uh}{H}(A) = 1] \le \InSec{uh}(H) = | |

627 | \epsilon$. | |

628 | ||

629 | Let $\rho \in \{0, 1\}^*$ be $A$'s coin tosses: $A$ chooses $x$ and $y$ as | |

630 | functions of $\rho$. For some \emph{fixed} $\rho$, | |

631 | \[ \Pr[K \getsr \keys H : H_K(x(\rho)) = H_K(y(\rho))] \le | |

632 | \InSec{uh}(H). \]% | |

633 | \end{slide} | |

634 | ||

635 | \begin{slide} | |

53aa10b5 | 636 | \head{Universal hashing, \seq: the dynamic view (cont.)} |

41761fdc | 637 | |

638 | Now we treat $\rho$ as a random variable, selected from some distribution | |

639 | $P$ on the set $\{0, 1\}^*$. We see that | |

640 | \begin{eqnarray*}[Ll] | |

641 | \Pr[\rho \getsr P; K \getsr \keys H : H_K(x(\rho)) = H_K(y(\rho))] \\ | |

642 | &= \sum_{\rho \in \{0, 1\}^*} | |

643 | P(\rho) \cdot \Pr[K \getsr \keys H : H_K(x(\rho)) = H_K(y(\rho))] \\ | |

644 | &\le \sum_{\rho \in \{0, 1\}^*} P(\rho) \cdot \InSec{uh}(H) | |

645 | = \InSec{uh}(H). | |

646 | \end{eqnarray*} | |

647 | Thus, no adversary can succeed in producing a collision in an | |

648 | $\epsilon$-almost universal hash with probability better than $\epsilon$. | |

649 | But obviously the adversary can ignore its coin tosses and simply return | |

650 | the best colliding pair. Hence the two notions are completely equivalent. | |

651 | \end{slide} | |

652 | ||

653 | \begin{slide} | |

654 | \topic{composition} | |

53aa10b5 | 655 | \head{Universal hashing, \seq: composition} |

41761fdc | 656 | |

657 | Suppose that $G$ is $\epsilon$-almost universal, and $G'$ is | |

658 | $\epsilon'$-almost universal, and $\dom G = \ran G'$. We define the | |

659 | composition $G \compose G'$ to be the family $H\colon (\keys G \times | |

660 | \keys G') \times \dom G' \to \ran G$ by $H_{k, k'}(m) = | |

661 | G_k(G'_{k'}(m))$. | |

662 | ||

663 | Then $H$ is $(\epsilon + \epsilon')$-almost universal. To see this, fix $x | |

664 | \ne y$, and choose $K = (k, k') \inr \keys G \times \keys G'$. Let $x' = | |

665 | G'_{k'}(x)$ and $y' = G'_{k'}(y)$. Following our previous result, we see: | |

666 | \begin{eqnarray*}[rl] | |

667 | \Pr[H_K(x) = H_K(y)] | |

668 | &= \Pr[G_k(G'_{k'}(x)) = G_k(G'_{k'}(y))] \\ | |

669 | &= \Pr[G_k(x') = G_k(y')] \\ | |

670 | &= \Pr[G_k(x') = G_k(y') \mid x' \ne y'] \Pr[G'_{k'}(x) \ne G'_{k'}(y)]\\ | |

671 | &\le \epsilon + \epsilon'. | |

672 | \end{eqnarray*} | |

673 | \end{slide} | |

674 | ||

675 | \begin{slide} | |

676 | \topic{the collision game} | |

53aa10b5 | 677 | \head{Universal hashing, \seq: the collision game} |

41761fdc | 678 | |

679 | Suppose that, instead of merely a pair $(x, y)$, our adversary was allowed | |

680 | to return a \emph{set} $Y$ of $q$ elements, and measure the probability | |

681 | that $H_K(x) = H_K(y)$ for some $x \ne y$ with $x, y \in Y$, and for $K | |

682 | \inr \keys H$. | |

683 | ||

53aa10b5 | 684 | Let $\InSec{uh-set}(H; q)$ be maximum probability achievable for sets $Y$ |

41761fdc | 685 | with $|Y| \le q$. Then |

686 | \[ \InSec{uh-set}(H; q) \le \frac{q(q - 1)}{2} \cdot \InSec{uh}(H) .\] | |

687 | \end{slide} | |

688 | ||

689 | \begin{proof} | |

690 | This is rather tedious. We use the dynamic view. Suppose $A$ returns $(x, | |

691 | Y)$ with $|Y| = q$, and succeeds with probability $\epsilon$. Consider | |

692 | \begin{program} | |

693 | Adversary $A'$: \+ \\ | |

694 | $(x, Y) \gets A$; \\ | |

695 | $y \getsr Y$; \\ | |

696 | \RETURN $(x, Y \setminus \{y\})$; | |

697 | \end{program} | |

698 | The worst that can happen is that $A'$ accidentally removes the one | |

699 | colliding element from $Y$. This occurs with probability $2/q$. So | |

700 | \[ \Succ{uh-set}{H}(A') \ge \frac{q - 2}{q} \Succ{uh-set}{H}(A). \] | |

53aa10b5 | 701 | Rearranging and maximizing gives |

41761fdc | 702 | \[ \InSec{uh-set}(H; q) \le |

703 | \frac{q}{q - 2} \cdot \InSec{uh-set}(H; q - 1). \] | |

704 | Note that $\InSec{uh-set}(H; 2) = \InSec{uh}(H)$ is our initial notion. A | |

705 | simple inductive argument completes the proof. | |

706 | \end{proof} | |

707 | ||

708 | \begin{slide} | |

709 | \topic{a MAC} | |

53aa10b5 | 710 | \head{Universal hashing, \seq: a MAC} |

41761fdc | 711 | |

53aa10b5 | 712 | Suppose that $H\colon \{0, 1\}^k \times \{0, 1\}^* \to \{0, 1\}^l$ is an |

713 | almost universal hash function, and $F\colon \{0, 1\}^{k'} \times \{0, | |

41761fdc | 714 | 1\}^l \to \{0, 1\}^L$ is a PRF\@. Define a MAC $\Xid{\mathcal{M}}{UH}^{H, |

715 | F} = (\Xid{T}{UH}^{H, F}, \Xid{V}{UH}^{H, F})$ where: | |

716 | \begin{eqnarray*}[rl] | |

717 | \Xid{T}{UH}^{H, F}_{K, K'}(m) &= F_{K'}(H_K(m)) \\ | |

718 | \Xid{V}{UH}^{H, F}_{K, K'}(m, \tau) &= \begin{cases} | |

719 | 1 & if $\tau = F_{K'}(H_K(m))$ \\ | |

720 | 0 & otherwise | |

721 | \end{cases}. | |

722 | \end{eqnarray*} | |

723 | We have | |

724 | \begin{eqnarray*}[Ll] | |

725 | \InSec{suf-cma}(\Xid{\mathcal{M}}{UH}^{H, F}; t, q_T, q_V) \\ | |

726 | & \le | |

727 | (q_V + 1) \biggl(\InSec{prf}(F; t, q_T + 1) + \frac{1}{2^L} + | |

728 | \frac{q_T(q_T - 1)}{2} \cdot \InSec{uh}(H)\biggr). | |

729 | \end{eqnarray*} | |

730 | \end{slide} | |

731 | ||

732 | \begin{proof} | |

733 | We shall prove the result for $q_V = 0$ and $q_T = q$, and appeal to the | |

734 | earlier result on verification oracles. | |

735 | ||

736 | Suppose $A$ attacks the scheme $\Xid{\mathcal{M}}{UH}^{H, F}$ in time $t$, | |

737 | issuing $q$ tagging queries. Consider a distinguisher $D$, constructed | |

738 | from a forger $A$: | |

739 | \begin{program} | |

740 | Distinguisher $D^{F(\cdot)}$: \+ \\ | |

741 | $K \getsr \{0, 1\}^k$; \\ | |

742 | $\Xid{T}{list} \gets \emptyset$; \\ | |

743 | $(m, \tau) \gets A^{\id{tag}(K, \cdot)}$; \\ | |

744 | \IF $m \notin \Xid{T}{list} \land \tau = F(H_K(m))$ | |

745 | \THEN \RETURN $1$; \\ | |

746 | \ELSE \RETURN $0$; \- \\[\smallskipamount] | |

747 | Oracle $\id{tag}(K, m)$: \+ \\ | |

748 | $\Xid{T}{list} \gets \Xid{T}{list} \cup \{m\}$; \\ | |

749 | \RETURN $F(H_K(m))$; \- \\[\smallskipamount] | |

750 | \end{program} | |

751 | Note that $A$ isn't provided with a verification oracle: that's because we | |

752 | didn't allow it any verification queries. | |

753 | ||

754 | We can see immediately that | |

755 | \[ \Pr[K \getsr \{0, 1\}^{k'} : D^{F_K(\cdot)} = 1] = | |

756 | \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A). \]% | |

757 | ||

758 | We must now find an upper bound for $\Pr[F \getsr \Func{l}{L} : | |

759 | D^{F(\cdot)}]$. Suppose that the adversary returns the pair $(m^*, | |

760 | \tau^*)$, and that its tagging oracle queries and their answers are $(m_i, | |

761 | \tau_i)$ for $0 \le i < q$. Consider the event $C$ that $H_K(m) = | |

762 | H_K(m')$ for some $m \ne m'$, with $m, m' \in \{m^*\} \cup \{\,m_i \mid 0 | |

763 | \le i < q\,\}$. | |

764 | ||

765 | If $C$ doesn't occur, then $F$ has not been queried before at $H_K(m)$, but | |

766 | there's a $2^{-L}$ probability that the adversary guesses right anyway. If | |

767 | $C$ does occur, then we just assume that the adversary wins, even though it | |

768 | might not have guessed the right tag. | |

769 | ||

770 | By our result on the collision game, $\Pr[C] \le q \cdot \InSec{uh}(H)$. | |

771 | Then | |

772 | \[ \Succ{prf}{F}(D) \ge | |

773 | \Succ{suf-cma}{\Xid{\mathcal{M}}{UH}^{H, F}}(A) - | |

774 | \frac{1}{2^L} - \frac{q(q - 1)}{2} \cdot \InSec{uh}(H). \]% | |

775 | The result follows. | |

776 | \end{proof} | |

777 | ||

778 | \begin{slide} | |

779 | \topic{almost XOR-universality} | |

53aa10b5 | 780 | \resetseq |

781 | \head{Almost XOR-universality, \seq: definition} | |

41761fdc | 782 | |

783 | Consider a family of hash functions $H\colon \keys H \times \dom H \to | |

784 | \{0, 1\}^L$. Define | |

785 | \[ \InSec{xuh}(H) = | |

786 | \max_{x \ne y, \delta} | |

787 | \Pr[K \getsr \keys H : H_K(x) \xor H_K(y) = \delta]. \]% | |

788 | If $\InSec{xuh}(H) < \epsilon$ then we say that $H$ is | |

789 | \emph{$\epsilon$-almost XOR-universal}, or \emph{AXU}. Setting $\delta = | |

790 | 0$ shows that | |

791 | \begin{eqnarray*}[rl] | |

792 | \InSec{xuh}(H) | |

793 | & \ge \max_{x \ne y} \Pr[K \getsr \keys H : H_K(x) \xor H_K(y) = 0] \\ | |

794 | & = \InSec{uh}(H). | |

795 | \end{eqnarray*} | |

796 | ||

797 | We can take a dynamic view of almost XOR-universality using the same | |

798 | technique as for almost universal functions. | |

799 | ||

800 | If $H$ is $2^{-L}$-almost XOR universal then we say that $H$ is | |

53aa10b5 | 801 | \emph{XOR-universal}. This is the best achievable. |

41761fdc | 802 | \end{slide} |

803 | ||

804 | \begin{proof} | |

805 | Fix some pair $x \ne y$. Choose $\delta \inr \{0, 1\}^L$. Then for any | |

806 | \emph{fixed} $K \in \keys H$, $H_K(x)$ and $H_K(y)$ are fixed, so $H_K(x) | |

807 | \xor H_K(y)$ is fixed, and $\Pr[H_K(x) \xor H_K(y) = \delta] = 2^{-L}$. | |

808 | Using the same trick as for proving the dynamic view: | |

809 | \begin{eqnarray*}[Ll] | |

810 | \Pr[\delta \getsr \{0, 1\}^L; K \getsr \keys H : | |

811 | H_K(x) \xor H_K(y) = \delta] \\ | |

812 | & = \sum_{K \in \keys H} \frac{1}{|{\keys H}|} | |

813 | \Pr[\delta \getsr \{0, 1\}^L; K \getsr \keys H : | |

814 | H_K(x) \xor H_K(y) = \delta] \\ | |

815 | & = \sum_{K \in \keys H} \frac{1}{|{\keys H}|} 2^{-L} = 2^{-L}. | |

816 | \end{eqnarray*} | |

817 | Since $H$ is arbitrary, this proves the lower bound on the almost | |

818 | XOR-universality. | |

819 | \end{proof} | |

820 | ||

821 | \begin{slide} | |

822 | \topic{composition} | |

53aa10b5 | 823 | \head{Almost XOR-universality, \seq: composition} |

41761fdc | 824 | |

825 | We extend our result about composition of almost-universal functions. | |

826 | Suppose that $G$ is $\epsilon$-almost XOR universal, and $G'$ is | |

827 | $\epsilon'$-almost universal (it doesn't have to be almost XOR-universal), | |

828 | and $\dom G = \ran G'$. | |

829 | ||

830 | Then the composition $H = G \compose G'$ is $(\epsilon + \epsilon')$-almost | |

831 | XOR-universal. The proof is simple, and very similar to the | |

832 | almost-universal case. | |

833 | \end{slide} | |

834 | ||

835 | \begin{slide} | |

836 | \topic{a better MAC} | |

53aa10b5 | 837 | \head{Almost XOR-universality, \seq: a better MAC} |

41761fdc | 838 | |

839 | The security result for the UH-based MAC contains a factor $q_T$, which | |

840 | it'd be nice to remove. Our new scheme uses an AXU hash $H\colon \keys H | |

841 | \times \{0, 1\}^* \to \{0, 1\}^l$ and a PRF $F\colon \keys F \times \{0, | |

842 | 1\}^l \to \{0, 1\}^L$. | |

843 | ||

844 | We first present a stateful version $\Xid{\mathcal{M}}{XUH}^{H, F}$. | |

845 | Choose $(K, K') \inr \keys H \times \keys F$, and initialize a counter $i | |

846 | \gets 0$. The tagging and verification algorithms are then: | |

847 | \begin{program} | |

848 | Algorithm $\Xid{T}{XUH}^{H, F}_{K, K'}(m)$: \+ \\ | |

849 | $\tau \gets (i, H_K(m) \xor F_{K'}(i))$; \\ | |

850 | $i \gets i + 1$; \\ | |

851 | \RETURN $\tau$; | |

852 | \next | |

853 | Algorithm $\Xid{V}{XUH}^{H, F}_{K, K'}(m, \tau)$: \+ \\ | |

854 | $(s, \sigma) \gets \tau$; \\ | |

855 | \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\ | |

856 | \ELSE \RETURN $0$; | |

857 | \end{program} | |

858 | Note that verification is stateless. | |

859 | \end{slide} | |

860 | ||

861 | \begin{slide} | |

53aa10b5 | 862 | \head{Almost XOR-universality, \seq: security of AXU-based MACs} |

41761fdc | 863 | |

864 | For the stateful scheme presented earlier, provided $q_T \le 2^l$, we have | |

865 | \begin{eqnarray*}[Ll] | |

866 | \InSec{suf-cma}(\Xid{\mathcal{M}}{XUH}^{H, F}; t, q_T, q_V) \\ | |

867 | & \le (q_V + 1)(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L}). | |

868 | \end{eqnarray*} | |

869 | \end{slide} | |

870 | ||

871 | \begin{slide} | |

53aa10b5 | 872 | \head{Almost XOR-universality, \seq: randomized AXU-based MAC} |

41761fdc | 873 | |

874 | We can avoid statefulness by using randomization. This new scheme is | |

875 | $\Xid{\mathcal{M}}{XUH$\$$}^{H, F} = (\Xid{T}{XUH$\$$}^{H, F}, | |

876 | \Xid{V}{XUH$\$$}^{H, F})$: | |

877 | \begin{program} | |

878 | Algorithm $\Xid{T}{XUH$\$$}^{H, F}_{K, K'}(m)$: \+ \\ | |

879 | $s \getsr \{0, 1\}^l$; \\ | |

880 | $\tau \gets (s, H_K(m) \xor F_{K'}(s))$; \\ | |

881 | \RETURN $\tau$; | |

882 | \next | |

883 | Algorithm $\Xid{V}{XUH$\$$}^{H, F}_{K, K'}(m, \tau)$: \+ \\ | |

884 | $(s, \sigma) \gets \tau$; \\ | |

885 | \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\ | |

886 | \ELSE \RETURN $0$; | |

887 | \end{program} | |

888 | \begin{eqnarray*}[Ll] | |

889 | \InSec{suf-cma}(\Xid{\mathcal{M}}{XUH$\$$}^{H, F}; t, q_T, q_V) \\ | |

890 | & \le (q_V + 1) | |

891 | \Bigl(\InSec{prf}(F; t, q_T + 1) + \InSec{xuh}(H) + 2^{-L} + | |

892 | \frac{q_T(q_T - 1)}{2^{l+1}}\Bigr). | |

893 | \end{eqnarray*} | |

894 | \end{slide} | |

895 | ||

896 | \begin{proof} | |

897 | We prove the result with $q_V = 0$ and $q_T = q$, and appeal to the result | |

898 | on verification oracles. Let $m_i$ be the message specified in the $i$-th | |

899 | tagging query ($0 \le i < q$), and let $(s_i, \sigma_i) = (s_i, H_K(m) \xor | |

900 | F_{K'}(s_i))$ be the tag returned. We call the $s_i$ the \emph{nonce}. | |

901 | ||

902 | We prove the result for the stateless scheme. The bound $q \le 2^l$ | |

903 | ensures that the nonces are all distinct (we have $s_i = i$). The security | |

904 | bound for the randomized version merely has as an extra term upper bound | |

905 | for the probability of a nonce collision. | |

906 | ||

907 | Let $A$ be an adversary attacking the MAC in time $t$, and using $q$ | |

908 | tagging queries. Then we present the following pair of adversaries: | |

909 | \begin{program} | |

910 | Distinguisher $D^{F(\cdot)}$: \+ \\ | |

911 | $i \gets 0$; \\ | |

912 | $\Xid{T}{list} \gets \emptyset$; \\ | |

913 | $K \getsr \keys H$; \\ | |

914 | $(m, \tau) \gets A^{\id{tag}}$; \\ | |

915 | $(s, \sigma) \gets \tau$; \\ | |

916 | \IF $(m, \tau) \notin \Xid{T}{list} \land | |

917 | \sigma = H_K(m) \xor F(s)$ | |

918 | \THEN \RETURN $1$; \\ | |

919 | \ELSE \RETURN $0$; \- \\[\smallskipamount] | |

920 | Oracle $\id{tag}(m)$: \+ \\ | |

921 | $\tau \gets (i, H_K(m) \xor F(i))$; \\ | |

922 | $\Xid{T}{list} \gets \Xid{T}{list} \cup \{(m, \tau)\}$; \\ | |

923 | $i \gets i + 1$; | |

924 | \RETURN $\tau$; | |

925 | \next | |

926 | Collision-finder $C$: \+ \\ | |

927 | $i \gets 0$; \\ | |

928 | $(m, \tau) \gets A^{\id{tag}}$; \\ | |

929 | $(s, \sigma) \gets \tau$; \\ | |

930 | \IF $s \ge i \lor m = m_s$ \THEN \ABORT; \\ | |

931 | \RETURN $(m, m_s, \sigma \xor \sigma_s)$; \- \\[\smallskipamount] | |

932 | Oracle $\id{tag}(m)$: \+ \\ | |

933 | $m_i \gets m$; \\ | |

934 | $\sigma_i \getsr \{0, 1\}^L$; \\ | |

935 | $\tau \gets (i, \sigma_i)$; \\ | |

936 | $i \gets i + 1$; \\ | |

937 | \RETURN $\tau$; | |

938 | \end{program} | |

939 | ||

940 | We need to find a lower bound on the advantage of $D$. If $F$ is chosen | |

941 | from the PRF then $D$ returns $1$ precisely when $A$ finds a valid | |

942 | forgery. We now examine the setting in which $F$ is a random function. | |

943 | ||

944 | Let $S$ be the event that $A$ succeeds in returning a valid forgery when | |

945 | $F$ is random, and let $N$ be the event that the nonce $s$ returned by $A$ | |

946 | is not equal to any nonce $s_i$ returned by the tagging oracle. Suppose | |

947 | $N$ occurs: then the random function $F$ has never been queried before at | |

948 | $F$, and $\Pr[F(s) = \sigma \xor H_K(m)]$ is precisely $2^{-L}$. | |

949 | ||

950 | So suppose instead that $N$ doesn't occur. Then, since the $s_i$ are | |

951 | distinct, there is a unique $i$ such that $s = s_i$. For $A$ to win, we | |

952 | must have $m \ne m_i$ (for if $m = m_i$ then the only valid tag is | |

953 | $H_K(m_i) \xor F(s_i) = \sigma_i$, which was already returned by the | |

954 | tagging oracle). If $A$'s forgery is successful then | |

955 | \[ \sigma = H_K(m) \xor F(s) | |

956 | \qquad \text{and} \qquad | |

957 | \sigma_i = H_K(m_i) \xor F(s_i) \]% | |

958 | but $s = s_i$, whence | |

959 | \[ H_K(m_i) \xor H_K(m) = \sigma \xor \sigma_i. \] | |

960 | Since the $s_i$ are distinct and $F$ is a random function, the $\sigma_i$ | |

961 | are independent uniformly-distributed random strings from $\{0, 1\}^L$. | |

962 | Hence the collision-finder $C$ succeeds with probability $\Pr[S \land | |

963 | \lnot N] \le \InSec{xuh}(H)$. | |

964 | ||

965 | Wrapping up, we have | |

966 | \begin{eqnarray*}[rl] | |

967 | \Adv{prf}{F}(D) | |

968 | & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) - | |

969 | (\Pr[S \mid N] \Pr[N] + \Pr[S \mid \lnot N] \Pr[\lnot N]) \\ | |

970 | & \ge \Succ{suf-cma}{\Xid{\mathcal{M}}{XUH}^{H, F}}(A) - | |

971 | (2^{-L} + \InSec{xuh}(H)). | |

972 | \end{eqnarray*} | |

973 | Maximizing and rearranging yields the required result. | |

974 | \end{proof} | |

975 | ||

976 | \begin{remark*} | |

977 | Note that our bound has a $2^{-L}$ term in it that's missing from | |

978 | \cite{Goldwasser:1999:LNC}. We believe that their proof is wrong in its | |

979 | handling of the XOR-collision probability. | |

980 | \end{remark*} | |

981 | ||

982 | \endinput | |

983 | ||

984 | %%% Local Variables: | |

985 | %%% mode: latex | |

986 | %%% TeX-master: "ips" | |

987 | %%% End: |