e0f3f010720f29c32bfd42c16b04a671b3088331
1 \xcalways\section{Symmetric encryption}\x
3 \xcalways\subsection{Syntax}\x
5 \begin{slide}
8 A \emph{symmetric encryption scheme} $\mathcal{E} = (E, D)$ is a set of
9 keys $\keys\mathcal{E}$ (usually $\{0, 1\}^k$ for some integer $k$) and
10 pair of algorithms:
11 \begin{itemize}
12 \item an \emph{encryption} algorithm $E\colon \keys\mathcal{E} \times \{0, 13 1\}^* \to \{0, 1\}^*$; and
14 \item a \emph{decryption} algorithm $D\colon \keys\mathcal{E} \times \{0, 15 1\}^* \to \{0, 1\}^*$.
16 \end{itemize}
17 We also have a \emph{correctness} requirement: for any $K \in 18 \keys\mathcal{E}$, and any plaintext $x$, if $E(K, x)$ returns $y$ then
19 $D(K, y)$ returns $x$.
21 We write $E_K(\cdot)$ rather than $E(K, \cdot)$, and $D_K(\cdot)$ rather
22 than $D(K, \cdot)$.
23 \end{slide}
25 \xcalways\subsection{Security notions}\x
27 \begin{slide}
30 In symmetric scheme, an adversary who doesn't know the key can't encrypt
31 data for itself. To modify our security notions by providing the adversary
32 with an encryption oracle.
34 We consider semantic security, indistinguishability and non-malleability,
35 against chosen-plaintext and chosen-ciphertext attacks. To make life more
36 complicated, we have three different indistinguishability notions.
38 We use the same notation to decscribe the decryption oracles provided in
39 various types of attacks:
40 \begin{tabular}[C]{l Mc Mc }
41 \hlx*{hv}
42 Attack & D_0(c) & D_1(c) \\ \hlx{vhv}
43 CPA & \bot & \bot \\
44 CCA1 & D_K(c) & \bot \\
45 CCA2 & D_K(c) & D_K(c) \\ \hlx*{vh}
46 \end{tabular}
47 \end{slide}
49 \begin{slide}
50 \topic{semantic security}
53 The semantic security game is as for the asymmetric case, except for the
54 presence of encryption oracles.
56 \begin{program}
57 Experiment $\Expt{sem-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
58 $K \getsr \keys\mathcal{E}$; \\
59 $(\mathcal{M}, s) \gets A^{E_K(\cdot), D_0(\cdot)} 60 (\cookie{select})$; \\
61 $x_0 \getsr \mathcal{M}$; $x_1 \getsr \mathcal{M}$; \\
62 $y \gets E_K(x_1)$; \\
63 $(f, \alpha) \gets A^{E_K(\cdot), D_1(\cdot)} 64 (\cookie{predict}, y, s)$; \\
65 \IF $f(x_b) = \alpha$ \THEN \RETURN $1$; \\
66 \ELSE \RETURN $0$;
67 \end{program}
68 The distribution $\mathcal{M}$ must be \emph{valid}: all strings in
69 $\supp\mathcal{M}$ must have the same length.
70 \end{slide}
72 \begin{slide}
73 \topic{find-then-guess}
76 The find-then-guess' (FTG) game corresponds to the standard public-key
77 indistinguishability notion.
78 \begin{program}
79 Experiment $\Expt{ftg-\id{atk}-$b$}{\mathcal{E}}(A)$: \+ \\
80 $K \getsr \keys\mathcal{E}$; \\
81 $(x_0, x_1, s) \gets A^{E_K(\cdot), D_0(\cdot)}(\cookie{find})$; \\
82 \IF $|x_0| \ne |x_1|$ \THEN \RETURN $0$; \\
83 $y \gets E_K(x_b)$; \\
84 $b' \gets A^{E_K(\cdot), D_1(\cdot)}(\cookie{guess}, y, s)$; \\
85 \RETURN $b'$;
86 \end{program}
87 \end{slide}
89 \begin{slide}
90 \topic{left-or-right}
93 The left-or-right' (LOR) notion is a natural extension of find-then-guess.
94 Rather than having to guess the hidden bit using a single challenge
95 ciphertext, the adversary is allowed to request more as it likes. It is
96 given an encryption oracle which accepts two arguments: it selects either
97 the left or the right plaintext, according to the hidden bit, and returns
98 the ciphertext.
99 \begin{program}
100 Experiment $\Expt{lor-\id{atk}-$b$}{\mathcal{E}}(A)$; \+ \\
101 $K \getsr \keys\mathcal{E}$; \\
102 $b' \gets A^{E_K(\id{lr}_b(\cdot, \cdot)), D_1(\cdot)}$; \\
103 \RETURN $b'$; \- \$\smallskipamount] 104 Function \id{lr}_b(x_0, x_1): \+ \\ 105 \RETURN x_b; 106 \end{program} 107 Note that, because the adversary only runs in one stage, we can only 108 consider chosen-plaintext and adaptive chosen-ciphertext attacks. 109 \end{slide} 111 \begin{slide} 112 \topic{real-or-random} 113 \head{Real-or-random indistinguishability} 115 The real-or-random' (ROR) notion is somewhat less natural, but turns out 116 to be useful for analysing block cipher encryption modes. 118 The adversary is given an oracle which, when given a plaintext x, either 119 returns an encryption of x or an encryption of a random string with the 120 same length as x. 121 \begin{program} 122 Experiment \Expt{ror-\id{atk}-0}{\mathcal{E}}(A); \+ \\ 123 K \getsr \keys\mathcal{E}; \\ 124 b' \gets A^{E_K(\id{rand}(\cdot)), D_1(\cdot)}; \\ 125 \RETURN b'; \- \\[\smallskipamount] 126 Function \id{rand}(x): \+ \\ 127 x' \getsr \{0, 1\}^{|x|}; \\ 128 \RETURN x'; 129 \next 130 Experiment \Expt{ror-\id{atk}-1}{\mathcal{E}}(A); \+ \\ 131 K \getsr \keys\mathcal{E}; \\ 132 b' \gets A^{E_K(\cdot), D_1(\cdot)}; \\ 133 \RETURN b'; 134 \end{program} 135 Again, only chosen-plaintext and adaptive chosen-ciphertext attacks are 136 applicable. 137 \end{slide} 139 \begin{slide} 140 \topic{relations between notions} 141 \head{Relations between notions \cite{Bellare:2000:CST}} 143 \[ \xymatrix @=2cm { 144 \txt{LOR} \ar@<0.5ex>[r]^1 \ar@<-0.5ex>[d]_3 & 145 \txt{ROR} \ar@<0.5ex>[l]^2 \\ 146 \txt{FTG} \ar@{-->}@<-0.5ex>[u]_4 \ar@<0.5ex>[r] & 147 \txt{SEM} \ar@<0.5ex>[l] 148 }$
149 \begin{list}{}{
150 \settowidth{\labelwidth}{\textbf{Key}}
152 \itemindent0pt\let\makelabel\textbf}
153 \item[Key] \begin{itemize}
154 \item A solid arrow $\xy\ar*+{A};<1.5cm, 0cm>*+{B}\endxy$ indicates an
155 \emph{security-preserving} reduction: if a scheme is secure in notion
156 $A$ then it is as secure in notion $B$, to within a small constant
157 factor.
158 \item A broken arrow $\xy\ar@{-->}*+{A};<1.5cm, 0cm>*+{B}\endxy$
159 indicates a non-security-preserving reduction.
160 \item The numbers refer to sections of the proof provided in the notes.
161 \end{itemize}
162 \end{list}
163 \end{slide}
165 \begin{proof}
166 We deal with the propositions one at a time. Most of them are pretty easy,
167 with the exception of the security-losing reduction from FTG to LOR.
168 \begin{enumerate}
170 \item We show that $\text{LOR-\id{atk}} \implies \text{ROR-\id{atk}}$.
171 Suppose $A'$ attacks $\mathcal{E}$ in the real-or-random sense.
172 \begin{program}
173 Adversary $A^{E(\cdot, \cdot), D(\cdot)}$: \+ \\
174 \RETURN $A'^{\id{ror-hack}(\cdot), D(\cdot)}$; \-\$\smallskipamount] 175 Oracle \id{ror-hack}(x): \+ \\ 176 x' \getsr \{0, 1\}^{|x|}; \\ 177 \RETURN E(x', x); 178 \end{program} 179 Since this provides a perfect simulation of the ROR game, 180 \[ \Adv{lor-\id{atk}}{\mathcal{E}}(A) = 181 \Adv{ror-\id{atk}}{\mathcal{E}}(A'),$%
182 and hence
183 $\InSec{ror-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le 184 \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D).$%
186 \item We show that $\text{ROR-\id{atk}} \implies \text{LOR-\id{atk}}$.
187 Suppose $A'$ attacks $\mathcal{E}$ in the left-or-right sense.
188 \begin{program}
189 Adversary $A^{E(\cdot), D(\cdot)}$: \+ \\
190 $\hat{b} \gets \{0, 1\}$; \\
191 $b' \gets A'^{\id{lor-hack}(\cdot, \cdot), D(\cdot)}$; \\
192 \IF $b' = \hat{b}$ \THEN \RETURN $1$; \\
193 \ELSE \RETURN $0$; \- \$\smallskipamount] 194 Oracle \id{lor-hack}(x_0, x_1): \+ \\ 195 \RETURN E(x_{\hat{b}}); 196 \end{program} 197 If the ROR oracle is returning correct encryptions, then A' will return 198 the correct bit \hat{b} with probability 199 \[ \frac{\Adv{lor-\id{atk}}{\mathcal{E}}(A')}{2} + \frac{1}{2};$
200 if the ROR oracle is returning ciphertexts for random plaintexts, then
201 $A'$ is being given no information about $\hat{b}$, and hence guesses
202 correctly with probability exactly $\frac{1}{2}$. We conclude that
203 $\Adv{ror-\id{atk}}{\mathcal{E}}(A) = 204 \frac{1}{2}\Adv{lor-\id{atk}}{\mathcal{E}}(A'),$%
205 and hence
206 $\InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le 207 2 \cdot \InSec{ror-\id{atk}}(\mathcal{E}; t, q_E, q_D).$%
209 \item We show that $\text{LOR-\id{atk}} \implies \text{FTG-\id{atk}}$.
210 Suppose $A'$ attacks $\mathcal{E}$ in the find-then-guess sense. We
211 assume, without loss of generality, that $A'$ never queries its
212 decryption oracle on ciphertexts it obtained from its encryption oracle.
213 \begin{program}
214 Adversary $A^{E(\cdot, \cdot), D(\cdot)}$: \+ \\
215 $(x_0, x_1, s) \gets A'^{\id{encrypt}(\cdot), D(\cdot)} 216 (\cookie{find})$; \\
217 $y \gets E(x_0, x_1)$; \\
218 $b' \gets A'^{\id{encrypt}(\cdot), D(\cdot)} 219 (\cookie{guess}, y, s);$ \\
220 \RETURN $b'$; \- \$\smallskipamount] 221 Oracle \id{encrypt}(x): \+ \\ 222 \RETURN E(x, x); 223 \end{program} 224 Since this provides a perfect simulation of the FTG game, 225 \[ \Adv{lor-\id{atk}}{\mathcal{E}}(A) = 226 \Adv{ftg-\id{atk}}{\mathcal{E}}(A'),$%
227 and hence
228 $\InSec{ftg-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le 229 \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E + 1, q_D).$%
231 \item We show that $\text{FTG-\id{atk}} \implies \text{LOR-\id{atk}}$,
232 though with a factor of $q_E$ loss of security.
234 This proof is slightly more tricky than the others. Consider the
235 following hybrid' games, defined for $0 \le i \le q_E$:
236 \begin{program}
237 Experiment $\Expt{hyb-$i$-\id{atk}-$b$}{\mathcal{E}}$: \+ \\
238 $K \getsr \keys\mathcal{E}$; \\
239 $j \gets 0$; \\
240 $b' \gets A^{E(\id{lr-hack}_b(\cdot, \cdot)), D_1(\cdot)}$; \\
241 \RETURN $b'$; \- \$\smallskipamount] 242 \next 243 Function \id{lr-hack}_b(x_0, x_1): \+ \\ 244 \IF j < i \THEN x \gets x_0; \\ 245 \ELSE \IF j > i \THEN x \gets x_1; \\ 246 \ELSE x \gets x_b; \\ 247 j \gets j + 1; \\ 248 \RETURN E_K(x_b); 249 \end{program} 250 As usual, we define 251 \[ \Adv{hyb-i-\id{atk}}{\mathcal{E}}(A) = 252 \Pr[\Expt{hyb-i-\id{atk}-1}{\mathcal{E}} = 1] - 253 \Pr[\Expt{hyb-i-\id{atk}-0}{\mathcal{E}} = 1].$%
255 Observe that we have the identities
256 \begin{eqnarray*}[rl]
257 \Expt{lor-\id{atk}-$0$}{\mathcal{E}} &\equiv
258 \Expt{hyb-$(q_E{-}1)$-\id{atk}-$0$}{\mathcal{E}}
259 \\
260 \Expt{lor-\id{atk}-$1$}{\mathcal{E}} &\equiv
261 \Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}}
262 \\
263 \tabpause{and, for $0 \le i < q_E$,}
264 \Expt{hyb-$i$-\id{atk}-$0$}{\mathcal{E}} &\equiv
265 \Expt{hyb-$(i{+}1)$-\id{atk}-$1$}{\mathcal{E}}.
266 \end{eqnarray*}
267 Thus,
268 \begin{eqnarray*}[rclclc]
270 &=& \Pr[\Expt{lor-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
271 \Pr[\Expt{lor-\id{atk}-$0$}{\mathcal{E}}(A) = 1]
272 \\*
273 &=& \Pr[\Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
274 \Pr[\Expt{hyb-$(q_E{-}1)$-\id{atk}-$0$}{\mathcal{E}}(A) = 1]
275 \\
276 &=& \Pr[\Expt{hyb-$0$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
277 \Pr[\Expt{hyb-$0$-\id{atk}-$0$}{\mathcal{E}}(A) = 1] &+ \\*
278 & & \Pr[\Expt{hyb-$1$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
279 \Pr[\Expt{hyb-$1$-\id{atk}-$0$}{\mathcal{E}}(A) = 1] &+ \\*
280 & & \multicolumn{1}{c}{\smash\vdots} &-&
281 \multicolumn{1}{c}{\smash\vdots} &+ \\*
282 & & \Pr[\Expt{hyb-$(q_E{-}1)$-\id{atk}-$1$}{\mathcal{E}}(A) = 1] &-&
283 \Pr[\Expt{hyb-$(q_E{-}1)$-\id{atk}-$0$}{\mathcal{E}}(A) = 1]
284 \\*
285 &=& \sum_{0\le i<q_E} \Adv{hyb-$i$-\id{atk}}{\mathcal{E}}(A)
286 \end{eqnarray*}
287 Now, there must be at least one $i$ for which
288 $\Adv{hyb-i-\id{atk}}{\mathcal{E}}(A) \ge 289 \frac{1}{q_E} \Adv{lor-\id{atk}}{\mathcal{E}}(A).$%
291 Suppose that $A'$ is an adversary attacking $\mathcal{E}$ in the LOR
292 sense. We can construct an FTG adversary $A$ for which
293 $\Adv{ftg-\id{atk}}{\mathcal{E}}(A) \ge 294 \frac{1}{q_E} \Adv{lor-\id{atk}}{\mathcal{E}}(A')$%
295 as follows:\footnote{%
296 The expression of the FTG adversary requires control flow operations
297 which aren't easily expressed in the pseudocode language we've used so
298 far, hence the cop-out into English.}
299 \begin{enumerate}
300 \item When invoked in the $\cookie{find}$ stage, run the LOR adversary,
301 passing it $A$'s decryption oracle.
302 \item Respond to its first $i$ left-or-right queries $(x_0, x_1)$ with
303 $E(x_0)$.
304 \item On the $(i + 1)$-th left-or-right query, $(x_0, x_1)$, package up
305 all of $A'$'s state, and return that, together with the pair $(x_0, 306 x_1)$ as the result of $A$'s $\cookie{find}$ stage.
307 \item When reinvoked in the $\cookie{guess}$ stage, return the challenge
308 ciphertext $y$ as the result of $A'$'s $(i + 1)$-th query.
309 \item Respond to the remaining $q_E - i - 1$ left-or-right queries
310 $(x_0, x_1)$ with $E(x_1)$.
311 \item Return the bit output by $A'$.
312 \end{enumerate}
313 This evidently simulates the environment of
314 $\Expt{hyb-$i$-\id{atk}-$b$}{\mathcal{E}}(A')$; hence $A$ achieves the
316 $\InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le 317 q_E \cdot \InSec{ftg-\id{atk}}(\mathcal{E}; t, q_E - 1, q_D).$%
319 Now we show that we can't obtain a better reduction. Suppose that
320 $\mathcal{E} = (E, D)$ is $(t, q_E, q_D, \epsilon)$-secure in the FTG
321 sense. We contruct a \emph{$p$-leaky} version, $\mathcal{E}' = (E', 322 D')$. Let $\id{maybe}(p)$ denote a function which returns $1$ with
323 probability $p$.
324 \begin{program}
325 Algorithm $E'_K(x)$: \+ \\
326 \IF $\id{maybe}(p) = 1$ \THEN \RETURN $1 \cat x$; \\
327 \RETURN $0 \cat E_K(x)$;
328 \next
329 Algorithm $D'_K(y')$: \+ \\
330 \PARSE $y'$ \AS $1\colon b, y$; \\
331 \IF $b = 1$ \THEN \RETURN $y$; \\
332 \RETURN $D_K(y)$;
333 \end{program}
334 A simple simulation argument shows that this scheme is still secure,
335 except for an additional term $p$, handling the case where the challenge
336 ciphertext $y^* = 1 \cat x^*$. It is easy to see that
337 $\InSec{lor-\id{atk}}(\mathcal{E}'; t, q_E, 0) \ge q_E p,$
338 concluding the proof.
339 \end{enumerate}
341 The proofs that $\text{FTG-\id{atk}} \implies \text{SEM-\id{atk}}$ and
342 $\text{SEM-\id{atk}} \implies \text{FTG-\id{atk}}$ are just as in the
343 public-key case (page~\pageref{pf:pub-ind-eq-sem}), except for the presence
344 of encryption oracles (which are passed on unmolested). And that's all we
345 need.
346 \end{proof}
348 \begin{exercise}
349 Consider the following ciphertext-or-random-string' security notion.
350 \begin{program}
351 Experiment $\Expt{cor-\id{atk}-$0$}{\mathcal{E}}(A)$: \+ \\
352 $b' \gets A^{\id{rand}(E_K(\cdot)), D_1(\cdot)}$; \\
353 \RETURN $b'$; \- \$\smallskipamount] 354 Function \id{rand}(x): \+ \\ 355 x' \getsr \{0, 1\}^{|x|}; \\ 356 \RETURN x'; 357 \next 358 Experiment \Expt{cor-\id{atk}-1}{\mathcal{E}}(A); \+ \\ 359 K \getsr \keys\mathcal{E}; \\ 360 b' \gets A^{E_K(\cdot), D_1(\cdot)}; \\ 361 \RETURN b'; 362 \end{program} 363 Relate this notion to the others we've already seen. 364 \answer% 365 It's not hard to see that \text{COR} \implies \text{LOR}; the proof is 366 similar to \text{ROR} \implies \text{LOR}, and we have 367 \InSec{cor-\id{atk}}(\mathcal{E}; t, q_E, q_D) \le 2\cdot 368 \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D). On the other hand, 369 \text{LOR} \not\implies \text{COR}. To see this, let \mathcal{E} = (E, 370 D) be an encryption scheme secure in the LOR-\id{atk} sense, and define 371 \mathcal{E}' = (E', D') by E'_K(x) = 0^n \cat E_K(x) and D'_K(y') = 372 D_K(y) if y' = 0^n \cat y for some y, or \bot otherwise. Because 373 the fixed padding is independent of the plaintext, 374 \InSec{lor-\id{atk}}(\mathcal{E}'; t, q_E, q_D) \le 375 \InSec{lor-\id{atk}}(\mathcal{E}; t, q_E, q_D). But \mathcal{E}' is not 376 COR-CPA secure because an adversary can check for the fixed padding; hence 377 \InSec{cor-cpa}(\mathcal{E}'; t, q_E, q_D) \ge 1 - q_E 2^{-n}. 378 \end{exercise} 380 \begin{exercise} 381 Let F\colon \{0, 1\}^k \times \{0, 1\}^l \to \{0, 1\}^l be a PRF, and let 382 g\colon \{0, 1\}^l \to \{0, 1\}^{2l} be a length-doubling PRG. Recall 383 from Exercise~\ref{ex:dbl-prg} the construction g^(i), defined by 384 \[ g^{(1)}(x) = g(x); \qquad 385 g^{(i+1)}(x) = g_0(x) \cat g^{(i)}(g_1(x)).$%
386 We define an encryption scheme $\mathcal{E} = (E, D)$ as follows:
387 \begin{program}
388 Algorithm $E_K(x)$: \\
389 $i \getsr \{0, 1\}^l$; \\
390 $n \gets \bigl\lceil \frac{|x|}{L} \bigr\rceil - 1$; \\
391 $s \gets F_K(i)$; \\
392 $p \gets g^{(n)}(s)$; \\
393 $y \gets i \cat (x \xor p)$; \\
394 \RETURN $y$;
395 \next
396 Algorithm $D_K(y)$: \\
397 \PARSE $y$ \AS $l\colon i, y'$; \\
398 $n \gets \bigl\lceil \frac{|x|}{L} \bigr\rceil - 1$; \\
399 $s \gets F_K(i)$; \\
400 $p \gets g^{(n)}(s)$; \\
401 $x \gets y' \xor p$; \\
402 \RETURN $x$;
403 \end{program}
404 Prove that
405 $\InSec{lor-cpa}(\mathcal{E}; t, q, \mu) \le 406 2 \cdot \InSec{prf}(F; t, q) + 407 2 q \mu \cdot \InSec{prg}(g; t) + q(q - 1),$%
408 where $\mu$ is the maximum value of $n$, as computed by $E_K(\cdot)$, for
409 any encryption query.
410 Hints:
411 \begin{parenum}
412 \item use a sequence of games, ending with one in which the ciphertext'
413 are random strings of the right length;
414 \item attack the PRF first;
415 \item use a hybrid argument to attack the PRG, as was used in the proof
416 that $\text{FTG} \implies \text{LOR}$.
417 \end{parenum}
419 For each game~$\G{i}$, $S_i$~is the event that the adversary guesses
420 correctly. Game~$\G0$ is the original attack game (with the hidden bit~$b$
421 selected uniformly). Game~$\G1$ is the same, except that if, for any pair
422 of ciphertexts, the $i$-values are equal, the game ends immediately: the
423 standard collision bound shows that $|{\Pr[S_1]} - \Pr[S_0]| \le q(q - 424 1)/2$. In game~$\G2$, rather than using $F_K$ to compute the seeds~$s$, we
425 just choose $s \in \{0, 1\}^l$ at random each time. Note that the
426 $i$-values are distinct; hence considering an adversary attacking $F$ as a
427 PRF, which simulates either $\G1$ or $\G2$ depending on whether its oracle
428 is an instance of~$F$ or a random function respectively, shows that
429 $|{\Pr[S_2]} - \Pr[S_1]| \le \InSec{prf}(F; t, q)$.
431 In game~$\G3$, rather than using the PRG~$g^{(n)}$, we generate the strings
432 $p$ uniformly at random from $\{0, 1\}^{l(n+1)}$, and claim that
433 $|{\Pr[S_3]} - \Pr[S_2]| \le q \mu \cdot \InSec{prg}(g; t)$ (proven below).
434 Finally, in game~$\G4$, rather than computing the ciphertext as $i \cat (x 435 \xor p)$, we just generate a random string $\{0, 1\}^{l(n+2)}$. Since $i$
436 and $p$ are uniform and random anyway, this doesn't affect the
437 distribution; it does show that the result is independent of the
438 adversary's ciphertext, however, so $\Pr[S_4] = \Pr[S_3] = \frac{1}{2}$.
439 Tying all of this together, $(\Adv{lor-cpa}{\mathcal{E}}(A) + 1)/2 \le 440 \frac{1}{2} + \InSec{prf}(F; t, q) + q\mu \cdot \InSec{prg}(g; t) + q(q - 441 1)/2$. Multiplying through by~2 and rearranging yields the required
442 result.
444 \def\H#1{\G[H]{#1}}%
445 We finally turn to the claim made earlier. In $\G2$, we use the PRG; in
446 $\G3$ we don't. We construct a number of hybrid games~$\H{i}$ for $0 \le i 447 \le q$ in which encryption query~$j$ (for $0 \le j < q$) is handled as
448 follows: if $0 \le j < i$ then the query is handled as in $\G3$; if $i \le 449 j < q$ then the query is handed as in $\G2$. Let $T_i$ be the event that
450 the adversary wins in game $\H{i}$. Clearly, $\H0 \equiv \G2$, and $\H{q} 451 \equiv \G3$. For each adjacent pair of hybrid games $\H{i}, \H{i+1}$ (for
452 $0 \le i < q$), we can bound $|{\Pr[T_{i+1}} - \Pr[T_i]|$ by considering an
453 adversary attacking~$g^{(n)}$ by running~$A$ and using its input as the XOR
454 mask~$p$ for query~$i$, and following the rules of game~$\H{i}$ for the
455 other queries: then if $y$~is random, it simulates $\H{i+1}$, whereas if
456 $y$ is the output of $g^{(n)}$ then it simulates $\H{i}$. Thus
457 $|{\Pr[T_{i+1}} - \Pr[T_i]| \le \mu \cdot \InSec{prg}(g; t)$ (by the answer
458 to \ref{ex:dbl-prg}), and $|{\Pr[S_3]} - \Pr[S_2]| = |{\Pr[T_{q-1}]} - 459 \Pr[T_0]| \le q \mu \cdot \InSec{prg}(g; t)$ as claimed.
460 \end{exercise}
462 \xcalways\subsection{Block cipher modes}\x
464 \begin{slide}
467 Block ciphers (which we model as PRPs) are readily available components,
468 and we have good tools for analysing their (heuristic) security. It'd be
469 good if we could use them to construct secure encryption schemes.
471 We analyse three standard \emph{modes of operation}:
472 \begin{description}
473 \item[Electronic Code Book (ECB)] Each plaintext block is encrypted
474 independently of the others, using the block cipher.
475 \item[Counter (CTR)] Choose a random starting point $i$. The plaintext
476 blocks are XORed with the result of encrypting the counter values $i$,
477 $i + 1$, \ldots
478 \item[Ciphertext Block Chaining (CBC)] The first plaintext block is XORed
479 with a random \emph{initialization vector} and encrypted using the block
480 cipher; thereafter, each plaintext block are XORed with the previous
481 ciphertext block and then encrypted with the block cipher.
482 \end{description}
483 \end{slide}
485 \begin{slide}
488 We consider pseudorandom permutations $E\colon \{0, 1\}^k \times \{0, 1\}^l 489 \to \{0, 1\}^l$ operating on $l$-bit blocks. We write $E_K(\cdot)$ rather
490 than $E(K, \cdot)$.
492 For the sake of simplicity, we assume that plaintexts are a multiple of $l$
493 bits in length. We shall consider chosen-plaintext attacks, and we shall
494 be quantifying our results in terms of:
495 \begin{itemize}
496 \item the running time $t$ of adversaries;
497 \item the number $q$ of queries made to the encryption oracle; and
498 \item the maximum size in bits $\mu$ of any individual encryption query.
499 \end{itemize}
501 We shall write `\FOREACH $l\colon z$ \FROM $x$ \DO \ldots' to denote
502 iteration over each $l$-bit block $z$ of $x$ in turn.
504 We use $\emptystring$ to denote the empty string.
505 \end{slide}
507 \begin{slide}
508 \topic{ECB}
509 \head{Electronic Code Book (ECB), 1: description}
511 We define the scheme $\Xid{\mathcal{E}}{ECB}^E = (\Xid{E}{ECB}^E, 512 \Xid{D}{ECB}^E))$ by setting $\keys\Xid{\mathcal{E}}{ECB}^E = \{0, 1\}^k$
513 and
514 \begin{program}
515 Algorithm $\Xid{E}{ECB}^E_K(x)$: \+ \\
516 $y \gets \emptystring$; \\
517 \FOREACH $l\colon z$ \FROM $x$ \DO \\
518 \quad $y \gets y \cat E_K(z)$; \\
519 \RETURN $y$;
520 \next
521 Algorithm $\Xid{D}{ECB}^E_K(y)$: \+ \\
522 $x \gets \emptystring$; \\
523 \FOREACH $l\colon z$ \FROM $y$ \DO \\
524 \quad $x \gets x \cat E_K^{-1}(z)$; \\
525 \RETURN $x$;
526 \end{program}
527 \end{slide}
529 \begin{slide}
530 \head{Electronic Code Book (ECB), 2: analysis}
532 ECB fails to disguise equality of message blocks. Hence, it is insecure in
533 the left-or-right sense.
534 \begin{program}
535 Adversary $A^{E(\cdot, \cdot)}$: \+ \\
536 $y \gets E(0^l \cat 1^l, 0^l \cat 0^l)$; \\
537 \PARSE $y$ \AS $l\colon y_0, l\colon y_1$; \\
538 \IF $y_0 = y_1$ \THEN \RETURN $1$; \\
539 \ELSE \RETURN $0$;
540 \end{program}
541 Since $\Xid{\mathcal{E}}{ECB}^E$ always encrypts blocks independently, and
542 the block cipher $E$ is deterministic, $A$ always succeeds. Hence,
543 $\InSec{lor-cpa}(\Xid{\mathcal{E}}{ECB}^E; t, 1, 2 l) = 1$
544 for some small $t$ describing the running-time of the adversary $A$.
546 According to our formal definitions, then, ECB mode is \emph{completely
547 insecure}.
548 \end{slide}
550 \begin{slide}
551 \topic{stateful counter mode}
552 \head{Counter (CTR), 1: a stateful mode}
554 We define two schemes. Firstly, a stateful-sender scheme
555 $\Xid{\mathcal{E}}{CTRS}^E = (\Xid{E}{CTRS}^E, \Xid{D}{CTRS}^E))$. We set
556 $\keys\Xid{\mathcal{E}}{ECB}^E = \{0, 1\}^k$, initialize $i \gets 0$, and
557 define
558 \begin{program}
559 Algorithm $\Xid{E}{CTRS}^E_K(x)$: \+ \\
560 $y \gets i$; \\
561 \FOREACH $l\colon z$ \FROM $x$ \DO \\ \quad \= \+ \kill
562 $y \gets y \cat (z \xor E_K(i))$; \\
563 $i \gets i + 1$; \- \\
564 \RETURN $y$;
565 \next
566 Algorithm $\Xid{D}{CTRS}^E_K(y)$: \+ \\
567 \PARSE $y$ \AS $l\colon i, y$; \\
568 $x \gets \emptystring$; \\
569 \FOREACH $l\colon z$ \FROM $y$ \DO \\ \quad \= \+ \kill
570 $x \gets x \cat (z \xor E_K(i))$; \\
571 $i \gets i + 1$; \- \\
572 \RETURN $x$;
573 \end{program}
574 \end{slide}
576 \begin{slide}
577 \head{Counter (CTR), 2: analysis of the stateful version}
579 We write $q' = q\mu/l$ for the total number of blocks queried by the
580 adversary, and we restrict our attention to the case $n \le 2^l$.
582 Firstly, suppose that, rather than a block cipher, we use a completely
583 random function $R \in \Func{l}{l}$. Then $E(0) \cat E(1) \cat \cdots$ is
584 a string of uniformly distributed and independent bits. Hence
585 $\InSec{lor-cpa}(\Xid{\mathcal{E}}{CTRS}^{\Func{l}{l}}; t, q, \mu) = 0$
586 for arbitrary $t$, and for $q \mu/l \le 2^l$.
588 A simple reduction shows that, for a pseudorandom function $F$, we have
589 $\InSec{ror-cpa}(\Xid{\mathcal{E}}{CTRS}^F; t, q, \mu) \le 590 \InSec{prf}(F; t, q'),$%
591 and hence, for a pseudorandom permutation $E$,
592 $\InSec{ror-cpa}(\Xid{\mathcal{E}}{CTRS}^E; t, q, \mu) \le 593 \InSec{prp}(E; t, q') + \frac{q'(q' - 1)}{2^{l+1}}.$%
594 \end{slide}
596 \begin{exercise}
597 Fill in the gaps in the above proof.
599 The reduction from the PRF distinguisher to the counter-with-PRF scheme
600 works as follows. Let $A$ attack $\Xid{\mathcal{E}}{CTRS}^F$ in the ROR
601 sense; consider adversary $B^{F(\cdot)}$: \{ $b \gets 602 A^{\Xid{E}{CTRS}^F(\cdot)}$; \RETURN $b$;~\}. If $F(\cdot)$ is an instance
603 of the PRF then $B$ encrypts messages chosen by $A$ faithfully; if
604 $F(\cdot)$ is a random function then the ciphertexts $B$ returns consists
605 of a counter followed by a random string, which is therefore distributed
606 identically to a ciphertext of a \emph{random} plaintext. Thus, $B$
607 simulates the real-or-random game perfectly. The result for a PRP follows
608 because $\InSec{prf}(F; t, q) \le \InSec{prp}(F; t, q) + q(q - 1) 609 2^{-L-1}$.
610 \end{exercise}
612 \begin{slide}
613 \topic{randomized counter mode}
614 \head{Counter (CTR), 3: a randomized mode}
616 The randomized scheme $\Xid{\mathcal{E}}{CTR$\$$}^E = (\Xid{E}{CTR\$$}^E,
617 \Xid{D}{CTR$\$$}^E)) differs from the stateful scheme in the encryption 618 algorithm only. We simply choose the starting value for the counter at 619 random, rather than remembering it. 620 \begin{program} 621 Algorithm \Xid{E}{CTR\$$}^E_K(x)$: \+ \\
622 $i \getsr \{0, 1\}^l$; \\
623 $y \gets i$; \\
624 \FOREACH $l\colon z$ \FROM $x$ \DO \\ \quad \= \+ \kill
625 $y \gets y \cat (z \xor E_K(i))$; \\
626 $i \gets i + 1$; \- \\
627 \RETURN $y$;
628 \next
629 Algorithm $\Xid{D}{CTR$\}^E_K(y)$: \+ \\ 630 \PARSE$y$\AS$l\colon i, y$; \\ 631$x \gets \emptystring$; \\ 632 \FOREACH$l\colon z$\FROM$y$\DO \\ \quad \= \+ \kill 633$x \gets x \cat (z \xor E_K(i))$; \\ 634$i \gets i + 1$; \- \\ 635 \RETURN$x$; 636 \end{program} 637 \end{slide} 639 \begin{slide} 640 \head{Counter (CTR), 4: analysis of the randomized version} 642 The randomized mode remains secure so long as a counter is never repeated. 643 This occurs with probability no greater than 644 $\frac{q\mu(q - 1)}{2^{l+1}}.$ 645 Hence, we have, for a pseudorandom function$F$, 646 $\InSec{ror-cpa}(\Xid{\mathcal{E}}{CTR\}^F; t, q, \mu) \le 647 \InSec{prf}(F; t, q') + \frac{q\mu(q - 1)}{2^{l+1}},$% 648 and, for a pseudorandom permutation$E$, 649 $\InSec{ror-cpa}(\Xid{\mathcal{E}}{CTR\}^E; t, q, \mu) \le 650 \InSec{prp}(E; t, q') + \frac{q'(q' - 1 + l(q - 1))}{2^{l+1}}.$% 651 \end{slide} 653 \begin{proof}[Proof of the collision bound] 654 Suppose all of the queries are maximum length. Then the probability that 655 two randomly started counter sequences overlap is$\mu\cdot 2^{-l}$. 656 Hence, an upper bound on the collision probability is given by 657 \begin{eqnarray*}[rl] 658 \Pr[\text{no collision}] &\le \frac{\mu}{2^l}(1 + 2 + \cdots + q - 1) \\ 659 &= \frac{\mu}{2^l} \frac{q(q - 1)}{2} \\ 660 &= \frac{q\mu(q - 1)}{2^{l+1}} 661 \end{eqnarray*} 662 as required. 663 \end{proof} 665 \begin{slide} 666 \topic{CBC} 667 \head{Ciphertext Block Chaining (CBC), 1: description} 669 We define the scheme$\Xid{\mathcal{E}}{CBC}^E = (\Xid{E}{CBC}^E,
670 \Xid{D}{CBC}^E))$by setting$\keys\Xid{\mathcal{E}}{CBC}^E = \{0, 1\}^k$671 and 672 \begin{program} 673 Algorithm$\Xid{E}{CBC}^E_K(x)$: \+ \\ 674$i \getsr \{0, 1\}^l$; \\ 675$y \gets i$; \\ 676 \FOREACH$l\colon z$\FROM$x$\DO \\ \quad \= \+ \kill 677$i \gets E_K(z \xor i)$; \\ 678$y \gets y \cat i$; \- \\ 679 \RETURN$y$; 680 \next 681 Algorithm$\Xid{D}{CBC}^E_K(y)$: \+ \\ 682 \PARSE$y$\AS$l\colon i, y$; \\ 683$x \gets \emptystring$; \\ 684 \FOREACH$l\colon z$\FROM$y$\DO \\ \quad \= \+ \kill 685$x \gets x \cat (i \xor E_K^{-1}(z))$; \\ 686$i \gets z$; \- \\ 687 \RETURN$x$; 688 \end{program} 689 \end{slide} 691 \begin{slide} 692 \head{Ciphertext Block Chaining (CBC), 2: analysis} 694 As before, we set$q' = q\mu/l$as the number of blocks queried by an 695 adversary attacking the encryption scheme. 697 As if by magic,\footnote{% 698 The proof of this result is omitted. The interested reader is directed 699 towards \cite{Bellare:2000:CST}.} % 700 we have the result 701 $\InSec{ror-cpa}(\Xid{\mathcal{E}}{CBC}^E; t, q, \mu) \le 702 \frac{q'(q' - 1)}{2^l}.$% 703 \end{slide} 705 \begin{slide} 706 \topic{requirement for random IVs in CBC mode} 707 \head{Ciphertext Block Chaining (CBC), 3: on randomness of IVs} 709 The initialization vector used in CBC encryption must be \emph{a priori} 710 unpredictable to the adversary. Suppose that$P(i)$, given an IV for a 711 ciphertext, can predict the IV which will be used with the next ciphertext 712 with probability$\epsilon$. Then we construct this adversary, attacking 713$\Xid{\mathcal{E}}{CBC}$in the ROR-CPA sense: 714 \begin{program} 715 Adversary$A^{E(\cdot)}$: \+ \\ 716$y \gets E(0^l)$; \PARSE$y$\AS$l\colon i, z$; \\ 717$j \gets P(y)$;$y' \gets E(j)$; \PARSE$y'$\AS$l\colon i', z'$; \\ 718 \IF$i' = j \land y = y'$\THEN \RETURN$1$; \\ 719 \ELSE \RETURN$0$; 720 \end{program} 721 The adversary succeeds when it guesses the IV correctly, \emph{except} when 722 the random encryption oracle happens to choose the same plaintext as we 723 wanted to encrypt anyway. So, therefore, 724 $\Adv{ror-cpa}{\Xid{\mathcal{E}}{CBC}^E} \ge \epsilon - 2^{-l}.$ 725 \end{slide} 727 \xcalways\subsection{Chosen-ciphertext security for symmetric encryption}\x 729 \begin{exercise} 730 Show that CTR and CBC modes are not secure against adaptive 731 chosen-ciphertext attacks. 732 \answer% 733 We use the FTG-CCA2 notion. For CTR mode: \cookie{find}: \RETURN$(0, 1,
734 \bot)$; \cookie{guess}:$y' \gets D(y \xor 0^L1)$; \RETURN$y' \xor 1$; 735 For CBC mode: same find stage,$y' \gets D(y \xor 1)$; \RETURN$y' \xor 1$; 736 \end{exercise} 738 \begin{slide} 739 \topic{integrity of ciphertexts} 740 \head{Integrity of ciphertexts \cite{Bellare:2000:AER}} 742 Informally, we say that an encryption scheme$\mathcal{E} = (E, D)$has 743 \emph{integrity of ciphertexts} (whose confusing short name is INT-CTXT) if 744 it's hard for an adversary equipped with an encryption oracle to come with 745 a new \emph{valid} ciphertext, i.e., one for which the decryption function 746$D_K$does not return the symbol$\bot$. 748 We shall see later that integrity of ciphertexts \emph{and} 749 indistinguishability under chosen-plaintext attacks together imply 750 chosen-ciphertext security. This is intuitively clear, but it's worth 751 proving anyway. 752 \end{slide} 754 \begin{slide} 755 \head{Integrity of ciphertexts (cont.)} 757 Consider the following game played by an adversary$A$: 758 \begin{program} 759 Experiment$\Expt{int-ctxt}{\mathcal{E}}(A)$: \+ \\ 760$K \getsr \keys\mathcal{E}$;$\Xid{y}{list} \gets \emptyset$; 761$y \gets A^{\id{encrypt}(\cdot), D_K(\cdot)}$; \\ 762 \IF$y \notin \Xid{y}{list} \land D_K(y) \ne \bot$763 \THEN \RETURN$1$; \\ 764 \ELSE \RETURN$0$; 765 \next 766 Oracle$\id{encrypt}(x)$: \+ \\ 767$y \gets E_K(x)$; \\ 768$\Xid{y}{list} \gets \Xid{y}{list} \cup \{y\}$; \\ 769 \RETURN$y$; 770 \end{program} 771 We define$A$'s success probability in this game by 772 $\Succ{int-ctxt}{\mathcal{E}}(A) = 773 \Pr[\Expt{int-ctxt}{\mathcal{E}}(A) = 1]$% 774 and write that 775 $\InSec{int-ctxt}(\mathcal{E}; t, q_E, q_D) = 776 \max_A \Succ{int-ctxt}{\mathcal{E}}(A),$% 777 where the maximum is over all adversaries running in time$t$and issuing 778$q_E$encryption and$q_D$decryption queries. 779 \end{slide} 781 \begin{slide} 782 \topic{INT-CTXT and LOR-CPA imply LOR-CCA} 783 \head{INT-CTXT and LOR-CPA together imply LOR-CCA} 785 We now prove the claim made earlier. Suppose that the adversary$A$786 attacks$\mathcal{E}$in the LOR-CCA sense. We consider these two 787 adversaries, attacking the chosen-plaintext security and ciphertext 788 integrity of$\mathcal{E}$respectively. 789 \begin{program} 790 Adversary$B^{E(\cdot, \cdot)}$: \+ \\ 791$b \gets A^{E(\cdot, \cdot), \Xid{D}{sim}(\cdot)}$; \\ 792 \RETURN$b$; \- \$\smallskipamount] 793 Oracle \Xid{D}{sim}(y); \+ \\ 794 \RETURN \bot; 795 \next 796 Adversary C^{E(\cdot), D(\cdot)}: \+ \\ 797 b \getsr \{0, 1\}; y^* \gets \bot; \\ 798 b' \gets A^{E(\id{lr}_b(\cdot, \cdot)), \Xid{D}{sim}(\cdot)}; \\ 799 \RETURN y^*; \- \\[\smallskipamount] 800 Function \id{lr}_b(x_0, x_1): \+ \\ 801 \RETURN x_b; \- \\[\smallskipamount] 802 Oracle \Xid{D}{sim}(y): \+ \\ 803 x \gets D(y); \\ 804 \IF x \ne \bot \THEN y^* \gets y; \\ 805 \RETURN x; 806 \end{program} 807 \end{slide} 809 \begin{slide} 810 \head{INT-CTXT and LOR-CPA together imply LOR-CCA2 (cont.)} 812 We analyse the advantage of B, attacking \mathcal{E} in the LOR-CPA 813 sense. Obviously, B is lying through its teeth in its simulation of 814 A's decryption oracle. If in fact all of A's decryption queries were 815 for invalid ciphertexts, B can't notice. So let V be the event that at 816 least one of A's ciphertexts was valid. Then 817 \[ \Adv{lor-cpa}{\mathcal{E}}(A) \ge 818 \Adv{lor-cca}{\mathcal{E}}(A) - 2\Pr[V].$% 819 To bound$\Pr[V]$, we consider adversary$C$, which simply records any of 820$A$'s decryption queries which returns a valid ciphertext. Since$A$is 821 forbidden from passing any ciphertexts obtained from its encryption oracle 822 to its decryption oracle,$C$'s returned ciphertext$y^*$is not one it 823 obtained from \emph{its} encryption oracle. So 824 $\Succ{int-ctxt}{\mathcal{E}}(A) = \Pr[V].$ 825 Concluding, then, 826 $\InSec{lor-cca}(\mathcal{E}; t, q_E, q_D) \le 827 \InSec{lor-cpa}(\mathcal{E}; t, q_E) + 828 2 \cdot \InSec{int-ctxt}(\mathcal{E}; t, q_E, q_D).$% 829 \end{slide} 831 \begin{slide} 832 \topic{strong MACs provide INT-CTXT} 833 \head{A strong MAC provides integrity of ciphertexts} 835 That's a very nice result, but how do we acheive INT-CTXT? Well, the 836 game in the definition looks very much like the forgery games we played 837 when we were thinking about MACs. 839 Suppose that$\mathcal{E} = (E, D)$is an encryption scheme secure in the 840 LOR-CPA sense, and$\mathcal{M} = (T, V)$is a strong MAC (in the SUF-CMA 841 sense). Then we can define$\Xid{\mathcal{E}}{auth}^{\mathcal{M}} =
842 (\Xid{E}{auth}^{\mathcal{E}, \mathcal{M}}, \Xid{D}{auth}^{\mathcal{E},
843 \mathcal{M}})$by 844 $\keys\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}} = 845 \keys\mathcal{E} \times \keys\mathcal{M}$% 846 and 847 \begin{program} 848 Algorithm 849$\Xid{E}{auth}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(x)$: \+ \\ 850$y \gets E_{K_E}(x)$; \\ 851$\tau \gets T_{K_T}(y)$; \\ 852 \RETURN$\tau \cat y$; 853 \next 854 Algorithm 855$\Xid{D}{auth}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(y')$: \+ \\ 856 \PARSE$y'$\AS$\tau, y$; \\ 857 \IF$V_{K_T}(y, \tau) = 0$\THEN \RETURN$\bot$; \\ 858 \ELSE \RETURN$D_{K_E}(y)$; 859 \end{program} 860 \end{slide} 862 \begin{slide} 863 \head{A strong MAC provides integrity of ciphertexts (cont.)} 865 The security proof for$\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}$866 is left as a trivial exercise. We end up with the result that 867 $\InSec{int-ctxt}(\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}; 868 t, q_E, q_D) \le 869 \InSec{suf-cma}(\mathcal{M}; t, q_E, q_D)$% 870 and hence 871 \begin{eqnarray*}[Ll] 872 \InSec{lor-cca}(\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}; 873 t, q_E, q_D) \\ 874 & \le \InSec{lor-cpa}(\mathcal{E}; t, q_E) + 875 2 \cdot \InSec{suf-cma}(\mathcal{M}; t, q_E, q_D). 876 \end{eqnarray*} 877 A MAC, therefore, can help us to attain a strong notion of secrecy, even if 878 no actual integrity appears to be required. This is an important lesson. 879 \end{slide} 881 \begin{exercise} 882 Prove the above result. 883 \answer% 884 Let$A$attack INT-CTXT. Construct adversary$B^{T(\cdot), V(\cdot)}$: \{ 885$K \getsr \keys\mathcal{E}$;$(y, \tau) \gets A^{\id{encrypt}(\cdot),
886 \id{decrypt}(\cdot)}$; \RETURN$(y, \tau)$;~\} Oracle$\id{encrypt}(x)$: 887 \{$y \gets E_K(x)$;$\tau \gets T(y)$; \RETURN$(y, \tau)$;~\} Oracle 888$\id{decrypt}(y, \tau)$: \{ \IF$V(y, \tau) = 1$\THEN \RETURN$D_K(y)$; 889 \ELSE \RETURN$\bot$;~\}. The simulation of the INT-CTXT game is perfect. 890 \end{exercise} 892 \begin{slide} 893 \topic{mixing encryption and MACs} 894 \head{Notes on mixing encryption and MACs} 896 To construct$\Xid{\mathcal{E}}{auth}^{\mathcal{E}, \mathcal{M}}$, we 897 applied a MAC to the \emph{ciphertext}. This isn't perhaps the most 898 intuitive way to combine an encryption scheme with a MAC. 900 There are three constructions which look plausible. 901 \begin{description} 902 \item[Encrypt-then-MAC:] 903 % 904$y \gets E_{K_E}(x)$;$\tau \gets T_{K_T}(y)$; \RETURN$\tau \cat y$; 905 \\ 906 Encrypt the plaintext, and MAC the ciphertext; used in IPsec and nCipher 907 Impath; we've proven its generic security, using the notion of integrity 908 of ciphertexts. 909 % 910 \item[MAC-then-encrypt:] 911 % 912$\tau \gets T_{K_T}(x)$;$y \gets E_{K_E}(\tau \cat x)$; \RETURN$y$; 913 \\ 914 MAC the plaintext, and encrypt both the plaintext and tag; used in SSL 915 and TLS; not \emph{generically} secure against chosen-ciphertext attacks. 916 % 917 \item[Encrypt-and-MAC:] 918 % 919$y \gets E_{K_E}(x)$;$\tau \gets T_{K_T}(x)$; \RETURN$\tau \cat y$; 920 \\ 921 Separately MAC and encrypt the plaintext; used in SSH; \emph{never} 922 secure against chosen-ciphertext, not generically secure against 923 chosen-plaintext! 924 \end{description} 925 \end{slide} 927 \begin{proof} 928 We begin with a few words on our approach, before we embark on the proof 929 proper. 931 To demonstrate the generic insecurity of a scheme, we assume the existance 932 of an encryption scheme and MAC (since if they don't exist, the result is 933 vacuously true) and construct modified schemes whose individual security 934 relates tightly to the originals, but the combined scheme is weak. 936 We demonstrate \emph{universal} insecurity by showing an attack which works 937 given \emph{any} component encryption and MAC schemes. 939 We prove security relationships using the LOR-CPA notion because this is 940 strongest, and bounds for other notions can be derived readily from the 941 left-or-right analysis. We prove insecurity using the FTG-CCA or FTG-CPA 942 notions, because they are weakest and show the strength of our results 943 best. 945 We've dealt with the generic security of encrypt-then-MAC already. We turn 946 our attention first first to the generic insecurity of the MAC-then-encrypt 947 scheme. 949 Let$\mathcal{E} = (E, D)$be a symmetric encryption scheme, and let 950$\mathcal{M} = (T, V)$be a MAC. We define the MAC-then-encrypt scheme 951$\Xid{\mathcal{E}}{MtE}^{\mathcal{E}, \mathcal{M}} =
952 (\Xid{E}{MtE}^{\mathcal{E}, \mathcal{M}}, \Xid{D}{MtE}^{\mathcal{E},
953 \mathcal{M}})$as follows: 954 $\keys\Xid{\mathcal{E}}{MtE}^{\mathcal{E}, \mathcal{M}} = 955 \keys\mathcal{E} \times \keys\mathcal{M}$% 956 and 957 \begin{program} 958 Algorithm 959$\Xid{E}{MtE}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(x)$: \+ \\ 960$\tau \gets T_{K_T}(x)$; \\ 961$\RETURN E_{K_E}(\tau \cat x)$; 962 \next 963 Algorithm 964$\Xid{D}{MtE}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(y)$: \+ \\ 965$x' \gets D_{K_E}(y)$; \\ 966 \PARSE$x'$\AS$\tau, x$; \\ 967 \IF$V_{K_T}(x, \tau) = 0$\THEN \RETURN$\bot$; \\ 968 \ELSE \RETURN$x$; 969 \end{program} 970 We construct a new encryption scheme$\mathcal{E}' = (E', D')$in terms of 971$\mathcal{E}$, such that the combined scheme 972$\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$is insecure in the 973 FTG-CCA sense. Our modified encryption scheme has$\keys\mathcal{E}' =
974 \keys\mathcal{E}$, and works as follows: 975 \begin{program} 976 Algorithm$E'_K(x)$: \+ \\ 977 \RETURN$0 \cat E_K(x)$; 978 \next 979 Algorithm$D'_K(y')$: \+ \\ 980 \PARSE$y'$\AS$1\colon b, y$; \\ 981 \RETURN$D_K(y)$; 982 \end{program} 983 That is, the encryption scheme prepends a single bit to the ciphertext, and 984 doesn't check its value during decryption. Intuitively, this makes the 985 scheme malleable: we can change the ciphertext by flipping the first bit, 986 but the MAC tag remains valid because the plaintext is unaffected. 988 Firstly, we prove that$\mathcal{E}'$is LOR-CPA if$\mathcal{E}$is. 989 Suppose$A'$attacks$\mathcal{E}'$in the LOR-CPA sense: then 990 \begin{program} 991 Adversary$A^{E(\cdot, \cdot)}$: \+ \\ 992 \RETURN$A'^{0 \cat E(\cdot, \cdot)}$; 993 \end{program} 994 has the same advantage. 996 Secondly, we show that the combined MAC-then-encrypt scheme 997$\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}$is insecure in the 998 FTG-CCA sense. Consider this adversary: 999 \begin{program} 1000 Adversary$B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\ 1001 \RETURN$(0, 1, \bot)$; 1002 \next 1003 Adversary$B^{E(\cdot), D(\cdot)}(\cookie{guess}, y', s)$: \+ \\ 1004 \PARSE$y'$\AS$1\colon b, y$; \\ 1005 \RETURN$D(1 \cat y)$; 1006 \end{program} 1007 The ciphertext$1 \cat y$was never returned by the encryption oracle 1008 (because it always returns the first bit zero); but the plaintext of$1
1009 \cat y$is the challenge plaintext. Hence,$B$wins always, and 1010 $\InSec{ftg-cca}(\Xid{\mathcal{E}}{MtE}^{\mathcal{E}', \mathcal{M}}; 1011 t, 0, 1) = 1,$% 1012 where$t$is the running time of the adversary$B$above. 1014 We now address the separate encrypt-and-MAC scheme, which we define 1015 formally. Let$\mathcal{E} = (E, D)$be a symmetric encryption scheme, and 1016 let$\mathcal{M} = (T, V)$be a MAC. Then the the encrypt-and-MAC scheme 1017$\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}} =
1018 (\Xid{E}{E\&M}^{\mathcal{E}, \mathcal{M}}, \Xid{D}{E\&M}^{\mathcal{E},
1019 \mathcal{M}})$is defined by: 1020 $\keys\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}} = 1021 \keys\mathcal{E} \times \keys\mathcal{M}$% 1022 and 1023 \begin{program} 1024 Algorithm 1025$\Xid{E}{E\&M}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(x)$: \+ \\ 1026$y \gets E_{K_E}(x)$; \\ 1027$\tau \gets T_{K_T}(x)$; \\ 1028$\RETURN \tau \cat y$; 1029 \next 1030 Algorithm 1031$\Xid{D}{E\&M}^{\mathcal{E}, \mathcal{M}}_{K_E, K_T}(y')$: \+ \\ 1032 \PARSE$y'$\AS$\tau, y$; \\ 1033$x \gets D_{K_E}(y)$; \\ 1034 \IF$V_{K_T}(x, \tau) = 0$\THEN \RETURN$\bot$; \\ 1035 \ELSE \RETURN$x$; 1036 \end{program} 1038 We first show that this scheme is \emph{universally} insecure against 1039 chosen-ciphertext attack. Let$\mathcal{E}$and$\mathcal{M}$be an 1040 arbitrary symmetric encryption scheme and MAC, respectively. The attack 1041 works because the MACs can be detached and used in chosen-ciphertext 1042 queries to test for equality of messages. 1043 \begin{program} 1044 Adversary$B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\ 1045 \RETURN$(0, 1, \bot)$; 1046 \next 1047 Adversary$B^{E(\cdot), D(\cdot)}$(\cookie{guess}, y', s): \+ \\ 1048$y_1' \gets E(1)$; \\ 1049 \PARSE$y'$\AS$\tau, y$; \\ 1050 \PARSE$y_1'$\AS$\tau_1, y_1$; \\ 1051 \IF$\tau = \tau_1 \lor D(\tau \cat y_1) \ne \bot$1052 \THEN \RETURN$1$; \\ 1053 \ELSE \RETURN$0$; 1054 \end{program} 1055 After receiving the challenge ciphertext, the adversary requests an 1056 additional encryption of the plaintext$1$. If the tags are equal on the 1057 two ciphertexts then we announce that the hidden bit is$1$. Otherwise, we 1058 attempt a decryption of the new ciphertext, using the tag from the 1059 challenge. If it decrypts successfully, we announce that the bit is$1$; 1060 otherwise we claim it is zero. 1062 Certainly, this strategy is always correct when the hidden bit is indeed 1063$1$. However, there is a possibility that the MACs are equal or verify 1064 correctly even when the hidden bit is$0$. To bound this probability, we 1065 construct the following simple adversary against the MAC: 1066 \begin{program} 1067 Adversary$B'^{T(\cdot), V(\cdot)}$: \+ \\ 1068$\tau \gets T(1)$; \\ 1069 \RETURN$(0, \tau)$; 1070 \end{program} 1071 We see readily that 1072 $\InSec{ftg-cca}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}}; 1073 t, 1, 1) \ge 1074 1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0),$% 1075 where$t$and$t'$are the running times of adversaries$B$and$B'$1076 respectively. 1078 Finally, we show that the encrypt-and-MAC scheme is generically insecure 1079 against chosen-plaintext attacks only. There are two strategies we could 1080 use. Since both offer useful insights into the properties of MACs, we 1081 present both here. 1082 \begin{itemize} 1084 \item \emph{Deterministic MACs.} In the proof of the universal weakness of 1085 the encrypt-and-MAC scheme, we used the check on the MAC to decide on the 1086 equality of two plaintexts given the ciphertexts. If the MAC is 1087 deterministic (e.g., a PRF) then we don't need a decryption query. 1089 Let$\mathcal{E} = (E, D)$be a symmetric cipher, and let$\mathcal{M} =
1090 (T, V)$be a deterministic MAC, e.g., a PRF, or HMAC. Then consider this 1091 adversary: 1092 \begin{program} 1093 Adversary$B^{E(\cdot)}(\cookie{find})$: \+ \\ 1094 \RETURN$(0, 1, \bot)$; 1095 \next 1096 Adversary$B^{E(\cdot)}(\cookie{guess}, y', s)$: \+ \\ 1097$y_1' \gets E(1)$; \\ 1098 \PARSE$y'$\AS$\tau, y$; \\ 1099 \PARSE$y_1'$\AS$\tau_1, y_1$; \\ 1100 \IF$\tau = \tau_1$\THEN \RETURN$1$; \\ 1101 \ELSE \RETURN$0$; 1102 \end{program} 1103 Since the MAC is deterministic, the tag attached to a ciphertext$1$is 1104 always the same. We bound the probability that$T_K(0) = T_K(1)$using 1105 the adversary$B'$above, and conclude that 1106 $\InSec{ftg-cpa}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}}; 1107 t, 1) \ge 1108 1 - \InSec{suf-cma}(\mathcal{M}; t', 1, 0),$% 1109 where$t$and$t'$are the running times of adversaries$B$and$B'$1110 respectively. 1112 \item \emph{Leaky MACs.} A MAC doesn't have to conceal information about 1113 messages. Suppose$\mathcal{M} = (T, V)$is a secure MAC. We define the 1114 leaky MAC$\mathcal{M}' = (T', V')$by stating that$\keys\mathcal{M}' =
1115 \keys\mathcal{M}''$and 1116 \begin{program} 1117 Algorithm$T'_K(x)$: \+ \\ 1118 \PARSE$x$\AS$1\colon x_0, z$; \\ 1119 \RETURN$x_0 \cat T_K(x)$; 1120 \next 1121 Algorithm$V'_K(x, \tau')$: \+ \\ 1122 \PARSE$\tau'$\AS$1\colon \tau_0, \tau$; \\ 1123 \PARSE$x$\AS$1\colon x_0, z$; \\ 1124 \IF$x_0 \ne \tau_0$\THEN \RETURN$0$; \\ 1125 \ELSE \RETURN$V_K(x, \tau)$; 1126 \end{program} 1127 We must first prove that$\mathcal{M}'$remains secure. To do this, 1128 consider an adversary$A'$attacking$\mathcal{M}'$. We construct$A$1129 attacking$\mathcal{M}$in the obvious way: 1130 \begin{program} 1131 Algorithm$A^{T(\cdot), V(\cdot)}$: \\ 1132$(x', \tau') \gets
1133 A'^{\Xid{T'}{sim}(\cdot), \Xid{V'}{sim}(\cdot)}$; \\ 1134 \PARSE$\tau'$\AS$1\colon \tau_0, \tau$; \\ 1135 \RETURN$(x, \tau)$; 1136 \next 1137 Oracle$\Xid{T'}{sim}(x)$: \+ \\ 1138 \PARSE$x$\AS$1\colon x_0, z'$; \\ 1139 \RETURN$x_0 \cat T(x)$; \- \$\smallskipamount] 1140 Oracle \Xid{V'}{sim}(x, \tau'): \+ \\ 1141 \PARSE \tau' \AS 1\colon \tau_0, \tau; \\ 1142 \PARSE x \AS 1\colon x_0, z; \\ 1143 \IF x_0 \ne \tau_0 \THEN \RETURN 0; \\ 1144 \ELSE \RETURN V(x, \tau); 1145 \end{program} 1146 Here, A simply simulates the environment expected by A'. It is clear 1147 that A succeeds whenver A' returns a valid tag for a \emph{new} 1148 message. However, suppose that A' returns a new tag \tau' for some 1149 old message x, for which the tag \tau was returned by the tagging 1150 oracle. Let x_0, \tau_0 and \tau'_0 be the first bits of x, 1151 \tau and \tau' respectively, and let \tau^* be the remaining bits 1152 of \tau'. If the pair (x, \tau') is to be a valid 1153 \mathcal{M}'-forgery, we must have x_0 = \tau_0 = \tau'_0. Hence, 1154 \tau and \tau' must differ in at least one other bit, and (x, 1155 \tau^*) is a valid \mathcal{M}-forgery. We conclude that 1156 \[ \InSec{suf-cma}(\mathcal{M}'; t, q_T, q_V) \le 1157 \InSec{suf-cma}(\mathcal{M}; t, q_T, q_V)$% 1158 as required. 1160 Now we show that the combined encrypt-and-MAC scheme is weak in the 1161 FTG-CPA sense. Consider this adversary attacking the scheme: 1162 \begin{program} 1163 Adversary$B^{E(\cdot), D(\cdot)}(\cookie{find})$: \+ \\ 1164 \RETURN$(0, 1, \bot)$; 1165 \next 1166 Adversary$B^{E(\cdot), D(\cdot)}$(\cookie{guess}, y', s): \+ \\ 1167 \PARSE$y'$\AS$\tau, y$; \\ 1168 \PARSE$\tau$\AS$1\colon b, \tau^*$; \\ 1169 \RETURN$b$; 1170 \end{program} 1171 The leaky MAC simply tells us the right answer. So 1172 $\InSec{ftg-cpa}(\Xid{\mathcal{E}}{E\&M}^{\mathcal{E}, \mathcal{M}'}; 1173 t, 0) = 1,$% 1174 where$t$is the running time of adversary$B\$ above.
1176 \end{itemize}
1178 This concludes the proof.
1179 \end{proof}
1181 %% TO DO: Include stuff about integrity-aware encryption modes some day.
1183 \endinput
1185 %%% Local Variables:
1186 %%% mode: latex
1187 %%% TeX-master: "ips"
1188 %%% End: