%Do not change 
\documentclass[12pt, oneside]{article}
\usepackage{amssymb,amsmath}
\usepackage[margin=1in]{geometry}
\usepackage{textpos}
\usepackage{mathtools}
\usepackage{xspace}
\usepackage{mdframed}
\usepackage{xcolor}
\newcommand\myeq{\stackrel{\mathclap{\normalfont\mbox{?}}}{=}}
\newcommand\eq{\stackrel{\mathclap{\normalfont\mbox{def}}}{=}}
\newcommand\rd{\textsuperscript{rd}\xspace}
\newcommand\nth{\textsuperscript{th}\xspace}
\newcommand\nd{\textsuperscript{nd}\xspace}
\newcommand{\eps}{\epsilon}

\newenvironment{answer}{\begin{mdframed}\textit{Answer:}}{ \end{mdframed}}
\newenvironment{colabs}{\begin{mdframed}\textit{Resource and Collaborator Statement: }}{ \end{mdframed}}
\newenvironment{proofSK}{\begin{mdframed}\textit{Sketch:}}{ \end{mdframed}}
\newcommand\bset{\{0,1\}}

\newcommand{\M}{\mathcal{M}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\Ad}{\mathcal{A}}
\newcommand{\Enc}{\mathtt{Enc}}
\newcommand{\Dec}{\mathtt{Dec}}
\newcommand{\PAD}{\mathtt{PAD}}
\newcommand{\Gen}{\mathtt{Gen}}
\newcommand{\PvK}{\mathsf{PrivK}}
\newcommand{\VPad}{\mathtt{PDec}}

\begin{document}
%Do not modify
\begin{textblock*}{4cm}(-1.7cm,-2.3cm)
\noindent {\large CS 555-Spring 2021} 
\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 3} \\ 
\textbf{Due date: Thursday , March  4\nd}
\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 (25 points)}
This is a programming assignment on Gradescope. Suppose we adopt the following padding scheme to pad $k < 16$ byte message $m=m_1\ldots m_k$ to $16$ bytes. $\PAD(m) = \langle 16-k\rangle^{16-k} || m_1\ldots m_k $ where $\langle 16-k\rangle$ is the encoding of the hexadecimal digit $16-k$ as a single byte and $\langle 16-k\rangle ^{16-k}$ denotes that byte repeated $16-k$ times. (In Python the command $\mathtt{bytes}([i])*j$ would output $j$ copies of the byte encoding $i$ where $0 \leq i \leq 255$. Thus, to produce $\langle 16-k\rangle^{16-k}$ we would set $i=j=16-k$ and run $\mathtt{bytes}([i])*j$. Obviously, $ ``||" $ is the concatenation operation. The encryption algorithm takes as input a $k<16$-byte message $m=m_1\ldots m_k$ and outputs $\Enc_K(m) = (r, F_K(r \oplus \PAD(m))$ 
where $F_K:\{0,1\}^{128}\rightarrow \{0,1\}^{128}$ is a PRF and the nonce $r \in \{0,1\}^{128}$ is selected uniformly at random. 

In the programming assignment (Python) you will be given a ciphertext $(r, F_K(r \oplus \PAD(m))$ encrypting an unknown message $m$ and API access to partial decryption oracle $\VPad_K(r,s) $ which computes $m' = r \oplus F^{-1}_K(s)$ and outputs true if $m'$ is properly padded; otherwise, false. You will need to implement a function $ \mathtt{RecoverMessage} $ which takes as input a ciphertext $(r,s)$ and recovers the underlying message $m$ after making oracle calls to $ \VPad_K(r, s)$. This question will be autograded with some public test cases and some secret test cases. 

Your turn-in should include one .py files with name: $ \mathtt{attack.py} $. We also provide a sample copy of  $ \mathtt{oracle.py} $ which will be used to test your solution. You should not modify or submit this file as we will be evaluating your solution with different test cases. We provide template for the these two files and are available for your usage.  Your tasks is to complete the functions that we specified. Finally, you can submit them on gradescope by uploading your $ \mathtt{attack.py} $ file there. 

\begin{colabs}
	\dots 
\end{colabs}


\subsection*{Question 2 (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) Suppose that $H$ is constructed using the Merkle-Damg{\aa}rd transform with the underyling hash function $h^s:\{0,1\}^{2n} \rightarrow \{0,1\}^n$. Let $m \in \{0,1\}^n$ be an arbitrary $n$ bit message and 
	let $t= \mathsf{Mac_{s,k}}(m)$ be the authentication tag for $m$. Generate an authentication tag $t'$ for the message $m' = m ||\langle 2n \rangle$ 
	where $\langle i \rangle$ denote an $n$-bit encoding of integer $i$.
	
	
	\item (15 points) Prove that this is a secure MAC if $H$ is modeled as a random oracle.
\end{itemize}

\begin{answer}
	\dots 
\end{answer}
\begin{colabs}
	\dots 
\end{colabs}

\subsection*{Question 3 (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$ different 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}

\begin{answer}
	\dots 
\end{answer}
\begin{colabs}
	\dots 
\end{colabs}


\section*{Question 4 (15 points)}
For each of the following constructions of a compression function $ h $ from a block cipher $ F_k $, either show an attack or prove collision resistance in the ideal-cipher model:

\begin{enumerate}
	\item $ h(x,k) = F_k(x) $. 
	
	\item $ h(x,k) = F_k(x) \oplus x \oplus k $. 
	
	\item $  h(x,k) = F_k(x) \oplus k $. 
	
\end{enumerate}

\begin{answer}
	\dots 
\end{answer}
\begin{colabs}
	\dots 
\end{colabs}


\section*{Question 5 (15 points)}
In the course slides we informally introduced the notion of Authenticated Encryption with Associated Data (AEAD) when looking at Galois Counter Mode (GCM). An AEAD encryption scheme consists of three algorithms $(\Gen, \Enc, \Dec)$ where the encryption algorithm $\Enc_K(a,m;R)$ takes as 
input a message $m$ associated data $a$ and random coins $R$ and outputs a ciphertext $c$. Similarly, the decryption algorithm $\Dec_K(a,c)$ takes as input a ciphertext $c$ and associated data $a$ and outputs a plaintext message $m$ or $\bot$ indicating failure. 
For correctness we require that for any secret key $K$, associated data $a$ and random coins $R$ we have $\Dec_K(a,\Enc_K(a,m;R))=m$. Intuitively, the scheme should resist chosen plaintext/ciphertext attacks and it should be impossible to forge a new ciphertext and/or tamper with the associated data. Your task is 
to provide a formal security definition that captures these intuitive properties and give a brief, but precise, explanation for why your definition captures these properties. You may choose to either define asymptotic or concrete security. (Hint: Think about what games you can define).  

\begin{answer}
	\dots 
\end{answer}
\begin{colabs}
	\dots 
\end{colabs}

\end{document}