Por Fernando Acero
Desde hace tiempo, estoy recibiendo correos de gente que me pregunta sobre la posibilidad de decodificar el archivo INSURANCE de Wikileaks, que presuntamente (el nombre lo pone) está codificado usando el algoritmo AES256. Al margen de las discusiones morales, prácticas y éticas, derivadas de decodificar a las bravas un archivo que presuntamente sirve para salvar la vida de alguien, nos podemos centrar en el estudio de la parte técnica de este asunto de la decodificación del AES, que todo hay que decirlo, es un asunto que me interesa mucho más...
De todos modos, ¿alguien se imagina lo que me pasaría si yo dijera en este momento: “Señores, durante una noche de insomnio y usando mi batería de tarjetas NVIDIA, he logrado decodificar el archivo INSURANCE de Wikileaks”?. Puede que en la puerta de mi casa encontrase tantos agentes secretos vigilando mis movimientos y tanta gente atacando mis sistemas informáticos, como periodistas en la final del mundial de fútbol y eso no me apetece en absoluto ¿y a ustedes?.
El ALGORITMO AES
El algoritmo AES (Advanced Encryption Satandard), también conocido como Rijndael, es un sistema de cifrado por bloques simétrico, pensado para sustituir al obsoleto DES y optimizado para las transmisiones seguras de mensajes a través de las redes de telecomunicaciones. AES es muy rápido, tanto en las implementaciones de software, como en las de hardware y además de ser relativamente fácil de implementar, requiere poca memoria para realizar los cálculos. Como nuevo estándar de cifrado, se está utilizando a gran escala por todo el mundo, lo que le parece muy interesante a los amigos de asuntos conspiratorios. El AES/Rijdael, fue desarrollado por dos criptólogos Belgas, llamados Daemen y Rijmen, cuando eran estudiantes de la Universidad Católica de Leuven.
La principal diferencia entre el AES y el DES al que sustituye, es que el AES usa una red de sustitución-permutación (serie de sustituciones y permutaciones, que se suceden unas a otras sobre una matriz), en lugar de una red de Feistel. El AES utiliza un bloque de tamaño fijo de 128 bits (originalmente podía usar bloques de varios tamaños) y las claves pueden ser de 128, 192 y 256 bits. Al igual que el DES, el procedimiento de codificación se basa en una operación básica llamada "ronda", que se repite un número fijo de de veces dependiendo del tamaño de la clave. Así, con las claves de 128 bits, se usan 10 rondas, 12 rondas con las de 192 bits y 14 rondas, para las claves de 256 bits. AES trabaja sobre una estructura conocida como el "estado AES", que es simplemente una reordenación del bloque básico, usando una matriz de 4×4 y por lo tanto, es un sistema que tiene una descripción matemática bastante simple, aunque para la mayoría de los comunes mortales, es más sencillo verlo como operaciones con bytes en una matriz de datos.
Los bloques básicos del AES son:
- SubBytes - Una sustitución no lineal en el estado AES.
- ShiftRows - Realiza un desplazamiento sobre las filas del estado AES.
- MixColumn - Mezcla columnas del estado de AES, haciendo cada celda una combinación de otras celdas.
- AddRoundKey - Mezcla la clave con el estado AES.
Una codificación AES consiste en la realización de los siguientes pasos sencillos:
1. Ronda Inicial:
- AddRoundKey
2. R-1 Rondas:
- SubBytes
- ShiftRows
- MixColumns
- AddRoundKey
3. Ronda final
- SubBytes
- ShiftRows
- AddRoundKey
El proceso de decodificación sin embargo, es más complicado que con el DES, en el que simplemente había que volver a “codificar” un mensaje ya “codificado”, usando por supuesto, la misma clave. En el caso del AES, es necesario definir las operaciones inversas para ShiftRows, SubBytes y MixColumns. Hay que señalar, que para la operación AddRoundKey no se requiere una inversa, puesto que basta con aplicarla otra vez con la misma clave, para obtener su inversa.
SEGURIDAD REAL DEL AES
Se dice que un sistema criptográfico está roto cuando existe algún ataque más rápido que una búsqueda exhaustiva (ataque por fuerza bruta), aunque este ataque sea solamente teórico, y no sea viable por la cantidad de datos, tiempo, o memoria necesaria.
Algunas personas han dicho que el AES está roto por los resultados obtenidos con una clave de 64 bits, que fue llevado a cabo por distributed.net, pero la realidad es que solamente fue un ataque por fuerza bruta de una clave muy pequeña de 64 bits, por lo que no lo podemos considerar como una ruptura del AES.
De hecho, el AES, a pesar de ser un algoritmo público y de uso público, está considerado como la NSA (Agencia de Seguridad Nacional de los EEUU) desde el año 2003, como algoritmo seguro para proteger información clasificada de nivel SECRETO usando claves de 128 bits y de ALTO SECRETO, si se usan claves de 192 o 256 bits. No deja de sorprender, teniendo en cuenta el amor-odio del Gobierno de los Estados Unidos con los sistemas de cifrado, que el gran público pueda tener acceso a un sistema de cifrado considerado apto por la NSA, para proteger información sensible del más alto nivel, lo que no deja de levantar muchas suspicacias.
LOS ATAQUES POSIBLES
La forma más asequible de ver si es posible realizar un ataque a un codificador de bloques, es intentar atacarlo mediante la reducción del número de rondas utilizadas en la codificación. Si recordamos, el AES usa 10 rondas para las claves de 128 bits, 12 rondas para claves de 192 bits, y 14 rondas para claves de 256 bits. Hasta el año 2005, los mejores ataques conocidos tuvieron éxito sobre versiones reducidas a 7 rondas para claves de 128 bits, de 8 rondas para las claves de 192 bits, y de 9 rondas, para las claves de 256 bits.
Sin embargo, también es cierto que en estos ataques se evidencia una escasa diferencia entre las rondas reales y las de los mejores ataques conocidos, por lo que con una pequeña mejora en los ataques, cabría la posibilidad de romper un cifrado que use todas las rondas. Está claro, la mejor vacuna para el problema, sería aumentar el número de rondas sin cambiar el algoritmo. Sin embargo, esta solución también tendría un impacto en la eficiencia del algoritmo y sobre todo, en la actualización de los sistemas basados en hardware. Hay que señalar, que se conocen algunos ataques exitosos sobre determinadas implementaciones del AES, que se basan en el canal auxiliar, pero estos ataques no atacan al algoritmo en sí mismo, sino a una implementación específica del mismo, por lo que tampoco son aplicables a la decodifcación del archivo de Wikeleaks.
En esta línea de investigación, en el año 2009, Alex Biryukov y Dmitri Khovratovich, de la Universidad de Luxemburgo, publicaron este interesante artículo, con dos ataques contra el algoritmo de cifrado AES, que mejoran de forma impresionante los resultados anteriores. Biryukov y Khovratovich anunciaron un ataque contra AES de 256 completo, es decir, con sus 14 rondas. El ataque tiene una complejidad computacional de solamente 2^96 operaciones, es decir, romper la seguridad de un AES256/14 sería tan difícil como probar 2^96 claves. No cabe la menor duda de que está fuera del alcance de la mayoría de los mortales, pero ver un algoritmo de 256 bits con una fortaleza equivalente a la de uno de solamente 96 bits, no dice mucho a favor del algoritmo. Pero tranquilidad, que esta afirmación tiene trampa, solamente funciona con determinadas claves “podridas”, es decir, con una clave de cada 34.000 millones. ¿Habrá usado Wikileaks una de esas claves podridas de forma voluntaria o involuntaria?. Sin duda es una buena pregunta, ya que no sabemos exactamente lo que pretende Wikileaks con este archivo, si que no lo abra nadie, o que solamente lo abran los que están “retratados” en él, para darles miedo.
Sin embargo, el otro ataque de Biryukov y Khovratovich, aunque es menos “efectivo” que el anterior, funciona con cualquier clave y demuestra otros datos preocupantes sobre el AES. El ataque contra el AES-128/10, tendría una complejidad matemática de 2^123 datos (claves), 2^176 en tiempo y de 2^152 en memoria, así que aunque curioso, esto no es nada preocupante por el momento. Sin embargo, el ataque contra el AES-256/14 es mucho más efectivo, ya que solamente se necesitan 2^119 en datos y tiempo y 2^77 en memoria. Dicho de otro modo, el AES-256 tiene la misma fortaleza que un teórico AES-119/14, por debajo del AES-123/10 que se obtendría con el ataque a un AES-128/10 y esto, con independencia de la clave que usemos. Es evidente que esto sigue estando fuera del alcance de cómputo de la mayoría de los mortales, pero ¿lo está del alcance de una superpotencia?, sobre todo, si tenemos en cuenta además, que los autores dicen que pueden mejorar el ataque al AES-256/14 a una complejidad de solamente 2^110,5?. Dicho esto, aunque la NSA dijo que el AES-128/10 era seguro para los SECRETOS y el AES-192/12 y el AES-256/14 para los ALTOS SECRETOS, lo cierto es que visto lo anterior, el AES-128/10 es más seguro que el AES-256/14 en igualdad de condiciones.
Pero si lo anterior no nos preocupa demasiado, hay otro interesante artículo, fechado el 19 de agosto de 2009, y firmado por unos reputados Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, y Adi Shamir. En este articulo comentan algo mucho más preocupante sobre el AES-256, ya que lograron ataques contra el AES-256/9 con una complejidad matemática de solamente 2^39 operaciones, contra el AES-256/10 con una complejidad de solamente 2^45 y consideran que el AES-246/11, podría tener una complejidad de solamente 2^70, valores todos ellos, muy por debajo de los logrados por Biryukov Khovratovich.
Está claro, no se está hablando del AES-256/14, pero es evidente, que hay un problema y grave con el AES-256, aunque solamente hayan llegado a las 10 rondas y especulado un poco sobre las 11 rondas. De nuevo me pregunto ¿está esto fuera del alcance de la NSA con todos sus medios técnicos y sus miles de matemáticos en plantilla?.
Bueno, para ser justos, hay otra trampa en el plantemiento de Shamir y sus amigos, estos ataques no son prácticos con el archivo de Wikileaks, pero solamente desde nuestro lado, ya que el que el que tiene los mensajes en claro (aunque no sepa exactamente los que son). Es decir, el Gobierno de los EEUU, lo tiene complicado, pero no tanto como nosotros, que no tenemos nada para empezar a trabajar. Los ataques anteriores se denominan de “claves relacionadas”, es decir, que se supone que el criptoanalista dispone de acceso a una serie de textos en claro, que han sido codificados mediante varias claves distintas, las cuales, tienen una relación específica entre ellas.
Parece demostrado en el caso del AES, que a mayor tamaño de la clave, menor es la dificultad para romperla. Algo que puede significar que no se eligió un número de rondas adecuado para el tamaño de cada clave, puede que por un compromiso entre la seguridad y la velocidad, pero que al final, ha comprometido la seguridad las versiones de AES 192/12 y 256/14. Los dos “paper” que hemos revisado anteriormente dicen lo mismo con distintas palabras, en este momento, es más seguro el AES-128/10 que el AES-256/14 y en términos estrictos lo podemos considerar roto, desde los primeros resultados de Biryukov y Khovratovich, ya que su fortaleza en ciertas condiciones es inferior a la de un ataque por fuerza bruta.
Teniendo en cuenta que Bruce Shneier ya recomendaba en su blog el día 30 de julio de 2009, que se usase AES-128/10 en lugar de AES-256/14, es curioso y no menos inquietante, que los responsables de Wikileaks, tan preocupados por la seguridad como están, hayan decidido proteger su archivo “salvavidas” con un roto AES-256.
Si me hubieran preguntado, si buscase la seguridad absoluta de que el archivo no sería abierto en un tiempo razonable y mi vida fuera en ello, yo no hubiera optado por el AES-256/14 ni por asomo, que hablando claro, en este momento, lo podemos considerar seguro, aunque menos seguro que el DES que pretende sustituir.
"Copyleft 2010 Fernando Acero Martín. Verbatim copying, translation and distribution of this entire article is permitted in any digital medium, provided this notice is preserved. Quotation is allowed."
