AES: otros ataques

24 Abril 2014
Published in Research

Es claro que hasta este momento, ninguno de los ataques realizado a full-AES ha tenido éxito, los ataques usualmente se concentran en la reducción de rondas. Muchos autores afirman que ninguno de los siguientes tipos de ataques, han podido ser más efectivos que una búsqueda exhaustiva de clave:

  • Criptoanálisis lineal
  • Criptoanálisis diferencial
  • Truncated diferencials
  • Interpolation attacks
  • Square attack

Sin embargo, la estructura ordenada y las profundas bases matemáticas que utiliza, lo hacen un objeto de estudio para nuevas propuestas de ataques, como lo son los ataques algebraicos. Dichos ataques consisten en plantear un sistema de ecuaciones y con las incógnitas de dicho sistema deducir la clave; una de las ventajas que presenta este tipo de ataque, es la poca cantidad de textos conocidos que se necesitan.

En 2002 Asiacrypt hace una publicación de Nicolas Courtois y Josef Pieprzyk [1] donde proponen un modelo teórico de AES, en el que aseguran se caracteriza como un sistema de ecuaciones cuadráticas, dicho sistema consta de 8000 ecuaciones con 1600 variables binarias, sin embargo, dicho ataque falló tratando de romper AES, como menciona el mismo Courtois en [2]. Además, varios expertos en criptografía han comentado que hay problemas en las matemáticas detrás de dicho ataque, probablemente los autores hayan cometido algún error, a pesar de esto, teniendo en cuenta la forma ordenada y la completa estructura matemática de AES, es posible que este tipo de criptoanálisis pueda llegar a ser uno de los más potentes para romper AES.

Otras publicaciones conocidas son:

  1. Impossible Differentials Attack: existe un ataque de este tipo a 5 rondas de AES, requiriendo 229 plaintext elegidos, 230 encripciones, 242 bytes de memoria, 226 pasos de precálculo. Estas condiciones fueron mejoradas en [3] y [4] para alcanzar un ataque a 6 rondas de AES.
  2. Square Attack: es un ataque dirigido a un algoritmo del tipo de Rijndael que basa su diseño en estructuras de bytes. Precisamente el primer ataque de este tipo fue hecho al algoritmo predecesor llamado “Square”. Este ataque puede romper a Rijndael de 6 a 7 rondas, que puede ser mejorado para atacar a 9 rondas de AES-256 con 277 plaintexts, con 256 claves relacionadas, y 2224 encripciones [5].
  3. Collision Attack: trata de encontrar dos entradas que producen el mismo valor hash, es decir, una colisión de hash. Este ataque afecta a todas las versiones de AES, 128, 192 y 256 con 7 rondas [6].

 

Referencias

  1. Nicolas C & Josef P. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations. ASIACRYPT '02 Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology (2002), pp. 267-287.
  2. http://www.cryptosystem.net/aes/
  3. J H C, M K, K K, J L & S K. Improved Impossible Differential Cryptanalysis of Rijndael and Crypton. ICISC (2001) LNCS 2288: pp. 39-49.
  4. Raphael CP & M U S. Generalised impossible differentials of advanced encryption standard. IEE Electronics Letters (2001) Vol. 37, Issue 14: pp. 896-898.
  5. N F, J K, S L, B S, M S, D W, D W & D W. Improved cryptanalysis of Rijndael. FSE 00, LNCS 1978, pp. 213-230.
  6. H G & M M. A collision Attack on 7 rounds of Rijndael. AES3papers, pp. 2-11.

Como se ha mencionado en un artículo anterior, las rondas que componen el algoritmo AES se pueden dividir en tres categorías diferentes: rondas inicial, ronda estándar y ronda final. A la hora del cifrado, la información es sometida a una cantidad diferente de rondas (10, 12 y 14 respectivamente) en cada caso en función de la longitud de la clave (128, 192 y 256 bits respectivamente). Cada una de dichas rondas se compone de combinaciones de transformaciones, las posibles transformaciones son: ByteSub, ShiftRow, MixColumns y AddRoundKey. La Figura # 1 muestra la relación de las transformaciones y las correspondientes rondas.

 

Figura # 1: Distribución de las transformaciones en cada ronda.

