PDF de programación - Implementación Eficiente en FPGA del Modo CCM usando AES

Centro de Investigaci´on y de Estudios Avanzados

del Instituto Polit´ecnico Nacional

Unidad Zacatenco

Departamento de Ingenier´ıa El´ectrica

Secci´on de Computaci´on

Implementaci´on Eficiente en FPGA del Modo CCM

usando AES

Tesis que presenta:

Emmanuel L´opez Trejo

para obtener el Grado de:

Maestro en Ciencias

en la Especialidad de:
Ingenier´ıa El´ectrica

Opci´on:

Computaci´on

Director de la Tesis:

Dr. Francisco Rodr´ıguez Henr´ıquez

Ciudad de M´exico, M´exico.

Septiembre 2005

ii

A Dios sea la gloria.
Gracias te doy Se˜nor
por permitirme ver
realizado este sue˜no.

A mi hermanita preciosa,
por su gran cari˜no y amor,
y por todos los grandes
momentos que hemos vivido juntos.

A mi madre adorada,
por su gran e inmenso amor,
que sin duda jam´as podr´e pagar,
por ser simplemente mi mejor amiga
y la persona que m´as quiero en este mundo.

A Paty, mi gran amor,
por todo su amor y cari˜no
que han hecho de mi vida algo
maravilloso.

iii

iv

Agradecimientos

Gracias le doy primeramente a Dios por permitirme culminar con ´exito este sue˜no, as´ı co-
mo por las grandes bendiciones que de su mano he recibido a lo largo de mi vida. S´e que sin
su ayuda nada hubiese podido conseguir.

Agradezco a mi mam´a por su infinito amor, por su paciencia y apoyo incondicional, sin
los cuales gran parte de lo que soy no ser´ıa posible. Gracias mam´a por estar siempre a mi lado
y por el aliento constante en los momentos m´as dif´ıciles, por tu disposici´on a escuchar mis
problemas, frustraciones, sue˜nos, anhelos, etc. Te agradezco por escuchar mis pl´aticas sobre
los problemas que ten´ıa que resolver, aunque no entendieras de lo que te estaba hablando.
Te doy las gracias por las palabras de motivaci´on, de orientaci´on y de confianza sin las cuales
mucho de esto no ser´ıa posible. Pero por sobre todo, te doy las gracias por traerme al mundo,
aun cuando casi te cost´o la vida y porque cada d´ıa me entregas una parte importante de tu
ser. Esta tesis es para ti, porque s´e que es la culminaci´on del excelente trabajo que llevas
realizando por m´as de 24 a˜nos. Gracias, mil gracias.

Gracias a mi hermanita adorada por su apoyo y paciencia en los momentos dif´ıciles, y
por tener siempre la frase adecuada para hacerme re´ır. Gracias por ser como eres y por todo
el amor que me brindas. Te quiero mucho no lo olvides.

Agradezco a Paty por su apoyo incondicional durante este tiempo y porque ha tra´ıdo
una nueva luz a mi vida. Gracias por todos los bellos momentos que hemos vivido juntos y
por las constantes palabras de ´animo que me motivaron a seguir adelante.

Una gratitud especial al resto de mi familia que en mayor o menor medida contribuye-
ron para que todo esto fuera posible. Gracias por su amor y cari˜no, forman una parte muy
especial en mi vida.

Agradezco al Consejo Nacional de Ciencia y Tecnolog´ıa, por el apoyo econ´omico recibido
durante la realizaci´on de mis estudios de Maestr´ıa mediante el otorgamiento de la beca-cr´edi-
to, as´ı como a trav´es del proyecto n´umero 45306.

Una gratitud especial a mis profesores en el CINVESTAV, cuyo conocimiento contri-
buy´o a ampliar y consolidar mi visi´on sobre las ciencias de la computaci´on. Sin duda no
podr´e pagar sus valiosas ense˜nanzas.

v

Agradezco al Dr. Francisco Rodr´ıguez Henr´ıquez por su tiempo y sus innumerables co-
mentarios para el desarrollo de esta tesis, as´ı como por gran paciencia y amplio conocimiento
para llevarla a buen t´ermino.

Gracias tambi´en a los Dres. Arturo D´ıaz P´erez y Carlos Artemio Coello Coello, por sus
valiosos comentarios para el enriquecimiento de este trabajo. Gracias por el tiempo que in-
virtieron en la revisi´on y correcci´on de este documento.

No puedo olvidar a mis compa˜neros y amigos, los cuales tambi´en contribuyeron para
hacer m´as agradable y sencilla mi estancia en el CINVESTAV. Gracias a cada uno de ellos
por su ayuda, orientaci´on y amistad.

Finalmente, pero no menos importante, gracias a Sof´ıa Reza por su apoyo y ayuda para

resolver los tr´amites acad´emicos, gracias por la gran paciencia al desarrollar su trabajo.

vi

Resumen

