Advanced Encryption Standard

L' Advanced Encryption Standard (AES), també conegut com a Rijndael (pronunciat "Rain Doll" en anglès), és un esquema de xifrat per blocs adoptat com un estàndard de xifrat pel govern dels Estats Units. S'espera que sigui utilitzat en el món sencer i analitzat exhaustivament, com va ser el cas del seu predecessor, el Data Encryption Standard (DES). L'AES fou anunciat per l'Institut Nacional d'Estàndards i Tecnologia (NIST) com FIPS PUB 197 dels Estats Units (FIPS 197) el 26 de novembre de 2001 després d'un procés d'estandardització que va durar 5 anys (vegeu procés d'Advanced Encryption Standard per a més detalls). Es va transformar en un estàndard efectiu el 26 de maig de 2002. Des de 2006, l'AES és un dels algorismes més populars usats en criptografia simètrica.

El xifrador va ser desenvolupat per dos criptòlegs belgues, Joan Daem i Vincent Rijmen, tots dos estudiants de la Katholieke Universiteit Leuven, i enviat al procés de selecció AES sota el nom "Rijndael".

Història

El 1997, l'Institut Nacional de Normes i Tecnologia (NIST) va decidir fer un concurs per escollir un nou algorisme de xifrat capaç de protegir informació confidencial durant segle xxi. Aquest algorisme es va denominar Advanced Encryption Standard (AES).

El 2 de gener de 1997 el NIST va anunciar la seva intenció de desenvolupar AES, amb l'ajuda de la indústria i de la comunitat criptogràfica. El 12 de setembre d'aquest any es va fer la convocatòria formal. En aquesta convocatòria s'indicaven diverses condicions per als algorismes que es presentaran:

• Ser de domini públic, disponible per a tothom.
• Ser un algorisme de xifrat simètric i suportar blocs de, com a mínim, 128 bits.
• Les claus de xifrat podrien ser de 128, 192 i 256 bits.
• Ser implementable tant en hardware com en software.

El 20 d'agost de 1998 el NIST va anunciar els 15 algorismes admesos a la primera conferència AES:

• CAT-256 (Entrust Technologies, Inc)
• CRYPTON (Future Systems, Inc)
• DEAL (Richard Outerbridge, Lars Knudsen)
• DFC (CNRS - Centre National pour la Recherche Scientifique - Ecole Normale Superieure)
• E2 (NTT - Nippon Telegraph and Telephone Corporation)
• FROG (TecApro International, S.A.)
• HPC (Rich Schroeppel)
• LOKI97 (Lawrie Brown, Josef Pieprzyk, Jennifer Seberry)
• MAGENTA (Deutsche Telekom AG)
• MARS (IBM)
• RC6 (RSA Laboratories)
• Rijndael (John Daem, Vincent Rijmen)
• SAFER+ (Cylink Corporation)
• Serpent (Ross Anderson, Eli Biham, Lars Knudsen)
• Twofish (Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, Niels Ferguson)

La segona conferència AES va tenir lloc el març de 1999 on es van discutir les anàlisis a què van ser sotmesos els candidats per la comunitat criptogràfica internacional. Es van admetre comentaris fins al 15 d'abril. El NIST va decidir l'agost de 1999 quals serien els 5 finalistes:

• MARS
• RC6
• Rijndael
• Serpent
• Twofish

Aquests algorismes van ser sotmesos a una segona revisió, més exhaustiva, que va durar fins al 15 de maig de 2000. Durant aquest període el NIST va admetre anàlisi dels algorismes finalistes.

Durant els dies 13 i 14 d'abril de 2000 va tenir lloc la tercera conferència AES on es van discutir els darrers anàlisi dels algorismes finalistes. Hi van estar presents els desenvolupadors dels algorismes finalistes.

