💻 computer science

Renting the Cracking Machine with a Cost-and-Time Analysis of Exhaustive DES-56 Key Search in the Cloud

Este artículo demuestra que, si bien una búsqueda exhaustiva completa del espacio de claves de 56 bits de DES utilizando instancias de AWS EC2 convencionales costaría aproximadamente 1,2 millones de dólares y tomaría unos 21 años con una flota modesta, la búsqueda es prácticamente factible para atacantes bien financiados que puedan intercambiar dinero por tiempo para completarla en tan solo un día, mientras que los ataques de subespacio más pequeños pueden ejecutarse por un costo insignificante.

Autores originales: Gonzalo Sharif Curi Martínez, Rodrigo Ramele

Publicado 2026-07-28✓ Author reviewed ⓘ

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Gonzalo Sharif Curi Martínez, Rodrigo Ramele

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina el mundo de las cerraduras y llaves digitales, donde los mensajes secretos se codifican para que solo el destinatario previsto pueda leerlos. Durante décadas, una cerradura específica, llamada el Estándar de Cifrado de Datos (DES), fue el estándar de oro para mantener los secretos seguros. Piensa en el DES como un enorme candado de combinación con un dial que tiene 56 números. Para romperlo, un ladrón tendría que probar cada una de las posibles combinaciones hasta que el candado hiciera clic y se abriera. Debido a que los números son tan altos, alguna vez se pensó que solo una supercomputadora o una máquina masiva y construida a medida podrían probarlos todos lo suficientemente rápido. Pero el mundo ha cambiado. Hoy tenemos "la nube", que es como alquilar un gigante ejército invisible de computadoras por minuto en lugar de comprar la tuya propia. La gran pregunta que los investigadores se han estado haciendo es: si solo quieres romper esta vieja cerradura, ¿cuánto cuesta alquilar ese ejército y cuánto tiempo tendrás que esperar? Es una pregunta que importa porque si el costo es bajo y el tiempo es corto, entonces la vieja cerradura ya no es segura, y necesitamos saber exactamente qué tan vulnerables son realmente nuestros viejos secretos.

Este artículo es como un experimento audaz donde dos investigadores, Gonzalo y Rodrigo, decidieron encontrar la respuesta rompiendo la cerradura DES alquilando de hecho un ejército en la nube. No construyeron una máquina especial; simplemente utilizaron computadoras estándar disponibles para cualquiera con una tarjeta de crédito en la nube AWS de Amazon. Establecieron un equipo de 37 de estas computadoras para trabajar juntas, cada una revisando una parte diferente de las enormes combinaciones de números. Trataron el trabajo como una gigantesca búsqueda del tesoro: escondieron un "tesoro" (una clave secreta) a diferentes distancias de la línea de salida y cronometraron cuánto tiempo tardó su ejército de computadoras en encontrarlo.

Los resultados fueron sorprendentemente rápidos y baratos para distancias pequeñas. Cuando el tesoro estaba escondido cerca (dentro de los primeros 100 millones de combinaciones), las computadoras pasaron la mayor parte del tiempo simplemente despertándose y preparándose para trabajar. En estos casos, todo el trabajo tomó unos dos minutos y costó menos de 50 centavos. Fue como pagarle a un taxista unos pocos dólares para que te lleve a la tienda de la esquina; el viaje en sí fue instantáneo, pero el tiempo se pasó principalmente esperando a que llegara el conductor.

Sin embargo, a medida que escondían el tesoro más lejos, la historia cambiaba. Cuando empujaron la búsqueda hasta los 15 mil millones de combinaciones, el tiempo dedicado a buscar realmente la clave se convirtió en el factor principal. Las computadoras trabajaron de manera constante, encontrando la clave en unos 87 minutos por un costo de aproximadamente $18. Los investigadores descubrieron que las computadoras eran increíblemente eficientes, revisando casi 3 millones de combinaciones por segundo en una sola máquina. Cuando sumas las 37 máquinas, estaban revisando más de 100 millones de claves cada segundo.

