Una gua para entender Advanced Encryption Standard (AES) con muecos de palo

Copyright 2009, Jeff Moserhttp://www.moserware.com/Traducido por Pablo Garaizar

Acto 1: rase una vez

Gestiono petabytes* de datos cada da. Cifrodesde jugosa inteligencia Alto Secreto hasta los aburridos paquetes que llegan a tu router WiFi. Lo hago todo!

* 1 petabyte = mucho

pero an as, no parece que a nadie le importe yo o mi historia.

La historia de cmo logr abrir mi propio camino para convertirme en el rey mundial del cifrado de bloques es mejor que la de Cenicienta.

Guau! Todava ests ah Quieres orla?Bien, empecemos...

Hace algn tiempo*, la gente -exceptuando a las agencias de inteligencia- no tena manera de juzgar la buena criptografa.

* ~ antes de 1975 para el pblico en general

EBG13 rf travny!

El ROT13 doblees mejor

Se promulg un edicto en todo el pas paraencontrar un algoritmo bueno y seguro.

Necesitamos un buen cifrado!

Un digno competidor llamado Luciferse dio a conocer.

Despus de ser modificado por la Agencia Nacionalde Seguridad (NSA), fue declarado el Estndar de

Cifrado de Informacin (DES).

Yo te nombro DES!

Caja 'S'ms fuerte

Clavemscorta

DES domin la tierra durante 20 aos.Los acadmicos lo estudiaron atentamente.Por primera vez haba algo especfico sobrelo que centrar su atencin. Naca el modernocampo de la criptografa.

' por lo que respecta a nuestro conocimiento, DESest a salvo de debilidades estadsticas o matemticas'.

Fjate en esa redde Feistel!

A lo largo de los aos, muchos atacantes desafiaron a DES y fue derrotado en varias batallas.

La nica manera de protegerse de esos ataques fueusar DES tres veces seguidas para formar 'Triple-DES'.

Esto fue efectivo, pero terriblemente lento.

Se promulg otro decreto* ...

Necesitamos algoal menos tan robustocomo Triple-DES, peroms rpido y flexible.

* ~ a principios de 1997

Esta es mi oportunidadde ser famoso!!

Usar FROG

Esta invitacin hizo que los cripto-magosse reunieran para desarrollar algo mejor.

Yo usarTwofish

Mis creadores, Vincent Rijmen y Joan Daemen,se encontraban entre esos cripto-magos. Combinaron sus apellidos para darme mi nombre: Rinjdael*.

* pronunciado 'reindal' para los que no sean belgas.

Yo

Todo el mundo se reuni para votar y...

Votadme!

Gan!!

y ahora soy el nuevo rey del cripto-mundo. Puedes encontrarme en cualquier parte. Incluso Intel est introduciendo instrucciones nativas para m en sus prximos chips para hacerme asombrosamente rpido.

Hoja de ruta de los procesadores Intel

Alguna pregunta?

Muy raro, me largo.

Bonita historia y todo eso, pero cmofunciona el cifrado?

Acto 2: Cifrado bsico

Muy buena pregunta! Solamente necesitas conocer 3 grandes ideas para entender el cifrado.

1 gran idea: confusin

Es una buena idea ocultar la relacin entre tu mensaje real y tu mensaje 'cifrado'. Un ejemplo de esta 'confusin' es el viejo y fiel 'Cifrado del Csar':

letras

en claro:

cifrado:

Es tambin una buena idea esparcir el mensaje.Un ejemplo de esta 'difusin' sera una simpletransposicin de columnas.

2 gran idea: difusin

Separado por 3 espacios

Despus de miles de aos, hemos aprendido que es una mala idea asumir que nadie terminar por conocer cmo funciona tu mtodo. Al final siemprehabr alguien que lo termine sabiendo.

3 gran idea: slo la clave es secreta

MAL MEJOR

Dime cmo funciona!

Genial! Ahorapuedo descifrarcualquier cosa!

Dime cmo funciona!

Mierda!

Sin problema! Est en la Wikipedia.Pero no s la clave.

Responde eso a tu pregunta?

Detalles?No soportolos detalles!

Est bien, pero ha sido muy general. Cmo funcionas t?

Acto 3: Detalles

Estara encantado de explicaros cmo funciono, pero antes tenisque firmar esto.

Uh, qu es eso?

Acuerdo de Prevencin de disparo en el pie

Yo, ________ prometo que, una vez vea lo simple que es AES realmente, no loimplementar en cdigo en produccin,

aunque sera realmente divertido hacerlo.

Este acuerdo tendr validez hasta queel abajo firmante invente una coreografaque compare y contraste la temporizacinbasada en cach y otros ataques indirectos

y sus contramedidas.

Firma Fecha

Tomo tus datos y los cargo en esta tabla de 4 x 4*.

* Esta es la 'matriz de estado' que siempre llevo conmigo.

Relleno al final,dado que no eranexactamente

16 bytes

En la ronda inicial calculo una OR-Exclusiva (XOR) de cada byte con el correspondiente de la clave para la primera ronda.

