Estándar de cifrado de datos

El 17 de marzo de 1975, el DES propuesto se publicó en el Registro Federal . Se solicitaron comentarios públicos y, al año siguiente, se celebraron dos talleres abiertos para debatir el estándar propuesto. Se recibieron críticas de los pioneros de la criptografía de clave pública Martin Hellman y Whitfield Diffie , ^{[ 1 ]} citando una longitud de clave reducida y las misteriosas " cajas S " como evidencia de interferencia indebida por parte de la NSA. Se sospechaba que el algoritmo había sido debilitado secretamente por la agencia de inteligencia para que ellos —pero nadie más— pudieran leer fácilmente los mensajes cifrados. ^{[ 9 ]} Alan Konheim (uno de los diseñadores del DES) comentó: "Enviamos las cajas S a Washington. Regresaron y todas eran diferentes". ^{[ 10 ]} El Comité Selecto de Inteligencia del Senado de los Estados Unidos revisó las acciones de la NSA para determinar si había habido alguna participación indebida. En el resumen no clasificado de sus conclusiones, publicado en 1978, el Comité escribió:

En el desarrollo de DES, la NSA convenció a IBM de que un tamaño de clave reducido era suficiente; ayudó indirectamente en el desarrollo de las estructuras de la caja S; y certificó que el algoritmo DES final estaba, según su leal saber y entender, libre de cualquier debilidad estadística o matemática. ^{[ 11 ]}

Sin embargo, también descubrió que

La NSA no alteró en absoluto el diseño del algoritmo. IBM inventó y diseñó el algoritmo, tomó todas las decisiones pertinentes al respecto y coincidió en que el tamaño de clave acordado era más que suficiente para todas las aplicaciones comerciales para las que se concibió el DES. ^{[ 12 ]}

Otro miembro del equipo DES, Walter Tuchman, declaró: «Desarrollamos el algoritmo DES completamente dentro de IBM utilizando empleados de IBM. ¡La NSA no dictó ni un solo cable!» ^{[ 13 ]} En contraste, un libro desclasificado de la NSA sobre historia de la criptología afirma:

En 1973, el NBS solicitó a la industria privada un estándar de cifrado de datos (DES). Las primeras propuestas fueron decepcionantes, por lo que la NSA comenzó a trabajar en su propio algoritmo. Entonces, Howard Rosenblum, subdirector de investigación e ingeniería, descubrió que Walter Tuchman, de IBM, estaba trabajando en una modificación de Lucifer para uso general. La NSA autorizó a Tuchman y lo incorporó para trabajar conjuntamente con la Agencia en su modificación de Lucifer. ^{[ 14 ]}

y

La NSA colaboró ​​estrechamente con IBM para reforzar el algoritmo contra todos los ataques, excepto los de fuerza bruta, y para fortalecer las tablas de sustitución, denominadas cajas S. Por otro lado, la NSA intentó convencer a IBM de que redujera la longitud de la clave de 64 a 48 bits. Finalmente, llegaron a un acuerdo sobre una clave de 56 bits. ^{[ 15 ] [ 16 ]}

