\documentstyle[11pt,twoside]{article}

\def\handoutdate{August 4, 1998}
\def\handoutname{Problem Session 2}
\def\handoutnumber{8}
\input{defs}


% ========================================================================

\begin{document}

\courseheader

\bigskip
\begin{center}
{\Large{\bf Problem Session 2}}
\end{center}

\bigskip

\bigskip
{\bf Problem 2.1: CBC MAC with variable length.}

Alice and Bob share a secret key $k$. Bob wants an assurance that the
message he receives are really coming from Alice. In order to obtain this 
Alice sends the message $m$ and a MAC along with it ${\sc MAC}_k(m)$. 

We say that a MAC is secure against {\em chosen message attack} if an 
attacker Eve, after requesting the MAC ${\sc MAC}_k(m_i)$ 
of $n$ messages of her choice
$m_1,\ldots,m_n$ will not be able to produce a {\em new} message 
$m \neq m_i$ and a valid ${\sc MAC}_k(m)$.

CBC-MAC is a way of implementing MACs using symmetric encryption scheme. 
Let 
\[f_k : \{0,1\}^{\ell} \rightarrow \{0,1\}^{\ell} \] 
be an encryption function with key $k$ (for example with $\ell=64$, $f$ could 
be DES.) Let $m$ be a message of length $b \ell$ bits. 
\[ m = m_1 \circ \ldots \circ m_b \] 
where $\circ$ denotes concatenation and $m_i$ is a block of length 
$\ell$ bits.  The MAC of $m$ is computed using the cipher $f$ in CBC mode: 
\[ {\sc MAC}_k(m) = f_k(f_k( \ldots f_k(f_k(m_1) 
			\oplus m_2) \oplus \ldots m_{b-1}) \oplus m_b) \]

\begin{enumerate}

\item  Show that the CBC--MAC does not support variable length
input. That is show that if messages have variable length it is possible 
to device a chosen message attack. 
{\em Hint: The idea is to ask for the MACs of two messages of length 
$\ell$ and construct from them the MAC of a message of length $2\ell$.}

\item Suppose the length of the messages is always smaller than 
$2^{\ell}$. An attempt to get around the above problem would be to
append the length of the message at the end as an extra block, before 
computing the MAC. Show that it is
still possible to mount an effective chosen message attack.

% \item Think of a possible fix. 
\end{enumerate}


\bigskip
{\bf Problem 2.2: Simultaneous encryption and authentication}

Let $(\enc,\dec)$ be a symmetric encryption scheme and $\MAC$ a
message authentication scheme. Suppose Alice and Bob share two
independent keys
$K_1$ and $K_2$ for privacy and authentication respectively. They want
to exchange messages $M$ in a private and authenticated way. Consider
sending each of the following as a means to this end, and indicate
whether it is secure or not. 
\begin{enumerate}

\item $M,\MAC_{K_2}(\enc_{K_1}(M))$
\item $\enc_{K_1}(M,\MAC_{K_2}(M))$
\item $\enc_{K_1}(M),\MAC_{K_2}(M)$
\item $\enc_{K_1}(M), \enc_{K_1}(\MAC_{K_2}(M))$
\item $\enc_{K_1}(M),\MAC_{K_2}(\enc_{K_1}(M))$
\item $\enc_{K_1}(M,A)$ where $A$ encodes the identity of Alice. Bob decrypts
the ciphertext and checks that the second half of the plaintext is $A$

\end{enumerate}

\bigskip
{\bf Problem 2.3: Error Correction in DES ciphertexts}

Suppose that $n$ plaintext blocks $x_1$,$\ldots$,$x_n$ are
encrypted using DES producing ciphertexts $y_1,\ldots,y_n$. Suppose that
one ciphertext block, say $y_i$, is transmitted incorrectly (i.e. some
1's are changed into 0's and viceversa.) How many plaintext blocks will 
be decrypted incorrectly if the ECB mode was used for encryption? 
What if CBC is used? 

\bigskip

{\bf Problem 2.4: RSA for paranoids.}

The best factoring algorithm known to date (the {\em number field sieve}) 
runs in 
$$e^{O(\log^{1/3} n \log \log^{2/3} n)}$$
That is, the running
time does not depend on the size of the smallest factor, but rather 
in the size of the whole composite number. 

The above observation seem to suggest that in order to preserve the 
security of RSA, it may not be necessary to increase the size of
both prime factors, but only of one of them. 

Shamir suggested the follwong version of RSA that he called 
{\em unbalanced RSA} (also known as RSA for paranoids). Choose
the RSA modulus $n$ to be 5,000 bits long, the product of a 500-bits
prime $p$ and a 4,500-bit prime $q$. Since usually RSA is usually used just to 
exchange DES keys we can assume that the messages being encrypted are
smaller than $p$. 

{\bf (A)} How would you choose the public exponent $e$? Is 3 a good
choice?

Once the public exponent $e$ is chosen, one computes $d=e^{-1} \bmod \phi(n)$
and keep it secret. The problem with such a big modulus $n$, is that 
decrypting a ciphertext $c=m^e \bmod n$ may take a long time (since one has 
to compute $c^d \bmod n$.) But since we know that $m<p$ we can 
just use the Chinese Remainder Theorem and compute $m_1=c^d \bmod p=m$.
Shamir claimed that this variant of RSA achieves better security against 
the advances of factoring, without losing in efficiency. 

{\bf (B)} Show how with a single chosen message attack (i.e. obtaining
the decryption of a message of your choice) you can completely break the
unbalanced RSA scheme, by factoring $n$.  

\bigskip

{\bf Problem 2.5: Common modulus RSA.}

Suppose Bob ($B$) and Charlie ($C$) use the same modulus $N$ in an RSA
cryptosystem, with different encryption exponents. That is, $B$'s
public key is $(N,e_B)$ and $C$'s public key is $(N,e_C)$. Suppose
further that $\gcd(e_B,e_C)=1$.

How could this happen? Say $B$ and $C$ belong to the same organization
which has one public modulus $N$. Different users just have different
encryption exponents.

Now suppose $A$ sends the {\em same\/} message $x$ to both $B$ and
$C$ in the standard RSA cryptosystem. Namely she computes $y_B=
x^{e_B}\bmod N$ and sends it to $B$, and she also computes
$y_C=x^{e_C}\bmod N$ and sends it to $C$.

Let $E$ be the adversary, who is wiretapping all communication. She
picks up $y_B$ and $y_C$. She of course knows all the public key
information, namely $(N_B,e_B)$, $(N_C,e_C)$, and the fact that
$\gcd(e_B,e_C)=1$. Let us say she is also aware of the fact that
$y_B,y_C$ are ciphertexts of the same message $x$. But she does
not know $x$.

However, now show how she can compute $x$ from the information she
holds. 

{\sl Hint:} Recall that if $a,b$ are numbers such that $\gcd(a,b)=1$
then the extended Euclid's algorithm can be used to compute numbers
$\alpha,\beta$ for which $\alpha a+\beta b=1$.
\bigskip




\end{document}
