Español | English
rss facebook linkedin Twitter

Rompamos AES-128. Yo no puedo ¿Y tu? ... Tampoco

En un comentario de un post anterior en el que se trataba de comparar el poder computacional de las grandes supercomputadores actuales con el poder de computación que se podría lograr con una botnet, se preguntaba sobre la posibilidad de romper una clave criptográfica AES de 128 bits con los recursos de una botnet. El tema es interesante, y en este post vamos a intentar tratar este asunto.

Lo primero de todo, deberíamos decir que, con la computación actual, romper la clave AES de 128 bits por fuerza bruta es inviable.

Vamos a simplificar el problema: para una clave de 128 bits de longitud tendríamos 2128 claves a comprobar; vamos a asumir que necesitamos un flop para comprobar si la clave es válida o no y vamos también a asumir que estamos en el peor caso posible, es decir, tenemos la mala suerte de que la clave válida es la última que comprobamos.

Echando unas cuentas rápidas y dadas las asunciones anteriores, si consideramos el roadrunner (el supercomputador más potente del mundo), la potencia pico de cómputo es algo menos de 1.5 petaflops, con lo cual necesitaríamos más de 74 billones de siglos. Como veis esto es algo inviable.

Compararlo con el tiempo que tardaría una botnet es complicado porque no se disponen de datos objetivos sobre la capacidad de cómputo de éstas. Lo podríamos comparar por ejemplo con el conjunto de la plataforma BOINC, dentro de la que hay proyectos como el SETI@HOME, MilkyWay@home, etc. Realmente, la forma de actuar de BOINC es similar a como funciona una botnet, aunque en el caso de BOINC los usuarios ceden voluntariamente sus recursos compuacionales al proyecto. Según su página web, toda la infraestructura tiene un poder de cómputo medio de más de 2.6 petaflops (más de un 80% que el mayor supercomputador del mundo!!) y por tanto necesitaríamos más de 41 billones de siglos. Por tanto, aunque uniéramos los dos, junto con todos los supercomputadores, seguiría siendo un tiempo demasiado grande como para planteárselo.

Normalmente, desde el punto de vista combinatorio, las claves de 128 bits son muy seguras, no así las de 64 bits. Por ejemplo, con las asunciones anteriores, se podría romper una clave de 64 bits (que no es poco) con una infraestructura como la de BOINC en menos de dos horas. Pero claro, hace falta tener una infraestructura de tal calibre a tu disposición lo cual no es muy habitual ... a no ser que te hagas con el control de una botnet muy, muy grande. Con la computación actual (si pensamos en modelos de computación cuántica la cosa cambia) y dejando aparte teorías de puertas traseras en los algoritmos de cifrado, la única forma de romper claves tan grandes es atacando el algoritmo de forma lateral, buscando colisiones, vulnerabilidades en la generación de claves, vulnerabilidades en la propia estructura matemática del algoritmo, en la generación de números pseudo-aleatorios, etc.

En el caso de AES, se considera un algoritmo seguro, de hecho, el AES -128 está aprobado por la Agencia de Seguridad Nacional Americana (NSA) para proteger documentos de seguridad nacional, no así para los documentos de seguridad crítica (top secret) para los que se requiere AES-256. Actualmente, se conocen ataques a la encriptación AES, pero lo que consiguen es reducir la complejidad de la búsqueda de la clave de forma que sea algo más eficiente que la búsqueda por fuerza bruta. Aún así, el orden de búsqueda es tan alto que es inviable descubrir la clave. Por ejemplo, el ataque XSL permite reducir la complejidad de la búsqueda para AES-128 a 2100 (con la arquitectura BOINC y las asunciones iniciales tardaríamos más de 17 millones de años en obtener la clave). Para claves AES-256 también hay ataques basados en colisiones locales ([1],[2]) que permiten reducir la búsqueda a un orden de 2119.

Como se puede ver, el cifrado AES de 128 bits o más es muy seguro (lo dice la NSA y también los creadores del algoritmo de ataque a AES-256). Pese a esto, no se puede descartar que en un futuro sí que se encuentre la forma de hacer posible romper el cifrado AES en un tiempo razonable.

Guzmán Santafé
S21sec labs

5 comentarios:

David dijo...

Muchas gracias Guzmán!Lo has explicado bastante claro.

Sobre lo que has comentado de no descartar que en un futuro se pueda romper el cifrado AES sólo hay que ver a sus antecesores como DES.

Anónimo dijo...

Buen post :)
Pero me surge una duda, entoncesssss ¿cómo es que las claves públicas RSA suelen ser de 512, 768, 1024, 2048, etc bits? ¿Son más vulneréibols a ataques no-por-fuerza-bruta?

S21sec labs dijo...

AES y RSA son dos sistemas criptográficos diferentes. AES es simétrico mientras que RSA es asimétrico (tenemos una clave pública y otra privada). El par de claves RSA se calcula a partir de dos números primos grandes (p y q) elegidos de forma aleatoria. El resultado de multiplicar p*q (al que se suele llamar n) forma parte (entre otras cosas) tanto de la clave pública como privada. La seguridad de RSA radica en la dificultad de factorizar números muy grandes (si somos capaces de factorizar n seremos capaces de obtener las calves RSA). El problema de factorización de números grándes es muy complejo, pero no es de orden exponencial (como lo es la fuerza bruta) sino que existen algoritmos que permiten obtener la factorización en un tiempo subexponencial respecto al número de bits. Por eso que aumentar un bit de la clave en RSA no es tan drástico como en AES [1] y por eso es necesario que las claves RSA tengan más bits que las AES. En 2005 se consiguió romper una clave RSA de 640 bits usando durante 5 meses un cluster de cómputo.

Guzmán

Anónimo dijo...

64 bit, no 640 bit

Cristian dijo...

Me parece genial la forma en la que explicas estos temas tan complejos. sigue para adelante!! Saludos desde argentina


(+34 902 222 521)


24 horas / 7 días a la semana



© Copyright S21sec 2013 - Todos los derechos reservados


login