Data Encryption Standard

El 17 de marzo de 1975, la propuesta de DES fue publicada en el Registro Federal. Se solicitaron comentarios por parte del público, y el año siguiente se abrieron dos talleres libres para discutir el estándar propuesto. Hubo algunas críticas desde ciertos sectores, incluyendo a los pioneros de la criptografía asimétrica Martin Hellman y Whitfield Diffie, mencionando la corta longitud de la clave y las misteriosas S-cajas como una evidencia de la inadecuada interferencia de la NSA. La sospecha era que el algoritmo había sido debilitado de manera secreta por la agencia de inteligencia de forma que ellos, y nadie más, pudiesen leer mensajes cifrados fácilmente. Alan Konheim (uno de los diseñadores de DES) comentó en una ocasión "enviaron las S-cajas a Washington. Cuando volvieron eran totalmente diferentes". El Comité de Inteligencia del Senado de los Estados Unidos revisó las acciones de la NSA para determinar si había existido algún comportamiento inadecuado. En el resumen desclasificado sobre sus conclusiones, publicado en 1978, el Comité escribía: "En el desarrollo de DES, la NSA convenció a IBM de que un tamaño de clave reducido era suficiente; participó de forma indirecta en el desarrollo de las estructuras de las S-cajas; y certificó que, hasta donde ellos conocían, estaban libres de cualquier punto débil matemático o estadístico.". De todas formas, también concluyó que "La NSA no ejerció presión en el diseño del algoritmo en modo alguno. IBM inventó y diseñó el algoritmo, tomó todas las decisiones respecto a él, y coincidió en que el tamaño de la clave era más que apropiado para todas las aplicaciones comerciales para las que estaba pensado DES". Otro miembro del equipo de DES, Walter Tuchman, decía también: "Desarrollamos todo el algoritmo DES en IBM y con gente de IBM. ¡La NSA no dictó ni un solo paso!".

Algunas de las sospechas sobre puntos débiles ocultos en las S-cajas fueron descartadas en 1990, con el descubrimiento independiente y la publicación libre por Eli Biham y Adi Shamir del criptoanálisis diferencial, un método general para romper cifrados de bloque. Las S-cajas de DES eran mucho más resistentes al ataque que si hubiesen sido escogidas al azar, lo que sugería que IBM conocía la técnica allá en los 70. Este era de hecho, el caso, en 1994, Don Coppersmith publicó los criterios de diseño originales para las S-cajas. IBM había descubierto el criptoanálisis diferencial en los 70 y, tras asegurar DES, la NSA les ordenó mantener en secreto la técnica. Coppersmith explica: "Esto era así porque el criptoanálisis diferencial puede ser una herramienta muy potente, contra muchos esquemas diferentes, y había la preocupación de que aquella información en dominio público podía afectar negativamente a la seguridad nacional". Shamir también comentó "Yo diría, al contrario de lo que algunos creen, que no hay evidencias de influencia alguna en el diseño de DES para que su estructura básica esté debilitada."

Las otras críticas, sobre que la longitud de clave era demasiado corta, se fundaban en el hecho de que la razón dada por la NSA para reducir la longitud de la clave de 64 bits a 56 era que los 8 bits restantes podían servir como bits de paridad, lo que en cierto modo resultaba sospechoso. Es ampliamente aceptado que la decisión de la NSA estaba motivada por la posibilidad de que ellos podrían llevar a cabo un ataque por fuerza bruta contra una clave de 56 bits varios años antes que el resto del mundo.

A pesar de la polémica, DES fue aprobado como estándar federal en noviembre de 1976, y publicado el 15 de enero de 1977 como FIPS PUB 46, autorizado para el uso no clasificado de datos. Fue posteriormente confirmado como estándar en 1983, 1988 (revisado como FIPS-46-1), 1993 (FIPS-46-2), y de nuevo en 1998 (FIPS-46-3), este último definiendo "TripleDES" (véase más abajo). El 26 de mayo de 2002, DES fue finalmente reemplazado por AES (Advanced Encryption Standard), tras una competición pública (véase Proceso de Advanced Encryption Standard). Hasta hoy día (2006), DES continúa siendo ampliamente utilizado.

