\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