forked from YuZhang/cryptography
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path3.2privatekey.tex
478 lines (476 loc) · 20.3 KB
/
3.2privatekey.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
\input{main.tex}
\title{Private-Key Encryption and Pseudorandomness (Part II)}
\begin{document}
\maketitle
\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}
\section{Stream Ciphers and Multiple Encryption}
\begin{frame}\frametitle{Security for Multiple Encryptions}
The multiple-message eavesdropping experiment $\mathsf{PrivK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
\item $\mathcal{A}$ is given input $1^n$, outputs $\vec{M}_0=(m_0^1,\dots,m_0^t)$, $\vec{M}_1=(m_1^1,\dots,m_1^t)$ with $\forall i, |m_0^i| = |m_1^i|$.
\item $k \gets \mathsf{Gen}(1^n)$, a random bit $b \gets \{0,1\}$ is chosen. Then $c^i \gets \mathsf{Enc}_k(m_b^i)$ and $\vec{C}=(c^1,\dots,c^t)$ is given to $\mathcal{A}$.
\item $\mathcal{A}$ outputs $b'$. If $b' = b$, $\mathsf{PrivK}^{\mathsf{mult}}_{\mathcal{A},\Pi}=1$, otherwise 0.
\end{enumerate}
\begin{figure}
\begin{center}
\input{tikz/multiple-enc-exp.tex}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Definition of Multi-Encryption Security}
\begin{definition}\label{def:sme}
$\Pi$ has \textbf{indistinguishable multiple encryptions in the presence of an eavesdropper} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PrivK}^{\mathsf{mult}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n).
\]
\end{definition}
\begin{alertblock}{Question:}
\begin{itemize}
\item Does any cipher we have learned so far have indistinguishable multiple encryptions in the presence of an eavesdropper?
\item Generally, if $\Pi$'s encryption function is \textbf{deterministic}, is $\Pi$ multiple-encryption-secure?
\end{itemize}
\end{alertblock}
%For the deterministic encryption, the adversary generates $m_0^1 = m_0^2$ and $m_1^1 \neq m_1^2$ and then outputs $b'=0$ if $c^1 = c^2$, otherwise $b'=1$.
\end{frame}
\begin{frame}\frametitle{Stream Ciphers}
\begin{itemize}
\item \textbf{Stream cipher}: Encrypting by XORing with pseudorandom stream
\item \textbf{State of the art}: No standardized and popular one\footnote{eStream project worked on it. Salsa20/12 is a promising candidate.}\\ Security is questionable, e.g., RC4 in WEP protocol in 802.11, Linear Feedback Shift Registers (LFSRs)
\end{itemize}
\begin{figure}
\begin{center}
\includegraphics[width=50mm]{pic/A5-1_GSM_cipher}
\end{center}
\end{figure}
\begin{alertblock}{WARNING}
Don't use any stream cipher. If necessary, construct one from a block cipher.
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{Secure Multiple Encryptions Using a Stream Cipher}
\begin{figure}
\begin{center}
\input{tikz/synchronizedmode}
\end{center}
\end{figure}
Initial vector $IV$ is chosen \emph{u.a.r} and public\\
\alert{Q: which mode is better in your opinion?}
\end{frame}
\begin{frame}\frametitle{Related Keys: Real World Cases}
Keys (the $IV$-key pair) for multiple enc. must be independent
\begin{exampleblock}{Attacks on 802.11b WEP}
Unsynchronized mode: $\mathsf{Enc}(m_i) := \left< IV_i, G(IV_i\|k) \oplus m_i\right>$\\
\begin{itemize}
\item Length of $IV$ is 24 bits, repeat $IV$ after $2^{24} \approx$ 16M frames
\item On some WiFi cards, $IV$ resets to $0$ after power cycle
\item $IV_i = IV_{i-1} + 1$. For RC4, recover $k$ after 40,000 frames
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Chosen-Plaintext Attacks (CPA)}
\textbf{CPA}: the adversary has the ability to obtain the encryption of plaintexts of its choice
\begin{exampleblock}{A story in WWII}
\begin{itemize}
\item Navy cryptanalysts believe the ciphertext ``AF'' means ``Midway island'' in Japanese messages
\item But the general did not believe that Midway island would be attacked
\item Navy cryptanalysts sent a plaintext that the freshwater supplies at Midway island were low
\item Japanese intercepted the plaintext and sent a ciphertext that ``AF'' was low in water
\item The US forces dispatched three aircraft carriers and won
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Security Against CPA}
The CPA indistinguishability experiment $\mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
\item $k \gets \mathsf{Gen}(1^n)$
\item $\mathcal{A}$ is given input $1^n$ and \textbf{oracle access} $\mathcal{A}^{\mathsf{Enc}_k(\cdot)}$ to $\mathsf{Enc}_k(\cdot)$, outputs $m_0, m_1$ of the same length
\item $b \gets \{0,1\}$. Then $c \gets \mathsf{Enc}_k(m_b)$ is given to $\mathcal{A}$
\item $\mathcal{A}$ \textbf{continues to have oracle access} to $\mathsf{Enc}_k(\cdot)$, outputs $b'$
\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}=1$, otherwise 0
\end{enumerate}
\begin{figure}
\begin{center}
\input{tikz/pri-cpa-exp.tex}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{CPA Security for Multiple Encryptions}
\begin{definition}\label{def:cap-ind}
$\Pi$ has \textbf{indistinguishable encryptions under a CPA (CPA-secure)} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PrivK}^{\mathsf{cpa}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n).
\]
\end{definition}
\begin{itemize}
\item \alert{Q: Is any cipher we have learned so far CPA-secure? Why?}
\end{itemize}
\begin{proposition}
Any private-key encryption scheme that is CPA-secure also is \textbf{multiple-encryption} CPA-secure.
\end{proposition}
\begin{itemize}
\item \alert{Q: Does \textbf{multiple-encryption-security} mean CPA-security?} (homework)
%\item \textbf{Fixed-length} CPA-secure encryption scheme can be used to construct a \textbf{arbitrary-length} CPA-secure one quite easily.
\end{itemize}
\end{frame}
\section{Constructing CPA-Secure Encryption Schemes}
\begin{frame}\frametitle{Concepts on Pseudorandom Functions}
\begin{figure}
\begin{center}
\input{tikz/keyed-func.tex}
\end{center}
\end{figure}
\begin{itemize}
\item \textbf{Keyed function} $F : \{0,1\}^* \times \{0,1\}^* \to \{0,1\}^*$ \\
$F_k : \{0,1\}^* \to \{0,1\}^*$, $F_k(x) \overset{\text{def}}{=} F(k,x)$
\item \textbf{Look-up table $f$}: $\{0,1\}^n \to \{0,1\}^n$ with size \alert{ = ? bits} %$n\cdot2^n$.
\item \textbf{Function family $\mathsf{Func}_n$}: all functions $\{0,1\}^n \to \{0,1\}^n$. $|\mathsf{Func}_n| = 2^{n\cdot2^n}$
\item \textbf{Length Preserving}: $\ell_{key}(n) = \ell_{in}(n) = \ell_{out}(n)$
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Definition of Pseudorandom Function}
\textbf{Intuition}: A PRF $F$ generates a function $F_k$ that is indistinguishable from truly random selected function $f$ (look-up table) in $\mathsf{Func}_n$.\\ However, the function has \textbf{exponential length}. Give $D$ the deterministic \textbf{oracle access $D^{\mathcal{O}}$} to the functions $\mathcal{O}$.
\begin{definition}
An efficient length-preserving, keyed function $F$ is a \textbf{pseudorandom function (PRF)} if
$\forall\;$ \textsc{ppt} distinguishers $D$,
\[ \left|\Pr[D^{F_k(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot)}(1^n)=1]\right| \le \mathsf{negl}(n),
\]
where $f$ is chosen \emph{u.a.r} from $\mathsf{Func}_n$.
\end{definition}
\begin{alertblock}{Q: Is the fixed-length OTP a PRF?}
\end{alertblock}
%\textbf{PRG vs. PRF}:
%\begin{itemize}
%\item Pseudorandomness over a set of strings vs. a set of functions.
%\item A PRG --- an instance of keyed PRF.
%\end{itemize}
%\textbf{Existence}: if PRG exists. In practice, block ciphers may be PRF.
\end{frame}
\begin{frame}\frametitle{Questions}
\begin{exampleblock}{Let $F: \{0,1\}^{n} \times \{0,1\}^{n} \to \{0,1\}^{n}$ be a secure PRF. Is $G$ a secure PRF?}
\begin{itemize}
\item $G((k_{1},k_{2}), x) = F(k_{1},x) \| F(k_{2},x)$
\item $G(k,x) = F(k, x\oplus 1^{n})$
\item $G(k,x) = reverse(F(k,x))$
\item $ G(k,x) = \left\{
\begin{array}{l l}
F(k,x) & \quad \text{when}\ x \neq 0^{n}\\
0^{n} & \quad \text{otherwise}\\
\end{array} \right. $
\item $ G(k,x) = \left\{
\begin{array}{l l}
F(k,x) & \quad \text{when}\ x \neq 0^{n}\\
k & \quad \text{otherwise}\\
\end{array} \right. $
\item $G(k,x) = F(k,x)\bigoplus F(k, x\oplus 1^{n})$
\end{itemize}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{CPA-Security from Pseudorandom Function}
\begin{columns}[t]
\begin{column}{4cm}
\begin{figure}
\begin{center}
\input{tikz/encryptionwithpf}
\end{center}
\end{figure}
\end{column}
\begin{column}{6cm}
\begin{construction}\label{thm:cpa}
\begin{itemize}
\item Fresh random string $r$.
\item $F_k(r)$: $\abs{k} = \abs{m} = \abs{r} = n$.
\item $\mathsf{Gen}$: $k \in \{0,1\}^n$.
\item $\mathsf{Enc}$: $s := F_k(r)\oplus m$, $c := \left<r, s\right>$.
\item $\mathsf{Dec}$: $m := F_k(r)\oplus s$.
\end{itemize}
\end{construction}
\begin{theorem}\label{thm:prf}
If $F$ is a PRF, this fixed-length encryption scheme $\Pi$ is CPA-secure.
\end{theorem}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Proof of CPA-Security from PRF}
\textbf{Idea}: First, analyze the security in an idealized world where $f$ is used in $\tilde{\Pi}$; next, claim that if $\Pi$ is insecure when $F_k$ was used then this would imply $F_k$ is not PRF by reduction.
\begin{proof}
(1) Analyze $\Pr[\mathsf{Break}]$, $\mathsf{Break}$ means $\mathsf{PrivK}_{\mathcal{A},\tilde{\Pi}}^{\mathsf{cpa}}(n) = 1$: \\
$\mathcal{A}$ collects $\{ \left< r_i, f(r_i) \right> \}$, $i=1,\dots,q(n)$ with $q(n)$ queries; \\
The challenge $c=\left<r_c, f(r_c)\oplus m_b\right>$. \\
\begin{itemize}
\item $\mathsf{Repeat}$: $r_c \in \{ r_i \}$ with probability $\frac{q(n)}{2^n}$. $\mathcal{A}$ can know $m_b$.
\item $\overline{\mathsf{Repeat}}$: As OTP, $\Pr[\mathsf{Break}]=\frac{1}{2}$
\end{itemize}
\[
\begin{split}
\Pr[\mathsf{Break}] & =\Pr[\mathsf{Break} \land \mathsf{Repeat}] + \Pr[\mathsf{Break} \land \overline{\mathsf{Repeat}}] \\
&\le \Pr[\mathsf{Repeat}] + \Pr[\mathsf{Break} | \overline{\mathsf{Repeat}}] \\
&\le \frac{q(n)}{2^n} + \frac{1}{2}.
\end{split}
\]
\end{proof}
\end{frame}
\begin{frame}\frametitle{Proof of CPA-Security from PRF (Cont.)}
\begin{proof}
(2) Reduce $D$ to $\mathcal{A}$:
\begin{figure}
\begin{center}
\input{tikz/pgfD}
\end{center}
\end{figure}
{\footnotesize
$ \Pr[D^{F_k(\cdot)}(1^n)=1] = \Pr[\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n) = 1] = \frac{1}{2} + \varepsilon(n). $
$ \Pr[D^{f(\cdot)}(1^n)=1] = \Pr[\mathsf{PrivK}_{\mathcal{A},\tilde{\Pi}}^{\mathsf{cpa}}(n) = 1] = \Pr[\mathsf{Break}] \le \frac{1}{2} + \frac{q(n)}{2^n}. $
$\Pr[D^{F_k(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot)}(1^n)=1] \ge \varepsilon(n) - \frac{q(n)}{2^n}.$
$\varepsilon(n)$ is negligible.
}
\end{proof}
\end{frame}
\begin{frame}\frametitle{Remarks on CPA-Security from PRF}
\begin{itemize}
\item For arbitrary-length messages, $m = m_1, \dots , m_{\ell}$
\[ c := \left< r_1, F_k(r_1) \oplus m_1, r_2, F_k(r_2) \oplus m_2, \dots, r_\ell, F_k(r_\ell) \oplus m_\ell\right>
\]
\begin{corollary}
If $F$ is a PRF, then $\Pi$ is CPA-secure for arbitrary-length messages.
\end{corollary}
\item \textbf{Efficiency}: $|c| = 2|m|$.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Pseudorandom Permutations}
\begin{itemize}
\item \textbf{Bijection}: $F$ is one-to-one and onto
\item \textbf{Permutation}: A bijective function from a set to itself
\item \textbf{Keyed permutation}: $\forall k, F_k(\cdot)$ is permutation
\item $F$ is a bijection $\iff F^{-1}$ is a bijection
\end{itemize}
\begin{definition}
An efficient, keyed permutation $F$ is a \textbf{strong pseudorandom permutation (PRP)} if
$\forall\;$ \textsc{ppt} distinguishers $D$,
\[ \left|\Pr[D^{F_k(\cdot),F_k^{-1}(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot),f^{-1}(\cdot)}(1^n)=1]\right| \le \mathsf{negl}(n),
\]
where $f$ is chosen \emph{u.a.r} from the set of permutations on $n$-bit strings.
\end{definition}
\begin{alertblock}{If $F$ is a pseudorandom permutation then is it a PRF?}
\end{alertblock}
\end{frame}
\begin{frame}\frametitle{Questions}
\begin{exampleblock}{Let $X = \{ 0,1\}$ (1 bit), answer the following questions.}
\begin{enumerate}
\item What are the functions in the permutation over $X$?
\item $K = \{0, 1\}$, what is the simplest permutation $F(k, x)$ over $X$?
\item Is your $F$ a secure PRP?
\item Is your $F$ a secure PRF?
\item What if $X = \{ 0,1\}^{128}$ and $K = \{0, 1\}^{128}$?
\item Could you give a (or another) PRP over $X = \{ 0,1\}^{128}$?
\end{enumerate}
\end{exampleblock}
\begin{proposition}
IF $F$ is a PRP and additionally $\ell_{in} (n) \ge n$, then $F$ is also a PRF.
\end{proposition}
\end{frame}
\section{Modes of Operation}
\begin{frame}\frametitle{PRF, PRP, PRG, and Modes of Operation}
\textbf{Modes of Operation:}
\begin{itemize}
\item A way of encrypting arbitrary-length messages using a PRP or PRF
\item A way of constructing a PRG from a PRP or PRF
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Electronic Code Book (ECB) Mode}
\begin{figure}
\begin{center}
\input{tikz/ECB}
\end{center}
\end{figure}
\begin{itemize}
\item \alert{Q: is it indistinguishable in the presence of an eavesdropper?}
\item \alert{Q: can $F$ be any PRF?}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Attack on ECB mode}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/ecb}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Cipher Block Chaining (CBC) Mode}
\begin{figure}
\begin{center}
\input{tikz/CBC}
\end{center}
\end{figure}
\begin{itemize}
\item $IV$: initial vector, a fresh random string.
\item \alert{Q: is it CPA-secure? what if $IV$ is always $0$?}
\item \alert{Q: is the encryption parallelizable, i.e., outputting $c_{2}$ before getting $c_{1}$?}
\item \alert{Q: can $F$ be any PRF?}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Output Feedback (OFB) Mode}
\begin{figure}
\begin{center}
\input{tikz/OFB}
\end{center}
\end{figure}
\begin{itemize}
\item \alert{Q: is it CPA-secure?}
\item \alert{Q: is the encryption parallelizable?}
\item \alert{Q: can $F$ be any PRF?}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Counter (CTR) Mode}
\begin{figure}
\begin{center}
\input{tikz/CTR}
\end{center}
\end{figure}
\begin{itemize}
\item $ctr$ is an $IV$
\item \alert{Q: is it CPA-secure?}
\item \alert{Q: is the encryption parallelizable?}
\item \alert{Q: can $F$ be any PRF?}\end{itemize}
\end{frame}
\begin{frame}\frametitle{CTR Mode Is CPA-secure}
\begin{theorem}
If $F$ is a PRF, then randomized CTR mode is CPA-secure.
\end{theorem}
\begin{proof}
The message length and the number of query are $q(n)$. \\
\textbf{Overlap}: the sequence for the challenge overlaps the sequences for the queries from the adversary.\\
$\mathsf{ctr}^*$: $\mathsf{ctr}$ in the challenge. $\mathsf{ctr}_i$: $\mathsf{ctr}$ in the queries, $i = 1,\dots,q(n)$.\\
$\mathsf{Overlap}$: $\mathsf{ctr}_i-q(n) < \mathsf{ctr}^* < \mathsf{ctr}_i + q(n)$.\\
\[\Pr[\mathsf{Overlap}] \le \frac{2q(n)-1}{2^n} \cdot q(n)\]
\end{proof}
\end{frame}
\begin{frame}\frametitle{Proof of CPA-secure CTR Mode (Cont.)}
\begin{proof}
See proof of theorem \ref{thm:prf}.
(1) Analyze $\mathsf{Break}$ : $\mathsf{PrivK}_{\mathcal{A},\tilde{\Pi}}^{\mathsf{cpa}}(n)=1$.
\[
\begin{split}
\Pr[\mathsf{Break}] & =\Pr[\mathsf{Break} \land \mathsf{Overlap}] + \Pr[\mathsf{Break} \land \overline{\mathsf{Overlap}}] \\
&\le \Pr[\mathsf{Overlap}] + \Pr[\mathsf{Break} | \overline{\mathsf{Overlap}}] \\
&\le \frac{2q(n)^2}{2^n} + \frac{1}{2}.
\end{split}
\]
(2) Reduce $D$ to $\mathcal{A}$
\[ \Pr[D^{f(\cdot)}(1^n)=1]=\Pr[\mathsf{PrivK}_{\mathcal{A},\tilde{\Pi}}^{\mathsf{cpa}}(n)=1] \le \frac{2q(n)^2}{2^n} + \frac{1}{2}
\]
\[\Pr[D^{F_k(\cdot)}(1^n)=1]=\Pr[\mathsf{PrivK}_{\mathcal{A},\Pi}^{\mathsf{cpa}}(n)=1] \le \frac{1}{2} + \varepsilon(n)
\]
\[ \text{If } F \text{ is PRP}, \varepsilon(n) \text{ is negligible.}
\]
\end{proof}
\end{frame}
\begin{frame}[fragile]\frametitle{$IV$ Should Not Be Predictable}
If $IV$ is predictable, then CBC/OFB/CTR mode is not CPA-secure.\\
\alert{Q: Why? (homework)}
\begin{exampleblock}{Bug in SSL/TLS 1.0}
$IV$ for record $\#i$ is last CT block of record $\#(i-1)$.
\end{exampleblock}
\begin{exampleblock}{API in OpenSSL}
\verb#void AES_cbc_encrypt (# \\
\verb# const unsigned char *in,# \\
\verb# unsigned char *out,# \\
\verb# size_t length,# \\
\verb# const AES_KEY *key,# \\
\verb# unsigned char *ivec, # \alert{\textbf{User supplies $IV$}} \\
\verb# AES_ENCRYPT or AES_DECRYPT);# \\
\end{exampleblock}
\end{frame}
%\begin{frame}\frametitle{PRP/PRF Switching Lemma (FYI)}
%\begin{lemma}
%$\forall\;$ \textsc{ppt} distinguishers $D$,
%\[ \left|\Pr[D^{f}=1] - \Pr[D^{p}=1]\right| \le \frac{q^{2}}{2^{n+1}},
%\]
%where $f$/$p$ is chosen \emph{u.a.r} from the set of functions/permutations on $n$-bit strings.
%\end{lemma}
%\begin{exampleblock}
%\end{exampleblock}
%\end{frame}
\section{Security Against Chosen-Ciphertext Attacks (CCA)}
\begin{frame}\frametitle{Security Against CCA}
The CCA indistinguishability experiment $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n)$:
\begin{enumerate}
\item $k \gets \mathsf{Gen}(1^n)$.
\item $\mathcal{A}$ is given input $1^n$ and oracle access $\mathcal{A}^{\mathsf{Enc}_k(\cdot)}$ and $\mathcal{A}^{\mathsf{Dec}_k(\cdot)}$, outputs $m_0, m_1$ of the same length.
\item $b \gets \{0,1\}$. $c \gets \mathsf{Enc}_k(m_b)$ is given to $\mathcal{A}$.
\item $\mathcal{A}$ continues to have oracle access \alert{\textbf{except for $c$}}, outputs $b'$.
\item If $b' = b$, $\mathcal{A}$ succeeded $\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}=1$, otherwise 0.
\end{enumerate}
\begin{definition}
$\Pi$ has \textbf{indistinguishable encryptions under a CCA (CCA-secure)} if $\forall$ \textsc{ppt} $\mathcal{A}$, $\exists$ $\mathsf{negl}$ such that
\[ \Pr\left[\mathsf{PrivK}^{\mathsf{cca}}_{\mathcal{A},\Pi}(n)=1\right] \le \frac{1}{2} + \mathsf{negl}(n).
\]
\end{definition}
\end{frame}
\begin{frame}\frametitle{Understanding CCA-security}
\begin{itemize}
\item In real world, the adversary might conduct CCA by influencing what gets decrypted
\begin{itemize}
\item If the communication is not authenticated, then an adversary may send certain ciphertexts on behalf of the honest party
\end{itemize}
\item CCA-security implies ``\textbf{non-malleability}''
\item None of the above scheme is CCA-secure
\end{itemize}
\begin{exampleblock}{CCA against Construction \ref{thm:cpa}}
$\mathcal{A}$ gives $m_{0}, m_{1}$ and gets $c = \left<r, F_k(r)\oplus m_{b}\right>$,
and then queries $c'$ which is the same with $c$ except that a single bit is flipped.
The $m' = c' \oplus F_k(r)$ should be the same with $m_{b}$ \alert{except \underline{$\qquad$}?}
\end{exampleblock}
\alert{Q: Show that the above modes (CBC, OFB and CTR) are also not CCA-secure. (homework)}
\end{frame}
\begin{frame}\frametitle{Padding-Oracle Attacks}
\textbf{PKCK \#5 Padding}: append $b$ bytes of $b$ to the message in order to make the total length a multiple of the block length (append a dummy block if needed). The decryption server will return a \textbf{Bad Padding Error} for incorrect padding.\\
\textbf{Padding-Oracle Attacks}:
\begin{itemize}
\item In a one-block CBC, by modifying the 1st byte of $IV$, attacker can learn whether $m$ is NULL. If yes, error will occur.
\end{itemize}
\begin{columns}[c]
\column{.5\textwidth}
\begin{figure}
\begin{center}
\input{tikz/CBC-small}
\end{center}
\end{figure}
\column{.5\textwidth}
\begin{itemize}
\item append $\{b\}^b$ as a dummy block if $m$ is NULL
\item change the 1st byte of $IV$ from $x$ to $y$, get decrypted block $(x \oplus y \oplus b) \| \{b\}^{b-1}$, and trigger an error
\end{itemize}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Padding-Oracle Attacks (Cont.)}
\begin{figure}
\begin{center}
\input{tikz/CBC-small}
\end{center}
\end{figure}
\begin{itemize}
\item If no error, then learn whether $m$ is 1 byte by modifying the 2nd byte of $IV$ and so on (changing the ciphertext)
\item Once learn the length of $m$, learn the last byte of $m$ ($s$) by modifying the one before the last block in the ciphertext
\item $m_{last} = \cdots s \| \{b\}^{b}$, $c_{last-1} = \cdots t \| \{\cdot \}^{b} $
\item modify $c_{last-1}$ to $c_{last-1}' = \cdots u \| (\{\cdot \}^{b} \oplus \{b\}^{b} \oplus \{b+1\}^{b}) $
\item \alert{Q: If no padding error, then $s$ = ?}
% s ^ t = u ^ (b+1), s= u ^ (b+1) ^ t
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Padding-Oracle Attacks: Real-world Case}
CAPTCHA server will return an error when deciphering the CT of a CAPTCHA text received from a user.
\begin{figure}
\begin{center}
\input{tikz/padding-oracle}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Summary}
\begin{itemize}
\item Asymptotic approach, proof of reduction, indistinguishable
\item PRG, PRF, PRP, stream cipher, block cipher
\item Security/construction against eavesdropping/CPA
\item EBC, CBC, OFB, CTR
\item CCA, padding-oracle attack
\end{itemize}
\end{frame}
\end{document}