\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
\newif\ifpdf
\ifx\pdfoutput\undefined \else
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\else
\pdftrue
\fi
\fi
\fi
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\PH}{\cclass{PH}}
\newcommand{\coNP}{\cclass{coNP}}
\newcommand{\AvgP}{\cclass{AvgP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\BQP}{\cclass{BQP}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newcommand{\BPL}{\cclass{BPL}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\vartriangle}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\LC}{\mathcal{LC}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\pmo}{\{\pm 1\}}
\newcommand{\set}[1]{\{ #1 \}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 4.}
\author{Boaz Barak}
\date{Total of 130 points. Due March 3rd, 2010.}
\begin{document}
\maketitle \vspace{-6ex}
\begin{exercise}[20+10 points]
Recall that in class we gave a construction of a \emph{probabilistic} CPA-secure encryption scheme (i.e., the function
$\Enc$ used extra randomness in computing the encryption). A \emph{deterministic} encryption scheme, is a pair $(E,D)$
such that $E$ is a function of the key and message only and uses no additional randomness. It of course must satisfy as
well that $D_k(E_k(x))=x$ for every key $k$ and message $x$.
\begin{enumerate}
\item Prove that a deterministic encryption scheme cannot be CPA secure.
\item Say that an encryption (E,D) is \emph{unique message CPA secure} if it satisfies the following relaxed
variant of CPA security--- we make the same definition as CPA security except we say that Eve cannot uss for
the two challenge messages $x_1,x_2$ of the challenge phase any of the messages she asked for encryptions to in
the attack phase. Give a construction based on the tools we learned in class (PRG's, PRF's, PRP's) of a unique
messages CPA secure \emph{deterministic} encryption scheme.
\item Suppose you a broker wants to encrypt his communication, and all of his messages are either ``buy'' or
``sell''. He wants to ensure that an adversary monitoring on the line, even if it found out by observing the
marker what were the first $i$ messages, will have no non-trivial advantage in predicting the next message
given the ciphertext. Would you recommend the Broker must use a CPA secure encryption or will a unique message
CPA secure scheme suffice?
For 10 extra points, \emph{prove} that given an encryption scheme with appropriate security, assuming that the
broker chooses ``sell'' with probability $p$ and ``buy'' with probability $1-p$, such an adversary will not be
able to guess the right message with probability better than $\max\{ p,1-p\}+ \e(n)$ where $\e$ is a negligible
function.
\end{enumerate}
\end{exercise}
%\begin{exercise}[20 points] Recall that in class we gave a construction of a \emph{probabilistic}
%CPA-secure encryption scheme (i.e., the function $\Enc$ used extra randomness in computing the encryption).
%
%\begin{enumerate}
%\item Show that there is no \emph{deterministic} encryption scheme satisfying the CPA security definition we gave
% in class.
%
%\item Give a variant of the CPA security definition for \emph{stateful} encryption schemes, where $\Enc$ and $\Dec$
% can keep state between each encryption and decryption they perform. Prove that there exists a deterministic
% stateful encryption scheme that is CPA secure under your definition.
%
%\end{enumerate}
%
%\end{exercise}
\begin{exercise}[25 points] Let $\{ p_k \}_{k\in\bits^*}$ be a pseudorandom permutation
collection, where for $k \in \bits^n$, $p_k$ is a permutation over $\bits^m$.
\begin{enumerate}
\item Consider the following encryption scheme $(\Enc,\Dec)$: $\Enc_k(x) = p_k(x)$ , $\Dec_k(y)=p_k^{-1}(y)$. Prove
that this scheme is \emph{not} a CPA-secure encryption.
\item Consider the following scheme $(\Enc,\Dec)$ that encrypts $m/2$-bit messages in the following way: on input
$x\in\bits^{m/2}$, $\Enc_k$ chooses $r \getsr\bits^{m/2}$ and outputs $p_k(x,r)$ (where comma denotes
concatenation), on input $y\in\bits^{m/2}$, $\Dec_k$ computes $(x,r) = p^{-1}_k(y)$ and outputs $x$. Prove that
$(\Enc,\Dec)$ \emph{is} a CPA-secure encryption scheme. See footnote for hint\footnote{\textbf{Hint:} \tiny Try
proving first for partial credit that this scheme satisfies the weaker notion of \emph{multiple message
security}. That is, for every polynomial $p=p(n)$ and $x_1,\ldots,x_p,x'_1,\ldots,x'_p \in \bits^{m/2}$ the two
sequences of random variables $\angles{ Enc_K(x_1) ,\ldots, \Enc_K(x_p) }$ and $\angles{ \Enc_K'(x'_1) ,
\ldots, \Enc_K'(x'_p)}$ are computationally indistinguishable (where $K$ and $K'$ are two independent random
variables distributed uniformly over $\bits^n$).}
\end{enumerate}
\end{exercise}
\newcommand{\CBC}[2]{\mathsf{CBC}_{#1}\angles{#2}}
\begin{exercise}[25 points] The CBC construction is often used to get
an encryption for larger message size. If $p:\bits^m\To\bits^m$ is a permutation, then $\CBC{\ell}{p}$ is a permutation
from $\bits^{\ell\cdot m}$ to $\bits^{\ell\cdot m}$ defined in the following way: for $x_1,\ldots,x_{\ell} \in
\bits^m$, let $y_0 = 0^n$ and define $y_i = p(y_{i-1} \oplus x_i)$. Then, $\CBC{\ell}{p}(x_1,\ldots,x_{\ell}) =
(y_1,\ldots,y_{\ell})$.\footnote{The string $y_0$ is called the initialization vector or IV, and in practice is often
chosen to be different than $0^m$. However, as long as it's a fixed public value this doesn't make any security
difference. Note that the KL book considers a different variant of CBC where the IV is chosen independently at random
for each encryption.} Note that the inverse of $\CBC{\ell}{p}$ can be computed in a similar way using the inverse of
$p(\cdot)$.
Let $\{ p_k \}$ be a pseudorandom permutation collection. Determine the CPA-security of the following two encryption
schemes which are based on the CBC construction. That is, for each scheme either prove that it is CPA-secure or give an
attack showing that it is not. For simplicity, we consider only the 3-block variant of the scheme (i.e. $\ell=3$).
\begin{enumerate}
\item\emph{(Padding in the end)} Given $p_k:\bits^m \To \bits^m$ and a message $x=x_1,x_2 \in\bits^{2m}$, $\Enc_k$
chooses $r \getsr \bits^m$ and outputs $\CBC{3}{p_k}(x_1,x_2,r)$. Decrypting done in the obvious way.
\item\emph{(Padding in the start)} Given $p_k:\bits^m \To \bits^m$ and a message $x=x_1,x_2 \in\bits^{2m}$,
$\Enc_k$ chooses $r \getsr \bits^m$ and outputs $\CBC{3}{p_k}(r,x_1,x_2)$. Decrypting done in the obvious way.
\end{enumerate}
\end{exercise}
\begin{exercise}[25 points] Prove that the following encryption scheme is
CCA secure. Let $\set{ p_k }$ be a collection of pseudorandom permutations mapping $\bits^{3n}$ to $\bits^{3n}$.
\begin{itemize}
\item To encrypt $x\in \bits^n$ with key $k$ do the following: choose $r\getsr \bits^n$, and send $p_k(x \| r
\| 0^n)$ (were $\|$ denotes concatenation).
\item To decrypt $y \in \bits^{3n}$, compute $x\|r\|w = p_k^{-1}(y)$. if $w\neq 0^n$ then output $\bot$.
Otherwise, output $x$.
\end{itemize}
\end{exercise}
\begin{exercise}[25 points] Let $(E,D)$ be a CPA secure scheme with key-size=message-size=$n$, and let $\{ f_k \}$ be a collection
of PRFs such that for every $k\in\bits^n$, $f_k:\bits^n\To\bits^n$. Consider the following scheme $(E',D')$:
\begin{description}
\item[Key] $k,k'$ each chosen uniformly and independently from $\bits^n$.
\item[Encrypt] $E'_{k,k'}(x) = (y,t)$ where $y=E_k(x)$ and $t = f_{k'}(y)$.
\item[Decrypt] $D_{k,k'}(y,t) = \bot$ if $f_{k'}(y)\neq t$ and $D_k(y)$ otherwise.
\end{description}
\begin{enumerate}
\item Prove that the scheme $(E',D')$ is CCA secure.
\item Let $(E'',D'')$ be the same scheme except that we reuse the key for the PRFs and encryption. That is, we
set $k=k'$ to be the same string chosen at random in $\bits^n$. Prove that this scheme is not necessarily
even CPA secure! That is, show that there exists a CPA secure $(E,D)$ and a PRF collection $\{ f_k \}$ such
that if we build $(E'',D'')$ using these components then the resulting scheme is not CPA secure. (For
partial credit, show that it's not CCA secure only.)
This example shows that ``reusing'' or ``recycling'' keys in cryptography is a very dangerous practice.
\end{enumerate}
\end{exercise}
\iffalse
\begin{exercise}[40 points] For each of the following statements either prove
that it is true, or give a counterexample showing that it is
false:\footnote{Counterexamples can be contrived as long as they
are valid. That is, if a statement says that every MAC scheme
satisfies a certain property then to show this statement false
you can present \emph{any} chosen-message attack secure MAC
scheme that does not satisfy this property. The MAC scheme can
be constructed just for the sake of a counterexample, and does
not have to be ``natural looking'', as long as it is
chosen-message attack secure.}
\begin{enumerate}
\item A MAC tag always maintains secrecy of the message.
That is, if $(\Sign,\Ver)$ is a CMA-secure MAC with
$m$-bit long messages and $n$-bit long keys, then for
every two strings $x$ and $x'$ in $\bits^m$, the random
variable $\Sign_{U_n}(x)$ is computationally
indistinguishable from the random variable
$\Sign_{U_n}(x')$.
\item A MAC tag always has to be longer than the message.
That is, for every MAC scheme $(\Sign,\Ver)$ ,
$|\Sign_k(x)| \geq |x|$.
\item Reusing a key for authentication and encryption does
not harm secrecy: Suppose that $(\Sign,\Ver)$ is a
secure MAC with $n$ bit key and $(\Enc,\Dec)$ is a
CPA-secure encryption scheme with $n$ bit key. Suppose
that a sender chooses $k \getsr bits^n$ and a random
number $x \getsr {1,\ldots,100}$, computes $y=\Enc_k(x)$
and sends $y, \Sign_k( y)$ (note that the same key $k$
is used for both authentication and encryption). Then,
\emph{secrecy} is preserved: an eavesdropper can not
guess $x$ with probability higher than, say $1/99$.
\item Reusing a key for authentication and encryption does
not harm secrecy if we use a pseudorandom generator.
Suppose that $\PRG$ is a PRG mapping $\bits^n$ to
$\bits^{2n}$ and in the scenario above the sender after
choosing the key $k$ first computes $k_1k_2 = \PRG(k)$
(i.e., $k_1$ denotes the first $n$ bits of the PRG's
output and $k_2$ denotes the second $n$ bits) and then
uses $k_1$ for the encryption and $k_2$ for the MAC.
Then, the eavesdropper can not guess $x$ with
probability higher than, say $1/99$.
\end{enumerate}
\end{exercise}
\begin{exercise}[40+10 points] An \emph{encrypted file system} is used to ensure
that theft or unauthorized access to a laptop or desktop
computer will not cause any compromise of sensitive data. The
idea is that there is a secret key $k$ on a smartcard, and this
key is required to read and write to the hard disk. Formally,
the interface to such a system is the operations:
\begin{description}
\item[\texttt{writeBlock$_k$($i$,$x$)}] Write $x\in\bits^m$
to the $i^{th}$ block of the hard disk using the secret
key $k$. We let $M$ denote the total number of blocks.
\item[\texttt{readBlock$_k$($i$)}] Returns a string in
$\bits^m$, which is the (decrypted) contents of the
$i^{th}$ block of the hard disk. We assume that if the
system detects that this block was tampered with then it
shuts down the computer.
\end{description}
Intuitively, the security of the system should be as follows:
suppose that each night, after using the computer normally (word
processing, internet, email etc..) for the day, the user of the
computer leaves home with her smartcard, and then an attacker
has complete access to the computer (i.e., able to read and
write directly to the hard disk). Then, the attacker should not
be able to learn anything about the contents. Of course the
attacker can ``wipe out'' the hard disk, in which case the
system will detect this and shut the computer down, but we do
not consider this a break of the system.
\begin{enumerate}
\item Suppose that we are only interested in preserving the
\emph{secrecy} of the data on the hard disk. is it still
important to prevent an attacker from \emph{modifying}
the contents of a block on the hard disk without being
detected?
\item Write a formal definition for security of an encrypted
file system scheme.
\item Give a construction for an encrypted file system. That
is, give algorithms for \texttt{writeBlock} and
\texttt{readBlock}. You can assume that you have access
to the functions \texttt{directWrite}($i,y$) and
\texttt{directRead}($i$) that allow you to directly read
and write blocks of the underlying hard disk. We denote
the block size of the underlying disk by $m'$ and the
total number of blocks by $M'$. The numbers $m$ and $M$
(defining the block size and number of blocks you
present to the user) are given to you, but you can
choose $m'$ and $M'$ to be any values of your choice.
Try to minimize the \emph{overhead} $M'm' - Mm$ (that
is, the difference between the number of bits you allow
the user to use and the number of bits you actually need
in the hard disk).
\item Prove that your construction remains secure in the
following two attack scenarios (for $10$ points bonus -
do this by first proving that your construction
satisfies your definition of Item~2, and then proving
that any construction satisfying that definition remains
secure under these attacks).
\begin{enumerate}
\item User chooses $x$ to be a random number between $1$
and $1000$ and writes it in the first block (i.e.,
runs \texttt{writeBlock}$_k$(1,$x$)). The attacker
then gets access to the hard disk and outputs a
guess $x'$. System is secure under this attack if
the probability that $x'=x$ is less than $1/999$
(for large enough $n$).
\item User chooses $x$ to be a random number between $1$
and $1000$ and writes it in the first block (i.e.,
runs \texttt{writeBlock}$_k$(1,$x$)) and writes the
number $1$ to the second block (i.e., runs
\texttt{writeBlock}$_k$(2,1)). The attacker then
gets access to the hard disk. User then reads the
value $y$ of the second block and publishes it on
the web (where everyone including the attacker can
see it). Attacker then gets again access to the hard
disk and outputs a guess $x'$. System is secure
under this attack if the probability that $x'=x$ is
less than $1/999$ (for large enough $n$).
\end{enumerate}
\end{enumerate}
\end{exercise}
\fi
\end{document}