4blockcipher.tex

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