La parte más emocionante de su descubrimiento es lo que sucede si realmente quieres romper la cerradura completa, no solo una pequeña parte de ella. La cerradura completa tiene alrededor de 72 cuatrillones de combinaciones posibles. Con su configuración actual de 37 computadoras, les tomaría unos 21 años revisar cada una de ellas. Eso suena imposible, pero los investigadores demostraron que, debido a que el trabajo es tan fácil de dividir, puedes intercambiar dinero por tiempo. Si tuvieras un bolsillo muy profundo y alquilaras una flota masiva de unas 140,000 computadoras, podrías romper la cerradura completa en tan solo un día. El costo total para ese esfuerzo masivo sería de alrededor de $1.2 millones.

Entonces, ¿qué significa esto? El artículo demuestra que la vieja cerradura DES está efectivamente rota. Si un malvado tiene una pequeña cantidad de dinero, puede romper una parte específica y limitada del código por el precio de una taza de café. Si tiene mucho dinero, puede romper todo el código en un solo día. Los investigadores también señalaron que, aunque su enfoque basado en computadoras fue rápido, el uso de tarjetas gráficas modernas (las que se usan para videojuegos) podría hacer esto aún más barato y rápido, reduciendo potencialmente el tiempo y el costo otras cien veces. La conclusión es clara: la cerradura de 56 bits ya no es una barrera; es solo una cuestión de cuánto efectivo estés dispuesto a gastar para romperla.

Resumen Técnico: Alquiler de la Máquina de Descifrado con un Análisis de Costo y Tiempo de la Búsqueda Exhaustiva de Claves DES-56 en la Nube

Planteamiento del Problema
El Estándar de Cifrado de Datos (DES), con su longitud de clave efectiva de 56 bits ( $2^{56} \approx 7.2 \times 10^{16}$ claves), ha sido criptográficamente vulnerado desde 1998. Si bien investigaciones previas han demostrado la viabilidad de romper DES utilizando hardware dedicado (ASICs, FPGAs) y optimizaciones algorítmicas, existe una falta de datos recientes, concretos y reproducibles respecto al costo y el tiempo requeridos para realizar una búsqueda exhaustiva de claves utilizando infraestructura de nube moderna y de uso común (commodity). La pregunta central abordada es: ¿Qué tan costoso y qué tan rápido es un ataque de fuerza bruta de DES cuando se ejecuta en un clúster de nube alquilado, donde el atacante paga solo por los segundos de tiempo de cómputo utilizados?

Metodología
Los autores implementaron un sistema de fuerza bruta distribuido en Amazon Web Services (AWS) para medir empíricamente el rendimiento y el costo de una búsqueda de claves DES.

Arquitectura del Sistema: El sistema utiliza un coordinador (Python) y 37 nodos de trabajo (instancias AWS EC2 c6i.2xlarge, cada una con 8 vCPUs). El espacio de claves de 56 bits se particiona en 37 rangos disjuntos. El coordinador lanza las instancias mediante scripts de user-data, distribuye los rangos de búsqueda y gestiona los resultados mediante Amazon SQS (Simple Queue Service) para el reporte de candidatos y Amazon S3 para la difusión de señales de parada.
Implementación de los Trabajadores: Los trabajadores están escritos en C con OpenMP para paralelizar la búsqueda en 8 vCPUs. La implementación incluye cuatro optimizaciones específicas para maximizar el rendimiento (throughput):
1. Tablas SP: Tablas precomputadas que combinan las sustituciones de las cajas S y la permutación P, las cuales caben enteramente en la caché L1.
2. LUT de indexación por bytes: Tablas de búsqueda para las permutaciones de bits (IP, IP⁻¹, PC-1, PC-2) para eliminar los bucles a nivel de bit.
3. Expansión de Desplazamiento de Bits Directa: Fusión de la función de expansión con la XOR de la subclave y el indexado de tablas para evitar la materialización de valores intermedios de 48 bits.
4. Rechazo Temprano (Modo COA): En el modo de Ataque de Solo Texto Cifrado (COA), el descifrado se detiene inmediatamente al encontrar un byte no imprimible. Esto rechaza aproximadamente el 99.96% de las claves aleatorias tras un solo bloque, reduciendo drásticamente el costo efectivo por clave.
Mecanismo de Puntuación: El sistema opera en modo de Ataque de Solo Texto Cifrado (COA), utilizando una puntuación de frecuencia de logaritmo basada en las frecuencias de unigramas del español para identificar texto plano significativo. Un umbral de $-4.0 \times \text{nbytes}$ separa los candidatos válidos del ruido aleatorio.
Diseño Experimental: Los autores realizaron 15 ensayos independientes divididos en dos grupos:
- Grupo A (Dominado por el arranque): 10 ensayos con desplazamientos de clave pequeños ( $10^6$ a $10^8$ ) para medir el impacto de la latencia de aprovisionamiento de las instancias de AWS.
- Grupo B (Dominado por la búsqueda): 5 ensayos con desplazamientos más grandes ( $10^9$ a $1.5 \times 10^{10}$ ) para medir el rendimiento de búsqueda bruto y el escalado lineal.

