forked from YuZhang/cryptography
-
Notifications
You must be signed in to change notification settings - Fork 0
/
4blockcipher.tex
506 lines (501 loc) · 19.3 KB
/
4blockcipher.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
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
\input{main.tex}
\title{Practical Constructions of Pseudorandom Permutations (Block Ciphers)}
\begin{document}
\maketitle
\begin{frame}
\frametitle{Outline}
\tableofcontents
\end{frame}
\section{Substitution-Permutation Networks}
\begin{frame}\frametitle{Block Ciphers}
\begin{itemize}
\item \textbf{Block Cipher} $F : \{0,1\}^n \times \{0,1\}^\ell \to \{0,1\}^\ell$. \\
$F_k : \{0,1\}^\ell \to \{0,1\}^\ell$, $F_k(x) \overset{\text{def}}{=} F(k,x)$. \\
$n$ is key length, $\ell$ is block length.
\item Constructions are \textbf{heuristic}, not proofed.
\item Considered as \textbf{PRP} in practice, not encryption scheme.
\begin{itemize}
\item In the call for proposals for AES:
\emph{The extent to which the algorithm output is indistinguishable from a random permutation on the input block.}
\end{itemize}
\item Is ``\textbf{good}'' if the best known attack has time complexity roughly \textbf{equivalent to a brute-force search for the key}.
\begin{itemize}
\item A cipher with $n=112$ which can be broken in time $2^{56}$ is insecure.
\item In a non-asymptotic setting, $2^{n/2}$ may be insecure.
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{The Confusion-Diffusion Paradigm}
\begin{itemize}
\item \textbf{Goal}: Construct \emph{concise} random-looking permutations.
\begin{itemize}
\item \alert{Q: a block length of $n$ bits require \underline{\qquad} bits for its representation.} %$\log(2^n!) \approx n\cdot 2^n $
\end{itemize}
\item \textbf{Confusion}: making the relationship between the key and the ciphertext as complex and involved as possible. \\
Construct a large random-looking permutation $F$ from smaller random permutations ${f_i}$. $F_k(x) = f_1(x_1)f_2(x_2) \cdots f_{i}(x_{i})$
\item \textbf{Diffusion}: the redundancy in the statistics of the plaintext is dissipated in the statistics of the ciphertext.
\item \textbf{Product cipher} combines multiple transformations.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{A Substitution-Permutation Network}
\begin{figure}
\begin{center}
\input{tikz/spn}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Design Principle 1 -- Invertibility of The $S$-boxes}
$S$-boxes must be invertible, otherwise the block cipher will not be a permutation.
\begin{proposition}
Let $F$ be a keyed function defined by a SPN in which the $S$-boxes are all one-to-one and onto. The regardless of the key schedule and the number of rounds, $F_k$ is a permutation for any choice of $k$.
\end{proposition}
\end{frame}
\begin{frame}\frametitle{Design Principle 2 -- The Avalanche Effect}
\begin{itemize}
\item \textbf{Avalanche effect}: changing a single bit of the input affects every bit of the output.
\item \textbf{Strict avalanche criterion}: a single input bit is complemented, each of the output bits changes with a 50\% probability.
\item \textbf{Bit independence criterion}: output bits $j$ and $k$ should change independently when any single input bit $i$ is inverted, for all $i$, $j$ and $k$.
\item $S$-box: changing a single bit of the input changes at least two bits in the output.
\item $P$-box: the output bits of any given $S$-box are spread into different $S$-boxes in the next round.
\item \alert{Q: For 4-bit $S$-boxes, changing 1 bit of the input affects \underline{\qquad} bits of the output after $R$ rounds of SPN.}
\end{itemize}
%\begin{exampleblock}{}
%For 4-bit $S$-boxes, changing 1 bit of the input affects $2^R$ bits of the output after $R$ rounds of SPN.
%\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{A Framework for KPA against Block Ciphers}
\textbf{KPA}: know some plaintext/ciphertext pairs under the same key.
\begin{enumerate}
\item Observe relationship between PT/CT and $k$ bits of the key.
\item Design a test on $t$ bits based on the above relationship.
\item Search in $k$-bit space; a guess passes test with pr. $2^{-t}$.
\item Use $p$ PT/CT pairs to determine the key with exp. $2^{k-(p)t}$.
\end{enumerate}
\begin{exampleblock}{KPA against 1-Round SPN with $16$-bit key}
\begin{description}
\item[Relationship] PT $\oplus$ Key $\oplus$ Input-of-$S$-boxes $=$ 0.
\item[Test] on $t=16$ bits: Input-of-$S$-boxes $=$ PT $\oplus$ Key.
\item[Search] in $k=16$ bit space; passing test with pr. $1/2^{16}$.
\item[Determine] the key with $p=1$ PT/CT pair and exp. $1$.
\end{description}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Attacks on Reduced-Round SPNs (Homework)}
Attack on a 2-round SPN: 64-bit block, 128-bit key (2 $\times$ 64-bit sub-keys), 16 $\times$ 4-bit $S$-boxes, and mixing with XOR.
\begin{figure}
\begin{center}
\input{tikz/attack-spn.tex}
\end{center}
\end{figure}
\begin{itemize}
\item Guessing 20 bits: 16 bits of the 1st sub-key, 4 bits of the 2nd.
\item Guess passes the 4-bit test with pr. $1/2^4$ ($1/2^n$ for $n$-bit test).
\item Use 8 I/O pairs to determine the key (with exp. $2^{20 - 4\times 8}$).
\item Break with complexity $8\cdot 2^{20} \cdot 16= 2^{27} \ll 2^{128}$ (16 $S$-boxes).
\end{itemize}
\end{frame}
\section{Feistel Networks}
\begin{frame}\frametitle{Feistel Networks}
\begin{columns}[t]
\begin{column}{4cm}
\begin{figure}
\begin{center}
\input{tikz/feistel}
\end{center}
\end{figure}
\end{column}
\begin{column}{6cm}
\begin{itemize}
\item \textbf{Idea}: Construct an invertible function from non-invertible components.
%\item \textbf{Round function} $f_i(R) \overset{def}{=} \hat{f}_i(k_i,R)$ ($\hat{f}_i$ mangler function).
\item $L_i := R_{i-1}$ and $R_i := L_{i-1} \oplus f_i(R_{i-1})$
\item \alert{\textbf{Inverting}: $L_{i-1} :=\ ?$} %R_i \oplus f_i(R_{i-1}) = R_i \oplus f_i(L_i)$.
\item \textbf{Decryption}: Operate with sub-keys in reverse order.
\end{itemize}
\begin{proposition}
\textbf{Luby-Rackoff Theorem}: Regardless of the mangler functions $\{\hat{f}_i\}$ and the number of rounds, $F_k$ is a permutation for any choice of $k$.
\end{proposition}
\end{column}
\end{columns}
\end{frame}
\begin{frame}\frametitle{Examples}
\begin{exampleblock}{What is the output of an $r$-round Feistel network when the input is $(L_0, R_0)$ in each of the following two cases:}
(a) Each round function $F$ outputs all $0$s, regardless of the input.\\
(b) Each round function $F$ is the identity function.
\end{exampleblock}
\end{frame}
\section{DES -- The Data Encryption Standard}
\begin{frame}\frametitle{The Design of DES}
\begin{itemize}
\item 16-round Feistel network.
\item 64-bit block
\item 56-bit key, 48-bit sub-key. (64bit key with 8 check bits)
\item Key schedule: 56 bits $\xrightarrow[\text{left rotation, PC}]{\text{divided into two halves}}$ 48 bits.
\item Begin with Initial Permutation ($IP$) and end with $IP^{-1}$.
\item Round function $f$ is non-invertible with 32-bit I/O.
\item $f_i$ is determined by mangler function $\hat{f}_i$ and sub-key $k_i$.
\item $S$-box is a 4-to-1 function, mapping 6-bit to 4-bit.
\end{itemize}
\end{frame}
\begin{frame}\frametitle{Overview of DES}
\begin{algorithm}[H]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKw{KwK}{KeySchedule}
\SetKw{KwC}{compute}
\DontPrintSemicolon
\caption{$\mathsf{DES}$}
\Input{key $k$, message $m$}
\Output{ciphertext $c$}
\BlankLine
$(k_{1},\dots,k_{16}) \gets KeySchedule(k)$\;
$m \gets IP(m)$\;
Parse $m$ as $L_{0}\| R_{0}$\;
\For{$r=1$ \KwTo 16}{
$L_{r} \gets R_{r-1}$\;
$R_{r} \gets f(k_{r},R_{r-1})\oplus L_{r-1}$\;
}
$c \gets IP^{-1}(L_{16}\| R_{16})$\;
\Return $c$\;
\end{algorithm}
\end{frame}
\begin{frame}\frametitle{The DES Mangler Function}
\begin{figure}
\begin{center}
\input{tikz/des}
\end{center}
\end{figure}
\end{frame}
\begin{frame}[fragile]\frametitle{An $S$-box in DES}
\begin{exampleblock}{An $S$-box}
Input: $b_{0,1,...,5}=011001$\\
Output: $S[b_{0,5}][b_{1,2,3,4}]=S[01][1100]=S[1][12]=9=1001$
\begin{semiverbatim}
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+--------------------------------------------------------------------------------------------------+
0 | 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 |
1 | 0 15 7 4 14 2 13 1 10 6 12 11 \alert{9} 5 3 8 |
2 | 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 |
3 | 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 |
+--------------------------------------------------------------------------------------------------+
\end{semiverbatim}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Key Schedule}
\begin{figure}
\begin{center}
\input{tikz/DESkey}
\end{center}
\end{figure}
Bits of shift is 1 or 2 in different rounds.
\end{frame}
\begin{frame}[fragile]\frametitle{Weak Keys of DES}
\begin{itemize}
\item \textbf{Weak keys}: makes the cipher behave in some undesirable way--producing \emph{identical} sub-keys.
\begin{exampleblock}{Weak keys (Key with check bits : key w/o check bits)}
\begin{semiverbatim}
01010101 01010101 : 0000000 0000000
FEFEFEFE FEFEFEFE : FFFFFFF FFFFFFF
E0E0E0E0 F1F1F1F1 : FFFFFFF 0000000
1F1F1F1F 0E0E0E0E : 0000000 FFFFFFF
\end{semiverbatim}
\end{exampleblock}
\item \textbf{Semi-weak keys}: producing only two different sub-keys.\\ A pair of semi-weak keys $k_1, k_2$: $F_{k_1}(F_{k_2}(M))=M$.
\begin{exampleblock}{Semi-weak key pairs (2 of total 6 pairs)}
\begin{semiverbatim}
011F011F 010E010E & 1F011F01 0E010E01
01E001E0 01F101F1 & E001E001 F101F101
\end{semiverbatim}
\end{exampleblock}
\end{itemize}
\end{frame}
\begin{comment}
\begin{frame}\frametitle{Attacks on Reduced-Round Variants of DES}
\textbf{1-round (48-bit key)}: \\
$S$-box is 4-to-1, so 4 possible values for each 6-bit key.\\
\# of possible keys: $4^{48/6} = 2^{16}$. \\
So a guess passes test with pr. $2^{-(48-16)}$.\\
Use another I/O pair to determine the key (with exp. $2^{-16}$).
\newline
\textbf{2-round}: $L_0\|R_0, L_2\|R_2$ are known I/O pair.
\begin{columns}[C]
\column{.5\textwidth}
\begin{figure}
\begin{center}
\input{tikz/feistel2.tex}
\end{center}
\end{figure}
\column{.5\textwidth}
\[
\begin{split}
L_1 &= R_0 \\
R_1 &= L_0 \oplus f_1(R_0) \\
L_2 &= R_1 = L_0 \oplus f_1(R_0) \\
R_2 &= L_1 \oplus f_2(R_1). \\
f_1(R_0) &= L_0 \oplus L_2 \\
f_2(L_2) &= R_2 \oplus R_0
\end{split}
\]
\end{columns}
So we know I/O pairs of both $f_1$ and $f_2$. \\
Break in time $2\cdot 2^{16}$ as two 1-round with two I/O pairs.
\end{frame}
\begin{frame}\frametitle{Attacks on Reduced-Round Variants of DES (Cont.)}
\textbf{3-round}:
\begin{columns}[C]
\column{.4\textwidth}
\begin{figure}
\begin{center}
\input{tikz/feistel3.tex}
\end{center}
\end{figure}
\column{.6\textwidth}
Without I/O pairs of any $f$, we know the inputs of $f_1$ and $f_3$ and the XOR of their outputs $ (L_0 \oplus L_2) \oplus (L_2 \oplus R_3) = L_0 \oplus R_3.$
\newline
\textbf{Idea}: The left/right half of the key affects the inputs only to the first/last four $S$-boxes. Brute-force needs $2\cdot 2^{28}$.
\end{columns}
\begin{itemize}
\item Check 16-bit XOR of outputs of four $S$-boxes on one half.
\item $2^{28}/2^{16}=2^{12}$ guesses on half-key pass check (with pr. $2^{-16}$).
\item Use another I/O pair to test $2^{12+12}$ keys (with exp. $2^{24-16\times 2}$).
\item Totally, $2\cdot 2^{28} + 2^{24} < 2^{30}$ time and $2\cdot 2^{12}$ space.
\end{itemize}
\end{frame}
\end{comment}
\begin{frame}\frametitle{Chronology of DES}
\begin{description}
\item[1973] NBS (NIST) publishes a call for a standard.
\item[1974] DES is published in the Federal Register.
\item[1977] DES is published as FIPS PUB 46.
\item[1990] Differential cryptanalysis with CPA of $2^{47}$ plaintexts.
\item[1997] DESCHALL Project breaks DES in public.
\item[1998] EFF's Deep Crack breaks DES in 56hr at \$250,000.
\item[1999] Triple DES.
\item[2001] AES is published in FIPS PUB 197.
\item[2004] FIPS PUB 46-3 is withdrawn.
\item[2006] COPACOBANA breaks DES in 9 days at \$10,000.
\item[2008] RIVYERA breaks DES within one day.
\end{description}
\end{frame}
\section{Increasing the Key Length of a Block Cipher}
\begin{frame}\frametitle{Double Encryption}
\begin{itemize}
\item \textbf{Internal tampering vs. Black-box constructions}: by modifying DES -- in even the smallest way -- we lose the confidence we have gained in DES.
\item \textbf{Double encryption}: $y = F'_{k_1,k_2}(x) \overset{\text{def}}{=} F_{k_2}(F_{k_1}(x))$.
\end{itemize}
\begin{figure}
\begin{center}
\input{tikz/doubleE}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{The Meet-In-the-Middle Attack}
\begin{figure}
\begin{center}
\input{tikz/meet-in-middle}
\end{center}
\end{figure}
\begin{itemize}
\item $z_0 = F_{k_1}(x) = F^{-1}_{k_2}(y) \iff y = F'_{k_1,k_2}(x)$.
\item Key pair $(k_1,k_2)$ satisfies the equation with probability $2^{-n}$.
\item The number of such key pairs is $2^{2n}/2^n = 2^n$.
\item With another two I/O pairs, the expected number of key pairs is $2^{n}/2^{2n}=2^{-n}$. So that is it!
\item $\mathcal{O}(2^n)$ time and $\mathcal{O}(2^n)$ space.
\end{itemize}
\end{frame}
%\begin{comment}
\begin{frame}\frametitle{DESX}
\begin{figure}
\begin{center}
\input{tikz/desx.tex}
\end{center}
\end{figure}
\textbf{Whitening}: XORing Input/Output with partial keys.\\
\textbf{DESX}:
\[k = (k_1,k_2,k_3), \abs{k_1}=\abs{k_3}=64, \abs{k_2}=56\]
\[y = k_3\oplus F_{k_2}(x \oplus k_1)\]
\[x = k_1\oplus F^{-1}_{k_2}(y \oplus k_3)\]
\newline
\textbf{Security}: $\abs{k}=184$, but break in time $2^{64+56}$.
\end{frame}
%\end{comment}
\begin{frame}\frametitle{Triple Encryption}
\begin{figure}
\begin{center}
\input{tikz/TDES}
\end{center}
\end{figure}
\begin{itemize}
\item $k_1 = k_2 = k_3$: a single $F$ with backward compatibility.
\item $k_1 \neq k_2 \neq k_3$: time $2^{2n}$ under the meet-in-the-middle attack.
\item $k_1 = k_3 \neq k_2$: time $2^{2n}$ with 1 I/O pair; time $2^{n}$ with $2^n$ pair.
\item \textbf{Triple-DES} (3DES): strong, but small block length and slow.
\end{itemize}
\end{frame}
\section{AES -- The Advanced Encryption Standard (FYI)}
\begin{frame}\frametitle{AES -- The Advanced Encryption Standard}
\begin{itemize}
\item In 1997, NIST calls for AES.
\item In 2001, Rijndael [J. Daemen \& V. Rijmen] becomes AES.
\item The first publicly accessible cipher for top secret information.
\item Not only security, also efficiency and flexibility, etc.
\item 128-bit block length and 128-, 192-, or 256-bit keys.
\item Not a Feistel structure, but a SPN.
\item Only non-trivial attacks are for reduced-round variants.
\begin{itemize}
\item $2^{27}$ on 6-round of 10-round for 128-bit keys.
\item $2^{188}$ on 8-round of 12-round for 192-bit keys.
\item $2^{204}$ on 8-round of 14-round for 256-bit keys.
\end{itemize}
\end{itemize}
\end{frame}
%\begin{frame}\frametitle{The AES Construction}
%\textbf{State}: 4-by-4 array of bytes. The initial state is the plaintext.
%\begin{enumerate}
%\item \textbf{AddRoundKey}: state XORed with the 128-bit sub-key.
%\item \textbf{SubBytes}: each byte replaced according to a single $S$-box.
%\item \textbf{ShiftRows}: each row cyclically shifted.
%\item \textbf{MixColumns}: each column multiplied by a matrix.
%\end{enumerate}
%\end{frame}
\begin{frame}\frametitle{Overview of AES}
\begin{algorithm}[H]
\SetKwInOut{Input}{input}
\SetKwInOut{Output}{output}
\SetKw{KwK}{KeySchedule}
\SetKw{KwC}{compute}
\DontPrintSemicolon
\caption{$\mathsf{AES}$}
\Input{key $k$, message $m$}
\Output{ciphertext $c$}
\BlankLine
$(k_{1},\dots,k_{10}) \gets Expand(k)$\;
$s \gets m\oplus k_{0}$\;
\For{$r=1$ \KwTo 10}{
$s \gets SubBytes(s)$\;
$s \gets ShiftRows(s)$\;
\lIf{$r \le 9 $}{$s \gets MixColumns(s)$}\;
$s \gets s\oplus k_{R}$\;
}
\Return $c \gets s$\;
\end{algorithm}
\emph{See an animation of Rijndael!}.
\end{frame}
%\begin{comment}
\section{Differential and Linear Cryptanalysis -- A Brief Look (FYI)}
\begin{frame}\frametitle{Linear Cryptanalysis}
\begin{itemize}
\item Linear relationships between the input and output: \\
the bit positions $i_1, ... ,i_\ell$ and $i_1', ... , i_\ell'$ have \textbf{bias} $p$ if for randomly-chosen input $x$ and key $k$, it holds that $y=F_k(x)$,
\[ \Pr [x_{i_1} \oplus \cdots \oplus x_{i_\ell} \oplus y_{i_1'} \oplus \cdots \oplus y_{i_\ell'} = 0] = p+\frac{1}{2}.
\]
\item Not require CPA, KPA are sufficient.
\item Attack steps:
\begin{enumerate}
\item Construct the linear approximation table of $S$-boxes.
\item Construct a linear approximation of the first $r-1$ rounds with a big bias.
\item Extracting sub-key bits of last round that satisfies the linear approximation well.
\end{enumerate}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{An Example of Linear Analysis of $S$-box}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/linear-sbox}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{An Example of Linear Distribution Table}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/linear-table}
\end{center}
\end{figure}
$x_{2}\oplus x_{3} = y_{1}\oplus y_{3} \oplus y_{4}$ for 12 times, the bias is $12 - 8 =4$ times
$x_{2}\oplus x_{3}: 0110 = 6,\quad y_{1}\oplus y_{3} \oplus y_{4}: 1011=B$, so $(6, B) =4$
\end{frame}
\begin{frame}\frametitle{An Example of Linear Cryptanalysis}
\begin{figure}
\begin{center}
\input{tikz/linear}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Differential Cryptanalysis}
\begin{itemize}
\item Specific differences $\Delta_x$ in the input that lead to specific differences $\Delta_y$ in the output with probability $p \gg 2^{-n}$.
\item $x_1\oplus x_2=\Delta_x$, $F_k(x_1) \oplus F_k(x_2)=\Delta_y$ with probability $p$.
\item This can be exploited by CPA.
\item Attack steps:
\begin{enumerate}
\item Construct the difference distribution table of $S$-boxes.
\item Construct a differential characteristics of the first $r-1$ rounds with a big bias.
\item Extracting sub-key bits of last round that satisfies the differential characteristics well.
\end{enumerate}
\end{itemize}
\end{frame}
\begin{frame}\frametitle{An Example of Differential Analysis of $S$-box}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/difference-sbox}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{An Example of Differential Distribution Table}
\begin{figure}
\begin{center}
\includegraphics[width=100mm]{pic/difference-table}
\end{center}
\end{figure}
$\Delta X = 1011 = B, \Delta Y = 0010 = 2$ for 8 times, so $(B, 2) = 8$
\end{frame}
\begin{frame}\frametitle{An Example of Differential Cryptanalysis}
\begin{figure}
\begin{center}
\input{tikz/differential}
\end{center}
\end{figure}
\end{frame}
%\end{comment}
\begin{frame}\frametitle{Remarks on Block Ciphers}
\begin{itemize}
\item \textbf{Block length} should be sufficiently large
\item \textbf{Message tampering} is not with message confidentiality
\item \textbf{Padding}: TLS: For $n>0$, $n$ byte pad is $n,n,\dots,n$
If no pad needed, add a dummy block
\item \textbf{Stream ciphers vs. block ciphers}:
\begin{itemize}
\item Steam ciphers are faster but have lower security
\item It is possible to use block ciphers in ``stream-cipher mode''
\end{itemize}
\end{itemize}
\begin{exampleblock}{Performance: Crypto++ 5.6, AMD Opetron 2.2GHz}
\begin{center}
\begin{tabular}{|c|c|c|} \hline
& \textbf{Block/key size} & \textbf{Speed MB/sec} \\ \hline
\textbf{RC4} & & 126 \\
\textbf{Salsa20/12} & & 643 \\
\textbf{Sosemanuk} & & 727 \\
\textbf{3DES} & 64/168 & 13 \\
\textbf{AES-128} & 128/128 & 109 \\ \hline
\end{tabular}
\end{center}
\end{exampleblock}
\end{frame}
\begin{frame}\frametitle{Comics on S-box [xkcd:153]}
If you got a big keyspace, let me search it.
\begin{figure}
\begin{center}
\includegraphics[width=70mm]{pic/sbox-talk}
\end{center}
\end{figure}
\end{frame}
\begin{frame}\frametitle{Summary}
\begin{itemize}
\item Block cipher is PRP.
\item confusion \& diffusion, SPN, Feistel network, avalanche effect.
\item DES, 3DES, AES.
\item reduced round, meet-in-the-middle, differential and linear cryptanalysis.
\end{itemize}
\end{frame}
\end{document}