Hace algún tiempo leí un artículo interesante de un “ataque exitoso” contra AES, el famoso algoritmo de criptografía simétrica. Raphael C.-W. Phan [1] presentó un “impossible differential attack” a 7 rondas para AES-192 y AES-256. Algunos se preguntarán: que tipo de ataque es este?, pues bien, es un criptoanálisis que se aprovecha de las diferencias que son imposible de darse, de un bloque de datos a través del cifrado, con la finalidad de descubrir la clave. Sin entrar en muchos detalles del método utilizado, a continuación comento algunos de los resultados más importantes de dicho estudio.

El ataque consiste en tomar parejas de textos idénticos en todos los bytes excepto en uno y comenzar a cifrar dichos textos, luego, se analizan los datos producidos a las salidas de cada una de las rondas con la finalidad de observar la evolución de la información durante el proceso de cifrado. Con esta información se van asignando las probabilidades para las claves imposibles o de probabilidad de 0.

El ataque se basa en el algoritmo expuesto en [1], que es utilizado para romper AES-192 y AES-256, consta de 9 pasos a seguir y se concentra en el sistema de expansión de claves. El algoritmo permite realizar ciertos cálculos y asignar probabilidades en el momento que se ha determinado alguna de las subclaves. En resumen, el autor espera determinar la clave en la séptima ronda, con el modelo matemático expuesto en dicho estudio, mediante la observación de los movimientos realizados por las diferentes transformaciones.

Resumiendo los resultados obtenidos en [1], para el caso de AES-192, se requirió de 292 textos en claro, 2153 palabras de memoria y 2186 encripciones, para el caso de AES-256 los textos en claro fueron 292,5, el mismo espacio de memoria 2153 y 2250,5 encripciones. La Tabla # 1 muestra una comparación entre los resultados presentados por [1] y otros dos ataques anteriores con menor cantidad de rondas.

 

Tabla # 1: Comparación de los resultados a ataques a AES [1].

 

Dejando de lado el proceso como tal, y analizando los resultados obtenidos en dicho ataque, se puede apreciar que para romper el algoritmo se han necesitado 2186 y 2250,5 encripciones para AES-192 y AES-256 respectivamente. Si se toma en cuenta que una búsqueda exhaustiva de clave hubiera tomado 2192 y 2256 para cada uno de los algoritmos respectivamente, se podría decir que el ataque presentado por [1] ha sido exitoso.

Ahora, es importante aclarar que se trata de un ataque a rondas reducidas (7 rondas) y que AES puede tener una longitud de clave de 128, 192 o 256 bits según sea el caso, para la cantidad de rondas estándar: 10, 12 y 14 respectivamente. Esto significa, que pese al ataque exitoso que se presenta, AES mantiene un margen de seguridad bastante amplio con respecto a este estudio, porque hay 5 rondas de diferencia (para AES-192) y por lo tanto, la complejidad para descifrar un paquete de información se incrementa al aplicar la cantidad de vueltas que define el estándar.

 

Referencias

  1. Raphael CP. Impossible differential cryptanalysis of 7-round Advanced Encryption Standard (AES). Information Processing Letters (2004) 91: pp. 33-38.

En la I Parte de Generalidades de AES (Advanced Encryption Standard) se describieron los aspectos más relevantes de AES y las S-Box. Ahora, comentaremos algunos detalles de las llamadas transformaciones (ByteSub, ShiftRow, MixColumns y AddRoundKey) y el proceso de generación de subclaves. Para ver más detalles de una manera más dinámica se recomienda la aplicación Rijndael Animation.

 

ByteSub

Esta transformación realiza una sustitución byte por byte en cada uno de los elementos de la matriz de estado, es decir, la matriz de estado [aij] se sustituye por la matriz [Sij], la Figura # 1 muestra dicho proceso. Utilizando la aplicación Rijndael Animation de [1], se puede observar como el primer byte de la matriz de estado ([a00]) se divide en dos grupos de cuatro bits cada uno y se utilizan como apuntadores a filas y columnas de la S-Box, respectivamente, para realizar la sustitución, en la Figura # 1 se muestra como el valor 19 será reemplazado por d4.

 

Figura # 1: Utilización de S-Box [1].

Página 1 de 2