Un tributo a XORHay una sencilla razn por la que uso XOR para aplicar la clave y en otros sitios: es rpido y barato, un simple cambio a nivel de bit. Usa muy poco hardware y puede hacerse en paralelo ya que no se usan molestos bits de acarreo.

Necesito muchas claves para usarlas en rondas posteriores.Derivo todas ellas a partir de la clave inicial usando una sencilla tcnica de mezcla que es realmente rpida. A pesarde las crticas*, es suficientemente buena.

* la mayora -por mucho- de las quejas en contra del diseo de AES se centran en esta simplificacin.

Clave inicial

Expansin de la clave: parte 1

Tomo la ltima columna de la clave de la anterior ronda y muevo el byte de arriba del todo a abajo:

Expansin de la clave: parte 2a

Luego, paso cada byte por una caja de sustitucin quelo traducir en algo distinto:

Entonces, hago xor de la columna con una'constante de ronda' que es diferente para cada ronda:

Expansin de la clave: parte 2b

Finalmente, hago xor del resultado con la primeracolumna de la clave de la ronda previa:

Primera columna nueva

Las otras columnas son super-fciles*. Solamente tengo que hacer XOR de la columna anterior con la misma columna de la clave de la ronda previa:

Expansin de la clave: parte 3

* date cuenta de que las claves de 256 bits son ligeramente ms complicadas.

Columna dela clave deronda previa

Columna previa

Nueva columna Nueva clave de ronda

Luego, empiezo con las rondas intermedias. Unaronda es simplemente una serie de pasos que repito varias veces. El nmero de repeticiones depende deltamao de la clave.

Ronda intermedia

Uso la confusin (1 gran idea) para ocultar larelacin de cada byte. Pongo cada byte en unacaja de sustitucin (sbox), que lo traducir a unbyte diferente

Aplicando confusin: bytes sustitutos

Denota'confusin'

Luego desplazo las filas hacia la izquierda

y entonces las ajusto al otro lado

Denota 'permutacin'

Aplicando difusin, parte 1: desplazar filas

Aplicando difusin, parte 2: mezclar columnas

Tomo cadacolumna ymezclo los

bits

Al final de cada ronda, aplico la siguiente clave de ronda con una XOR:

Aplicando seguridad de la clave: aadir la clave de ronda

En la ronda final, me salto el paso de 'mezclar columnas',ya que no va a incrementar la seguridad y solamente ralentiza el proceso:

Ronda final

* la difusin que proporcionara no se aprovechara en la siguiente ronda.

y eso es todo. Cada ronda que hago aade msconfusin y difusin a los bits. Tambin hace quela clave influya en ellos. Cuantas ms rondas, mejor!

Determinar el nmero de rondas siempreimplica varios compromisos

SeguridadRendimiento

'La seguridad siempre implica un coste en rendimiento' Vincent Rijmen

Cuando estaba siendo desarrollado, un chico listo fue capaz de encontrar un atajo a travs de 6 rondas. Eso no est bien! Si miras cuidadosamente, vers que cada bit de la salida de una ronda depende de cada bit de dos rondas atrs. Para incrementar esta 'avalancha de difusin', aad 4 rondas extra ms. Este es mi 'margen de seguridad'.

Tericamente'roto'

'Margen de seguridad'

As que en imgenes, tenemos esto:

Descifrar implica hacer todo al revsAqu la 'ronda final' va al principio.

la 'ronda inicial' va al final.

Inverso de aadir clave de rondaInverso de

sustituir bytesInverso de

desplazar columnas Inverso de mezclar columnas

Un ltimo detalle: no debera de ser usado tal cual, sino como pieza de construccin de un 'modo' decente.

MAL! Mejor

Tiene sentido? Respondeeso a tu pregunta?

Casi... salvo cuando movas tus manosy usabas analogas extraas. Qu es lo que realmente ocurre?

Otra pregunta genial!No es difcil, pero... implicaun poco de... matemticas.

Las mates son difciles! Vamosde compras!

De acuerdo.Dale calor!

Acto 4: Matemticas

Volvamos a tu clase de lgebra

Vamos clase,cul es larespuesta?

T

Yo lo s!Es 2x.

Deberacopiarle

SaldrAshley

conmigo?

Repasando las bases

la incgnita suma

multiplicacincuadrado grado

coeficiente

polinomio

Cambiaremos las cosas ligeramente. Antes, los coeficientes podan ser tan grandes como queramos.Ahora solamente pueden ser 0 o 1:

Antes Ahora

Coeficientes grandes Coeficientes pequeosla nueva suma

* Hecho curioso: ahora, la 'nueva suma' es igual que la sustraccin:

Recuerdas cmo las multiplicaciones podan hacer que las cosas crecieran rpido?

Grande y asqueroso!

Con la 'nueva suma', las cosas son ms sencillas,pero la x13 es todava demasiado grande. Hagamos que no se pueda ir ms all de x7. Cmo podramos hacerlo?

