\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\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{\eqdef}{\stackrel{def}{=}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\indist}{\approx}
\newcommand{\dist}{\Delta}
\newtheorem{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\Adv}{\ensuremath{\mathsf{Adv}}}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{SAT}}}
\newcommand{\COL}{\ensuremath{\mathsf{3COL}}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\Time}{\cclass{Time}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\angles}[1]{\langle #1 \rangle}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Handout 4: Message Authentication Codes and Chosen-Ciphertext Security}
\author{Boaz Barak}
\date{Total of 109 points. \\ Exercises due October 18th, 2005 1:30pm.}
\begin{document}
\maketitle
\begin{exercise}[20 points] Consider the following variant of CMA-security for
MACs: instead of giving the adversary black boxes for both the
signing and verification algorithms, give it only a black box for
the signing algorithm. Let's call this definition CMA'-security.
That is,
\begin{quote} \vspace{-4ex}
\begin{definition}A pair of algorithms
$(\Sign,\Ver)$ (with $\Sign:\bits^n\times\bits^m\To\bits^t$,
$\Ver:\bits^n\times\bits^m\times\bits^t\To\bits$) is a
$(T,\e)$-CMA'-secure MAC if for every $x,k$,
$\Ver_k(x,\Sign_k(x))=1$ andf or every $T$-time $\Adv$, if we run
the following experiment:
\begin{itemize}
\item Choose $k \getsr \bits^n$
\item Give adversary access to black box for $\Sign_k(\cdot)$
\item Adversary \emph{wins} if it comes up with a pair
$\angles{x',s'}$ such that \textbf{(a)} $x'$ is \emph{not} one of
the messages that the adversary gave to the black box
$\Sign_k(\cdot)$ and \textbf{(b)} $\Ver_k(x',s')=1$.
\end{itemize}
Then the probability $\Adv$ wins is at most $\e$.
$(\Sign,\Ver)$ is CMA'-secure if there are super-polynomial
functions $T,\e$ such that for every $n$, $(\Sign,\Ver)$ is
$(T(n),\e(n))$-CMA'-secure. In other words, there is no
polynomial-time $\Adv$ that succeeds with polynomial probability to
break it.
\end{definition}
\end{quote}
\noindent A MAC scheme has \emph{unique tags} if for every message
there is only one tag that passes verification. An equivalent way of
stating this property is that the verification algorithm on input
$x$ and $t$ outputs $1$ if and only if $S_k(x)=1$. Note that the MAC
scheme we saw in class has this property. Prove that for MACs with
unique tags, CMA security and CMA' security are \emph{equivalent}
(e.g., such a scheme is $(T,\e)$-CMA secure if and only if it is
$(T',\e')$-CMA' secure for some $T'$,$\e'$ polynomially related to
$T,\e$. (The condition of unique tags is important --- if a MAC
scheme does \emph{not} have unique tags then these notions may not
be equivalent.)
\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 A CMA-secure MAC scheme has to be \emph{probabilistic} that
is, $\Sign_k(x)$ can't be a deterministic function of $k$ and $x$
and has to toss additional coins.
\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 integrity: In the same setting as the previous item,
\emph{integrity} is preserved. That is, if the receiver obtains
$(y,t)$, where $\Ver_k(y,t)=1$ and computes $x'= \Dec_k(y)$ then
$x=x'$.
\end{enumerate}
\end{exercise}
%\begin{exercise} login protocol using CCA.
%\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. $i$ is a number between $1$ and
$M$. (It is assumed that $k$ will be used to protect the contents of
the hard disk)
\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 $(T,\e)$-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). If
you can, try to explicitly write the overhead as a function of the
other parameters ($T,\e,m,M$). You can assume that $T=1/\e>M>m$.
Also, if it makes your life simpler, you can assume that any
primitives you use (pseudorandom functions, permutations,
generators) are $(2^{n/10},2^{-n/10})$-secure.
\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}
I know this exercise may be too short for those already addicted to
infinitely long crypto homework \verb!:)! If you find yourself in
need of more questions, for additional 10 points you can submit with
this handout the answer to Exercise~9 (the back-door cipher
question) (or a revised answer if you already submitted this).
\end{document}