diff options
Diffstat (limited to 'Assignment3/CamilStaps-assignment3.tex')
| -rw-r--r-- | Assignment3/CamilStaps-assignment3.tex | 219 |
1 files changed, 219 insertions, 0 deletions
diff --git a/Assignment3/CamilStaps-assignment3.tex b/Assignment3/CamilStaps-assignment3.tex new file mode 100644 index 0000000..da7d433 --- /dev/null +++ b/Assignment3/CamilStaps-assignment3.tex @@ -0,0 +1,219 @@ +\documentclass[a4paper]{article} + +\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox} +\usepackage[margin=2cm]{geometry} + +\title{Homework $3$} +\author{Camil Staps (s4498062)} + +\newcommand{\R}{\mathbb R} +\newcommand{\Q}{\mathbb Q} +\newcommand{\Z}{\mathbb Z} +\newcommand{\N}{\mathbb N} +\newcommand{\F}{\mathbb F} +\newcommand{\Zstar}{\Z^{^*}} + +\DeclareMathOperator{\ord}{ord} +\DeclareMathOperator{\lcm}{lcm} +\DeclareMathOperator{\lsb}{lsb} +\DeclareMathOperator{\Prob}{Pr} +\DeclareMathOperator{\Adv}{Adv} + +\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n} + +\usepackage{tikz} +\usetikzlibrary{shapes.multipart,shapes.gates.logic.IEC,shapes.arrows,positioning,decorations.markings} + +\begin{document} +\maketitle + +\section*{Solution} + +\begin{enumerate} +\item + \begin{enumerate} + \item + \begin{enumerate} + \item + \begin{minipage}[t]{\linewidth} + \centering + \adjustbox{valign=t}{% + \begin{tikzpicture}[LFSR/.style={rectangle split, rectangle split horizontal=true, rectangle split parts=#1, draw, anchor=center}, ARROW/.style={draw,thick,single arrow,single arrow head extend=3pt,transform shape}]] + \node[LFSR=5] (register) {\nodepart{one}$s_4$\nodepart{two}$s_3$\nodepart{three}$s_2$\nodepart{four}$s_1$\nodepart{five}$s_0$}; + \node[circle, inner sep=0, below=6mm of register.one south] (xor) {\scalebox{1}{$\oplus$}}; + \draw[->] (register.one south) -- (xor); + \draw[->] (register.two south) |- (xor); + \draw (register.three south) |- (xor); + \draw (register.five south) |- (xor); + \draw (xor.west) -- ++(left:4mm) node[anchor=north] (hook1) {}; + \draw[->] (hook1) |- (register.one west); + \draw[->] (register.five east) -- ++(right:4mm) node[anchor=west] {$\dots$}; + \end{tikzpicture} + } + \end{minipage} + + \item + $$M = \begin{pmatrix} + 0 & 1 & 0 & 0 & 0 \\ + 0 & 0 & 1 & 0 & 0 \\ + 0 & 0 & 0 & 1 & 0 \\ + 0 & 0 & 0 & 0 & 1 \\ + 1 & 0 & 1 & 1 & 1 + \end{pmatrix}$$ + + \item + That bit stream contains $0^L$. We know that $0 \oplus \dots \oplus 0 = 0$, so after $0^L$, only zeros can follow. However, this is not the case. Therefore, this bit stream cannot be a part of the output of this LFSR. + + \item + % In figure \ref{fig:1ai} we see that $c_L=1$. We then check if $C(X)$ is an irreducible polynomial. Since $C(X)=\dots+1$ and $\deg(C(X))=5$, we only need to consider products of two polynomials $f_1,f_2$ for which $\deg(f_1)+\deg(f_2)=5$ and both polynomials have a term $1$. We then check all possible combinations: + + % \begin{table}[h] + % \centering + % \begin{tabular}{>{$}l<{$} >{$}l<{$} | >{$}l<{$}} + % f_1(x) & f_2(x) & (f_1 \circ f_2)(x) = (f_2 \circ f_1)(x) \\\hline + % x^4 + x^3 + x^2 + x + 1 & x + 1 & x^5 + 1 \\ + % x^4 + x^3 + x^2 + 1 & x + 1 & x^5 + x^2 + x + 1 \\ + % x^4 + x^3 + x + 1 & x + 1 & x^5 + x^3 + x^2 + 1 \\ + % x^4 + x^3 + 1 & x + 1 & x^5 + x^3 + x + 1\\ + % x^4 + x^2 + x + 1 & x + 1 & x^5 + x^4 + x^3 + 1\\ + % x^4 + x^2 + 1 & x + 1 & x^5 + x^4 + x^3 + x^2 + x + 1\\ + % x^4 + x + 1 & x + 1 & x^5 + x^4 + x^2 + 1\\ + % x^4 + 1 & x + 1 & x^5 + x^4 + x + 1\\ + + % x^3 + x^2 + x + 1 & x^2 + x + 1 & x^5 + x^3 + x^2 + 1\\ + % x^3 + x^2 + x + 1 & x^2 + 1 & x^5 + x^4 + x + 1\\ + % x^3 + x^2 + 1 & x^2 + x + 1 & x^5 + x + 1\\ + % x^3 + x^2 + 1 & x^2 + 1 & x^5 + x^4 + x^3 + x + 1\\ + % x^3 + x + 1 & x^2 + x + 1 & x^5 + x^4 + 1\\ + % x^3 + x + 1 & x^2 + 1 & x^5 + x^2 + x + 1\\ + % x^3 + 1 & x^2 + x + 1 & x^5 + x^4 + x^3 + x^2 + x + 1\\ + % x^3 + 1 & x^2 + 1 & x^5 + x^3 + x^2 + 1\\ + % \end{tabular} + % \end{table} + + % Since $C(X)$ does not appear in the rightmost column of this table, it is an irreducible polynomial. + + In the figure above we see that $c_L=1$. Using sage, we find that $C(X)$ is a primitive polynomial: + + \begin{minted}[tabsize=0]{python} + sage: Z2P.<x> = GF(2)[] + sage: (x^5+x^3+x^2+x+1).is_primitive() + True + \end{minted} + + The period of this LFSR is then $2^L-1=31$. + + \item + We construct the states using matrix multiplication. As an example we show $M\cdot s_1$: + $$M\cdot s_1 = \begin{pmatrix}0 & 1 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 1 \\1 & 0 & 1 & 1 & 1\end{pmatrix} \cdot \begin{pmatrix}0 \\ 0 \\ 0 \\ 0 \\ 1\end{pmatrix} = \begin{pmatrix}0 \\ 0 \\ 0 \\ 1 \\ 1\end{pmatrix} = s_3$$ + We can then continue with $M\cdot s_3$. Using that method, we find the state sequence $s_1$, $s_3$, $s_6$, $s_{12}$, $s_{25}$, $s_{18}$, $s_4$, $s_9$, $s_{19}$, $s_7$, $s_{15}$, $s_{31}$, $s_{30}$, $s_{29}$, $s_{27}$, $s_{23}$, $s_{14}$, $s_{28}$, $s_{24}$, $s_{17}$, $s_2$, $s_5$, $s_{10}$, $s_{21}$, $s_{11}$, $s_{22}$, $s_{13}$, $s_{26}$, $s_{20}$, $s_8$, $s_{16}$, $s_1$, which indeed contains $31$ different states (all states except $s_0$). + \end{enumerate} + + \item + We know with sage that these two polynomials are primitive: + + \begin{minted}[tabsize=0]{python} + sage: (x^3+x+1).is_primitive() + True + sage: (x^5+x^2+1).is_primitive() + True + \end{minted} + + Therefore, the two LFSRs have period $2^L-1$, that is, $7$ for $\text{LFSR}^f$ and $31$ for $\text{LFSR}^g$. Of course, there is also the obvious period $1$ for both LFSRs if we start with $s_0$. + + Combining this we find the periods illustrated in table \ref{tab:1b}. + + \begin{table} + \setlength\extrarowheight{2pt} + \centering + \begin{tabular}{l | l | l | l | l} + Period $\text{LFSR}^f$ & Initial state (e.g.) & Period $\text{LFSR}^g$ & Initial state (e.g.) & Combined period \\\hline + $1$ & \texttt{000} & $1$ & \texttt{00000} & $2^{1\cdot1}-1=1$ \\ + $1$ & \texttt{000} & $31$ & \texttt{00001} & $2^{1\cdot31}-1=2^{31}-1$ \\ + $7$ & \texttt{001} & $1$ & \texttt{00000} & $2^{7\cdot1}-1=2^7-1$ \\ + $7$ & \texttt{001} & $31$ & \texttt{00001} & $2^{7\cdot31}-1=2^{217}-1$ \\ + \end{tabular} + \caption{} + \label{tab:1b} + \end{table} + \end{enumerate} + +\item + \begin{proof} + Given a certain ciphertext $c$ we define the set $M_c$ as the set with all plaintexts that could give $c$ using some key and this cipher: + $$M_c \stackrel{\text{def}}{=} \{m\in\pazocal{M} \mid \exists_{k\in\pazocal{K}}[E(k,m) = c]\}$$ + For all $k\in\pazocal{K}, c\in\pazocal{C}$ we have $D(k,c) = c-k\pmod{256} \in \{0,\dots,255\} = \pazocal{M}$. Therefore, for any $c\in\pazocal{C}$, we have $|M_c| = |\pazocal{K}| = |\pazocal{M}|$, meaning that given a certain ciphertext, any plaintext in $\pazocal{M}$ could be the plaintext corresponding to that ciphertext. Hence, seeing the ciphertext does not give us information about the plaintext, or: + $$\forall_{m\in\pazocal{M},c\in\pazocal{C}}\left[\Prob(m = m' \mid c) = \Prob(m = m')\right].$$ + Therefore, this cipher has perfect secrecy. + \end{proof} + +\item + \begin{enumerate} + \item + $L_2 = R_1 = L_0 \oplus F(k_1,R_0)$ and $R_2 = L_1 \oplus F(k_2,R_1) = R_0 \oplus F(k_2, L_0 \oplus F(k_1, R_0))$. + \item + We are only interested in the left parts of the encryptions, which we shall denote as $L_{2,0}$ and $L_{2,1}$ for the left parts of the could-be encryptions of $m_0$ and $m_1$, respectively. Following the equations found in the last exercise, we have $L_{2,0} = 1^{32} \oplus F(k_1,1^{32}) = \overline{F(k_1,1^{32})}$ and $L_{2,1} = 0^{32} \oplus F(k_1,1^{32}) = F(k_1,1^{32})$. Therefore, in case $F_2$ was used, we have $L_{2,0} = \overline{L_{2,1}}$. For a random permutation this happening has the very small chance of $\frac1{2^{64}}$. + + If an adversary thus checks whether $L_{2,0} \stackrel?= \overline{L_{2,1}}$ and finds out it's true, he has a non-negligible advantage with which he can assume $F_2$ was used. In case this equation does \emph{not} hold, he has a non-negligible advantage with which he can assume a random permutation was used. + \end{enumerate} + +\item + \begin{enumerate} + \item + One key has an effective length of $56$ bits. With two keys we have an effective keylength of $2\cdot56=112$ bits. This gives $|\pazocal{K}| = 2^{112}$. The amount of encryptions we have to perform for exhaustive key search is then $2^{112-1}$. + \item + $D^{2DES}(k_1||k_2, c) = D^{DES}(k_1, D^{DES}(k_2, c))$. + \item + \begin{proof} + \begin{align*} + m &= D^{DES}(k_1, D^{DES}(k_2, c)) \\ + E^{DES}(k_1, m) &= E^{DES}(k_1, D^{DES}(k_1, D^{DES}(k_2, c))) \\ + &\qquad\text{(Encryption and decryption with $k_1$ cancel out)} \\ + E^{DES}(k_1, m) &= D^{DES}(k_2, c) + \end{align*} + \end{proof} + \item + $A = 2^{56}$ since the keylength of one DES key is $56$. A ciphertext block encrypted with DES is $64$ bits long. Without overhead we have then $B=64\cdot2^{56}$. + + We have a block length of $64$ and a key length of $56$. If we compute the encryptions of some plaintext using all possible keys, and the decryptions of some ciphertext using all possible keys, we have two lists of $2^{56}$ 64-bit candidates for a middle point in 2DES. Following the birthday paradox, the probability two values from the two lists are the same is high enough to reasonably expect false alarms\footnote{See \url{http://en.wikipedia.org/wiki/Birthday_problem#Probability_table}}. + \item + See the python files for the answers to exercise i through iv. See \texttt{Readme.md} for explanation and usage information. + + I found the keypair $k_1=\mathtt{0101010101164613}, k_2=\mathtt{0101010102a719c2}$ using: + + \begin{verbatim} + $ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24 + Making dictionary (p:0123456789abcdef;l:24)... 417.513822s + Finding matches... 419.125502s + Key generation: 102.954099s + Decryption: 269.473773s + Matching dictionary: 15.134741s + k1: 0101010101164613; k2: 0101010102a719c2 + \end{verbatim} + + This was done on a Lenovo U410, i7-3517U @ 1.9GHz with 8GB RAM and 16GB /swap. It takes about seven minutes to create the dictionary, and again seven minutes to try all keys for the second key and find matches. On lilo, this takes a bit less than five minutes each. + + With $l=24$ we're likely to find only one possible keypair since the chance on false alarms is much lower. For higher $l$, in particular $l=56$, the chance on false alarms is much higher, meaning that the first keypair is most likely \emph{not} the actual keypair. More plaintext-ciphertext pairs can then help to find the right keypair. We do that in this case only for verification: + + \begin{verbatim} + $ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24 + Making dictionary (p:1122334455667788;l:24)... 386.554364s + Finding matches... 424.907323s + Key generation: 106.151418s + Decryption: 271.449573s + Matching dictionary: 15.2167599999s + k1: 0101010101164613; k2: 0101010102a719c2 + $ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24 + Making dictionary (p:99aabbccddeeff00;l:24)... 394.505993s + Finding matches... 431.637707s + Key generation: 109.764972s + Decryption: 274.681545s + Matching dictionary: 14.4759990001s + k1: 0101010101164613; k2: 0101010102a719c2 + \end{verbatim} + + An adversary uses a method like \texttt{nthKey} instead of trying all $2^{64}$ possible 64-bit strings since some of the bits are parity bits. If he would try all $2^{64}$ possible 64-bit strings, he would waste time and storage on trying keys that aren't valid anyway. + \end{enumerate} +\end{enumerate} + +\end{document} |