Otro ataque teórico, el criptoanálisis lineal, fue publicado en 1994, pero fue un ataque por fuerza bruta en 1998 el que demostró que DES podría ser atacado en la práctica, y se destacó la necesidad de un algoritmo de repuesto. Estos y otros métodos de criptoanálisis se comentan con más detalle posteriormente en este artículo.

La introducción de DES es considerada como un desencadenador del estudio académico de la criptografía, en particular de los métodos para romper cifrados de bloque. Bruce Schneier escribe:

"De puertas hacia dentro, la NSA ha visto a DES como uno de sus grandes errores. Si hubiesen sabido que los detalles serían publicados para que la gente pudiese escribir software, nunca hubieran estado de acuerdo. DES hizo más para galvanizar el campo de la criptografía que nunca nada antes. Ahora había un algoritmo que estudiar: uno que la NSA decía que era seguro."

Cambiando

La estructura básica del algoritmo aparece representada en la Figura 1: hay 16 fases idénticas de proceso, denominadas rondas. También hay una permutación inicial y final denominadas PI y PF, que son funciones inversas entre sí (PI "deshace" la acción de PF, y viceversa). PI y PF no son criptográficamente significativas, pero se incluyeron presuntamente para facilitar la carga y descarga de bloques sobre el hardware de mediados de los 70. Antes de las rondas, el bloque es dividido en dos mitades de 32 bits y procesadas alternativamente. Este entrecruzamiento se conoce como esquema Feistel.

La estructura de Feistel asegura que el cifrado y el descifrado sean procesos muy similares — la única diferencia es que las subclaves se aplican en orden inverso cuando desciframos. El resto del algoritmo es idéntico. Esto simplifica enormemente la implementación, en especial sobre hardware, al no haber necesidad de algoritmos distintos para el cifrado y el descifrado.

El símbolo rojo "⊕" representa la operación OR exclusivo (XOR). La función-F mezcla la mitad del bloque con parte de la clave. La salida de la función-F se combina entonces con la otra mitad del bloque, y los bloques son intercambiados antes de la siguiente ronda. Tras la última ronda, las mitades no se intercambian; ésta es una característica de la estructura de Feistel que hace que el cifrado y el descifrado sean procesos parecidos.

La función-F, representada en la Figura 2, opera sobre medio bloque (32 bits) cada vez y consta de cuatro pasos:

Figura 2 —La función Feistel (Función-F) de DES.

1. Expansión — la mitad del bloque de 32 bits se expande a 48 bits mediante la permutación de expansión, denominada E en el diagrama, duplicando algunos de los bits.
2. Mezcla — el resultado se combina con una subclave utilizando una operación XOR. Dieciséis subclaves — una para cada ronda — se derivan de la clave inicial mediante la generación de subclaves descrita más abajo.
3. Sustitución — tras mezclarlo con la subclave, el bloque es dividido en ocho trozos de 6 bits antes de ser procesados por las S-cajas, o cajas de sustitución. Cada una de las ocho S-cajas reemplaza sus seis bits de entrada con cuatro bits de salida, de acuerdo con una trasformación no lineal, especificada por una tabla de búsqueda. Las S-cajas constituyen el núcleo de la seguridad de DES — sin ellas, el cifrado sería lineal, y fácil de romper.
4. Permutación — finalmente, las 32 salidas de las S-cajas se reordenan de acuerdo a una permutación fija; la P-caja

Alternando la sustitución de las S-cajas, y la permutación de bits de la P-caja y la expansión-E proporcionan las llamadas "confusión y difusión" respectivamente, un concepto identificado por Claude Shannon en los 40 como una condición necesaria para un cifrado seguro y práctico.

Figura 3 — La generación de clave de DES.