Resultos Clave

Rendimiento (Throughput): El sistema alcanzó un rendimiento agregado medido de aproximadamente 108 millones de claves por segundo (2.91 M de claves/s por instancia) a través de las 37 instancias. El ajuste lineal para el tiempo de búsqueda frente al desplazamiento arrojó un $R^2$ de 0.9994, confirmando un rendimiento constante.
Regímenes de Tiempo y Costo:
- Desplazamientos Pequeños ( $\le 10^8$ ): El tiempo total está dominado por la latencia de arranque de AWS (aproximadamente 90 segundos). El tiempo medio para estos ensayos fue de $116.8 \pm 20.1$ segundos, con un costo promedio de $0.41 por ataque.
- Desplazamientos Grandes: El tiempo de búsqueda se convierte en el factor dominante. Una clave en un desplazamiento de $1.5 \times 10^{10}$ requirió aproximadamente 87 minutos y costó $18.
- Extrapolación del Espacio de Claves Completo:
  - Al rendimiento medido, una sola flota de 37 instancias requeriría aproximadamente 21 años (caso de peor escenario) o 10.6 años (caso esperado) para agotar el espacio de claves completo de $2^{56}$ .
  - Sin embargo, debido a la naturaleza "vergonzosamente paralela" de la carga de trabajo, el tiempo puede intercambiarse por dinero de forma lineal. Los autores estiman que una búsqueda exhaustiva completa costaría aproximadamente $1.2 millones (caso esperado) o $2.3 millones (caso de peor escenario).
  - Con una flota lo suficientemente grande (por ejemplo, $\approx 1.4 \times 10^5$ instancias), la búsqueda completa podría completarse en un día con el mismo presupuesto estimado.

Significancia y Reivindicaciones
El artículo proporciona la primera respuesta empírica y reproducible sobre el costo y el tiempo de romper DES en infraestructura de nube de uso común. Los autores concluyen que:

Ataques de Subespacio Acotado: Para claves dentro de una fracción conocida y manejable del espacio de claves, el ataque es trivialmente barato (menos de $1) y rápido (minutos).
Exhaustión Total: Aunque es costoso, una búsqueda exhaustiva completa está "firmemente al alcance" de un atacante bien financiado utilizando únicamente recursos de uso común. Ya no es una barrera técnica, sino presupuestaria.
Cambio Económico: En comparación con el hardware dedicado histórico (por ejemplo, COPACOBANA en 2006), la computación en la nube ofrece una barrera de entrada drásticamente menor sin inversión de capital inicial.
Perspectiva Futura: Los autores señalan que su implementación basada en CPU no es la opción más rentable; sugieren que portar el sistema a GPUs (citando rendimientos potenciales de miles de millones de claves/s) podría reducir tanto el tiempo como el costo en uno o dos órdenes de magnitud.

El artículo afirma que DES no ofrece una seguridad significativa en la era moderna, ya que la combinación de capacidad elástica en la nube y procesamiento paralelo hace que el espacio de claves sea efectivamente rastreable para cualquier entidad con el financiamiento suficiente.

Más como este