Cómo se descifró DES

DES tiene 2^56 claves posibles, lo que equivale aproximadamente a 72 mil billones (72,057,594,037,927,936) de claves. Aunque parece una cantidad enorme, es un espacio finito que puede buscarse sistemáticamente con suficiente capacidad de cómputo.

El agotamiento de claves (fuerza bruta) requiere probar, en promedio, la mitad del espacio de claves antes de encontrar la clave correcta. En el caso de DES, esto significa aproximadamente 2^55 descifrados de prueba, cada uno de los cuales requiere unas pocas operaciones en hardware moderno.

En 1997, RSA Data Security ofreció un premio de $10,000 por descifrar un mensaje cifrado con DES. Rocke Verser coordinó un esfuerzo de computación distribuida en el que participaron decenas de miles de ordenadores conectados a Internet.

Tras 96 días de búsqueda, se encontró la clave. El texto en claro era "La criptografía sólida hace del mundo un lugar más seguro." El esfuerzo demostró que DES podía romperse, aunque requería meses y una coordinación masiva.

La Electronic Frontier Foundation construyó Deep Crack por $250,000 en 1998. Contenía 1,856 ASIC diseñados a medida, cada uno capaz de probar 2.5 millones de claves DES por segundo, lo que proporcionaba a Deep Crack una velocidad combinada de más de 90 mil millones de claves por segundo.

Deep Crack podía agotar todo el espacio de claves de DES en unos 9 días de media. Esto demostró que un adversario decidido, con una inversión de $250,000, podía romper DES en menos de dos semanas.

En el DES Challenges II-1 (febrero de 1998), Deep Crack, combinado con la red de computación voluntaria de distributed.net, logró descifrar DES en solo 39 días. Challenges II-2 (julio de 1998) se resolvió en 56 horas.

La rápida mejora de 96 días a 56 horas en tan solo un año demostró con qué rapidez las mejoras del hardware y una mejor coordinación podían acelerar los ataques por fuerza bruta.

En enero de 1999, Deep Crack de la EFF, combinado con distributed.net, rompió DES Challenge III en solo 22 horas y 15 minutos, y ganó un premio de $10,000 de RSA Security.

Esta demostración definitiva de que DES podía romperse en menos de 24 horas puso fin, en la práctica, a cualquier argumento a favor de la seguridad de DES. Poco después, NIST inició el proceso de selección de un reemplazo para DES, que se convertiría en AES.

Distributed.net organizó iniciativas de computación voluntaria en las que usuarios normales de Internet donaban tiempo de CPU para los desafíos de DES. En su momento de máxima participación, colaboraron cientos de miles de ordenadores.

Cada ordenador probaba una parte diferente del espacio de claves, bajo la coordinación de un servidor central. Esto abrió el camino al modelo de computación distribuida para el criptoanálisis, que todavía se utiliza hoy en desafíos como la ruptura de cifrados antiguos.

La búsqueda exhaustiva de claves funciona porque cada descifrado de DES es rápido (microsegundos en hardware) e independiente. No existe ninguna dependencia entre probar la clave N y la clave N+1, por lo que la búsqueda se paraleliza perfectamente entre cualquier número de máquinas.

Esta naturaleza perfectamente paralelizable significa que duplicar el hardware reduce exactamente a la mitad el tiempo. Añadir más máquinas proporciona una aceleración lineal, lo que hace que los costes sean favorables para los adversarios.

Eli Biham y Adi Shamir publicaron el criptoanálisis diferencial en 1990, una técnica que aprovecha cómo se propagan las diferencias entre pares de entradas a través de las rondas del cifrado. Para DES, requiere teóricamente 2^47 textos en claro elegidos.

Posteriormente se reveló que las cajas S de DES se habían diseñado teniendo en cuenta la resistencia al criptoanálisis diferencial, lo que sugiere que la NSA conocía esta técnica en la década de 1970. El ataque es impresionante desde el punto de vista teórico, pero en la práctica queda superado por la fuerza bruta mediante hardware.

Mitsuru Matsui publicó el criptoanálisis lineal en 1993, un ataque que requiere 2^43 textos en claro conocidos para atacar DES. Implementó el ataque y logró romper DES experimentalmente en 1994, confirmando el análisis teórico.

El criptoanálisis lineal encuentra aproximaciones lineales al comportamiento de las cajas S y las utiliza para recuperar bits de la clave mediante un sesgo estadístico. En teoría, requiere muchos menos datos que la fuerza bruta, pero resultaba impráctico antes de los ataques con hardware.

El criptoanálisis diferencial se publicó en 1990, pero requiere textos en claro elegidos, algo poco práctico en la mayoría de las situaciones reales. El criptoanálisis lineal se publicó en 1993 y funciona con textos en claro conocidos, pero requiere 2^43 de ellos.

La fuerza bruta mediante hardware (Deep Crack) rompió DES en 22 horas en 1999. En la práctica, el ataque con hardware fue más devastador que los avances teóricos del criptoanálisis, porque no requería ningún par especial de texto en claro y texto cifrado.

La ruptura pública y documentada de DES tuvo consecuencias inmediatas para las políticas de seguridad. NIST inició el proceso del concurso AES en 1997, el mismo año en que tuvo éxito el Desafío DES I. El concurso se diseñó explícitamente para evitar las debilidades del proceso de estandarización de DES.

Los bancos y las agencias gubernamentales comenzaron a migrar a 3DES como medida provisional mientras se desarrollaba AES. La cronología de la ruptura de DES determinó directamente la urgencia y el calendario del esfuerzo de adopción de AES.

Ponga a prueba su comprensión de la historia de la ruptura de DES.

El tiempo necesario para romper DES se redujo progresivamente: 96 días en 1997, 56 horas en 1998 y 22 horas en 1999. Deep Crack, de la EFF, utilizó ASIC diseñados a medida para probar 90 mil millones de claves por segundo.

Tanto el criptoanálisis diferencial (2^47 textos en claro elegidos) como el criptoanálisis lineal (2^43 textos en claro conocidos) también rompen DES en teoría, pero la fuerza bruta mediante hardware fue el factor decisivo en la práctica. La ruptura en 22 horas acabó con la utilidad de DES como cifrado viable.