La Figura 3 representa la generación de claves para el cifrado — el algoritmo que se encarga de proporcionar las subclaves. Primero, se seleccionan 56 bits de la clave de los 64 iniciales mediante la Elección Permutada 1 (PC-1) — los ocho bits restantes pueden descartarse o utilizarse como bits de comprobación de paridad. Los 56 bits se dividen entonces en dos mitades de 28 bits; a continuación cada mitad se trata independientemente. En rondas sucesivas, ambas mitades se desplazan hacia la izquierda uno o dos bits (dependiendo de cada ronda), y entonces se seleccionan 48 bits de subclave mediante la Elección Permutada 2 (PC-2) — 24 bits de la mitad izquierda y 24 de la derecha. Los desplazamientos (indicados por "<<<" en el diagrama) implican que se utiliza un conjunto diferente de bits en cada subclave; cada bit se usa aproximadamente en 14 de las 16 subclaves.

La generación de claves para descifrado es similar — debe generar las claves en orden inverso.

Para cualquier tipo de cifrado, el método de ataque más simple es el ataque por fuerza bruta — probando una por una cada posible clave. La longitud de clave determina el número posible de claves, y por tanto la factibilidad del ataque. En el caso de DES, ya en sus comienzos se plantearon cuestiones sobre su longitud de clave, incluso antes de ser adoptado como estándar, fue su reducido tamaño de clave, más que el criptoanálisis teórico, el que provocó la necesidad de reemplazarlo. Se sabe que la NSA animó, o incluso persuadió a IBM para que redujera el tamaño de clave de 128 bits a 64, y de ahí a 56 bits; con frecuencia esto se ha interpretado como una evidencia de que la NSA poseía suficiente capacidad de computación para romper claves de este tamaño incluso a mediados de los 70.

Académicamente, se adelantaron varias propuestas de una máquina para romper DES. En 1977, Diffie y Hellman propusieron una máquina con un coste estimado de 20 millones de dólares que podría encontrar una clave DES en un solo día. Hacia 1993, Wiener propuso una máquina de búsqueda de claves con un coste de un millón de dólares que encontraría una clave en 7 horas. La vulnerabilidad de DES fue demostrada en la práctica en 1998 cuando la Electronic Frontier Foundation (EFF), un grupo dedicado a los derechos civiles en el ciberespacio, construyó una máquina a medida para romper DES, con un coste aproximado de 250000 dólares (véase EFF DES cracker). Su motivación era demostrar que se podía romper DES tanto en la teoría como en la práctica: "Hay mucha gente que no creerá una verdad hasta que puedan verla con sus propios ojos. Mostrarles una máquina física que pueda romper DES en unos pocos días es la única manera de convencer a algunas personas de que realmente no pueden confiar su seguridad a DES." La máquina rompió una clave por fuerza bruta en una búsqueda que duró poco más de 2 días; más o menos al mismo tiempo, un abogado del Departamento de Justicia de los Estados Unidos proclamaba que DES era irrompible.

Existen tres ataques conocidos que pueden romper las dieciséis rondas completas de DES con menos complejidad que un ataque por fuerza bruta: el criptoanálisis diferencial (CD), el criptoanálisis lineal (CL) y el ataque de Davies. De todas maneras, estos ataques son sólo teóricos y no es posible llevarlos a la práctica; este tipo de ataques se denominan a veces debilidades certificacionales.