Algunas de las sospechas sobre las debilidades ocultas en las cajas S se disiparon en 1990 con el descubrimiento independiente y la publicación abierta por parte de Eli Biham y Adi Shamir del criptoanálisis diferencial , un método general para romper cifrados de bloques. Las cajas S de DES eran mucho más resistentes al ataque que si se hubieran elegido al azar, lo que sugiere firmemente que IBM conocía la técnica en la década de 1970. Este fue, en efecto, el caso; en 1994, Don Coppersmith publicó algunos de los criterios de diseño originales para las cajas S. ^{[ 17 ]} Según Steven Levy , los investigadores de IBM Watson descubrieron ataques criptoanalíticos diferenciales en 1974 y la NSA les pidió que mantuvieran la técnica en secreto. ^{[ 18 ]} Coppersmith explica la decisión de IBM de mantener el secreto diciendo: "Eso se debió a que [el criptoanálisis diferencial] puede ser una herramienta muy poderosa, utilizada contra muchos esquemas, y existía la preocupación de que dicha información en el dominio público pudiera afectar negativamente la seguridad nacional". Levy cita a Walter Tuchman: «[Nos pidieron que marcáramos todos nuestros documentos como confidenciales... De hecho, numeramos cada uno y los guardamos en cajas fuertes, porque se consideraban clasificados por el gobierno de EE. UU. Dijeron que lo hiciera. Así que lo hice». ^{[ 18 ]} Bruce Schneier observó que «La comunidad académica tardó dos décadas en darse cuenta de que los "ajustes" de la NSA en realidad mejoraron la seguridad del DES». ^{[ 19 ]}

A pesar de las críticas, 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 su uso en todos los datos no clasificados. Posteriormente, fue reafirmado como estándar en 1983, 1988 (revisado como FIPS-46-1), 1993 (FIPS-46-2) y nuevamente en 1999 (FIPS-46-3), este último prescribiendo " Triple DES " (véase más abajo). El 26 de mayo de 2002, DES fue finalmente reemplazado por el Estándar de Cifrado Avanzado (AES), tras un concurso público . El 19 de mayo de 2005, FIPS 46-3 fue retirado oficialmente, pero el NIST ha aprobado Triple DES hasta el año 2030 para información gubernamental sensible. ^{[ 20 ]}

El algoritmo también se especifica en ANSI X3.92 (hoy X3 se conoce como INCITS y ANSI X3.92 como ANSI INCITS 92), ^{[ 21 ]} NIST SP 800-67 ^{[ 20 ]} e ISO/IEC 18033-3 ^{[ 22 ]} (como un componente de TDEA ).

Otro ataque teórico, el criptoanálisis lineal, se publicó en 1994, pero fue el descifrador de DES de la Electronic Frontier Foundation en 1998 el que demostró que DES podía ser atacado de forma muy práctica y puso de manifiesto la necesidad de un algoritmo alternativo. Estos y otros métodos de criptoanálisis se analizan con más detalle más adelante en este artículo.

Se considera que la introducción de DES fue un catalizador para el estudio académico de la criptografía, en particular de los métodos para descifrar cifrados de bloques. Según una retrospectiva del NIST sobre DES,

Se puede decir que el DES impulsó el estudio y desarrollo no militar de algoritmos de cifrado. En la década de 1970, había muy pocos criptógrafos, salvo los de organizaciones militares o de inteligencia, y escaso estudio académico de la criptografía. Actualmente, existen numerosos criptólogos académicos activos, departamentos de matemáticas con sólidos programas en criptografía y empresas y consultoras comerciales de seguridad de la información . Una generación de criptoanalistas se ha iniciado analizando (es decir, intentando descifrar) el algoritmo DES. En palabras del criptógrafo Bruce Schneier , ^{[ 23 ]} «El DES contribuyó más que ninguna otra cosa a dinamizar el campo del criptoanálisis. Ahora existía un algoritmo que estudiar». Una sorprendente cantidad de la literatura abierta sobre criptografía en las décadas de 1970 y 1980 trataba sobre el DES, y este es el estándar con el que se ha comparado todo algoritmo de clave simétrica posterior. ^{[ 24 ]}

La estructura general del algoritmo se muestra en la Figura 1: hay 16 etapas de procesamiento idénticas, denominadas rondas . También hay una permutación inicial y final , denominadas IP y FP , que son inversas (IP "deshace" la acción de FP, y viceversa). IP y FP no tienen significado criptográfico, pero se incluyeron para facilitar la carga y descarga de bloques en el hardware de 8 bits de mediados de la década de 1970. ^{[ 30 ]}

Antes de las rondas principales, el bloque se divide en dos mitades de 32 bits y se procesa alternativamente; este proceso cruzado se conoce como esquema Feistel . La estructura Feistel garantiza que el cifrado y el descifrado sean procesos muy similares; la única diferencia radica en que las subclaves se aplican en orden inverso durante el descifrado. El resto del algoritmo es idéntico. Esto simplifica enormemente la implementación, especialmente en hardware, ya que no se requieren algoritmos de cifrado y descifrado independientes.

El símbolo ⊕ representa la operación XOR ( OR exclusivo ). La función F mezcla la mitad de un bloque con parte de la clave. El resultado de la función F se combina con la otra mitad del bloque, y las mitades se intercambian antes de la siguiente ronda. Tras la ronda final, las mitades se intercambian; esta es una característica de la estructura Feistel que hace que el cifrado y el descifrado sean procesos similares.

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

1. Expansión : el medio bloque de 32 bits se expande a 48 bits mediante la permutación de expansión , denotada como E en el diagrama, duplicando la mitad de los bits. La salida consta de ocho piezas de 6 bits (8 × 6 = 48 bits), cada una con una copia de 4 bits de entrada correspondientes, más una copia del bit inmediatamente adyacente de cada una de las piezas de entrada a cada lado.
2. Mezcla de claves : el resultado se combina con una subclave mediante una operación XOR. Dieciséis subclaves de 48 bits (una para cada ronda) se derivan de la clave principal utilizando el esquema de claves (que se describe a continuación).
3. Sustitución : tras incorporar la subclave, el bloque se divide en ocho fragmentos de 6 bits antes de ser procesado por las cajas S , o cajas de sustitución . Cada una de las ocho cajas S reemplaza sus seis bits de entrada con cuatro bits de salida según una transformación no lineal, proporcionada en forma de tabla de consulta . Las cajas S constituyen la base de la seguridad de DES; sin ellas, el cifrado sería lineal y fácilmente vulnerable.
4. Permutación : finalmente, las 32 salidas de las cajas S se reorganizan según una permutación fija , la caja P. Esto está diseñado para que, después de la permutación, los bits de la salida de cada caja S en esta ronda se distribuyan entre cuatro cajas S diferentes en la siguiente ronda.

La alternancia de sustitución a partir de las cajas S y la permutación de bits a partir de la caja P y la expansión E proporciona, respectivamente, la denominada " confusión y difusión ", un concepto identificado por Claude Shannon en la década de 1940 como una condición necesaria para un cifrado seguro pero práctico.

La Figura 3 ilustra el esquema de claves para el cifrado: el algoritmo que genera las subclaves. Inicialmente, se seleccionan 56 bits de la clave de los 64 iniciales mediante la Opción Permutada 1 ( PC-1 ); los ocho bits restantes se descartan o se utilizan como bits de verificación de paridad . Los 56 bits se dividen en dos mitades de 28 bits; cada mitad se procesa por separado. En rondas sucesivas, ambas mitades se rotan a la izquierda uno o dos bits (especificado para cada ronda), y luego se seleccionan 48 bits de subclave mediante la Opción Permutada 2 ( PC-2 ): 24 bits de la mitad izquierda y 24 de la derecha. Las rotaciones (indicadas con "<<<" en el diagrama) implican que se utiliza un conjunto diferente de bits en cada subclave; cada bit se utiliza en aproximadamente 14 de las 16 subclaves.

El esquema de claves para el descifrado es similar: las subclaves están en orden inverso al del cifrado. Aparte de este cambio, el proceso es el mismo que para el cifrado. Los mismos 28 bits se transmiten a todas las cajas de rotación.

A continuación se muestra el pseudocódigo del algoritmo DES.

// Todas las variables son de 64 bits sin signo.// Preprocesamiento: relleno con la diferencia de tamaño en bytes para rellenar el mensaje hasta alcanzar un múltiplo de 64 bits de longitud.var key // Las claves proporcionadas por el usuario var keys [ 16 ] var left , right// Generar claves// PC1 (64 bits a 56 bits) clave := permutación ( clave , PC1 ) izquierda := ( clave desplazamiento a la derecha 28 ) y 0xFFFFFFF derecha := clave y 0xFFFFFFFpara i de 1 a 16 hacer derecha := derecha izquierda rotar KEY_shift [ i ] izquierda := izquierda izquierda rotar KEY_shift [ i ] var concat := ( izquierda izquierda shift 28 ) o derecha // PC2 (56 bits a 48 bits) keys [ i ] := permutación ( concat , PC2 ) fin para// Para descifrar un mensaje, invierta el orden de las claves. Si se descifra, invierta las claves. Fin de la condición .// Cifra o descifra para cada bloque de 64 bits del mensaje con relleno do var tmp// IP chunk := permutación ( chunk , IP ) izquierda := chunk desplazamiento a la derecha 32 derecha := chunk y 0xFFFFFFFF para i de 1 a 16 hacer tmp := derecha // E (32 bits a 48 bits) derecha := expansión ( derecha , E ) derecha := derecha xor keys [ i ] // Sustitución (48 bits a 32 bits) derecha := sustitución ( derecha ) // P derecha := permutación ( derecha , P ) derecha := derecha xor izquierda izquierda := tmp fin para // Concatenar derecha e izquierda var cipher_chunk := ( derecha desplazamiento a la izquierda 32 ) o izquierda // FP cipher_chunk := permutación ( cipher_chunk , FP ) fin para

Para cualquier cifrado , el método de ataque más básico es la fuerza bruta : probar todas las claves posibles una por una. La longitud de la clave determina el número de claves posibles y, por lo tanto, la viabilidad de este enfoque. En el caso de DES, surgieron dudas sobre la idoneidad de su tamaño de clave desde el principio, incluso antes de que se adoptara como estándar, y fue precisamente el pequeño tamaño de la clave, más que el criptoanálisis teórico, lo que dictó la necesidad de un algoritmo de reemplazo . Como resultado de las discusiones con consultores externos, incluida la NSA, el tamaño de la clave se redujo de 256 bits a 56 bits para que cupiera en un solo chip. ^{[ 31 ]}

En el ámbito académico, se presentaron varias propuestas para una máquina de descifrado DES. En 1977, Diffie y Hellman propusieron una máquina con un costo estimado de $20,000,000 (equivalente a $106,260,297 en 2025) que podría encontrar una clave DES en un solo día. ^{[ 1 ] [ 32 ]} Para 1993, Wiener había propuesto una máquina de búsqueda de claves con un costo de $1,000,000 (equivalente a $2,228,749 en 2025) que encontraría una clave en 7 horas. Sin embargo, ninguna de estas primeras propuestas se implementó jamás, o al menos, ninguna implementación fue reconocida públicamente. La vulnerabilidad de DES se demostró prácticamente a finales de la década de 1990. ^{[ 33 ]} En 1997, RSA Security patrocinó una serie de concursos, ofreciendo un premio de $10,000 al primer equipo que descifrara un mensaje cifrado con DES para el concurso. Ese concurso fue ganado por el Proyecto DESCHALL , liderado por Rocke Verser, Matt Curtin y Justin Dolske, utilizando ciclos de inactividad de miles de computadoras en Internet. La viabilidad de descifrar DES rápidamente se demostró en 1998 cuando la Electronic Frontier Foundation (EFF), un grupo de derechos civiles en el ciberespacio, construyó un descifrador de DES personalizado, con un costo aproximado de $250,000 (equivalente a $493,824 en 2025) (ver descifrador de DES de la EFF ). Su motivación era demostrar que DES era vulnerable tanto en la práctica como en la teoría: " Hay muchas personas que no creerán una verdad hasta que la vean con sus propios ojos. Mostrarles una máquina física que puede descifrar DES en unos días es la única manera de convencer a algunas personas de que realmente no pueden confiar su seguridad a DES " . La máquina descifró una clave por fuerza bruta en poco más de 2 días de búsqueda.

El siguiente descifrador de DES confirmado fue la máquina COPACOBANA construida en 2006 por equipos de las Universidades de Bochum y Kiel , ambas en Alemania . A diferencia de la máquina EFF, COPACOBANA consta de circuitos integrados reconfigurables disponibles comercialmente. 120 de estas matrices de puertas programables en campo (FPGA) del tipo XILINX Spartan-3 1000 funcionan en paralelo. Están agrupadas en 20 módulos DIMM, cada uno con 6 FPGA. El uso de hardware reconfigurable hace que la máquina sea aplicable también a otras tareas de descifrado de códigos. ^{[ 34 ]} Uno de los aspectos más interesantes de COPACOBANA es su factor de costo. Una máquina se puede construir por aproximadamente $10000 (equivalente a $15,527 en 2025) . ^{[ 35 ]} La disminución del costo en aproximadamente un factor de 25 con respecto a la máquina EFF es un ejemplo de la mejora continua del hardware digital —véase la ley de Moore . Desde 2007, SciEngines GmbH , una empresa derivada de los dos socios del proyecto COPACOBANA, ha mejorado y desarrollado sucesores de COPACOBANA. En 2008, su COPACOBANA RIVYERA redujo el tiempo necesario para romper DES a menos de un día, utilizando 128 Spartan-3 5000. SciEngines RIVYERA ostentaba el récord de ruptura por fuerza bruta de DES, habiendo utilizado 128 FPGA Spartan-3 5000. Su modelo LX150 de 256 Spartan-6 ha reducido aún más este tiempo. ^{[ 36 ]}

En 2012, David Hulton y Moxie Marlinspike anunciaron un sistema con 48 FPGA Xilinx Virtex-6 LX240T, cada FPGA contenía 40 núcleos DES totalmente segmentados que se ejecutaban a400  MHz , para una capacidad total de 768 gigakeys/seg. ^{[ 37 ]} El sistema puede buscar exhaustivamente en todo el espacio de claves DES de 56 bits en aproximadamente 26 horas y este servicio se ofrece en línea por una tarifa. ^{[ 38 ]} Sin embargo, el servicio ha estado fuera de servicio desde 2024.para mantenimiento ^{[ 38 ]}

Se conocen tres ataques que pueden romper las 16 rondas completas de DES con menos complejidad que una búsqueda por fuerza bruta: criptoanálisis diferencial (DC), ^{[ 39 ]} criptoanálisis lineal (LC), ^{[ 40 ]} y el ataque de Davies . ^{[ 41 ]} Sin embargo, los ataques son teóricos y generalmente se consideran inviables en la práctica; este tipo de ataques a veces se denominan debilidades de certificación.

• El criptoanálisis diferencial fue redescubierto a finales de la década de 1980 por Eli Biham y Adi Shamir ; era conocido anteriormente tanto por IBM como por la NSA y se mantuvo en secreto. Para romper las 16 rondas completas, el criptoanálisis diferencial requiere 2 ⁴⁷ textos planos elegidos . ^{[ 39 ]} DES fue diseñado para ser resistente al DC.
• El criptoanálisis lineal fue descubierto por Mitsuru Matsui y requiere 2 ⁴³ textos planos conocidos ; ^{[ 40 ]} el método fue implementado por Matsui en 1994 y fue el primer criptoanálisis experimental de DES que se informó. No hay evidencia de que DES haya sido diseñado para ser resistente a este tipo de ataque. Una generalización de LC —criptoanálisis lineal múltiple— fue sugerida en 1994 y fue refinada posteriormente por Biryukov y otros; su análisis sugiere que se podrían usar 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 ⁴³ ). ^{[ 42 ]} Una reducción similar en la complejidad de datos se puede obtener en una variante de texto plano elegido del criptoanálisis lineal. ^{[ 43 ]} Junod realizó varios experimentos para determinar la complejidad temporal real del criptoanálisis lineal, e informó que era algo más rápido de lo previsto, requiriendo un tiempo equivalente a 2 evaluaciones DES ^{39-41 . [ 44 ]}
• Ataque de Davies mejorado : mientras que el criptoanálisis lineal y diferencial son técnicas generales y se pueden aplicar a varios esquemas, el ataque de Davies es una técnica especializada para DES, sugerida por primera vez por Donald Davies en los años ochenta y mejorada por Biham y Biryukov en 1997. ^{[ 41 ] [ 45 ]} La forma más potente del ataque requiere 2 ⁵⁰ textos planos conocidos , tiene una complejidad computacional de 2 ⁵⁰ y tiene una tasa de éxito del 51 %.

