%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
% You may add the packages you need here
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}

\begin{document}
% Do not modify 

%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Fall 2018} 
\end{textblock*}

%Do not modify other than putting your name where stated
\begin{textblock*}{8cm}(-1.5cm,-1cm)
\noindent {Name: } 
\end{textblock*}
%Do not modify other than typing your acknowledgement where stated
\begin{textblock*}{13.5cm}(-1.5cm,0cm)
\noindent {Purdue E-mail: } 
\end{textblock*}
\begin{textblock*}{18.5cm}(-1.5cm,0.5cm)
\noindent \textit{\footnotesize  I collaborated with (...). I affirm that I wrote the solutions in my own words and that I understand the solutions I am submitting.} 
\end{textblock*}
\vspace{1cm}

%Do not modify other than typing the homework number after #
\begin{center}
\textbf{\Large Homework 2} \\ 
\textbf{Due date: Tuesday, October 2\nd 3:00 PM}
\end{center}

%Rest should contain your solution for the homework. Feel free to improvise in ways that you believe make grading easier.
\subsection*{Question 1 (15 points)} 
\begin{enumerate}
	\item What is the effect of a single-bit error in the ciphertext when using the CBC, OFB, and CTR modes of operations?
	\item Show that the CBC, OFB, and CTR modes of operation do not yield CCA-secure encryption schemes (regardless of $F$). Briefly describe how an attacker could win the CCA-Security game with non-negligible advantage.
	\item Let F be a pseudorandom permutation. Consider the mode of operation in which a uniform value $\mathsf{ctr} \in \{0,1\}^n$ is chosen, and the $i^{th}$ ciphertext block $c_i$ is computed as $c_i:= F_{k}(\mathsf{ctr} + i + m_i)$. Show that this scheme does not have indistinguishable encryptions in the presence of an eavesdropper.
\end{enumerate}
\subsection*{Question 2 (20 points)}
Let $F:{\{ 0,1\} ^n} \times {\{ 0,1\} ^{n }} \to {\{ 0,1\} ^{n}}$ be a length-preserving pseudorandom function. For the following construction of a keyed function $F':{\{ 0,1\} ^n} \times {\{ 0,1\} ^{n - 2}} \to {\{ 0,1\} ^{4n}}$, state whether $F'$ is a pseudorandom function: if yes prove it, if not show an attack.
\begin{itemize}
\item $F'_k(x) \eq {F_k}(00||x)||{F_k}(x||01)||{F_k}(10||x)||{F_k}(x||11)$
\item $F'_k(x) \eq {F_k}(0||x||0)||{F_k}(0||x||1)||{F_k}(1||x||0)||{F_k}(1||x||1)$
\end{itemize}

\subsection*{Question 3 (20 points)}
	Before HMAC, it was common to define a MAC of arbitrary-length message as $\mathsf{Mac_{s,k}}(m) = H^s(k||m)$ where $H$ is a collision-resistant hash function. We assume $s$ is known to the attacker, and $k$ is kept secret.
	\begin{itemize}
		\item (5 points) Show that this is not a secure MAC when $H$ is constructed using Merkle-Damg{\aa}rd transform. Explain how an attacker can win the MAC security game.

		\item (15 points) Prove that this is a secure MAC if $H$ is modeled as a random oracle.
	\end{itemize}
\break
\subsection*{Question 4 (20 points)}
Let $(\mathsf{Gen}_1,H_1)$ and $(\mathsf{Gen}_2, H_2)$ be two hash functions. We define $(\mathsf{Gen}, H)$ as follow:
\begin{itemize}
 	\item $\mathsf{Gen}:$ runs $\mathsf{Gen_1}$ and $\mathsf{Gen_2}$ to obtain $s_1,s_2$
 	\item $H^{s_1,s_2}(x)=H_1^{s_1}(x)||H_2^{s_2}(x)$
 \end{itemize} 
 Prove that if at least one of $(\mathsf{Gen}_1,H_1)$ and $(\mathsf{Gen}_2,H_2)$ is collision resistant, then $(\mathsf{Gen},H)$ is collision resistant
\subsection*{Question 5 (25 points)}
One way to build a Pseudorandom Permutation from a pseudorandom function is to use a Feistel Network. In particular, if we select $k$ PRF keys $K_1,K_2,...,K_k$ we can define the Pseudorandom Permutation $PRP_{K_1,K_2,...,K_k}(L_0,R_0) = (L_k,R_k)$ where for each $0\leq i< k$ we have $L_{i+1}=R_i$ and $R_{i+1} = L_i \oplus F_{K_{i+1}}(R_i)$. 

It has been shown that if $F_K$ is a secure PRF and we use a $k=4$ round Feistel network that the permutation $PRP_{K_1,K_2,K_3,K_4}$ is a strong pseudorandom permutation. When $k=3$ it is known that $PRP_{K_1,K_2,K_3}$ is a pseudorandom permutation, but not a {\em strong} pseudorandom permutation. {\bf Recall:} A strong PRP means that no PPT attacker can distinguish $PRP_{K_1,K_2,K_3}$ from a truly random permutation $f$ when given oracle access to {\em both} the permutation (either $PRP_{K_1,K_2,K_3}$ or $f()$) AND its inverse (either $PRP_{K_1,K_2,K_3}^{-1}$ or $f^{-1}()$). In the security game for a regular PRP the distinguisher is not given oracle access to the inverse permutation.
\begin{enumerate}
 	\item (2 points)
	Show that when $k=1$ the function is not a regular PRP. You should explain what the distinguisher does and show that its advantage is non-negligible.

	\item (5 points) 
	Show that when k=2 the function is not a regular PRP. You should explain what the distinguisher does and show that its advantage is non-negligible.
	\item (10 points)
	We will show that when $k=3$ the function is not a strong PRP. Consider a distinguisher that makes two queries to the permutation $g$ (either $PRP_{K_1,K_2,K_3}$ or $f()$) and one query to $g^{-1}$. The first two queries to $g()$ are as follows $g(L_0,R_0)$ and $g(L_0', R_0')$ where $R_0=R_0'$ but $L_0' \neq L_0$. Let $(L_3,R_3)$ and $(L_3',R_3')$ denote the outputs of both queries. Finally, consider the query $g^{-1}(L_3', R_3' \oplus L_0 \oplus L_0')$ and let $(L_0'',R_0'')$ denote the output of this query. Supposing that $g= PRP_{K_1,K_2,K_3}$ is the Feistel Network defined above write down a formula for $R_0''$ in terms of variables known to the distinguisher. {\bf Note:} Your formula should only use variables that are known to the distinguisher such as $L_0,L_0', R_0, R_0'$ or $L_3,L_3', R_3, R_3'$. By contrast, your formula should not involve the secret keys $K_1,K_2,K_3$ or internal values (e.g., $R_2'$) that would not be known to the distinguisher.
	\item (5 points): Supposing that $g=f$ is a truly random permutation and letting $(L_0'',R_0'')$ denote the output of the query $g^{-1}(L_3', R_3' \oplus L_0 \oplus L_0')$ upper bound the probability that  $R_0''$ satisfies the above formula.

 	\item (3 points): Using the last two observations explain why our $k=3$ Feistel round construction $PRP_{K_1,K_2,K_3}$ is not a strong $PRP$. What does the distinguisher do? (Note: it is possible to answer parts D and E without answering part C).
 \end{enumerate} 
 
\end{document}