e0f3f010720f29c32bfd42c16b04a671b3088331
[doc/ips] / enc-symm.tex
1 \xcalways\section{Symmetric encryption}\x
2
3 \xcalways\subsection{Syntax}\x
4
5 \begin{slide}
6 \head{Symmetric encryption syntax}
7
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$.
20
21 We write $E_K(\cdot)$ rather than $E(K, \cdot)$, and $D_K(\cdot)$ rather
22 than $D(K, \cdot)$.
23 \end{slide}
24
25 \xcalways\subsection{Security notions}\x
26
27 \begin{slide}
28 \head{Symmetric encryption security notions}
29
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.
33
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.
37
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}
48
49 \begin{slide}
50 \topic{semantic security}
51 \head{Semantic security}
52
53 The semantic security game is as for the asymmetric case, except for the
54 presence of encryption oracles.
55
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}
71
72 \begin{slide}
73 \topic{find-then-guess}
74 \head{Find-then-guess indistinguishability}
75
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}
88
89 \begin{slide}
90 \topic{left-or-right}
91 \head{Left-or-right indistinguishability}
92
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}
110
111 \begin{slide}
112 \topic{real-or-random}
113 \head{Real-or-random indistinguishability}
114
115 The `real-or-random' (ROR) notion is somewhat less natural, but turns out
116 to be useful for analysing block cipher encryption modes.
117
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}
138
139 \begin{slide}
140 \topic{relations between notions}
141 \head{Relations between notions \cite{Bellare:2000:CST}}
142
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}}
151 \leftmargin\labelwidth\advance\leftmargin\labelsep
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}
164
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}
169
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). \]%
185
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). \]%
208
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). \]%
230
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.
233
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]. \]%
254
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]
269 \Adv{lor-\id{atk}}{\mathcal{E}}(A)
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). \]%
290
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
315 claimed advantage. Thus,
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). \]%
318
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}
340
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}
347
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}
379
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}
418 \answer%
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)$.
430
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.
443
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}
461
462 \xcalways\subsection{Block cipher modes}\x
463
464 \begin{slide}
465 \head{Block cipher modes}
466
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.
470
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}
484
485 \begin{slide}
486 \head{General notation}
487
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)$.
491
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}
500
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.
503
504 We use $\emptystring$ to denote the empty string.
505 \end{slide}
506
507 \begin{slide}
508 \topic{ECB}
509 \head{Electronic Code Book (ECB), 1: description}
510
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}
528
529 \begin{slide}
530 \head{Electronic Code Book (ECB), 2: analysis}
531
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$.
545
546 According to our formal definitions, then, ECB mode is \emph{completely
547 insecure}.
548 \end{slide}
549
550 \begin{slide}
551 \topic{stateful counter mode}
552 \head{Counter (CTR), 1: a stateful mode}
553
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}
575
576 \begin{slide}
577 \head{Counter (CTR), 2: analysis of the stateful version}
578
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$.
581
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$.
587
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}
595
596 \begin{exercise}
597 Fill in the gaps in the above proof.
598 \answer%
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}
611
612 \begin{slide}
613 \topic{randomized counter mode}
614 \head{Counter (CTR), 3: a randomized mode}
615
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}
638
639 \begin{slide}
640 \head{Counter (CTR), 4: analysis of the randomized version}
641
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}
652
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}
664
665 \begin{slide}
666 \topic{CBC}
667 \head{Ciphertext Block Chaining (CBC), 1: description}
668
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}
690
691 \begin{slide}
692 \head{Ciphertext Block Chaining (CBC), 2: analysis}
693
694 As before, we set $q' = q\mu/l$ as the number of blocks queried by an
695 adversary attacking the encryption scheme.
696
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}
704
705 \begin{slide}
706 \topic{requirement for random IVs in CBC mode}
707 \head{Ciphertext Block Chaining (CBC), 3: on randomness of IVs}
708
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}
726
727 \xcalways\subsection{Chosen-ciphertext security for symmetric encryption}\x
728
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}
737
738 \begin{slide}
739 \topic{integrity of ciphertexts}
740 \head{Integrity of ciphertexts \cite{Bellare:2000:AER}}
741
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$.
747
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}
753
754 \begin{slide}
755 \head{Integrity of ciphertexts (cont.)}
756
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}
780
781 \begin{slide}
782 \topic{INT-CTXT and LOR-CPA imply LOR-CCA}
783 \head{INT-CTXT and LOR-CPA together imply LOR-CCA}
784
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}
808
809 \begin{slide}
810 \head{INT-CTXT and LOR-CPA together imply LOR-CCA2 (cont.)}
811
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}
830
831 \begin{slide}
832 \topic{strong MACs provide INT-CTXT}
833 \head{A strong MAC provides integrity of ciphertexts}
834
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.
838
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}
861
862 \begin{slide}
863 \head{A strong MAC provides integrity of ciphertexts (cont.)}
864
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}
880
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}
891
892 \begin{slide}
893 \topic{mixing encryption and MACs}
894 \head{Notes on mixing encryption and MACs}
895
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.
899
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}
926
927 \begin{proof}
928 We begin with a few words on our approach, before we embark on the proof
929 proper.
930
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.
935
936 We demonstrate \emph{universal} insecurity by showing an attack which works
937 given \emph{any} component encryption and MAC schemes.
938
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.
944
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.
948
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.
987
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.
995
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.
1013
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}
1037
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.
1061
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.
1077
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}
1083
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.
1088
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.
1111
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.
1159
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.
1175
1176 \end{itemize}
1177
1178 This concludes the proof.
1179 \end{proof}
1180
1181 %% TO DO: Include stuff about integrity-aware encryption modes some day.
1182
1183 \endinput
1184
1185 %%% Local Variables:
1186 %%% mode: latex
1187 %%% TeX-master: "ips"
1188 %%% End: