Algoritmo de Rijndael

Algoritmo AES (Advanced Encryption Standard).

En el año 1997, el Instituto Nacional de Estándares y Tecnología de EEUU (NIST), inicia un proceso abierto para la selección de un nuevo algoritmo de cifrado, que sustituya al actual estándar de cifrado, criticado por especialistas e instituciones en seguridad. Este nuevo algoritmo debe ser útil no sólo para proteger la información del Gobierno EEUU, sino que también deberá responder al sector privado, y y de ser posible constituirse en un estandar por el resto de países, fundamentalmente los Europeos.

En Septiembre de 1997 se presentan los criterios de evaluación y requisitos mínimos que debían cumplir todos los algoritmos que optarán a ganar el concurso, entre ellos destacaban:
•    El algoritmo debe ser público.
•    Debe ser un algoritmo de cifrado en bloque simétrico.
•    La longitud de la clave debe ser como mínimo 128 bits.
•    Su diseño debe permitir aumentar la longitud de la clave según las necesidades.
•    Debe ser implementable tanto en HW como en SW

Los algoritmos que satisfagan los requisitos propuestos serán juzgados por los siguientes factores:
¦    Seguridad.
¦    Eficiencia computacional.
¦    Requisitos de memoria.
¦    Implementable en HW y SW.
¦    Simplicidad de diseño.
¦    Flexibilidad.

NIST, propuso que cualquier organización, institución o persona pudiera participar de forma activa en este concurso, ya fuera presentando algoritmos, o enviando informes o pruebas de cualquier tipo para poner en evidencia las características de cualquier de los algoritmos candidatos. La intención de este estándar es que sea robusto, por lo menos, hasta la mitad del presente siglo, o por lo menos hasta que se publiquen estudios criptoanaliticos o incluso posibles máquinas futuras de supercomputación, como la soñada computación cuántica, que debilite seriamente su seguridad.

Para el proceso de selección se llevaron a cabo varias rondas, con los siguientes resultados:

Primera Ronda. Agosto de 1998, acá se seleccionan quince propuestas. Los quince algoritmos analizados fueron:
•    CAST-256 [Entust Technologies, Inc. C.Adams]
•    CRYPTION. [Future Systems, Inc. Chae Hoon Lim]
•    DEAL. [L.Knudsen, R. Outerbridge]
•    DFC. [CNRS-Ecole Normale Superiere. S.Vaudenay]
•    E2.   [NTT Nipón   Telegraph   and  Telephone Corporation. M.Kanda].
•    FROG. [TecApro International S.A. (D. Georgoudis, Leroux, Chaves]
•    HPC. [R. Schoeppel]
•    LOKI97. [L.Brown, J.Pieprzyk, J.Seberry]
•    MAGENTA [Deutshe Telekom A.G. K, Huber]
•    MARS. [IBM. Nevenki Zunic]
•    RC6. [RSA Laboratories. Rivest, M.Robshaw, Sidney, Yin]
•    RIJNDAEL [Joan Daemen, Vicent Rijmen]
•    SAFER+. [Cylink Corporation. L.Chen]
•    SERPENT. [R.Anderson, E.Biham, L.Knudsen]
•    TWOFISH[B.Schneier,J.Kelsey,D. Whiting, D.Wagner,C.may,N.Ferguson ]
 
Segunda Ronda.

En Marzo de 1999, se celebró la segunda conferencia de Candidatos a AES, en la que se discutió los resultados de las numerosas pruebas y criptoanálisis realizados por la comunidad criptográfica mundial sobre los quince candidatos iniciales. Basándose en estos comentarios y análisis, NIST seleccionó cinco candidatos finalistas:

MARS. [IBM. Nevenki Zunic]

RC6. [RSA Laboratories. Rivest, M.Robshaw, Sidney, Yin]
RIJNDAEL [Joan Daemen, Vicent Rijmen]
SERPENT. [R.Anderson, E.Biham, L.Knudsen]
TWOFISH [B.Schneier, J.Kelsey, D.Whiting, D.Wagner,
C.may, N.Ferguson ]

Tercera Ronda.

Finalmente, el 2 de octubre de 2000, el NIST anunció el algoritmo ganador. Las votaciones del concurso establecieron el siguiente ranking:

RIJNDAEL — 86 votos SERPENT — 59 votos TWOFISH — 31 votos RC6 —23 votos MARS — 13 votos

El algoritmo Rijndael ganó el concurso, por permitir la mejor combinación de seguridad-velocidad-eficiencia, sencillez y flexibilidad.
 
Destacando su sencillez, que había permitido un análisis muy intenso de su estructura.

Los creadores de este ingenio son dos ingenieros electrónicos belgas, un equipo bastante modesto, teniendo en cuenta que en el proceso de selección se enfrentaban a algoritmos creados por equipos de multinacionales tan fuertes y poderosas como IBM, Deuche Telekom, así como equipos de criptólogos de reputada fama mundial como, por ejemplo, Bruce Schneier (Twofish), autor de varios libros de criptografía, o Ronald Rivest (RC6), coautor del algoritmo de clave asimétrica RSA.

El algoritmo fue bautizado como Rijndael en un juego de fusión entre los apellidos de sus dos creadores: Vincent Rijmen, nacido en 1970, matemático de la facultad de Ciencias de la Universidad Católica de Lovaina, y su ex-colega en dicha universidad Joan Daemen, nacido en 1965, ingeniero electrónico y especialista en sistemas de seguridad electrónica bancaria.

Por tanto, en Octubre de 2000, quedó establecido el estándar AES (algoritmo Rijndael) como el estándar actual de comunicaciones de EEUU y por derivación de todo el mundo. Actualizándose paulatinamente todas las aplicaciones y servicios del estándar previo DES al nuevo sistema de cifrado.

Algoritmo Rijndael.

Inicialmente se estudia su estructura y motivos de diseño para permitir cifrar y descifrar información. A continuación, analizaremos la seguridad que ofrece éste algoritmo y finalmente los ataques posibles documentados que puede sufrir.

Conceptos Matemáticos Preliminares.

El algoritmo Rijndael funciona a nivel de bytes, interpretando estos como elementos de un cuerpo de Galois GF(2 ), y a nivel de registros de 32 bits, considerándolos como polinomios de grados menor que 4 con coeficientes que son a su vez polinomios en GF(2 ). El nacimiento de la teoría de Galois estuvo motivada por el intento de responder a la siguiente cuestión:

¿Por qué no existe una fórmula para la resolución de ecuaciones polinómicas de quinto grado (o superior) en términos de los coeficientes del polinomio, usando operaciones algebraicas (suma, resta, multiplicación, división) y la extracción de raíces (raíces cuadradas, cúbicas, etc); tal como existe para las ecuaciones de segundo, tercer y cuarto grado?

El teorema de Abel-Ruffini que es parte de la teoría de Galois, da una respuesta a esta pregunta. La teoría de Galois proporciona no sólo una elegante respuesta a esta cuestión, sino que también explica en detalle por qué es posible resolver ecuaciones de grado inferior al quinto, y por qué las soluciones son expresables mediante operaciones algebraicas y extracción de raíces.

Cuerpos Finitos. En este algoritmo todos los bytes se interpretan como elementos de un cuerpo finito. Concretamente, se representan mediante Campos de Galois que se representan como GF(k). Los campos de Galois son muy interesantes en criptografía, gracias a que existe un inverso aditivo y multiplicativo que permite cifrar y descifrar en el mismo cuerpo Zk, eliminando así los problemas de redondeo o truncamiento de valores si tales operaciones de cifrado y descifrado se hubiesen realizado en aritmética real. En nuestro caso, interesa utilizar una aritmética en módulo "p" sobre polinomios de grado "m", siendo "p" un número primo. Este campo de Galois queda representado como: GF(pm), en donde los elementos de GF(pm) se representan como polinomios con coeficientes en Zp de grado menor que m.

Especificación del Algoritmo.

El algoritmo Rijndael es un sistema simétrico de cifrado por bloques, por tanto utiliza la misma clave para el proceso de cifrado como para el proceso de descifrado. Su diseño permite la utilización de claves de sistema con longitud variable siempre que sea múltiplo de 4 bytes. La longitud de las claves utilizadas por defecto son 128 (AES-128), 192 (AES-192) y 256 (AES-256) bits. De la misma manera el algoritmo permite la utilización de bloques de información con un tamaño variable siempre que sea múltiplo de 4 bytes, siendo el tamaño mínimo recomendado de 128 bits (el tamaño mínimo de 16 bytes).

Este algoritmo opera a nivel de byte, interpretando éstos como elementos de un cuerpo de Galois GF(28), y a nivel de registros de 32 bits, considerándolos como polinomios de grado menor que 4 con coeficientes que son a su vez polinomios en GF(2 ).
 
El tema de la criptografía es un asunto que no dejará de ser estudiado y analizado, se ha pasado de la criptografía simétrica clásica heredada a lo largo de las decadas, a criptográfia pública, ahora el auge de la criptografía cuántica, estudios sobre aplicaciones concretas como criptografía "fluorescente",etc. El tiempo nos dirá cuál sistema será el mejor en cuanto a seguridad, mientras tanto lo mejor será estar atentos.

Por ahora tratemos de entender el funcionaniemto de éste algoritmo con la siguiente aplicación en C#.