\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 110 points. Due October 18th, 2007.}
\begin{document}
\maketitle \vspace{-6ex}
\begin{exercise}[30 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}[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}
\end{document}