También se han propuesto ataques contra versiones con menos rondas del cifrado, es decir, versiones de DES con menos de 16 rondas. Este tipo de análisis permite comprender cuántas rondas son necesarias para garantizar la seguridad y qué margen de seguridad conserva la versión completa.

El criptoanálisis diferencial-lineal fue propuesto por Langford y Hellman en 1994 y combina el criptoanálisis diferencial y lineal en un solo ataque. ^{[ 46 ]} Una versión mejorada del ataque puede romper DES de 9 rondas con 2 ^15,8 textos planos elegidos y tiene una complejidad temporal de 2 ^29,2 . ^{[ 47 ]}

DES exhibe la propiedad de complementación, a saber, que

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

dónde${\displaystyle {\overline {x}}}$es el complemento bit a bit de${\displaystyle x.}$${\displaystyle E_{K}}$indica cifrado con clave${\displaystyle K.}$${\displaystyle P}$y${\displaystyle C}$denotan los bloques de texto plano y texto cifrado, respectivamente. La propiedad de complementación significa que el trabajo para un ataque de fuerza bruta podría reducirse en un factor de 2 (o un solo bit) bajo el supuesto de texto plano elegido . Por definición, esta propiedad también se aplica al cifrado TDES. ^{[ 48 ]}

DES también tiene cuatro llamadas 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 equivalentemente,${\displaystyle E_{K}=D_{K}.}$