La tecnolog´ıa de redes inal´ambricas ha tenido un crecimiento exponencial en los ´ultimos
a˜nos, lo que ha incrementado la necesidad de contar con esquemas de seguridad que brin-
den una adecuada protecci´on de los datos. Diversos algoritmos han sido dise˜nados para tal
fin, sin embargo, el utilizado en el est´andar IEEE 802.11b, el WEP, ha sido vulnerado en
m´ultiples ocasiones, lo que hace necesario el desarrollo de nuevas alternativas para proteger
la informaci´on que se transmite a trav´es de este tipo de redes.

En a˜nos recientes, nuevos esquemas se han propuesto para sustituir al WEP, siendo el
modo de operaci´on CCM el candidato m´as fuerte para tomar el lugar como el esquema de
seguridad en las redes inal´ambricas. En esta tesis, presentamos la implementaci´on de dicho
modo de operaci´on en un FPGA y brindamos las ideas b´asicas para conseguir una imple-
mentaci´on eficiente. El dise˜no presentado en este trabajo, consigue una eficiencia altamente
competitiva con las aplicaciones comerciales, as´ı como con implementaciones acad´emicas re-
portadas en la literatura abierta.

Presentamos el an´alisis de los resultados obtenidos y damos una proyecci´on de su utilidad

comparada con aplicaciones comerciales disponibles actualmente.

vii

viii

Abstract

Over the last years Wireless technology has grown exponentially, which has increased the
necessity of suitable security schemes that provides an adequate protection of the informa-
tion. Many algorithms had been designed for this purpose, however, the most widely used
in the IEEE 802.11b standard, the WEP, has been broken in multiple occasions, making
necessary the development of new alternatives to protect the information that is broadcast
in this type of networks.

In recent years, new schemes had been proposed to substitute the WEP, being the CCM
mode of operation the most promising scheme for becoming the new security protocol in wire-
less network environments. In this Thesis, we present the FPGA implementation of the CCM
mode of operation and we give the basic ideas in order to get an efficient implementation.
The design presented in this work, achieves a great performance compared with commercial
applications, and also with the academic ones reported in the open literature.

We present a rigorous analysis of the results obtained giving a projection of its usefulness

compared with commercial applications currently available.

ix

x

´Indice general

1. Seguridad en dispositivos de c´omputo restringido

1.1. Seguridad en dispositivos port´atiles . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
1.1.1. Tecnolog´ıa de redes inal´ambricas
1.1.2. El protocolo WEP . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.3. Nuevas propuestas para la seguridad . . . . . . . . . . . . . . . . . .
1.2. Seguridad en hardware reconfigurable . . . . . . . . . . . . . . . . . . . . . .
1.2.1. Tecnolog´ıa de hardware reconfigurable
. . . . . . . . . . . . . . . . .
1.2.2. Propuestas de seguridad en hardware reconfigurable . . . . . . . . . .

2. El Cifrador por bloques AES

2.1. Breve historia del AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. El inicio del proceso del AES . . . . . . . . . . . . . . . . . . . . . .
2.1.2. Criterios de evaluaci´on . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Los componentes del AES . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1. Datos de entrada y salida . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2. Las rondas del AES . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Optimizaci´on de los pasos del AES . . . . . . . . . . . . . . . . . . . . . . .
2.3.1. Optimizaci´on de MixColumns y AddRoundKey . . . . . . . . . . . . .
2.3.2. Optimizaci´on en el Algoritmo de KS . . . . . . . . . . . . . . . . . .

3. El modo de operaci´on CCM

3.1.

Introducci´on al modo de operaci´on CCM . . . . . . . . . . . . . . . . . . . .
3.1.1. Los par´ametros del CCM . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2. Las entradas en este modo de operaci´on . . . . . . . . . . . . . . . .
3.2. Autenticaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Cifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Descifrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Verificaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. La seguridad del modo CCM . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7. Pruebas de rendimiento del CCM en tarjetas comerciales . . . . . . . . . . .
3.7.1. Descripci´on de las tarjetas inal´ambricas . . . . . . . . . . . . . . . . .
3.7.2. Pruebas realizadas
. . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
1
6
12
21
24
25
31

33
33
34
34
35
35
36
42
43
43

45
45
47
47
49
51
54
55
56
58
58
58

xi

3.7.3. Resultados de las pruebas

. . . . . . . . . . . . . . . . . . . . . . . .

59

4. La implementaci´on del CCM en FPGAs

4.1. La plataforma de desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. El Lenguaje de programaci´on VHDL . . . . . . . . . . . . . . . . . . . . . .
4.3. Ciclo del dise˜no en FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Consideraciones para la implementaci´on . . . . . . . . . . . . . . . . . . . .
4.5.
Implementaci´on del AES . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5.1. Arquitectura General del AES . . . . . . . . . . . . . . . . . . . . . .
Implementaci´on de las Rondas del AES . . . . . . . . . . . . . . . . .
4.5.2.
4.5.3.
Implementaci´on de la expansi´on de llave . . . . . . . . . . . . . . . .
Implementaci´on del CCM . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.1. Las par´ametros e informaci´on de entrada y salida del CCM . . . . . .
4.6.2. Arquitectu