El 15 maig 2000 va finalitzar el període públic d'anàlisi. El NIST va estudiar tota la informació disponible per decidir quin seria l'algorisme guanyador. El 2 d'octubre de 2000 es va votar quin seria l'algorisme que finalment guanyaria el concurs. El resultat va ser el següent:

• MARS: 13 vots
• RC6: 23 vots
• Rijndael: 86 vots
• Serpent: 59 vots
• Twofish: 31 vots

L'algorisme Rijndael va guanyar el concurs i el novembre de 2001 es va publicar FIPS 197 on s'assumia oficialment.

Desenvolupament

Rijndael va ser un refinament d'un disseny anterior de Daem i Rijmen, Square; Square va ser al seu torn un desenvolupament de Shark.

Al contrari que el seu predecessor DES, Rijndael és una xarxa de substitució-permutació, no una xarxa de Feistel. AES és ràpid tant en programari com a maquinari, és relativament fàcil d'implementar, i requereix poca memòria. Com nou estàndard de xifrat, s'està utilitzant actualment a gran escala.

Descripció del xifrat

En la fase de SubBytes , cada byte al state és reemplaçat amb la seva entrada en una taula de cerca fixa de 8 bits, S ; b ij = S (a ij ) .

En el pas ShiftRows , els bytes en cada fila de l'state són rotats de manera cíclica cap a l'esquerra. El nombre de llocs que cada byte és rotat difereix per a cada fila.

En el pas MixColumns , cada columna de l'state és multiplicada per un polinomi constant c (x) .

En el pas AddRoundKey , cada byte de l'state es combina amb un byte de la subclau utilitzant l'operació XOR (⊕).

