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

En 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
http://blog.s21sec.com/2009/10/rompamos-aes-128-yo-no-puedo-y-tu.html