Usaremos a nuestro amigo el 'reloj matemtico*' para hacer esto. Solamente suma cosas y hace la divisin.Presta atencin al resto de la divisin:

* Esto se conoce tambin como 'suma modular'. Los locos por las matemticas lo llaman 'grupo'. AES utiliza un grupo especial llamado un 'campo finito'.

4 en punto + 10 horas = 2 en punto

+ 10 horas =

Podemos hacer matemticas 'de reloj' con polinomios. En lugar de dividir por 12, mis creadores me dijeron que usara

donde

es muy grande, tenemos que hacerlo ms pequeo

tiene coeficientesSupongamos que queremos multiplicar

* Recuerda que cada es o bien 0 o bien 1.

Lo dividimos entre y tomamos elresto:

Fjate como las b's se desplazan hacia la izquierda 1 posicin. Esto es simplemente

b7 multiplicado por unpolinomio pequeo

El resto:

Ahora ya estamos preparados para la explosin msfuerte del pasado: los logaritmos. Una vez dominados, el resto es pan comido. Los logaritmos nos permiten convertir multiplicacin en suma:

A la inversa:

Luego

simple polinomio y contemplar cmo se complica la magia*.

* Si continuas multiplicando por (x1) y tomas el resto despus de dividirpor m(x), vers que generars todos los posibles polinomios por debajo deX8. Esto es muy importante!

simple polimonio

Podemos usar algoritmos en nuestro nuevo mundo. En lugar de usar 10 como base, podemos emplear el

Por qu molestarnos con todas estas matemticas?*El cifrado trata con bits y bytes, no? Bueno, existeuna ltima conexin: un polinomio de 7 grado puedeRepresentar exactamente 1 byte, dado que ahora solamente utilizamos 0 o 1 como coeficientes:

Un solo byte!!

* A pesar de que solamente trabajaremos con bytes a partir de ahora, las matermticas nos aseguran que todo se resuelve bien.

Trabajando con bytes, la suma de polinomios se convierte en una simple xor. Podemos usar nuestros conocimientos de logartimos para hacer una tabla para multiplicar muy rpidamente*.

* Podemos crear la tabla dado que seguimos multiplicando por

Dado que sabemos cmo multiplicarlos, podemos encontrar el byte del polinomio 'inverso' para cada byte. Este es el byte que deshar/invertir el polinomio de nuevo a 1. Solamente hay 255 posibilidades*, as que podemos usar la fuerza bruta para encontrarlos:

encontrado por fuerza bruta usando un bucle for

* Hay solamente 255 y no 256 porque el 0 no tiene inverso.

Ahora ya podemos entender la misteriosa s-box.Tomaun byte 'a' y le aplica dos funciones. La primera es 'g',que solamente encuentra el byte inverso. La segunda es'f', que complica las matemticas a propsito en contra para frustrar ataques.

Tambin podemos entender esas locas constantes de ronda en la expansin de la clave. Las consigo empezando con '1' y continuo multiplicando por 'x':

Constantes de las primeras 10 rondas

Mezclar las columnas es lo ms complicado. Trato cada columna comoun polinomio. Uso entonces nuestro nuevo mtodo para multiplicarlo porUn polinomio especialmente preparado y entonces tomo resto despus de Dividirlo por x4+1. Esto se simplifica con una matriz de multiplicacin:

la columnapolinomio especial

Guau Creo que lo he entendido. Esrelativamente sencillo una vez encajasLas piezas. Gracias por explicarlo. He de irme.Un placer.

!Vuelve cuando quieras!

Pero hay mucho ms de lo que hablar: mi resistenciaal criptoanlisis lineal y diferencial, mi estrategia'Wide Trail', la implausibilidad de ataques de claves relacionadas, y... mucho ms... pero no queda nadie.

Oh, de acuerdo... todava hay aburrido trfico de router que tiene que ser cifrado. Me tengo que ir!

Fin

Pgina 1Pgina 2Pgina 3Pgina 4Pgina 5Pgina 6Pgina 7Pgina 8Pgina 9Pgina 10Pgina 11Pgina 12Pgina 13Pgina 14Pgina 15Pgina 16Pgina 17Pgina 18Pgina 19Pgina 20Pgina 21Pgina 22Pgina 23Pgina 24Pgina 25Pgina 26Pgina 27Pgina 28Pgina 29Pgina 30Pgina 31Pgina 32Pgina 33Pgina 34Pgina 35Pgina 36Pgina 37Pgina 38Pgina 39Pgina 40Pgina 41Pgina 42Pgina 43Pgina 44Pgina 45Pgina 46Pgina 47Pgina 48Pgina 49Pgina 50Pgina 51Pgina 52Pgina 53Pgina 54Pgina 55Pgina 56Pgina 57Pgina 58Pgina 59Pgina 60Pgina 61Pgina 62Pgina 63Pgina 64Pgina 65Pgina 66Pgina 67Pgina 68Pgina 69Pgina 70Pgina 71Pgina 72