Estrictament parlant, AES no és precisament Rijndael (encara que en la pràctica se'ls diu de manera indistinta), ja que Rijndael permet un major rang de mida de blocs i longitud de claus; AES té una mida de bloc fix de 128 bits i mides de clau de 128, 192 o 256 bits, mentre que Rijndael pot ser especificat per una clau que sigui múltiple de 32 bits, amb un mínim de 128 bits i un màxim de 256 bits.

La majoria dels càlculs de l'algorisme AES es fan en un cos finit determinat.

AES opera en una matriu de 4 × 4 bytes, anomenada state (algunes versions de Rijndael amb una mida de bloc més tenen columnes addicionals al state).

Pseudo-codi

• Expansió de la clau usant l'esquema de claus de Rijndael.
• Etapa inicial:

1. AddRoundKey

• Rondes:

1. SubBytes - en aquest pas es realitza una substitució no lineal on cada byte és reemplaçat amb un altre d'acord amb una taula de cerca.
2. ShiftRows - en aquest pas es realitza una transposició on cada fila del "state» és Rotat de manera cíclica un nombre determinat de vegades.
3. MixColumns - operació de barreja que opera a les columnes del «state», combinant els quatre bytes en cada columna utilitzant una transformació lineal.
4. AddRoundKey - cada byte de l'«state» és combinat amb la clau «round»; cada clau «round» es deriva de la clau de xifrat utilitzant una iteració de la clau.

• Etapa final:

1. SubBytes
2. ShiftRows
3. AddRoundKey

Etapa SubBytes-Substitució de bits

En l'etapa SubBytes , cada byte a la matriu és actualitzat utilitzant la caixa-S de Rijndael de 8 bits. Aquesta operació proveeix la no linealitat en el xifrat. La caixa-S utilitzada prové de la funció inversa al voltant del GF (2 ⁸ ), conegut per tenir grans propietats de no linealitat. Per evitar atacs basats en simples propietats algebraiques, la caixa-S es construeix per la combinació de la funció inversa amb una transformació afí invertible. La caixa-S també es tria per evitar punts estables (i és per tant un derangement), i també qualssevol punts estables oposats.

La caixa-S és descrita en major profunditat en l'article caixa-S de Rijndael.

Etapa ShiftRows-Desplaçar files

El pas ShiftRows opera a les files del state; trencada de manera cíclica els bytes en cada fila per un determinat offset. En AES, la primera fila queda a la mateixa posició. Cada byte de la segona fila és mogut una posició a l'esquerra. De manera similar, la tercera i quarta files són rotades pels offsets de dos i tres respectivament. D'aquesta manera, cada columna de l'state resultant del pas ShiftRows està composta per bytes de cada columna de l'state inicial. (Variants de Rijndael amb més gran de bloc tenen offsets diferents).

Etapa MixColumns-Barrejar columnes

En el pas MixColumns , els quatre bytes de cada columna de l'state es combinen utilitzant una transformació lineal invertible. La funció MixColumns pren quatre bytes com a entrada i retorna quatre bytes, on cada byte d'entrada influeix totes les sortides de quatre bytes. Juntament amb ShiftRows , MixColumns implica difusió al xifrat. Cada columna es tracta com un polinomi GF (2 ⁸ ) i després es multiplica el mòdul $x^{4}+1$ amb un polinomi fix $c(x)$. El pas MixColumns es pot veure com una multiplicació matricial al camp finit de Rijndael.

Etapa AddRoundKey-Càlcul de les subclaus

En el pas AddRoundKey , la subclau es combina amb el state. En cada ronda s'obté una subclau de la clau principal, utilitzant la iteració de la clau, cada subclau és de la mateixa mida del state. La subclau s'agrega combinant cada byte de l'state amb el corresponent byte de la subclau utilitzant XOR.

Optimització de xifrat

En sistemes de 32 bits o més gran de paraula, és possible accelerar l'execució d'aquest algorisme mitjançant la conversió de les transformacions SubBytes , ShiftRows i MixColumn en taules. Es tenen quatre taules de 256 entrades de 32 bits que utilitzen un total de 4 kilobytes (4096 bytes) de memòria, un Kb cada taula. D'aquesta manera, una ronda de l'algorisme consisteix en 16 recerques en una taula seguida de 16 operacions XOR de 32 bits en el pas AddRoundKey . Si la mida de 4 kilobytes de la taula és massa gran per una plataforma determinada, l'operació de cerca a la taula es pot dur a terme mitjançant una sola taula de 256 entrades de 32 bits mitjançant l'ús de rotacions circulars.

Seguretat

Fins a 2005, no s'ha trobat cap atac reeixit contra l'AES. L'Agència de Seguretat Nacional dels Estats Units (NSA) va revisar tots els finalistes candidats al AES, incloent el Rijndael, i va declarar que tots ells eren prou segurs per al seu ús en informació no classificada del govern dels Estats Units. El juny de 2003, el govern dels Estats Units va anunciar que el AES podia ser usat per a informació classificada:

" The design and strength of all key lengths of the AES algorithm (ie, 128, 192 and 256) are sufficient to protect classified information up to the SECRET level. TOP SECRET information will require use of either the 192 or 256 key lengths. The implementation of AES in products intended to protect national security systems and/or information must be reviewed and certified by NSA prior to their acquisition and use.

Aquest fet marca la primera vegada que el públic ha tingut accés a un xifrador aprovat per la NSA per a informació super secreta (TOP SECRET). Molts productes públics fan servir claus de 128 bits per defecte.

El mètode més comú d'atac cap a un xifrador per blocs consisteix a intentar diversos atacs sobre versions del xifrador amb un nombre menor de rondes. El AES té 10 rondes per claus de 128 bits, 12 rondes per claus de 192 bits, i 14 rondes per claus de 256 bits. Fins a 2005, els millors atacs coneguts són sobre versions reduïdes a 7 rondes per claus de 128 bits, 8 rondes per claus de 192 bits, i 9 rondes per claus de 256 bits (Ferguson et al, 2000).

Alguns criptògrafs mostren preocupació sobre la seguretat del AES. Ells senten que el marge entre el nombre de rondes especificat al xifrador i els millors atacs coneguts és molt petit. El risc és que es pot trobar alguna manera de millorar els atacs i en aquest cas, el xifrat podria ser trencat. En el context criptogràfic es considera "trencat" un algorisme si hi ha algun atac més ràpid que una recerca exhaustiva (atac per força bruta). De manera que un atac contra el AES de clau de 128 bits que requereixi 'només' 2 ¹²⁰ operacions seria considerat com un atac que "trenca" el AES tot tenint en compte que per ara seria un atac irrealitzable. Fins ara, aquestes preocupacions poden ser ignorades. L'atac de força bruta més llargament publicitat i conegut ha estat contra una clau de 64 bits RC5 per distributed.net.

Una altra preocupació és l'estructura matemàtica de AES. A diferència de la majoria de xifradores de blocs, AES té una descripció matemàtica molt ordenada. Això no ha portat encara a cap atac, però alguns investigadors estan preocupats que futurs atacs potser trobin una manera d'explotar aquesta estructura.

En 2002, un atac teòric, anomenat "atac XSL", va ser anunciat per Nicolas Courtois i Josef Pieprzyk, mostrant una potencial debilitat en l'algorisme AES. Diversos experts criptogràfics han trobat problemes en les matemàtiques que hi ha per sota de l'atac proposat, suggerint que els autors potser hagin comès un error en les seves estimacions. Si aquesta línia d'atac pot ser presa contra AES, és una qüestió encara oberta. Fins al moment, l'atac XSL contra AES sembla especulatiu, és improbable que ningú pogués dur a terme a la pràctica aquest atac.

Atacs de canal auxiliar

Els atacs de canal auxiliar no ataquen l'xifrador en si, sinó a les implementacions del xifrador en sistemes que revelen dades inadvertidament.

L'abril de 2005, Daniel J. Bernstein va anunciar un atac temporitzat de cache que solia trencar un servidor a mesura que usava el xifrat AES per OpenSSL. Aquest servidor va ser dissenyat per donar la major quantitat d'informació sobre els temps d'execució com fos possible, i l'atac requeria prop de 200 milions de fitxers de text en clar. Es diu que l'atac no és pràctic en implementacions del món real; Bruce Schneier va anomenar a aquesta investigació un "bonic atac de temps" .

L'octubre de 2005, Adi Shamir i dos investigadors van presentar un article demostrant diversos atacs de temps de cache contra AES. Un dels atacs va obtenir una clau de AES sencera després de tan sols 800 escriptures, a 65 mil·lisegons. Aquest atac requereix que l'atacant pugui executar programes en el mateix sistema que realitza el xifrat de AES.

Implementacions

• Una calculadora de AES que mostra valors intermedis en Javascript
• Implementació de AES per Brian Gladman amb llicència BSD
• Implementació de AES de domini públic de Pablo Barreto escrita en C
• Implementació de AES de domini públic de DJ Bernstein
• Codi font amb llicència GPL de l'algorisme optimitzat de Rijndael al carrer
• Biblioteca GPL Nettle que també inclou una implementació de AES
• Evolsystem: exemple d'algorisme de xifrat AES - Rijndael
• Rijndael Inspector: programa fet a Flash per a xifrar i desxifrar utilitzant AES-128

Notes

• Mides de bloc de 128, 160, 192, 224, i 256 bits són suportats per l'algorisme Rijndael, però només blocs de 128 bits de mida són especificats en el AES.

Bibliografia

• Nicolas Courtois, Josef Pieprzyk, "Cryptanalysis of Block Ciphers with Overdefined Systems of Equations". pp267-287, ASIACRYPT 2002.
• Joan Daem and Vincent Rijmen, "The Design of Rijndael: AES - The Advanced Encryption Standard." Springer-Verlag, 2002. ISBN 3-540-42580-2.
• Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Michael Stay, David Wagner and Doug Whiting: Improved Cryptanalysis of Rijndael. FSE 2000, pp213-230

Enllaços externs

• John Savard's description of the AES algorithm