.pl 10.0i .po 0 .ll 7.2i .lt 7.2i .nr LL 7.2i .nr LT 7.2i .ds LF Leech .ds RF [Pág. %] .ds LH RFC 3607 .ds RH Septiembre 2003 .ds CH El Criptoanálisis de la Lotería China .hy 0 .ad l .in 0 .nf Network Working Group M. Leech Request for Comments: 3607 Nortel Networks Categoría: Informativa Septiembre 2003 Traducción al castellano: Marzo 2004 Rubén Afonso Francos rafrancos@terra.es .fi .sp .sp .nf Reconsiderando el Criptoanálisis de la Lotería China: Internet como una herramienta para romper códigos .fi .sp Estado de este memorándum .sp .in 3 Este memorándum proporciona información para la comunidad Internet, no especifica ningún tipo de estándar de Internet, y su distribución es ilimitada. .sp .ti 0 Aviso de Copyright .sp Copyright (C) The Internet Society (2003). Todos los Derechos Reservados. .sp .ti 0 Resumen .sp .in 3 Este documento reconsidera el ataque criptográfico masivamente paralelo conocido como el ataque de la Lotería China, analiza las analogías existentes entre Internet y la Lotería China, y las consecuencias derivadas de dichas similitudes. .sp .ti 0 .sp 1. Introducción .sp En 1991, Quisquater y Desmedt [DESMEDT91] propusieron un ataque, algo esotérico pero con base teórica, contra DES y sistemas de cifrado similares. Ellos lo denominaron el ataque de La Lotería China. Estaba basado en el uso de hardware masivamente paralelo, utilizando equipos convencionales como hardware de criptoanálisis. .sp En la década que ha transcurrido desde que Quisquater y Desmedt propusieran la Lotería China como una idea, se han producido avances considerables en algunos campos que han hecho que valga la pena reconsiderar sus estudios. .sp En 1991, Internet tenía alrededor de 8 millones de máquinas conectadas y en 2002, la cifra es variable pero llega a los 100 millones. Desde que se redactó el documento de la Lotería China hasta nuestros días, la potencia de los ordenadores de mesa se ha multiplicado por 150, aproximadamente. .sp .ti 0 2. Sinergía Peligrosa .sp El crecimiento de Internet y el ritmo imparable de la Ley de Moore se han combinado creando un peligro potencial para los criptosistemas existentes: el criptoanálisis mediante fuerza bruta. .sp En los últimos años, muchos ataques a gran escala llevados a cabo por los denominados Gusanos de Internet [SPAFF91] han conseguido comprometer e infectar a un número sorprendentemente grande de ordenadores conectados a Internet. En el 2001, la organización Cooperative Association for Internet Data Analysis (Asociación Cooperativa para el Análisis de los Datos de Internet) [CAIDA2001] informó que el gusano Code Red v2 fue capaz de infectar alrededor de 350000 ordenadores en sus primeras 14 horas de operación. El Code Red modificaba la página web del servidor infectado con un mensaje de índole política; esto era algo muy llamativo e hizo que se le prestase atención casi de inmediato. .sp Imaginemos por un momento un gusano de Internet con un propósito más oscuro y peligroso: criptoanalizar, mediante fuerza bruta, un mensaje para conocer la clave utilizada para cifrarlo. Para que el gusano tenga éxito, deberá evitar la detección durante el tiempo necesario para poder alcanzar un nivel significativo de sistemas infectados y disponer así de suficientes ciclos de CPU que le permitan completar el criptoanálisis. Además, nuestro gusano también tendrá que evitar ser detectado durante el tiempo suficiente para que la clave hallada tenga alguna utilidad para el dueño del gusano. De hecho, estudios recientes [USEN2002] sobre gusanos sigilosos muestran un panorama bastante preocupante sobre ésta última característica. .sp Incluso después de que dicho gusano fuese detectado sería casi imposible conocer qué clave ha sido atacada. Un ataque realista usaría uno o dos fragmentos de texto cifrado, y algún fragmento de texto plano, o características probables de éste último. Con tan pocos datos es muy difícil determinar la víctima. .sp .ti 0 3. El ganador llama a casa .sp Cuando una determinada instancia del gusano obtiene la clave, necesita contactar con el atacante para poder transmitírsela, intentando siempre minimizar el riesgo de que éste sea descubierto. .sp Una técnica posible sería que el gusano cifrase la clave descubierta mediante un sistema de clave pública utilizando la clave pública de/los atacante/s y la almacenase escondida en la web del servidor infectado. El gusano también podría hacer copias de forma que los sitios web vecinos, topológicamente hablando, también poseyesen la clave. El archivo que contiene la clave podría ser identificado con alguna palabra única para que el atacante lo pudiese localizar utilizando los motores de búsqueda de Internet. El gusano podría hacer que este proceso fuese más eficiente utilizando los servicios de "registro de claves" que ofrecen algunos de estos motores. .sp Otro método podría ser publicar un mensaje (posiblemente cifrado con PGP) en varios grupos de noticias mediante un servicio anónimo de envío de noticias. .br De forma similar se podrían usar los servicios de "chat" de Internet, como el IRC; de hecho, cada vez es más frecuente ver como se utilizan éste último y servicios similares para controlar gusanos y virus de forma anónima y en tiempo real. .sp Cualquiera de estos métodos puede servir tanto para que la instancia "ganadora" del gusano envíe los resultados al atacante como para que éste envíe nuevos datos a la ingente tropa de sistemas infectados. .sp .ti 0 4. Valoración de la amenaza .sp Tanto el crecimiento de Internet como la evolución del rendimiento de las CPU's se duplican de forma medianamente predecible. La evolución de los procesadores parece seguir la Ley de Moore: su rendimiento se dobla cada 1.5 años, mientras que el tamaño de Internet, aparentemente, se duplica cada 3 años. .sp Relacionando el tiempo de crecimiento de Internet y el tiempo de evolución de los procesadores, podemos determinar matemáticamente el tiempo de ataque necesario para cualquier año dado. .sp Para simplificar asumiremos que es posible construir un gusano capaz de pasar desapercibido y que puede llegar a infectar aproximadamente al 0.5% de todos los ordenadores conectados a Internet. .sp En 1995, J. Touch, del ISI, publicó un análisis detallado del rendimiento del MD5 [RFC1810]. Por entonces, el rendimiento del MD5 implementado mediante software alcanzaba los 87 mbits/segundo, o lo que es lo mismo, 170.000 operaciones de bloques simples de MD5 por segundo. En el mismo año, el rendimiento máximo del DES estaba entorno a las 50.000 operaciones de clave/cifrado por segundo. .sp En 1995, Internet tenía alrededor de 20.000.000 de ordenadores conectados. En 2002, esta cifra varía alrededor de los 100.000.000. .sp En el apéndice A se adjunta un sencillo programa en C que se puede utilizar para predecir el rendimiento de nuestro hipotético gusano en cualquier año dado. Si probamos con el año 2002 obtenemos: .sp .in 7 .nf Año de la estimación: 2002 Para un número total de anfitriones infectados de 503968 Rendimiento asociado: MD5 9.79e+11/seg DES 2.88e+11/seg DES podría romperse en 1.45 días aproximadamente. DES con una contraseña de 8 caracteres podría romperse en 16.29 minutos aproximadamente. MD5 con una clave de 64 bits podría romperse es 218.04 días aproximadamente. MD5 con una contraseña de 8 caracteres podría romperse en 4.79 minutos aproximadamente. .fi .sp .in 3 Los números obtenidos sugieren que un ataque no detectado contra el MD5, para una longitud razonable de clave, es improbable en el 2002. Sin embargo, en la misma fecha se podría lograr casi con certeza un ataque satisfactorio contra DES. .sp .ti 0 5. Consideraciones de seguridad .sp DES ha demostrado ser débil en el pasado reciente. El éxito de la máquina de EFF, descrito en [EFF98] muestra como un hardware masivamente paralelo puede tener éxito sin demasiado esfuerzo. Además ha dejado de manifiesto que tal nivel de análisis mediante fuerza bruta puede conseguirse sin recurrir a componentes electrónicos especializados. Es obvio que DES debe ser abandonado en favor de 3DES o bien del nuevo AES [FIPS197]. .sp El panorama que nos presenta MD5 (cuando se usa en construcciones simples de MAC) parece mucho más esperanzador. Si se utilizan en mensajes cortos, las claves largas de MD5 están a salvo, computacionalmente hablando, así que si se usa MD5 parece razonable utilizar las claves más largas posibles dentro de los límites prácticos. .sp Los sistemas operativos se están volviendo cada vez más complejos y los ataques perpetrados por los gusanos, virus, troyanos y demás programas maliciosos, cada vez más sofisticados. Aunque sus intenciones han sido principalmente el vandalismo a gran escala, sus métodos podrían centrarse en actividades más específicas, y tal vez, más siniestras. .sp Hasta Febrero del 2003, al menos un gusano, conocido como W32/Opaserv.A, ha sido diseñado para realizar un ataque distribuído mediante fuerza bruta contra DES. .sp .sp .sp .sp .sp .sp .ti 0 6. Agradecimientos .in 3 John Morris, de Nortel IS, aportó la idea de escribir de forma anónima en un grupo de noticias. .sp .ti 0 Apéndice A: Código Fuente. .sp .nf /* * Este programa calcula el desarrollo de un hipotético * gusano que realizase el ataque de la * Lotería China, basándose en la fecha actual, * estimaciones de la tasa de crecimiento de Internet y la * Ley de Moore. * */ #include #include /* * EPOCH for the calculations */ #define EPOCH 1995.0 /* * Tamaño de Internet (en 1995) */ #define INTERNET_SIZE 20000000.0 /* * Rendimiento del software MD5 (en 1995) */ #define MD5PERF 170000.0 /* * Rendimiento del software DES (en 1995) */ #define DESPERF 50000.0 main (argc, argv) int argc; char **argv; { double yeardiff; double cryptoperf, multiplier; double cracktime; yeardiff = (double)atoi(argv[1]) - EPOCH; /* * El intervalo de duplicación estimado por la Ley de Moore * es de 1.5 años. */ cryptoperf = yeardiff / 1.5; cryptoperf = pow(2.0, cryptoperf); /* * Algo aproximado -- no todos los ordenadores infectados serán los más rápidos. */ cryptoperf *= 0.450; /* * El tamaño de Internet se duplica cada 3 años */ multiplier = yeardiff / 3.0; multiplier = pow(2.0, multiplier); multiplier *= (INTERNET_SIZE*0.0050); fprintf (stderr, "Año de la estimación: %d\n", atoi(argv[1])); fprintf (stdout, "Para un total de ordenadores infectados igual a %d\n", (int)multiplier); fprintf (stdout, "Rendimiento adicional MD5 %5.2e/seg DES %5.2e/sec\n", MD5PERF*cryptoperf*multiplier, DESPERF*cryptoperf*multiplier); cracktime = pow(2.0, 55.0); cracktime /= (DESPERF*cryptoperf*multiplier); fprintf (stdout, "DES podría romperse en %3.2lf días\n", cracktime/86400.0); cracktime = pow(2.0, 8.0*6.0); cracktime /= (DESPERF*cryptoperf*multiplier); fprintf (stdout, "DES con contraseñas de 8 caracteres podría romperse en %3.2lf minutos\n",cracktime/60); cracktime = pow(2.0, 64.0); cracktime /= (MD5PERF*cryptoperf*multiplier); fprintf (stdout, "MD5 con claves de 64 bits podría romperse en %3.2lf días\n", cracktime/86400.0); cracktime = pow(2.0, 8.0*6.0); cracktime /= (MD5PERF*cryptoperf*multiplier); fprintf (stdout, "MD5 con contraseñas de 8 caracteres podría romperse en %3.2lf minutos\n", cracktime/60); } .fi .sp .bp .ti 0 Referencias de la Normativa .sp .nf [DESMEDT91] "Chinese Lotto as an Exhaustive Code-Breaking Machine". J. Quisquater, Y. Desmedt, Computer, v. 24, n. 11, Nov 1991, pp. 14-22. [RFC1810] Touch, J., "Report on MD5 Performance", RFC 1810, Junio 1995. [EFF98] "Cracking DES: Secrets of Encryption Research, Wiretap Politics & Chip Design", Electronic Frontier Foundation, 1998. [CAIDA2001] "CAIDA Analysis of Code Red" http://www.caida.org/analysis/security/code-red/ [SPAFF91] "The Internet Worm Program: An Analysis", Eugene Spafford, 1991. [FIPS197] "Advanced Encryption Standard", US FIPS197, Noviembre, 2001. [USEN2002] "How to 0wn the Internet in Your Spare Time", Proc. 11th Usenix Security Symposium, 2002. .sp .fi .sp .ti 0 Dirección del autor .sp .in 3 Marcus D. Leech Nortel Networks P. O. Box 3511, Station C Ottawa, ON Canada, K1Y 4H7 .sp Teléfono: +1 613-763-9145 Correo electrónico: mleech@nortelnetworks.com .bp .sp 6 .ti 0 Declaración completa de Copyright .sp Copyright (C), The Internet Society (2003). Todos los Derechos Reservados .sp Este documento y sus traducciones pueden ser copiadas y distribuídas a otros, y los documentos derivados que comenten, expliquen o ayuden en su implementación deben ser preparados, copiados, publicados y distribuídos, en su totalidad o en parte, sin restricciones de ningún tipo, asegurándose de que la noticia sobre copyright anteriormente citada y este párrafo son incluídos en dichas copias y documentos derivados. Sin embargo, este documento no debe ser modificado de ninguna manera, como puede ser eliminando la noticia de copyright de arriba o las referencias a la Internet Society u otras organizaciones de Internet, a excepción de lo que sea necesario para el desarrollo de los estándares de Internet, caso en el cual se seguirán los procedimientos de copyright definidos en el proceso de los Estándares de Internet, o de lo necesario para traducir este documento a otros lenguajes distintos del inglés. .sp Los permisos limitados aquí citados son perpetuos y no serán revocados por Internet Society o por sus sucesores o asignados. .sp Este documento y la información contenida en él se proporcionan "TAL CUAL", y LA SOCIEDAD INTERNET Y EL GRUPO DE TRABAJO DE INGENIERÍA DE INTERNET NIEGAN TODA GARANTÍA, EXPLÍCITA O IMPLÍCITA, INCLUYENDO, PERO NO LIMITÁNDOSE A, CUALQUIER GARANTÍA DE QUE EL USO DE ESTA INFORMACIÓN NO INFRINGIRÁ NINGÚN DERECHO O GARANTÍA IMPLÍCITA DE MERCANTIBILIDAD O USO PARA ALGÚN PROPÓSITO EN PARTICULAR. .sp .ti 0 Reconocimiento .sp En la actualidad, el soporte para la función del editor de RFCs es proporcionado por la Internet Society (Sociedad Internet).