Removed spaces in path

1 files changed, 142 insertions, 0 deletions

diff --git a/Assignment5/CamilStaps-assignment5.tex b/Assignment5/CamilStaps-assignment5.tex
new file mode 100644
index 0000000..4ee403a
--- /dev/null
+++ b/Assignment5/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}