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