\documentstyle[12pt,spanish]{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{7}{27 de Agosto}{Gregorio Gonz\'alez}

% TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI

\section{Criptoan\'alisis Diferenciable}
\subsection{El M'etodo de Criptoan'alisis Diferenciable}

El m\'etodo de Criptoan\'alisis Diferenciable fue presentado por 
Eli Biham y Adi Shamir en 1990.\footnote{E. Biham y A.Shamir, 
1.- {\em ``Differential Cryptanalysis of DES-like 
Cryptosystems'' \/}, Advances in Cryptology--CRYPTO '90 Proceedings, 
Springer Verlag, 1991, pp. 2-21; 2.- {\em ``Differential Cryptanalysis of 
DES-like Cryptosystems'' \/}, Journal of Cryptology, v.4, n. 1, 1991, pp 
3-72; 3.- {\em ``Differential Cryptanalysis of FEAL and N-Hash'' \/}, 
Advances in 
Cryptology--EUROCRYPT '91 Proceedings, Springer-Verlag, 1991, pp. 
1-16.} 
  Este m\'etodo permite realizar un ataque de texto plano elegido que 
resulta m\'as eficiente que un ataque de fuerza bruta contra el sistema DES.

El criptoan\'alisis diferenciable se basa en el an\'alisis de la 
propagaci\'on de diferencias entre dos textos planos a trav\'es de las 
funciones del criptosistema cuando se usa la misma clave.  B\'asicamente, 
se toma un par de textos planos, posiblemente al azar, pero con una 
cierta "distancia" elegida.  Seg\'un la clave usada, la diferencia en la 
entrada llevar\'a con mayor o menor probabilidad a ciertas diferencias 
en la salida (texto cifrado).  El criptoan\'alisis diferenciable 
aprovecha el hecho que estas distribuciones en la diferencia de salida 
no son uniformes.  Al obtener la diferencia entre los textos cifrados, se 
puede descartar aquellas claves con las cuales esta diferencia tiene 
probabilidad cero.  A medida que se analizan m\'as pares de textos, se 
ir\'an descartando claves hasta que una clave aparecer\'a como la m\'as
 probable.  Esta es la clave correcta. 

El m\'etodo sirve para atacar un criptosistema o una parte de \'el que 
tenga la estructura que se muestra en la \figref{fig:estructura}.

\begin{figure}\label{fig:estructura}
\begin{center}
\input{c7-f1}
\end{center}
\caption{Estructura de un criptosistema atacable mediante criptoan'alisis 
diferenciable.}
\end{figure}

Se define la diferencia seg\'un el criptosistema a atacar.  Para el 
criptosistema DES la diferencia adecuada es el XOR.  La condici\'on que 
debe cumplir esta operaci\'on (y que se usa para elegirla) es la siguiente:
$$
\triangle B = B - B^{\prime} = f(X,k) - f(X^{\prime},k) = \triangle X.
$$
Es decir, que la diferencia no se altere con $f$, independientemente de 
la clave (ver \figref{fig:diferencias}).  Se define entonces:
\begin{figure}\label{fig:diferencias}
\begin{center}
\input{c7-f2} 
\end{center}  
\caption{Propagaci\'on de las diferencias a trav\'es del criptosistema.}
\end{figure}
$$
IN(\delta,\tau) = \{ B : g(B) - g(B+\delta) = \tau \}.
$$
En el caso de DES:
$$
IN(\delta,\tau) = \{ B : g(B) \oplus g(B\oplus\delta) = \tau \},
$$
Y constru'imos:
$$
K(X,\delta,\tau) = \{ k : f(X,k) \in IN(\delta,\tau) \}.
$$
Notemos que si encriptamos $X,~X^{\prime}=X-\delta~$ y obtenemos 
$Y,~Y^{\prime}$ tal que $\triangle Y=\tau$ entonces necesariamente $k\in 
K(X,\delta,\tau)$.

Lo que se desea es que el cardinal de $K(X,\delta,\tau)$ sea mucho menor 
que la cantidad de claves 
posibles.  Este conjunto b\'asicamente representa aquellas claves para 
las cuales las diferencias obtenidas tienen probabilidad mayor que cero.

El ataque procede de la siguiente forma:

\begin{enumerate}
     \item  Crear contadores para todas las claves posibles
     \item  Elegir {$X,\delta$}, determinar 
$X^{\prime},Y,Y^{\prime},$ y $\tau=\triangle Y$
     \item  Calcular $IN(\delta,\tau)$
     \item  Incrementar los contadores para las claves en $K(X,\delta,\tau)$
\end{enumerate}

El contador de la clave correcta se incrementa en cada paso.  Si para 
una clave dada, alguna de las diferencias obtenidas con un par de textos 
planos tiene probabilidad cero de ocurrir, su contador no se incrementa en 
ese paso.  El proceso desde el paso 2 al 4 se repite hasta que s\'olo 
queda una clave con el contador igual al n\'umero de pares de texto 
analizados.  Dicha clave es la correcta.

\subsection{Problemas del Criptoan'alisis Diferenciable}

A pesar de su aparente simplicidad, este ataque puede resultar impr'actico
en varios casos.
Primero que nada, hay una probabilidad bastante baja de tener 'exito 
hasta que se pasa de cierto umbral, es decir, mientras no se verifiquen 
suficientes pares de textos es imposible distinguir la clave correcta 
de las dem'as que no se han descartado.  Adem'as, este ataque es 
costoso desde el punto de vista del almacenamiento de datos, pues requiere 
contadores para las $2^{48}$ claves posibles 
(en el caso de DES).  
Otro problema es el n'umero de textos planos necesario para descartar 
todas las claves menos una.  Se puede probar que un criptosistema es 
inmune al criptoan'alisis diferenciable demostrando que requiere analizar 
m'as textos planos que los que es posible generar con el tama~no de 
bloque utilizado. 

\subsection{Un Ejemplo: Criptoan'alisis de 3-DES}

Ignoraremos las permutaciones de entrada y salida pues son f'aciles de 
deshacer (ya que son de dominio p'ublico, i.e. conocidas).  Vamos a 
tratar de descubrir la tercera subclave, ya que la clave completa se 
puede obtener a partir de ella ciclando sobre las $2^{8}$ posibilidades 
(ya que esto no es demasiado costoso).
Recordemos que:
\begin{eqnarray*}
L_{i}&=&R_{i-1} \\
R_{i}&=&L_{i-1}\oplus f(R_{i-1},K_{i})~~~i=1,2,3. \\
\end{eqnarray*}

Donde la entrada es $L_{0}R_{0}$ y la salida es $L_{3}R_{3}$. Luego:
\begin{eqnarray*}
R_{3} &=& L_{2}\oplus f(R_{2},K_{3})\\
&=& R_{1}\oplus f(R_{2},K_{3})\\
&=& L_{0} \oplus f(R_{0},K_{1})\oplus f(R_{2},K_{3}).\\
\end{eqnarray*}
Sea entonces $L_{3}^{\prime}R_{3}^{\prime}$ otra salida, correspondiente 
a la entrada $L_{0}^{\prime}R_{0}^{\prime}$. Sigue que:
\begin{eqnarray*}
\triangle R_{3} &=& R_{3}\oplus R_{3}^{\prime} \\
&=& \triangle L_{0} \oplus f(R_{0},K_{1})\oplus 
f(R_{0}^{\prime},K_{1})\oplus f(R_{2},K_{3})\oplus f(R_{2}^{\prime},K_{3})\\
\end{eqnarray*}
El ataque es de texto plano elegido, as'i que en particular podemos tomar las
entradas de forma que $R_{0}=R_{0}^{\prime}$.  Luego:
\begin{eqnarray*}
\triangle R_{3} &=&\triangle L_{0}\oplus f(R_{2},K_{3})\oplus 
f(R_{2}^{\prime},K_{3})\\
\triangle R_{3}\oplus \triangle L_{0} &=& f(R_{2},K_{3})\oplus 
f(R_{2}^{\prime},K_{3}).\\
\end{eqnarray*}
Recordemos que en DES, la estructura de $f$ es la que se muestra en la 
\figref{fig:DES}:
\begin{figure}\label{fig:DES}
\begin{center}
\input{c7-f3} 
\end{center}  
\caption{Estructura de $f$ en el criptosistema DES.}
\end{figure}
Sigue que:
\begin{eqnarray*}
\triangle R_{3}\oplus \triangle L_{0} &=& P(C) \oplus 
P(C^{\prime}) \\
&=& P(C \oplus C^{\prime}),\\
\end{eqnarray*} 
de donde se ve que:
\begin {eqnarray*}
\triangle C &=& P^{-1}(\triangle R_{3}\oplus \triangle L_{0}). \\
\end{eqnarray*}
Luego $\triangle C_{i},~i=1,\dots,8$ son conocidos.  Veamos que 
$\triangle B_{i},~i=1,\dots,8$ tambi'en son conocidos.
$$
E(R_{2})\oplus K_{3} = B~~ y ~~ E(R_{2}^{\prime})\oplus K_{3} = 
B^{\prime} \\
$$
luego
$$
\triangle B = E(R_{2})\oplus E(R_{2}^{\prime}). \\
$$
Es decir, $\triangle B$ no depende de la clave.

Como $L_{3}=R_{2},~L_{3}^{\prime}=R_{2}^{\prime}$, se tiene que:
$$
\triangle B = E(L_{3})\oplus E(L_{3}^{\prime})
$$
Luego $\triangle B_{i},~i=1,\dots,8$ se pueden obtener a partir de la 
informaci'on que poseemos.
Con esto podemos montar un ataque de criptoan'alisis diferenciable contra 
cada una de las 8 cajas-S.  Con ello 
obtenemos 6 bits de la clave $K_{3}$ por cada caja, en total 48 bits.  
Los restantes 8 se obtienen por fuerza bruta sin mayor problema (ya que 
son $2^{8}=256$ posibles combinaciones).

\subsection{Criptoan'alisis Diferenciable y DES}

El criptoan'alisis diferenciable funciona contra DES en cualquiera de sus 
modos de operaci'on, ECB, CBC, CFB y OFB con la misma complejidad 
computacional, es decir, ninguno de estos modos presenta ventajas 
respecto a los otros en cuanto a resistencia contra este ataque.

En la siguiente tabla presentamos un resumen de los mejores ataques 
diferenciales contra DES con distintos n\'umeros de pasos
\footnote{E. Biham y A. Shamir,{\em``Differential Cryptanalysis of the Data 
Encryption Standard''\/}, Springer-Verlag, 1993.}
.  La primera columna es el n\'umero de pasos de la implementaci'on.  Las 
siguientes dos son el 
n\'umero de textos elegidos o textos conocidos que deben ser examinados 
para efectuar el ataque (el criptoan\'alisis diferenciable puede adaptarse a 
una forma con texto plano conocido en vez de elegido de manera relativamente 
simple).  La cuarta columna es el n\'umero de estos textos que fueron 
analizados realmente en estos ataques m\'as exitosos.

\begin{tabular}{cccc}

N\'umero de & Textos~ Elegidos & Textos Conocidos & Textos Analizados \\
  Pasos \\
8 & $2^{14}$ & $2^{38}$ & 4 \\ 
9 & $2^{24}$ & $2^{44}$ & 2 \\
10 & $2^{24}$ & $2^{43}$ & $2^{14}$ \\ 
11 & $2^{31}$ & $2^{47}$ & 2 \\
12 & $2^{31}$ & $2^{47}$ & $2^{21}$ \\
13 & $2^{39}$ & $2^{52}$ & 2 \\
14 & $2^{39}$ & $2^{51}$ & $2^{29}$ \\
15 & $2^{47}$ & $2^{56}$ & $2^{7}$ \\
16 & $2^{47}$ & $2^{55}$ & $2^{36}$ \\

\end{tabular}

La resistencia de DES se puede mejorar aumentando el n\'umero de pasos,  
como se puede apreciar en la tabla.  
Un ataque de criptoan\'alisis 
diferenciable de texto elegido contra un DES con 17 o 18 pasos toma 
aproximadamente el mismo tiempo que un ataque de fuerza bruta.
\footnote{B. Schneier, {\em ``Applied Cryptography'', Wiley, 1996, p. 
289.}}
Con 19 pasos o m\'as, el criptoan\'alisis diferenciable se hace imposible 
porque requiere m'as textos planos elegidos que los que se pueden generar 
con el tama\~no de bloque que utiliza DES (m\'as de $2^{64}$ textos, donde 
los textos son de 64 bits). 

Este ataque depende mucho de la estructura de las cajas-S.  Estas
est'an optimizadas contra el criptoan\'alisis diferenciable, es decir,
est\'an constru'idas de manera de hacer que el ataque sea lo m\'as
dif\'icil posible.    

?`Por qu'e DES es tan resistente al criptoan'alisis diferenciable?
?`Por qu'e est'an optimizadas las cajas-S para hacer que este ataque sea 
lo m'as dif'icil que sea posible? 
?`Por qu'e tiene la cantidad justa de pasos para que sea ineficiente, pero
ni uno m'as?
La respuesta es porque los dise~nadores conoc'ian este ataque.  Don 
Coppersmith, de la IBM, escribi'o: 
\footnote{D. Coppersmith, 1.- {\em ``The Data Encryption Standard (DES) 
and Its Strength against Attacks''\/}, Technical Report RC 18613, IBM 
T.J. Watson Center, Dic. 1992; 2.- {\em ``The Data Encryption Standard 
(DES) and Its Strength against Attacks'',\/} IBM Journal of Research and 
Development, v. 38, n. 3, Mayo 1994, pp. 243-250}

\begin{quote}
 El dise~no aprovechaba ciertas t'ecnicas de criptoan'alisis, 
principalmente la t'ecnica del ``criptoan'alisis diferenciable'', que no eran
conocidas en la literatura publicada. Tras discusiones con NSA, se 
decidi'o que entregar las consideraciones del dise~no revelar'ia la 
t'ecnica del criptoan'alisis diferenciable, una t'ecnica poderosa que 
puede ser utilizada contra varios criptosistemas.  Esto a su vez 
debilitar'ia la ventaja competitiva que los Estados Unidos disfrutaba 
sobre el resto de los pa'ises en materia de criptograf'ia. 
\end{quote}

Adi Shamir desafi'o a Coppersmith a decir que no hab'ia encontrado ning'un 
ataque m'as fuerte contra DES desde entonces, pero Coppersmith no ha 
respondido.  Sabiendo que la NSA conoc'ia el criptoan'alisis 
diferenciable m'as de 15 a~nos antes que el mundo acad'emico, 
existe cierta preocupaci'on en cuanto a qu'e m'etodos habr'an 
desarrollado en esos 15 a~nos de ventaja, durante los cuales ciertamente sus 
investigadores no deben haber estado descansando precisamente.

\subsection{Ideas Alternativas}

Existen otros m'etodos con ciertas similitudes al criptoan'alisis 
diferenciable que se han utilizado tambi'en contra DES, con mayor o menor 
'exito.  Entre ellas tenemos el Criptoan'alisis de Clave Relacionada 
(Related Key Cryptanalysis) y el Criptoan'alisis Lineal.
\subsubsection{Criptoan'alisis de Clave Relacionada}
La clave de DES se rota cierta cantidad de bits en cada paso: 2 tras cada 
paso salvo los pasos 1,2,9 y 16, en los cuales rota uno s'olo. ?`Por qu'e?

El criptoan'alisis de clave relacionada es similar al criptoan'alisis 
diferencial, pero examina las diferencias entre claves.  El ataque en s'i 
es muy distinto: El criptoanalista toma deliberadamente cierta relaci'on 
entre dos claves, pero no conoce las claves mismas.  Se encriptan datos 
con ambas claves.  En la versi'on de texto plano conocido, se dispone de 
el texto plano y el texto cifrado con ambas claves.  En la versi'on con 
texto plano elegido, el criptoanalista elige el texto plano a encriptar 
con ambas claves (pero no las claves).  

Un DES modificado, en el cual la clave se rota exactamente dos bits en 
cada paso, es menos seguro.  Utilizando criptoan'alisis de clave 
relacionada se puede quebrar esta variante usando $2^{17}$ textos 
elegidos de clave elegida o $2^{33}$ textos conocidos de clave elegida. 
\footnote{E. Biham, 1.- {\em ``New Types of Cryptanalitic Attacks Using 
Related Keys''\/}, Technical Report \#753, Computer Science 
Department, Technion--Israel Institute of Technology, Sep. 1992.; 2.-
{\em ``New Types of Cryptanalitic Attacks Using Related Keys''\/}, 
Journal of Cryptology, v. 7, n. 4, 1994, pp. 229-246.}.

Este ataque es bastante impr'actico, pero es interesante por tres motivos:
\begin{itemize}
\item Uno, es el primer ataque criptoanal'itico contra el sistema de 
generaci'on de subclaves de DES. 
\item Dos, este ataque es independiente del 
n'umero de pasos del criptosistema, es igualmente efectivo contra DES con 
16, 32 o 1000 pasos.  
\item Y tres, DES es inmune a este ataque.  La variaci'on en el n'umero 
de bits que se rotan frustra el ataque de clave relacionada.
\end{itemize} 
\subsubsection{Criptoan'alisis Lineal}

El Criptoan'alisis Lineal es otro tipo de ataque, inventado por Mitsuru 
Matsui. 
\footnote{M. Matsui, 
{\em``Linear Cryptanalysis Method for DES Cypher''\/},
Advances in Cryprology--EUROCRYPT '93 Proceedings, Springer-Verlag, 1994, 
pp. 386-397.}
Este ataque usa aproximaciones lineales para 
describir la acci'on de un criptosistema de bloque (en este caso DES).
Esto significa que si tomamos el ``o exclusivo'' (XOR) de algunos de los 
bits del texto plano, el XOR de algunos del texto cifrado, y 
tomamos el XOR de ambas cosas, obtendremos un bit que ser'ia el XOR de 
algunos bits de la clave.  Esto es una aproximaci'on lineal, y 
coincidir'a con la realidad con cierta probabilidad $p$.  Si $p\not= 
\frac{1}{2}$, este sesgo puede ser aprovechado.  Utilizando textos planos 
y sus textos cifrados se puede ir adivinando los valores de los bits de 
la clave.  Mientras m'as datos se tiene, m'as confiable es la 
estimaci'on.  Mientras mayor es el sesgo (i.e. mientras mayor es $\mid p 
- \frac{1}{2}\mid$) mayor es la tasa de 'exitos con la misma cantidad de 
datos conocidos.

Si las aproximaciones lineales fuesen insesgadas, entonces resultar'ian 
en 32 de 64 entradas posibles (a cada caja-S. Este ataque est'a dirigido 
a dicha parte del algoritmo DES).  Si hay una caja con sesgo 
suficientemente grande, el ataque puede funcionar.  La caja-S m'as 
sesgada es $S_{5}$.  De hecho, el segundo bit de entrada es igual al XOR 
de los cuatro de la salida s'olo en 12 casos.  Esto se traduce en una 
probabilidad de $\frac{3}{16}$, i.e. un sesgo de $\frac{5}{16}$, y es el 
sesgo m'as extremo de todas las cajas-S. (Seg'un el libro de Schneier, 
Shamir not'o este sesgo, pero no pudo encontrar una manera de explotarlo).

Contra un DES de 16 pasos, este ataque puede encontrar la clave con un 
promedio de $2^{43}$ textos conocidos.  Una implementaci'on en software 
de este ataque quebr'o una clave DES en 50 d'ias usando 12 estaciones 
HP9735 
\footnote{M. Matsui, {\em ``The First Experimental Cryptanalysis of the Data 
Encryption Standard''\/}, Advances in Cryptology--CRYPTO '94 Proceedings, 
Springer-Verlag, 1994, pp. 1-11.} 
.  Es el ataque m'as efectivo contra DES que se conoce a la fecha.

El criptoan'alisis lineal depende fuertemente de la estructura de las 
cajas-S, y las cajas-S del DES no est'an optimizadas contra este ataque.  
De hecho, el ordenamiento de las cajas-S elegido para DES est'a entre el 
9\% y el 16\% que ofrecen menor protecci'on contra este ataque. 
\footnote{B. Schneier, {\em ``Applied Cryptography''\/}, Segunda 
Edici'on, Wiley, 1996, p. 293.} 
  De acuerdo a Don Coppersmith
\footnote{D. Coppersmith, 1.- {\em ``The Data Encryption Standard (DES)   
and Its Strength against Attacks''\/}, Technical Report RC 18613, IBM
T.J. Watson Center, Dic. 1992; 2.- {\em ``The Data Encryption Standard
(DES) and Its Strength against Attacks'',\/} IBM Journal of Research and
Development, v. 38, n. 3, Mayo 1994, pp. 243-250}, la resistencia contra el 
criptoan'alisis lineal ``no fu'e parte del criterio de dise~no del 
DES''.  O bien no conoc'ian el criptoan'alisis lineal, o conoc'ian otro 
ataque mucho m'as poderoso, haciendo que la resistencia contra 'este 
tuviera prioridad sobre la resistencia contra el criptoan'alisis lineal. 

\bigskip
\bigskip
EL criptoan'alisis lineal es m'as reciente que el diferencial, y pueden 
haber mayores mejoras a su rendimiento en los a~nos venideros.  Algunas 
ideas se han propuesto, 
\footnote{Ver referencias [1270],[811] del libro de Schneier.} 
pero no es claro que puedan ser 
utilizadas efectivamente contra un DES completo (con sus 16 pasos).  Sin 
embargo, funcionan bastante bien contra variantes de menos pasos.

\subsection{Direcciones a Explorar}

Se han hecho algunos trabajos intentando extender el concepto de 
criptoan'alisis diferenciable a derivadas de orden superior 
\footnote{Ver referencias [702,161,927,858,860] del libro de Schneier.}
  Lars Knudsen usa ``derivadas parciales'' para 
atacar DES de 6 pasos; requiere 32 textos elegidos y 20.000 
encriptaciones. \footnote{
L.R. Knudsen, {\em``Applications of Higher Order Differentials and
Partial Differentials''\/}, K.U. Leuven Workshop on Cryptographic
Algorithms, Springer-Verlag, 1995.}
  Todav'ia es muy pronto para saber si estas 
extensiones facilitar'an quebrar un DES de 16 pasos.
Otra v'ia de ataque es el Criptoan'alisis Lineal-Diferenciable, que 
combina ambas t'ecnicas antes presentadas.  Susan Langford y Hellman 
tienen un ataque contra 8-DES que descubre 10 bits de la clave con una 
probabilidad de 'exito de un 80\% con 512 textos planos elegidos y un 95\% 
de probabilidad de 'exito con 768 textos planos elegidos, 
\footnote{S.K. Langford y M.E. Hellman, {\em``Cryptanalysis of 
DES''\/} presentado en la conferencia 1994 RSA Data Security, Redwood 
Shores, California, 12-14 de Enero 1994}.  Tras el 
ataque se requiere una b'usqueda de fuerza bruta de los bits restantes 
($2^46$ claves posibles).  Mientras que este ataque consume un tiempo 
similar a ataques previos, requiere mucho menos texto plano.  
Lamentablemente parece que no se extiende con facilidad a DES con m'as pasos.
Sin embargo, este ataque es nuevo y el trabajo sigue.  Es posible que 
haya un descubrimiento grande en alg'un momento durante los pr'oximos a~nos.
Tal vez mezclando ambos enfoques \dots ?`Qui'en sabe?

\subsection{El Criterio de Dise~no de las Cajas-S}

Tras la salida a la luz p'ublica del criptoan'alisis diferenciable, IBM 
public'o el verdadero criterio de dise~no de las cajas-S. 
\footnote{D. Coppersmith, 1.- {\em ``The Data Encryption Standard (DES)   
and Its Strength against Attacks''\/}, Technical Report RC 18613, IBM
T.J. Watson Center, Dic. 1992; 2.- {\em ``The Data Encryption Standard
(DES) and Its Strength against Attacks'',\/} IBM Journal of Research and
Development, v. 38, n. 3, Mayo 1994, pp. 243-250}
  El criterio para las cajas S es: \begin {itemize}
\item Cada caja-S tiene 6 bits de entrada y 4 de salida (pues era el 
mayor tama~no que se pod'ia implementar en un s'olo chip con la 
tecnolog'ia de 1974).
\item Ning'un bit de salida de una caja-S podr'ia estar demasiado cerca 
de ser una funci'on lineal de los bits de entrada.
\item Si se fijan el bit de m'as a la izquierda y el de m'as a la derecha 
de la entrada de una caja-S, y se var'ia el resto, cada salida posible de 
4 bits se obtiene exactamente una vez. 
\item Si dos entradas a una caja-S difieren exactamente en un bit, las 
salidas deben ser distintas en al menos dos bits.
\item Si dos entradas a una caja-S difieren en sus primeros dos bits y 
son id'enticas en los 'ultimos dos, las dos salidas no pueden ser iguales.
\item Para cualquier diferencia no nula de 6 bits entre las entradas, no 
m'as de 8 de los 32 pares de entradas que tienen esa misma diferencia 
pueden dar la misma diferencia en la salida.
\item Un criterio similar al anterior, pero para el caso de tres cajas-S 
activas (i.e. para cualquier par de diferencias no nulas, no m'as de 
cierta cantidad de los tripletes de entradas puede dar el mismo par de 
diferencias de salida). \end{itemize}
Claramente el sexto criterio apunta a defender las cajas-S contra el 
criptoan'alisis diferenciable, agrandando los conjuntos de claves 
posibles para cada par de diferencias de entrada y salida.

El art'iculo explica estos criterios y sus razones de ser.  Generar cajas-S 
es sumamente f'acil hoy en d'ia, pero era una tarea complicada en aquella 
'epoca.  Se dice que tuvieron computadores corriendo durante meses para 
fabricar las famosas cajas-S.
\end{document}


