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