\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{epsfig}

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


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

\begin{document}

\courseheader

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

\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$.}

{\bf Solution}

This is one possible solution (there are many).  We use the fact that
$A \oplus A \oplus B = B$.  We request the MAC's of two unrelated
messages $m_1$, $m_2$, and get $f(m_1), f(m_2)$.

We now construct a new message thus:
\[ M' = m_1 \circ (f(m_1) \oplus m_2) \]
Note that this message is two blocks long, and we can compute it from
the information we have.  We know that the encryption of the above
message is:
\begin{equation*}
\begin{split}
CBC-MAC(M') &= CBC-MAC(m_1 \circ (f(m_1) \oplus m_2)) \\
	& = f \left( f(m_1) \oplus (f(m_1) \oplus m_2) \right) \\
	& = f \left( m_2 \right)
\end{split}
\end{equation*}
Note that the CBC-MAC of the above message is the same as for a
message we have already requested, so we know it.


\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.

{\bf Solution}

Again, this is just one possible solution.

Ask for the following three encryptions:
\begin{eqnarray*}
CBC-MAC(m_1) & = & f(f(m_1) \oplus 1) \\
CBC-MAC(m_2) & = & f(f(m_2) \oplus 1) \\
CBC-MAC(m1 \circ 1 \circ m_3) & = & f(f(f(f(m_1) \oplus 1) \oplus m_3)
\oplus 3)
\end{eqnarray*}

With the above, we can now generate the CBC-MAC of a new three block message:
\[ M' =  m_2 \circ 1 \circ \left( \left[ f(f(m_1) \oplus 1) \right] \oplus 
			\left[ f(f(m_2) \oplus 1) \right]     \oplus
			m_3 \right) \]

Its CBC-MAC is the following:
\begin{equation*}
\begin{split}
CBC-MAC(M') & = f \left( f \left( f \left( f(m_2) \oplus 1 \right) \oplus \left( \left[ f(f(m_1) \oplus 1) \right] \oplus 
			\left[ f(f(m_2) \oplus 1) \right]     \oplus
			m_3 \right) \right) \oplus 3 \right) \\
	& = f \left( f \left( f \left( f(m_1) \oplus 1 \right) \oplus m_3
			\right) \oplus 3 \right)
\end{split}
\end{equation*}

Which is, of course, something we already know.

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


\clearpage
{\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))$

{\bf Solution} Clearly not private, since $M$ is visible.

\item $\enc_{K_1}(M,\MAC_{K_2}(M))$

{\bf Solution} This method appears to be secure

\item $\enc_{K_1}(M),\MAC_{K_2}(M)$

{\bf Solution} depending on the MAC scheme in use, this may not be
private.

\item $\enc_{K_1}(M), \enc_{K_1}(\MAC_{K_2}(M))$

{\bf Solution} appears to be safe.

\item $\enc_{K_1}(M),\MAC_{K_2}(\enc_{K_1}(M))$

{\bf Solution} Again, this appears to be safe.

\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$

{\bf Solution} This scheme may be flawed, depending on the symmetric
encryption scheme being used. Since there is nothing tying $A$ to the
message $M$, it may be possible to generate different messages that
can be concatenated with $A$.

\end{enumerate}

\clearpage
{\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? 

{\bf Solution}

ECB mode basically encrypts each block indpendently. If the only
change is that some bits are corrupted , though no bits are lost or
added, then all the blocks will be the same except for the single
block where the bits are corrupted. This block corresponds to exactly
one source block, which will be corrupt after the decryption. So only
one block will change.

CBC mode chains all the blocks, so errors in one block can lead to
more problems:

\begin{center}
\epsfig{file=sol-2-1.eps}
\end{center}

If C2 is corrupt in the above picture, M3 will be decrypted
incorrectly, as will M2. None of the others should be affected by this
corruption. So a single block corruption affects (at most) 2 source
blocks.

\clearpage
{\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 follwing 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?

{\bf Solution}

$n = pq$. Assume w.l.o.g. that $p<<q$, $m < p$.  If $e = 3$, $m^3 <
p^3 < n$. This means we can compute the decryption of $m^3$ by taking
the integer cubic root (no modulo necessary, since we never 'wrapped
around'). So the choice of $e = 3$ is VERY bad.  One must choose $e$
to be fairly large.

\bigskip

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$.  

{\bf Solution}

If we choose the message $-1 \bmod n \equiv (n-1)$, we know that its
decryption is going to be $-1$ as well. However, we are going to be
given $-1 \bmod p = p-1$, from which we can quickly compute $p$. Note
this creates a ciphertext that would normally not happen since we
assumed that $m < p$, but it is nevertheless a valid attack on this
system.


\clearpage
{\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

{\bf Solution}

{\bf Note:} The system is worse than the problem asks to prove,
since in fact any employee can factor $N$ relatively quickly. However,
that is not what we are being asked to prove, and maybe in this setup
the employees can be trusted.

Eve has $y_B = x ^{e_B} \bmod N$ and $y_C = x^{e_C} \bmod N$. Extended
Euclid, when given $e_B, e_C$ will return $(\alpha, \beta)$ such that
$\alpha e_B + \beta e_C = 1$ (not in a field, but over the integers).

From this fact, Eve can get $(\alpha, \beta)$ and compute:

\begin{equation*}
\begin{split}
 \left[ (y_B)^\alpha \cdot (y_C)^\beta \right] \bmod N & = \
           \left[ (x^{e_B} \bmod N)^\alpha \cdot (x^{e_C}
           \bmod N) ^ \beta \right] \bmod N \\
  & = x^{\alpha e_B} \cdot x^{\beta e_C} \bmod N \\
  & = x^{\alpha e_B + \beta e_C} \bmod N \quad = \quad x^1 \bmod N \\
  & = x
\end{split}
\end{equation*}

She has therefore computed $x$ without needing to factor or break RSA
in any meaningful way. Therefore, this system is flawed.

\end{document}