\documentstyle[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 Oto\~no, 1998} } \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{9}{13 de Abril}{Gonzalo Navarro\footnotemark} \footnotetext{Estos apuntes est\'an basados en la transcripci\'on de Gregorio Gonz\'alez (27/8/96)} % TRANSCRIPCION DE LA CATEDRA COMIENZA AQUI \section{Compromiso Tiempo-Memoria (cont.)} Dado un texto plano $X$ conocido y un texto $Y=e(X)$ encriptado, la alternativa de fuerza bruta consiste en probar todas las claves $K$ hasta hallar la que cumpla $Y=e_K(X)$. Esto no necesita espacio extra pero requiere tiempo $\widetilde{O}(|{\cal K}|)$ \footnote{Recordar que $\widetilde{O}(X)$ significa $O(X \times polylog(X))$.}. Por ejemplo en DES requeriremos $2^{56}$ encripciones, lo que en 1992 con un chip especializado de US\$ 300 demorar\'{\i}a unos 136 a\~nos (claro que se puede correr en varios chips en paralelo, por ejemplo demorar\'{\i}a un mes teniendo 1600 chips, a un costo de casi un mill\'on de d\'olares). Por otro lado, dado un $X$ {\em fijo}, podr\'{\i}amos encriptar $X$ con todas las claves $K$ posibles y almacenar los pares $(e_K(X),K)$ previamente (indexados por la primera componente). Una vez hecho este preprocesamiento podr\'{\i}amos f\'acilmente romper cualquier criptosistema dado mediante el c\'alculo de $Y=e(X)$ y luego la b\'usqueda de $Y$ en la tabla, de lo que se obtendr\'{\i}a $K$. Esta b\'usqueda toma poco tiempo porque la tabla est\'a  indexada por esa componente, de modo que necesitamos un preprocesamiento de tiempo $\widetilde{O}(|{\cal K}|)$, espacio $\widetilde{O}(|{\cal K}|)$ y luego tiempo $O(\log |{\cal K}|)$ por cada clave. Este espacio equivale aproximadamente a $2^{60}$ bytes, o $2^{30}$ Gb. Obviamente ninguna de las dos ideas es factible. La pregunta es si ser\'a posible una estrategia intermedia, que use una cantidad razonable de tiempo y de memoria. Esta es la base de la idea que se detalla a continuaci\'on. Supongamos que elegimos una {\em funci\'on de reducci\'on} $R$ $$ R ~:~ {\cal C} ~~\longrightarrow~~ {\cal K} $$ que convierte textos cifrados en claves de alguna manera (ej. en DES podr\'{\i}a eliminar 8 de los 64 bits para que quedaran 56). Dada $R$ se define $g$: $$ g ~:~ { K} ~~\rightarrow~~ { K} ~~~~~~~~~~~~~~~~ g(k) = R(e_k(x))~,$$ donde $x$ es un texto plano {\em fijo}. El objetivo de $g$ es simplemente tener una forma determin\'{\i}stica pero que se comporte como aleatoria para generar claves a partir de una clave inicial. Para obtener esto se usa $e_k(x)$, que si el criptosistema es bueno deber\'{\i}a comportarse as\'{\i} (en forma determin\'{\i}stica y aparentemente aleatoria). El objetivo de $R$ es permitir la composicionalidad de $g$, dado que la salida de $e()$ puede no ser del mismo tipo que la entrada. Teniendo esto, elegimos $m$ claves {\em iniciales} $K_1,...,K_m$ al azar (o aparentemente al azar\footnote{No usar $g()$ para simular este azar, pues entonces $X(i+1,0) = X(i,1)$.}). Una vez obtenido $K_i$, denominamos $X(i,0) = K_i$, y calculamos $X(i,j) = g(X(i,j-1))$, para $j$ desde 1 hasta $t$. Esto produce una matriz de claves, a saber \medskip \begin{tabular}{ccccccccc} $K_1 = X(1,0)$ & $\longrightarrow$ & $X(1,1)$ & $\longrightarrow$ & $X(1,2)$ & $\longrightarrow$ & $....$ & $\longrightarrow$ & $X(1,t)$ \\ $K_2 = X(2,0)$ & $\longrightarrow$ & $X(2,1)$ & $\longrightarrow$ & $X(2,2)$ & $\longrightarrow$ & $....$ & $\longrightarrow$ & $X(2,t)$ \\ $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ & $...$ \\ $K_m = X(m,0)$ & $\longrightarrow$ & $X(m,1)$ & $\longrightarrow$ & $X(m,2)$ & $\longrightarrow$ & $....$ & $\longrightarrow$ & $X(m,t)$ \end{tabular} \medskip Es importante entender, sin embargo, que salvo la primera y la \'ultima columna, nada de esta matriz se almacena en memoria. Los resultados de las columnas intermedias se usan s\'olo para llegar al $X(i,t)$. Una vez obtenida la \'ultima columna a partir de la primera, se genera una tabla que almacene los pares $(X(i,t),X(i,0))$, indexada por la primera componente. Con esto concluye el preprocesamiento. Supongamos ahora que nos presentan un texto cifrado $y$, que corresponde a encriptar nuestro $x$ con alguna clave desconocida (o sea $y=e_K(x)$). Reducimos el texto cifrado $y$ a una clave (notar que esta reducci\'on no tiene m\'as significado que, por ejemplo, sacarle algunos bits para que quede del largo adecuado, es un mapeo casi aleatorio). Es decir, calculamos $R(y)$. La apuesta es que, con un poco de suerte, existe un $X(i,j)$ en la matriz que cumple $R(y) = X(i,j)$ (para alg\'un $j>0$, $i$). Si esto ocurre, lo que tenemos es que $$R(y) = X(i,j) = g(X(i,j-1)) = R(e_{X(i,j-1)}(x))$$ y por lo tanto es bastante posible que $y = e_k(x)$, donde $k=X(i,j-1)$. Es decir, $X(i,j-1)$ tiene buenas posibilidades de ser la clave. C\'omo buscamos en esta matriz, si no la hemos almacenado? Tenemos que se cumple que si $R(y) = X(i,j)$, entonces $g^{t-j}(R(y)) = X(i,t)$. Es decir, si iteramos $g$ suficientes veces (m\'aximo $t$) sobre $R(y)$ llegaremos a $X(i,t)$. Estos $X(i,t)$ no s\'olo est\'an almacenados sino que tenemos la tabla indexada por ellos. N\'otese que la inversa no es cierta, es decir que podemos llegar a un $X(i,t)$ por iteraci\'on y sin embargo nuestra $R(y)$ puede no estar realmente en la fila (dado que $g$ no es inyectiva). Sin embargo, hay una buena posibilidad. De modo que el algoritmo es \begin{enumerate} \item Dado $y \in {\cal C}$ \item $y_0 \leftarrow R(y)$ \item for $j=1..t$, calcular $y_j = g(y_{j-1})$ \item for $j=1..t$, \item \ \ \ buscar $y_j$ en la primera coordenada de la tabla \item \ \ \ si se hall\'o, reportar la posible clave $y_{t-j}$ \end{enumerate} En general se recomienda constru\'{\i}r $s$ tablas distintas (con distintas funciones $R$). En este caso, la memoria requerida es $\widetilde{O}(sm)$ (dado que cada tabla tiene dos columnas, su espacio es $\widetilde{O}(m)$). El tiempo requerido es el de iterar $t$ veces sobre una b\'usqueda indexada, que toma $\widetilde{O}(t)$, lo que para las $s$ tablas totaliza $\widetilde{O}(ts)$. Para el prec\'alculo hay que generar todas las tablas (aunque no se almacenen), de modo que el costo es $\widetilde{O}(smt)$. La consideraci\'on final es la probabilidad de hallar la clave. En la pr\'actica el m\'etodo no es m\'as que una prueba sobre $s \times m \times t$ claves casi aleatorias. Por lo tanto, la probabilidad de que ninguna de ellas sea la que buscamos es $$ \left(1-\frac{1}{|\cal K|}\right)^{smt} . $$ Se recomienda usar este m\'etodo con $t=m=s=|{\cal K}|^{1/3}$, con lo cual la probabilidad de no encontrar la clave es $$ \left(1-\frac{1}{|\cal K|}\right)^{|{\cal K}|} ~=~ e^{-1}~(1 + O(1/|{\cal K})) $$ dado que $e^{-1} \approx 37\%$ no es despreciable, parece m\'as recomendable hacer crecer $s$. Dada una probabilidad de error tolerada $\epsilon$, vamos a elegir $s=a|{\cal K}|^{1/3}$, $m=t=|{\cal K}|^{1/3}$ para obtener esa probabilidad. En este caso la probabilidad de error es $e^{-a}$, que igualado a $\epsilon$ nos da $a = \ln (1/\epsilon)$. Esta ``constante'' afecta tanto al tiempo como al espacio del algoritmo. Se podr\'{\i}a afectar s\'olo al tiempo o al espacio si se agrandaran $m$ o $t$ en vez de $s$. En el caso $a=1$, con DES la cantidad de memoria requerida es cercana a $2^{11}$ Gb, y el tiempo ser\'{\i}a 2 horas y cuarto con la m\'aquina referida antes. Si en cambio us\'aramos $s=1,~t=|{\cal K}|^{2/3},~m=|{\cal K}|^{1/3}$ tendr\'{\i}amos la misma probabilidad de hallar la clave (63\%) pero ahora el espacio ser\'{\i}a de s\'olo 4 Mb, y el tiempo ser\'{\i}a el mismo de antes. Este c\'alculo apunta a que no es buena idea hacer crecer $s$, y $s=1$ parecer\'{\i}a \'optimo. Es posible que la raz\'on para elegirlo grande tenga que ver con la poca aleatoriedad real de las tablas, donde ciertas claves no pueden aparecer de ninguna forma. % GZL \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 (en teor\'{\i}a al menos) 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 unas pocas claves aparecer\'an como las \'unicas posibles. Se iterar\'a entonces probando todas las claves de ese peque\~no conjunto (en un caso ideal podr\'{\i}amos obtener una \'unica clave posible, que ser\'{\i}a necesariamente la que buscamos). Otra posible alternativa, si no hay claves con probabilidad cero, usar las probabilidades para probar las claves en cierto orden, de la m\'as a la menos probable. 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} \begin{center} \input{c9-f1} \end{center} \caption{Estructura de un criptosistema atacable mediante criptoan\'alisis diferenciable.} \label{fig:estructura} \end{figure} Hemos dicho que usamos una ``distancia'' elegida entre textos planos y cifrados. Esta distancia (que representaremos con el operador de diferencia, ``$-$'') se define seg\'un el criptosistema a atacar. Para el criptosistema DES la diferencia adecuada es el XOR, denotado $\oplus$. Recordemos que $({\cal Z}_2)^n$ con este operador es un grupo abeliano, es decir tenemos conmutatividad, asociatividad, neutro (0) e inverso ($X^{-1}=X$). Dado este valor del inverso, el operador es nilpotente ($X \oplus X = $ neutro). La condici\'on que debe cumplir la operaci\'on diferencia (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 al aplicar la funci\'on $f$ sobre $X,X'$, su diferencia no se altere (ver \figref{fig:diferencias}). \begin{figure} \begin{center} \input{c9-f2} \end{center} \caption{Propagaci\'on de las diferencias a trav\'es del criptosistema.} \label{fig:diferencias} \end{figure} Dado que el \'unico punto donde la clave interviene es en la funci\'on $f$, esto implica inmediatamente que podemos montar un ataque sobre $g$. Para este ataque podemos elegir la diferencia ($\triangle B = \triangle X$), pero no podemos elegir el ``texto''. Esto se debe a que la entrada de $g$ es $B$, que no podemos controlar. Llamaremos ``texto intermedio'' a $B$. Se define entonces: $$ IN(\delta,\tau) = \{ B : g(B) - g(B-\delta) = \tau \}. $$ como el conjunto de todos los textos intermedios que convierten una diferencia $\delta$ en la entrada en una diferencia $\tau$ en la salida (diremos que estos textos intermedios ``llevan $\delta$ a $\tau$''). En el caso de DES: $$ IN(\delta,\tau) = \{ B : g(B) \oplus g(B\oplus\delta) = \tau \}, $$ Y constru\'{\i}mos: $$ K(X,\delta,\tau) = \{ k : f(X,k) \in IN(\delta,\tau) \}. $$ como el conjunto de todas las claves que aplicadas sobre $X$ pueden generar un texto intermedio que lleve de $\delta$ a $\tau$. %GZL: realmente necesario? 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)$. La rec\'{\i}proca tambi\'en es cierta. La idea es fijar $\delta$ y generar pares $X,X'$, pasarlos por el criptosistema y determinar el $\tau$ resultante. S\'olo las claves que pertenecen a $K(X,\delta,\tau)$ pueden ser la correcta. Si hacemos esto varias veces achicaremos el conjunto. Este conjunto representar\'a aquellas claves para las cuales las diferencias obtenidas tienen probabilidad mayor que cero. Lo que se desea es que restringiendo sucesivamente las claves posibles mediante los $K(X,\delta,\tau)$ terminemos con un conjunto manejable de candidatos que se puedan verificar exhaustivamente. El principal problema es que debemos tener una forma eficiente de obtener $K(X,\delta,\tau)$ sin recorrer todo el espacio, pues sino el costo de calcular $K(X,\delta,\tau)$ se acerca al de la b\'usqueda en todo el espacio de claves. El ataque procede de la siguiente forma: \begin{enumerate} \item $S \leftarrow {\cal K}$ \item Mientras $|S| >$ tama\~no razonable \item \ \ \ \ Elegir $X, X' = X-\delta$ \item \ \ \ \ Determinar $Y,Y^{\prime}$ y $\tau=\triangle Y$ \item \ \ \ \ $S \leftarrow S \cap K(X,\delta,\tau)$ \item Probar exhaustivamente las claves de $S$ \end{enumerate} \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 almacenar un subconjunto arbitrario de las $|{\cal K}|$ claves posibles (ej. de $2^{56}$ claves en el caso de DES). Si el subconjunto es $S$, se necesitan a lo menos $\log_2 {{|{\cal K}|} \choose {|S|}}$ bits para almacenarlo, lo cual en el peor caso ($|S| = |{\cal K}|/2$) implica $|{\cal K}|$ bits. Otro problema es el n\'umero de textos planos necesario para descartar casi todas las claves. 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. O al menos que se deben analizar tantos textos planos que el ataque no es mucho m\'as eficiente que la b\'usqueda exhaustiva. Finalmente, es imperativo tener un buen algoritmo para calcular los conjuntos $K(X,\delta,\tau)$ sin proceder por b\'usqueda sobre todas las claves, pues sino el enfoque pierde la gracia. Una vez que $S$ es relativamente peque\~no es f\'acil calcular su intersecci\'on con el nuevo $K(X,\delta,\tau)$ mediante recorrer $S$. Pero el comienzo es dif\'{\i}cil y la soluci\'on parece depender de los detalles espec\'{\i}ficos del criptosistema que se ataca. \subsection{Un Ejemplo: Criptoan\'alisis de 3-DES} Veremos ahora un ejemplo de criptoan\'alisis diferencial aplicado a DES con tres iteraciones s\'olamente. Este criptosistema calcula a partir de una clave $K$ de 56 bits, tres subclaves $K_1,K_2$ y $K_3$. Cada una de ellas tiene 48 bits elegidos de $K$, y se conoce cu\'ales son estos bits. De modo que si una s\'ola de las claves $K_i$ fuera conocida, tendr\'{\i}amos autom\'aticamente 48 bits de $K$, y los restantes 8 se podr\'{\i}an obtener por b\'usqueda exhaustiva sobre las $2^8 = 256$ posibilidades. Ignoraremos las permutaciones de entrada y salida de DES, pues son f\'aciles de deshacer (ya que son de dominio p\'ublico, o sea conocidas). Vamos a tratar de descubrir la tercera subclave $K_3$. 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} \\ &=& L_{0} \oplus f(R_{0},K_{1})\oplus f(R_{2},K_{3}) \oplus L_{0}' \oplus f(R_{0}',K_{1})\oplus f(R_{2}',K_{3}) \\ &=& \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, al ser $\oplus$ nilpotente: \begin{eqnarray*} \triangle R_{3} &=&\triangle L_{0}\oplus f(R_{2},K_{3})\oplus f(R_{2}^{\prime},K_{3}) , \end{eqnarray*} luego \begin{eqnarray*} \triangle R_{3}\oplus \triangle L_{0} &=& f(R_{2},K_{3})\oplus f(R_{2}^{\prime},K_{3}) \end{eqnarray*} (lo \'ultimo se obtiene operando con $\triangle L_0 = (\triangle L_0)^{-1}$ de ambos lados). Recordemos que en DES, la estructura de $f$ es la que se muestra en la \figref{fig:DES}, \begin{figure} \begin{center} \input{c9-f3} \end{center} \caption{Estructura de $f$ en el criptosistema DES.} \label{fig:DES} \end{figure} donde $P$ es nuevamente una permutaci\'on (recordar que el operador de permutaci\'on conmuta con $\oplus$). Dado que la $f(A,J)$ de la figura es $f(R_2,K_3)$ (pues nos referimos al \'ultimo paso), se tiene que $$ \triangle R_{3}\oplus \triangle L_{0} = f(R_2,K_3) \oplus f(R_2',K_3) = P(C) \oplus P(C') = P(C \oplus C')$$ de donde se deduce 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 (dado que $\triangle C$ es la concatenaci\'on de los $\triangle C_i$). Veamos que $\triangle B_{i},~i=1,\dots,8$ tambi\'en son conocidos (mediante mostrar que $\triangle B$ es conocido). En la iteraci\'on final de la \figref{fig:DES}, se tiene $A=R_2$ y $J = K_3$, de modo que $$ 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 los $\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 (ya que se comportan como se especific\'o en la \figref{fig:estructura}). Con ello obtenemos 6 bits de la clave $K_{3}$ por cada caja, en total 48 bits (no tenemos m\'as que concatenar los 8 grupos de 6 bits obtenidos). Los restantes 8 para llegar a $K$ se obtienen por fuerza bruta sin mayor problema, tal como se explic\'o. Por \'ultimo, es interesante notar que dentro de cada caja-S el conjunto de textos planos y claves posibles es completamente manejable (4 y 6 bits, respectivamente). No habr\'{\i}a el menor problema en almacenar todas las $2^6 = 64$ claves distintas, ni en recorrer el conjunto exhaustivamente para calcular $K(X,\delta,\tau)$. Incluso si prob\'aramos todos los textos posibles ($2^4 = 16$), no necesitar\'{\i}amos m\'as de $2^{10} = 1024$ iteraciones en total. Sumando sobre las 8 cajas y considerando las $2^8$ alternativas a probar al final, tenemos un total de $2^{13} + 2^8 = 8448$ operaciones ``r\'apidas'' (encripciones a lo sumo), lo cual es un n\'umero despreciable. \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} %GZL: no entendi la ultima columna 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\'{\i}das de manera de hacer que el ataque sea lo m\'as dif\'{\i}cil 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\'{\i}cil 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\'{\i}an 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\'{\i}a la t\'ecnica del criptoan\'alisis diferenciable, una t\'ecnica poderosa que puede ser utilizada contra varios criptosistemas. Esto a su vez debilitar\'{\i}a la ventaja competitiva que los Estados Unidos disfrutaba sobre el resto de los pa\'{\i}ses en materia de criptograf\'{\i}a. \end{quote} Adi Shamir desafi\'o a Coppersmith a decir que no hab\'{\i}a encontrado ning\'un ataque m\'as fuerte contra DES desde entonces, pero Coppersmith no ha respondido. Sabiendo que la NSA conoc\'{\i}a el criptoan\'alisis diferenciable m\'as de 15 a~nos antes que el mundo acad\'emico, existe cierta intriga 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 del 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{enumerate} \item es el primer ataque criptoanal\'{\i}tico contra el sistema de generaci\'on de subclaves de DES. \item este ataque es independiente del n\'umero de pasos del criptosistema, es igualmente efectivo contra DES con 16, 32 o 1000 pasos. \item 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{enumerate} \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\'{\i}a 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\'{\i}an 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\'{\i}as 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\'{\i}an el criptoan\'alisis lineal, o conoc\'{\i}an 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 encripciones. \footnote{ L.R. Knudsen, {\em``Applications of Higher Order Differentials and Partial Differentials''\/}, K.U. Leuven Workshop on Cryptographic Algorithms, Springer-Verlag, 1995.} Todav\'{\i}a es muy pronto para saber si estas extensiones facilitar\'an quebrar un DES de 16 pasos. Otra v\'{\i}a 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. \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\'{\i}a implementar en un s\'olo chip con la tecnolog\'{\i}a de 1974). \item Ning\'un bit de salida de una caja-S podr\'{\i}a 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\'{\i}a 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\'{\i}culo explica estos criterios y sus razones de ser. Generar cajas-S es sumamente f\'acil hoy en d\'{\i}a, pero era una tarea complicada en aquella \'epoca. Se dice que tuvieron computadores corriendo durante meses para fabricar las famosas cajas-S. \end{document}