\documentstyle[12pt]{article}

\textwidth=6in
\oddsidemargin=0.25in
\evensidemargin=0.25in
\topmargin=-0.1in
\footskip=0.8in
\parindent=0.0cm
\parskip=0.3cm
\textheight=8.00in
\setcounter{tocdepth} {3}
\setcounter{secnumdepth} {2}
\newtheorem{theorem}{Teorema}
\newtheorem{exercise}{Ejercicio}
\newtheorem{corollary}{Corolario}
\newtheorem{lemma}{Lema}
\newtheorem{observation}{Observaci\'on}
\newtheorem{comentary}{Comentario}
\newtheorem{proposition}{Proposici\'on}
\newtheorem{definition}{Definici\'on}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\newcommand{\qedbox}{\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newcommand{\qed}{\nopagebreak\mbox{}\hfill\qedbox\smallskip}
\newcommand{\startproof}{\noindent{\em Dem:}\hspace{1em}}
\newenvironment{dem}{\startproof}{\qed}
\newenvironment{proof}{{\bf Dem:}\hspace{1em}}{\qed\newline}


\newcommand{\catedra}[4]{
   \pagestyle{headings}
   \thispagestyle{plain}
   \newpage
   \noindent
   \begin{center}
   \makebox[0in]{\framebox{
      \vbox{
    \hbox to 6in { {\bf MA-53G Intr. a la Criptograf\'{\i}a
                        \hfill Semestre Primavera, 1996}  }
       \vspace{4mm}
       \hbox to 6in { {\Large \hfill C\'atedra No. #1 : #2 \hfill} }
       \vspace{2mm}
       \hbox to 6in { {\it Transcriptor: #3 \hfill} }
      }
   }}
   \end{center}
   \markboth{C\'atedra No. #1 : #2}{C\'atedra No. #1 : #2}
   \vspace*{4mm}
}

% LISTA DE MACROS PERSONALES COMIENZA AQUI

\renewcommand{\emph}[1]{{\em #1}}
\newcommand{\plain}{{\cal P}}
\newcommand{\cipher}{{\cal C}}
\newcommand{\key}{{\cal K}}
\newcommand{\encrip}{{\cal E}}
\newcommand{\decrip}{{\cal D}}

\newcommand{\modulo}{{\cal Z}}
\newcommand{\kernel}{\mbox{\rm Ker}}
\newcommand{\determ}[1]{\mbox{\rm det}(#1)}
\newcommand{\mcd}[2]{\mbox{\rm mcd}(#1,#2)}
\newcommand{\mcm}[2]{\mbox{\rm mcm}(#1,#2)}
\newcommand{\set}[2]{\{#1\,|\,#2\}}
\newcommand{\smidge}{{\kern .05em}}
\newcommand{\Colon}{{\smidge\colon\;\:}}
\newcommand{\eqdef}{\stackrel{\rm def}{=}}

\newcommand{\chapref}[1]{\mbox{Capitulo~\ref{#1}}}
\newcommand{\secref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\ssecref}[1]{\mbox{Secci\'on~\ref{#1}}}
\newcommand{\apref}[1]{\mbox{Ap\'endice~\ref{#1}}}
\newcommand{\thref}[1]{\mbox{Teorema~\ref{#1}}}
\newcommand{\defref}[1]{\mbox{Definici\'on~\ref{#1}}}
\newcommand{\corref}[1]{\mbox{Corolario~\ref{#1}}}
\newcommand{\lemref}[1]{\mbox{Lema~\ref{#1}}}
\newcommand{\propref}[1]{\mbox{Proposici\'on~\ref{#1}}}
\newcommand{\figref}[1]{\mbox{Figura~\ref{#1}}}
\newcommand{\tablref}[1]{\mbox{Tabla~\ref{#1}}}
\newcommand{\eqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\ineqref}[1]{\mbox{(\ref{#1})}}
\newcommand{\comref}[1]{\mbox{Comentario~\ref{#1}}}
\newcommand{\EE}{{I\!\! E}}
\newcommand{\PP}{{I\!\! Pr}}

% FIN LISTA DE MACROS PERSONALES

\begin{document}
% LOS DATOS IDENTIFICATORIOS DE LA CATEDRA TRANSCRITA VAN AQUI
% (modificar los parametros en invocacion de la siguiente macro:
%	primer parametro: No. de catedra transcrita
%	segundo parametro: fecha de catedra transcrita
%	tercer parametro: Nombre del transcriptor
\catedra{6}{21 de Agosto}{Rodrigo Gonz\'alez}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Descripci\'on de DES}

DES (Data Encryption Standard) encripta un texto plano $x$ de una longitud
de 64 bits, i.e. $x\:\in\:(\modulo_{2})^{64}$, usando una clave $K$ la
cual es un bitstring (un string en su representaci\'on en bits) de 56 bits,
obteniendo un texto cifrado de 64 bits.

Veamos ahora un esquema del DES. El algoritmo consiste en 3 etapas:
\begin{enumerate}
\item Dado un texto plano $x$, un bitstring $x_0$ es constitu\'{\i}do
mediante permutaci\'on de los bits de $x$, de acuerdo a una permutacion
inicial $IP$ fija. Nosotros escribimos $x_0=IP(x)=L_0R_0$, donde $L_0$
abarca  los primeros 32 bits de $x_0$ y $R_0$ los \'ultimos 32 bits.
\item 16 iteraciones de una funci\'on conocida es entonces calculada.
Se calcula $L_iR_i$, $1 \leq i \leq 16$, de acuerdo a la
siguiente regla:
\begin{eqnarray*}
L_i & = & R_{i-1}\\
R_i & = & L_{i-1} \oplus f(R_{i-1},K_i),
\end{eqnarray*}
donde $\oplus$ denota el o-exclusivo de dos bitstrings. La funci\'on $f$
se describir\'a mas adelante, y $K_1,K_2,\ldots,K_{16}$, son bitstrings
de 48 bits, calculados como una funci\'on de las claves $K$.
(De hecho, cada $K_i$ es una selecci\'on permutada de bits de $K$.)
\item Aplicando la permutaci\'on inversa $IP^{-1}$ a los bistring
$R_{16}L_{16}$ se obteniene el texto cifrado $y$. Que es,
$y=IP^{-1}(R_{16}L_{16})$. Notar el orden inverso de $L_{16}$ y $R_{16}$.
\end{enumerate}

Explicaremos ahora la funci\'on $f$. La funci\'on $f$ toma como entrada
un primer argumento $A$, el cual es un bitstring de longitud de 32 bits,
y un segundo argumento $J$ que es un bitstring de longitud de 48 bits,
produciendo como salida un bitstring de longitud de 32 bits. Los siguientes
pasos son ejecutados:
\begin{enumerate}
\item El primer argumeto $A$ es "expandido" a un bitstring de longitud
de 48 bits de acuerdo a una funci\'on de expanci\'on $E$ fija. $E(A)$
consiste en 32 bits de $A$, permutados de una cierta manera, con 16 de
los bits apareciendo dos veces.
\item Se calcula $E(A)\oplus J$ y se escribe el resultado como la
concatenaci\'on de 8 strings de 6-bits  $B=B_1B_2B_3B_4B_5B_6B_7B_8$.
\item El pr\'oximo paso usa 8 cajas-S $S_1,\ldots,S_8$. Cada $S_i$ es
un arreglo de 4x16 fijo cuyas entradas se interpretan como enteros de 0
al 15. Dado un bitstring de largo 6, digamos $B_j=b_1b_2b_3b_4b_5b_6$,
nosotros calculamos $S_j(B_j)$ como sigue; los dos bits $b_1b_6$
determinan la representaci\'on binaria de una fila $r$ de $S_j$
($0\leq r \leq 3$), y los 4 bits $b_2b_3b_4b_5$ determinan la
representaci\'on binaria de una columna $c$ de $S_j$ ($0\leq c \leq 15$).
Entonces $S_j(B_j)$ est\'a definido a ser la entrada $S_j(rc)$, escrita en
binario como un bitstring de longitud 4. Asi, nosotros calculamos
$C_j=S_j(B_j)$, ($0\leq j \leq 8$).
\item El bitstring $C=C_1C_2C_3C_4C_5C_6C_7C_8$ de longitud de 32 bits
es permutado de acuerdo a una permutaci\'on $P$ fija. El resultante
bitstring $P(C)$ esta definido como $f(A,J)$.
\end{enumerate}

\section{Claves Intermedias}


Veamos como generar $K_{1},\dots,K_{16}\:\in\:(\modulo_{2})^{48}$ a partir
de $K\:\in\: (\modulo_{2})^{56}$

En la pr\'actica $K$ tiene 64 bits y 8 de ellos son bits de paridad
(8,16,24,\dots,64) que se setean de forma que:

$k_i+\dots +k_{i+7}$ sea impar, con $i=1,9,\dots$, donde
$K=(k_1,\dots,k_{64})$

Para calcular las claves intermedias se procede de la siguiente manera:

\begin{itemize}
\item Dada una clave $K$ de 64-bits, se descarta los bits de paridad  y
se permutan  los restantes bits de $K$ de acuerdo a una permutaci\'on $PC-1$
fija. Nosotros escribiremos $PC-1(K)=C_0D_0$, donde $C_0$ abarca los 28
primeros bits de $PC-1(K)$ y $D_0$ los \'ultimos 28 bits.
\item Para $i$ recorriendo desde 1 a 16, calculamos:
\begin{eqnarray*}
C_i & = & LS_i(C_{i-1})\\
D_i & = & LS_i(D_{i-1}),
\end{eqnarray*}
y $K_i=PC-2(C_iD_i)$. $LS_i$ es un shift c\'{\i}clico a la izquierda de
1 o 2 bits, dependiendo del valor de $i$ (shift de 1 bit si $i=1,2,9,16$
y shift de 2 bits en caso contrario). $PC-2$ es otra permutaci\'on fija.
\end{itemize}

\section{Controversias}

Cuando el DES fue propuesto como estandar, fue muy criticado. Una de las
objeciones al DES concierne a las cajas-S. Todos los calculos excepto los 
de las cajas-S son lineales. Las cajas-S, son las componentes no lineales
del criptosistema, y son vitales para su seguridad. Mucha 
gente sugieren que las cajas-S pueden contener una "trapdoors" escondida, 
la cual le permitiria a la NSA decriptar el DES. Es imposible desmentir  
tal afirmaci\'on, ya que no hay  evidencias que indiquen que esas 
"trapdoors" existan o no.

La principal cr\'{\i}tica a DES es que el tama\~no del espacio de claves,
$2^{56}$, es demasiado peque\~no para que el criptosistema sea seguro.
Varias maquinas especializadas han sido propuestas para un ataque 
de texto plano y de su correspondiente texto cifrado conocidos, las
cuales esencialmente mejoran la b\'usqueda exhaustiva de la clave.
Esto es, dado un texto plano $x$, de 64-bits, y su correspondiente
texto cifrado $y$, cada clave posible ser\'a testeada hasta
encontrar un clave $K$ tal que $e_K(x)=y$ (notar que puede haber
m\'as de una).

\section{Modo de Uso}

A pesar que la descripci\'on del DES es bastante larga, puede ser implimentado
de manera muy eficiente, tanto en hardware como en sotfware. Las \'unicas
operaciones aritm\'eticas a ser realizadas son los o-exclusivos entre
bitstrings. La funci\'on de expanci\'on $E$, las cajas-S, las permutaciones
$IP$ y $P$, y los c\'alculos de $K_1,K_2,\ldots,K_{16}$ todos pueden ser
hechos eficientemente mediante "table lookup" (Tablas permanentes
que quedan en memoria para su acceso, en software) o mediante
"hard-wiring" dentro de un circuito.
\newpage
\subsection{DES Triple}

La pregunta obvia es ?`por qu\'e no iterar DES dos veces en vez de tres?.

En generar iterar dos veces un criptosistema los hace suceptibles a un ataque 
que se denomina "meet in the middle" [Merkle y Hellmam]. A continuaci\'on
describiremos este ataque:

Sea $(\plain, \plain, \key, \encrip, \decrip)$ un criptosistema cualquiera. 
Para atacar $S^2$ se puede proceder de la siguiente forma:
\begin{enumerate}
\item Se elige un $p \in \plain$ al azar.
\item Se determina $c=e_{K_{2}}(e_{K_{1}}(p))$ (el ataque es de texto plano 
conocido).
\item Se construye una tabla (ver figura 1)
\end{enumerate}
\begin{figure}\label{fig:Tabla}
\begin{center}
\input{c6-f1}
\end{center}
\caption{Tabla de busqueda de coincidencia de claves}
\end{figure}

La idea es que si calculamos $d_K(c)$ y se tiene que
$e_{K_{i}}(p)=d_K(c)$ entonces $K_i$ es un candidato a ser
$K_1$, y $K$ es un candidato a ser $K_2$.

Para verificar que los potenciales candidatos son los correctos, se
verifica si $e_{K_{i}}(p_j)=d_K(c_j) \:\: j=1,\dots$; donde
$e_{K_{2}}(e_{K_{1}}(p_j))=c_j$.

El ataque requiere $O(|\key|)$ memoria, esto ya que para todo K posible
se calcula $e_K(p)$ y su resultado se guarda en memoria. Estudiemos el
tiempo que demora el ataque, nos interesa que
$N=\EE_{p,k}[|\{k' : e_k(p)=e_{k'}(p)\}|]$ sea peque\~no, (donde $p,k$
indica sobre que par\'ametros se esta calculando la esperanza).

Para un buen criptosistema uno espera que:

$$N\simeq \frac{|\key |}{|\plain |}.$$

Luego uno esperar\'{\i}a que:

$$\PP_{p,k}[e_k(p)=c]\simeq\frac{|\key |}{|\key ||\plain |}=
\frac{1}{|\plain |}.$$

Ya que, si tengo $p \in \plain$, y aplico $e_K$ sobre $p$ obtengo 
que $e_K(p) \in \cipher=\plain$, luego si se supone que dado un
$c \in \cipher$, $|p: e_K(p)=c|=cte$, i.e. se sigue una distribuci\'on
uniforme sobre las imagenes de $e_K$, obteniendo el resultado anterior. 
Por otro lado tenemos que:
\begin{center}
\begin{tabular}{r c l}
$N$&=&$|\key |\EE_{p,k}[\PP_{k'}[e_k(p)=e_{k'}(p)]]$\\
&=&$|\key |\PP_{p,k,k'}[e_k(p)=e_{k'}(p)]$\\
&=&$|\key |\sum_{c\in \plain} \PP_{p,k,k'}[e_k(p)=c,e_{k'}(p)=c]$\\
& $\simeq$ & $|\key |\sum_{c\in \plain} \PP_{p,k}[e_k(p)=c]^2\simeq
\frac{|\key |}{|\plain |}.$\\
\end{tabular}
\end{center}

En el \'ultimo paso se supone que $\PP_{p,k,k'}[e_k(p)=c,e_{k'}(p)=c] \simeq
\PP_{p,k}[e_k(p)=c]^2$, ya que los eventos $e_k(p)=c$ y $e_{k'}(p)=c$ son
m\'as o menos independientes, esto se puede ver en que la elecci\'on de la
clave K es totalmente aleatoria sobre el espacio de claves.

Luego el tiempo esperado que demora del ataque es $O(\frac{|\key ||\key |}
{|\plain |})$, ya que $\frac{|\key |}{|\plain |}$ representa
$\EE_{p,k}[|\{k' : e_k(p)=e_{k'}(p)\}|]$,es decir, el valor esperado de
coincidencias con la clave; y que adem\'as esto se hace para cada
$K\in \key$, es decir, $|\key |$ veces.
\newpage
\subsection {Otros modos de uso del DES}

Otros 4 modos de operaci\'on han sido desarrollados para el DES.

\subsubsection{ECB (electronic codebook mode)}

El modo ECB corresponde al usual uso de un cifrado por bloques: dada una
secuencia $x_1x_2\ldots$ de un texto plano por bloques de 64 bits, cada
$x_i$ es encriptado con la misma clave $K$, produciendo un string de
bloques de texto cifrado, $y_1y_2\ldots$.

\subsubsection{CBC (cipher block chaining mode)}

En el modo CBC, cada bloque de texto cifrado $y_i$ es x-ored (hacer el
o-exclusivo con x) con el pr\'oximo bloque de texto plano $x_{i+1}$
antes de ser encriptado con la clave $K$. Formalmente, se parte con un
vector de inicializaci\'on de 64 bits $IV$, y definimos $y_0=IV$.
Entonces construimos $y_1,y_2,\ldots$ con la regla $y_i=e_K(y_{i-1})
\oplus x_i, i \geq 1.$

\subsubsection{OFB (output feedback mode) y CFB (cipher feedback mode)}

En los modos OFB y CFB, una keystream (flujo de claves) es generado,
el cual es x-ored con el texto plano. OFB es un criptosistema de
chorro, el chorro de claves es producido mediante la encripci\'on
reiterada de un vector de inicializaci\'on $IV$. Se define $z_0=IV$,
y entonces se calcula el chorro de claves $z_1z_2\ldots$ con la
regla $z_i=e_K(z_{i-1}), i \geq 1$. La secuencia de texto plano
$x_1x_2\ldots$ es entonces encriptada calculando $y_i=x_i
\oplus z_i, i \geq 1$.

En el modo CFB , se parte con $y_0=IV$ (vector de inicializaci\'on) y
se produce un chorro de claves $z_1z_2z_3\ldots$ mediante la encripci\'on
del anterior bloque cifrado. Esto es, $z_i=e_K(y_{i-1}), i \geq 1$.
Como en el modo OFB, $y_i=x_i \oplus z_i, i \geq 1$.

\subsubsection{MAC (message authentication code)}

La propiedad de que los bloques cifrados dependan de todos los
anteriores, es decir, que los $y_i$ dependen de los $x_j$ con $j\leq i$
es una propiedad que es \'util para efectos de autentificaci\'on, esto
ocurre en los modos  CBC y CFB.

Describiremos como el modo CBC es usado para producir un MAC. Empezamos
con un vector de inicializaci\'on $IV$ consistente de puros ceros.
Entonces se construyen los bloques de texto cifrado $y_1, \ldots , y_n$
con la clave $K$, usando CBC. Finalmente, definimos el MAC como $y_{n}$.
Luego Alicia transmite la secuencia de texto plano , $x_1, \ldots , x_n$
, junto con el MAC. Entonces B  recibe $x_1, \ldots , x_n$, y puede
reconstruir $y_1, \ldots , y_n$ usando la clave $K$ (secreta), y verificar
que $y_{n}$ es el mismo MAC que se recibio.

La idea es que B puede verificar la integridad del mensaje recibido
$x_1, \ldots , x_n$ calculando su MAC y verificar que corresponde al MAC
transmitido.

Podemos combinar el proceso anterior con encripci\'on de dos formas:
\begin{enumerate}
\item Tomar $x_1, \ldots , x_n$ generar el MAC de $x_1, \ldots , x_n$,
digamos $x_{n+1}$ y encriptar $x_1, \ldots , x_{n+1}$ y enviarlo.
\item Tomar $x_1, \ldots , x_n$ encriptar y obtener $y_1, \ldots , y_n$.
Calcular el MAC de $y_1, \ldots , y_n$, digamos $y_{n+1}$ y enviar
$y_1, \ldots , y_{n+1}$
\end{enumerate}
\end{document}


