\def\me{1} %Change to 0 so that solutions appear. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \def\num{1} %homework number \def\daystohandout{9} %days to complete it from today \def\modulename{Cryptography} \def\course{$\begin{array}{c} \mbox{UPM}\end{array}$\ ~~~~~Computer Security} %course name % \documentclass[11pt]{article} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{latexsym} \usepackage[usenames, dvipsnames]{color} \usepackage{advdate} \setlength{\oddsidemargin}{.0in} \setlength{\evensidemargin}{.0in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-0.4in} \setlength{\textheight}{8.5in} \newcommand\startingdate{\today} %date the homework is given \newcommand\due{\AdvanceDate[\daystohandout]\today} %due date % Ignore stuff \newcommand{\ignore}[1]{} \newcommand{\handout}[5]{ \renewcommand{\thepage}{\arabic{page}} \noindent \begin{center} \framebox{ \vbox{ \hbox to 5.78in { {\bf \course} \hfill #2 } \vspace{4mm} \hbox to 5.78in { {\Large \hfill #5 \hfill} } \vspace{2mm} \hbox to 5.78in { {\it #3 \hfill #4} } } } \end{center} \vspace*{4mm} } \def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}} \def\qed{\hspace*{\fill} \vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}} \newenvironment{solution}{\begin{trivlist}\item[]{\bf Solution:}} {\qed \end{trivlist}} \newenvironment{solsketch}{\begin{trivlist}\item[]{\bf Solution Sketch:}} {\qed \end{trivlist}} \renewcommand{\eqref}[1]{Equation~(\ref{eq:#1})} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{observation}[theorem]{Observation} \newtheorem{proposition}[theorem]{Proposition} \newcommand{\definitionclose}{\hspace*{\fill}$\diamondsuit$} \newcounter{defcounter} \setcounter{defcounter}{0} \newenvironment{definition}{\medskip\noindent\refstepcounter{defcounter}{\sc Definition \thedefcounter}\hspace{1ex}}{\definitionclose \smallskip} % \newtheorem{claim}[theorem]{Claim} \newtheorem{fact}[theorem]{Fact} \newtheorem{assumption}[theorem]{Assumption} \newcommand{\hint}[1]{({\bf Hint}: {#1})} %Put more macros here, as needed. \newcommand{\al}{\alpha} \newcommand{\Z}{\mathbb Z} \renewcommand{\ni}{\noindent} \newcommand{\room}{\medskip\ni} \newcommand{\brak}[1]{\langle #1 \rangle} \newcommand{\bit}[1]{\{0,1\}^{#1}} \newcommand{\zo}{\{0,1\}} \newcommand{\nin}{\not\in} \newcommand{\set}[1]{\{#1\}} \newcommand{\jac}[2]{\left(\frac{#1}{#2}\right)} \newcommand{\comput}{\approx} \def\owf{{\sf OWF}} \def\owp{{\sf OWP}} \def\prg{{\sf PRG}} \def\adv{{\sf Adv}} \def\prf{{\sf PRF}} \def\ppt{{\sf PPT}} \def\negl{{\sf negl}} \def\poly{{\sf poly}} \newcommand{\M}{\mathcal{M}} \newcommand{\C}{\mathcal{C}} \newcommand{\K}{\mathcal{K}} \newcommand{\xor}{\oplus} \newcounter{pppp} \newcommand{\prob}{\arabic{pppp}} %problem number \newcommand{\increase}{\addtocounter{pppp}{1}} %problem number %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%% LATEX COMMAND FOR PROTOCOL FIGURES %%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% BCK flow commands \newcommand{\verylongrightarrow}[1] %longleft and rightgoing arrows {\setlength{\unitlength}{.01in} %for protocols \begin{picture}(#1,1) \put(0,0){\thicklines\vector(1,0){#1}} \end{picture}} \newcommand{\rightgoing}[2]{{\stackrel{{\displaystyle #1}} {\verylongrightarrow{#2}}}} \newcommand{\verylongleftarrow}[1] {\setlength{\unitlength}{.01in} \begin{picture}(#1,1) \put(#1,0){\thicklines\vector(-1,0){#1}} \end{picture}} \newcommand{\leftgoing}[2]{{\stackrel{{\displaystyle #1}} {\verylongleftarrow{#2}}}} %\newcommand{\leftgoinga}[1]{\leftgoing{#1}{400} } %\newcommand{\rightgoinga}[1]{\rightgoing{#1}{400} } \newcommand{\longleft}[1]{\leftgoing{#1}{400} } \newcommand{\longright}[1]{\rightgoing{#1}{400} } \newcommand{\shortleft}[1]{\leftgoing{#1}{200} } \newcommand{\shortright}[1]{\rightgoing{#1}{200} } \newcommand{\shortleftright}[1]{\leftrightgoing{#1}{200} } \newcommand{\verylongleft}[1]{\leftgoing{#1}{500} } \newcommand{\verylongright}[1]{\rightgoing{#1}{500} } \def\sep{\,,\,} %used with arrow figures \newcommand{\lncs}[1]{#1} \newcommand{\full}[1]{} %\def\Hk{H} %\def\Hl{\bar H} \newcommand{\pprotocol}[5]{ {\begin{figure}[#4] \lncs{ } \begin{center} \fbox{ \small \hbox{\quad \full{\begin{minipage}{6.5in}} \lncs{\begin{minipage}{6.3in}} % \begin{center} % {\bf #1} % \end{center} #5 \lncs{ \vspace{-.45cm} } \caption{\label{#3} #2} \end{minipage} \quad } } \end{center} \lncs{ } \end{figure} } } %1:TITLE 2: caption 3: label 4:htb 5: content \newcommand{\protocol}[4]{ \pprotocol{#1}{#2}{#3}{htbp!}{#4} } %%%%%%%%%% END LATEX COMMAND FOR PROTOCOL FIGURES %%%%%%%%%%%%%%%% % Uncomment to remove page numbers %\pagestyle{empty} %first argument description, second number of points \newcommand{\newproblem}[2]{\increase \section*{Problem \prob~(#1) \hfill {#2}}} \begin{document} \handout{PS\num}{Date: \startingdate}{ %Name: }{ Deadline: \due }{\modulename~Module - Homework} \ignore{ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % New Problem template %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newproblem{Topic -- Question name}{X Points} text \ni Answer the following questions: \begin{itemize} \item[(a)] (x points) [question] \\ \hint{ hint-if-needed} \ifnum\me=0 \begin{solution} Write solution here. \end{solution} \fi \item[(b)] (y points) [question] \ifnum\me=0 \begin{solution} Write solution here. \end{solution} \fi \end{itemize} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % begin Crypto %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\newproblem{Cryptography}{20 Points} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{(1) Randomized encryption is not enough (6 Points)} In class we discussed that a deterministic encryption scheme cannot be secure in the IND-CPA sense. Also, we saw that for this reason the ECB mode of operation is not IND-CPA secure. In this problem you will prove that simply randomizing an encryption method is not sufficient to make the encryption IND-CPA secure. \medskip Let $E_{K}: \bit{n} \to \bit{n}$ be a {\em blockcipher} which supports inputs of $n$ bits, and consider the following randomized version of ECB: \begin{itemize} \item \underline{$\mathsf{RandECB\mbox{-}Encrypt}(K, M)$:} the algorithm takes as input the key $K$ and a message $M$ consisting of $L$ blocks of $n$ bits each, $M = M_1 || M_2 || M_3 || \cdots || M_{L} $, and performs the following steps: \begin{itemize} \item Sample a random $n$-bit string $IV \leftarrow \{0,1\}^{n}$; \item For $i=1$ to $L$: \item ~~Compute $C_i \leftarrow E_K(IV \xor M_i)$; \item Output $IV || C_1 || \cdots || C_{L}$. \end{itemize} \end{itemize} \begin{itemize} \item[(a)] (1 point) Show a decryption algorithm for this encryption, and prove its correctness. \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \item[(b)] (5 points) Show an IND-CPA attack against the scheme. Namely, describe an algorithm which: chooses two specific messages of two blocks each, $M=M_1 || M_2$ and $M'=M'_1 || M'_2$; receives a ciphertext $C^* = (IV^{*} || C^{*}_1 || C^{*}_{2})$ that is computed as either $\mathsf{RandECB\mbox{-}Encrypt}(K, M)$ or $\mathsf{RandECB\mbox{-}Encrypt}(K, M')$; and efficiently determines which is the case. Concretely, how can you choose $M$ and $M'$? What test can you do on $C^{*}$? \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection*{(2) Encryption is not a secure MAC method (4 points)} In class we discussed that using a secure encryption as a method to generate MACs may not guarantee integrity. In this problem you are asked to prove that this is the case for the OFB mode of operation. Let $E_{K}: \bit{n} \to \bit{n}$ be a {\em blockcipher} which supports inputs of $n$ bits, and consider the OFB encryption method that we studied in class. For a message $M$ of length $2n$, OFB with $E_{K}$ works as follows. \begin{itemize} \item \underline{$OFBEncrypt(K, M)$:} on input the key $K$ and a message $M$ consisting of two blocks of $n$ bits each, $M = M_1 || M_2$, choose $IV \leftarrow \bit{n}$ uniformly at random, compute \[ C_1 \leftarrow E_K(IV) \oplus M_1, \quad C_2 \leftarrow E_{K}(E_K(IV)) \oplus M_2 \] and return $(IV, C_1, C_2)$. \item \underline{$OFBDecrypt(K, (IV, C_1, C_2))$:} on input the key $K$ and a ciphertext $(IV, C_1, C_2)$, compute \[ M_1 \leftarrow E_K(IV) \oplus C_1, \quad M_2 \leftarrow E_{K}(E_K(IV)) \oplus C_2 \] and return $(M_1, M_2)$. \end{itemize} Next, consider the following MAC candidate scheme \begin{itemize} \item \underline{$MAC(K, M)$:} output $T \leftarrow OFBEncrypt(K,M)$; \item \underline{$Verify(K, M, T)$:} output `accept' iff $M = OFBDecrypt(K,T)$. \end{itemize} and consider an attacker who sees a MAC $T$ on a message $M$. \medskip \ni Describe an attack algorithm that, without the knowledge of the secret key $K$, can create a valid MAC on any other message $M^{*}$ (different from $M$). Justify the correctness of the attack. Namely, describe an algorithm that on input a message $M$ and a valid MAC $T = (IV, C_1, C_2)$ for it, outputs a valid MAC $T^* = (IV^*, C_1^*, C_2^*)$ for a given message $M^{*}$.\\ \\ $Attack(M, T, M^{*})$:\\ \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \subsection*{(3) Security of Hash-and-Sign Digital Signatures (6 points)} Let $\Sigma = (Sign, Ver)$ be a digital signature that supports messages of fixed length $\ell$, i.e., any $M \in \{0,1\}^{\ell}$. As we have seen in the class, we can use $\Sigma$ to construct a scheme for arbitrarily long messages -- i.e., any $M \in \{0,1\}^{*}$ -- by combining it with a collision-resistant hash function $H: \{0,1\}^* \to \{0,1\}^{\ell}$. Precisely, the new digital signature scheme for arbitrary messages is $\Sigma^* = (Sign^*, Ver^*)$ where the signing and verification algorithms are defined as follows: $$Sign^*(sk, M) := Sign(sk, H(M))$$ $$Ver^*(pk, M, \sigma) := Ver(pk, H(M), \sigma)$$ The security claim is that $\Sigma^*$ is a secure digital signature scheme (for messages in $\{0,1\}^{*}$) if: $\Sigma$ is a secure digital signature (for messages in $\{0,1\}^{\ell}$), and $H$ is a collision-resistant hash function. \medskip \begin{itemize} \item [a)] (4 points) Suppose that the hash function $H$ used in the construction of $\Sigma^*$ is {\em not} collision resistant. How can you break the security (unforgeability) of $\Sigma^*$? Describe an attack against the security of $\Sigma^*$, and justify why the attack works. ({\bf Hint:} The attacker can obtain one signature (produced using $Sign^*$) on a message $M_1$ of its choice, and then it must produce a forgery, that is a valid signature on a new message $M_2 \neq M_1$. Recall that this adversary must use the fact that the collision-resistance of $H$ can be broken.) \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \item [b)](1 point) Suppose that in the digital signature scheme $\Sigma^*$ above we use some function $H$ that when applied to messages that have more than $\ell$ bits, say $(x_1,x_2,x_3,\dots,x_m)$ with $m>\ell$, then $$H (x_1,x_2,x_3,\dots, x_m)=(x_1,x_2,\dots,x_{\ell-1}, x_{\ell}\xor x_{\ell+1}\xor...\xor x_m)$$ To be more clear \begin{itemize} \item Define the first $\ell-1$ bits of the output to be the first $\ell-1$ bits of the input. \item Define the last bit of the output to be the XOR of the remaining bits of the input. \end{itemize} Regardless of how $H$ is defined for messages of $\ell$ bits or less, $H$ can not be collision resistant (and then the digital signature scheme $\Sigma^*$ cannot be secure because of part a)). Why is it not collision resistant? \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \item [c)](1 point) Suppose instead we use some function $H$ that when applied to messages that have $\ell$ bits or less, pads the message with zeros until we get $\ell$ bits and then outputs that string. That is, whenever $m\leq \ell$: $$H(x_1,x_2,\dots,x_m)=(x_1,x_2,\dots,x_m,\underbrace{0,\dots,0}_{\ell-m \textrm{ zeros}})$$ Assume $\ell$ is at least 2. Regardless of how $H$ is defined for more than $\ell$ bits, $H$ can not be collision resistant (and then the digital signature scheme $\Sigma^*$ cannot be secure). Why is it not collision resistant? \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \end{itemize} \subsection*{(4) Authenticated communication (4 points)} Suppose that Bob has a public key $pk_{Bob}$ certified by a certification authority (where he knows the corresponding secret key $sk_{Bob}$) trusted by both Alice and Bob, but Alice does not have such a certified key pair. We assume that Bob's key can be used both for public key encryption and for digital signatures. Alice wants to communicate with Bob through an insecure channel where Eve can see and modify messages. In order to have faster communication, Alice wants to use a symmetric key encryption scheme to encrypt messages. Alice and Bob come up with the following protocol: \underline{Alice:} Chooses a key $K$ and encrypts $K$ under Bob's public key $pk_{Bob}$, i.e., she sends $c=Enc(K,pk_{Bob})$ \underline{Bob:} Decrypts the key $K$ using his secret key (i.e. $K=Dec(c,sk_{Bob})$) and sends the message $m=\texttt{``received''}$ signed with his secret key, i.e. he computes $\sigma=Sign(m,sk_{Bob})$ and sends $(m, \sigma)$ to Alice. \underline{Alice:} Verifies the signed message by Bob by applying $Ver(m,\sigma,pk_{Bob})$. If this outputs $1$, she will start to use $K$ to send encrypted messages to Bob with the symmetric key encryption scheme. \begin{itemize} \item [(a)] (2 points) Can Bob be sure that it is Alice who is sending the message $c$? \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \item [(b)] (2 points) Suppose that Bob has executed the same protocol before with Amanda. When Alice and Bob execute this protocol, can Alice be sure that she has received the message $m$ from Bob, even though the verification of its signature outputs 1? \ifnum\me=0 \begin{solution} **** INSERT SOLUTION HERE **** \end{solution} \fi \end{itemize} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}