• El criptoanálisis diferencial fue descubierto a finales de los 80 por Eli Biham y Adi Shamir, aunque era conocido anteriormente tanto por la NSA como por IBM y mantenido en secreto. Para romper las 16 rondas completas, el criptoanálisis diferencial requiere 2⁴⁷ textos planos escogidos. DES fue diseñado para ser resistente al CD.
• El criptoanálisis lineal fue descubierto por Mitsuru Matsui, y necesita 2⁴³ textos planos conocidos (Matsui, 1993); el método fue implementado (Matsui, 1994), y fue el primer criptoanálisis experimental de DES que se dio a conocer. No hay evidencias de que DES fuese adaptado para ser resistente a este tipo de ataque. Una generalización del CL — el criptoanálisis lineal múltiple — se propuso en 1994 (Kaliski and Robshaw), y fue mejorada por Biryukov y otros (2004); su análisis sugiere que se podrían utilizar múltiples aproximaciones lineales para reducir los requisitos de datos del ataque en al menos un factor de 4 (es decir, 2⁴¹ en lugar de 2⁴³). Una reducción similar en la complejidad de datos puede obtenerse con una variante del criptoanálisis lineal de textos planos escogidos (Knudsen y Mathiassen, 2000). Junod (2001) realizó varios experimentos para determinar la complejidad real del criptoanálisis lineal, y descubrió que era algo más rápido de lo predicho, requiriendo un tiempo equivalente a 2³⁹–2⁴¹ comprobaciones en DES.
• El ataque mejorado de Davies: mientras que el análisis lineal y diferencial son técnicas generales y pueden aplicarse a multitud de esquemas diferentes, el ataque de Davies es una técnica especializada para DES. Propuesta por vez primera por Davies en los 80, y mejorada por Biham and Biryukov (1997). La forma más potente del ataque requiere 2⁵⁰ textos planos conocidos, tiene una complejidad computacional de 2⁵⁰, y tiene un 51% de probabilidad de éxito.

Existen también ataques pensados para versiones del algoritmo con menos rondas, es decir versiones de DES con menos de dieciséis rondas. Dichos análisis ofrecen una perspectiva sobre cuantas rondas son necesarias para conseguir seguridad, y cuánto «margen de seguridad» proporciona la versión completa. El criptoanálisis diferencial-lineal fue propuesto por Langford y Hellman en 1994, y combina criptoanálisis diferencial y lineal en un mismo ataque. Una versión mejorada del ataque puede romper un DES de 9 rondas con 2^15.8 textos planos conocidos y tiene una complejidad temporal de 2^29.2 (Biham y otros, 2002).

DES presenta la propiedad complementaria, dado que

${\displaystyle E_{K}(P)=C\Leftrightarrow E_{\overline {K}}({\overline {P}})={\overline {C}}}$

donde ${\displaystyle {\overline {x}}}$ es el complemento a bit de ${\displaystyle x}$. ${\displaystyle E_{K}}$ es el cifrado con la clave ${\displaystyle K.}$ ${\displaystyle P}$ y ${\displaystyle C}$ son el texto plano y el texto cifrado respectivamente. La propiedad complementaria implica que el factor de trabajo para un ataque por fuerza bruta se podría reducir en un factor de 2 (o de un único bit) asumiendo un ataque con texto plano escogido.

DES posee también cuatro claves débiles. El cifrado (E) y el descifrado (D) con una clave débil tienen el mismo efecto (véase involución):

${\displaystyle E_{K}(E_{K}(P))=P}$ o lo que es lo mismo, ${\displaystyle E_{K}=D_{K}}$. Hay también seis pares de claves semi-débiles. El cifrado con una de las claves de un par de claves semi-débiles, ${\displaystyle K_{1}}$, funciona de la misma manera que el descifrado con la otra, ${\displaystyle K_{2}}$:

${\displaystyle E_{K_{1}}(E_{K_{2}}(P))=P}$ o lo que es lo mismo, ${\displaystyle E_{K_{2}}=D_{K_{1}}}$

Es bastante fácil evitar las claves débiles y semi-débiles en la implementación, ya sea probándolas explícitamente, o simplemente escogiéndolas aleatoriamente; las probabilidades de coger una clave débil o semidébil son despreciables.

Se ha demostrado también que DES no tiene estructura de grupo, o más concretamente, el conjunto ${\displaystyle \{E_{K}\}}$ (para todas las claves posibles ${\displaystyle K}$) no es un grupo, ni siquiera está "cerca" de ser un grupo (Campbell y Wiener, 1992). Ésta fue una cuestión abierta durante algún tiempo, y si se hubiese dado el caso, hubiera sido posible romper DES, y las modalidades de cifrado múltiple como Triple DES no hubiesen incrementado la seguridad.