También hay seis pares de claves semidébiles . El cifrado con uno de los pares de claves semidébiles,${\displaystyle K_{1}}$, funciona de forma idéntica al descifrado con el otro,${\displaystyle K_{2}}$:

${\ Displaystyle E_ {K_ {1}} (E_ {K_ {2}} (P)) = P}$o equivalentemente,${\ Displaystyle E_ {K_ {2}} = D_ {K_ {1}}.}$

Es bastante sencillo evitar las claves débiles y semidébiles en una implementación, ya sea comprobándolas explícitamente o simplemente eligiéndolas al azar; la probabilidad de elegir una clave débil o semidébil por casualidad es insignificante. En realidad, estas claves no son más débiles que las demás, ya que no otorgan ninguna ventaja a un ataque.

También se ha demostrado que DES no es un grupo , o más precisamente, el conjunto.${\displaystyle \{E_{K}\}}$(para todas las claves posibles)${\displaystyle K}$) bajo composición funcional no es un grupo, ni "cercano" a ser un grupo. ^{[ 49 ]} Esta fue una cuestión abierta durante algún tiempo, y si hubiera sido así, habría sido posible romper DES, y los modos de cifrado múltiples como Triple DES no aumentarían la seguridad, porque el cifrado repetido (y el descifrado) con diferentes claves sería equivalente al cifrado con otra clave única. ^{[ 50 ]}