Esquema de Seguridad Redes Ad-Hoc M Viles Inal Mbricas PDF
Esquema de Seguridad Redes Ad-Hoc M Viles Inal Mbricas PDF
TESIS DOCTORAL
Autor:
D. Oscar Delgado Mohatar
Director/es:
Dr. D. José María Sierra Cámara
Dra. Dª Amparo Fúster Sabater
Departamento de Informática
Firma
Presidente:
Vocal:
Vocal:
Vocal:
Secretario:
Calificación:
Leganés, de de
Í NDICE GENERAL
I. Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I .1. El nuevo escenario de juego . . . . . . . . . . . . . . . . . . . . . . . . . . 13
I .1.1. La Internet de las cosas . . . . . . . . . . . . . . . . . . . . . . . . 13
I .2. Las redes inalámbricas y la telefonı́a móvil . . . . . . . . . . . . . . . . . 14
I .2.1. Redes móviles ad-hoc . . . . . . . . . . . . . . . . . . . . . . . . . 16
I .3. Necesidad de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
I .4. Objetivos de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
I .5. Organización de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3
4 ÍNDICE GENERAL
Bibliografı́a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
6
Í NDICE DE FIGURAS
7
8 ÍNDICE DE FIGURAS
11
12 ÍNDICE DE CUADROS
INTRODUCCI ÓN
Sin embargo, los cambios se suceden a una velocidad de vértigo y lo visto has-
ta ahora no es más que la punta del iceberg. La denominada Internet de las cosas está
considerada por muchos como la próxima gran revolución en la actual Sociedad de la
Información y en nuestro actual modo de vida [1].
En pocas palabras, podrı́a decirse que la próxima generación de Internet consiste en
una red de todo tipo de objetos con capacidad de conexión entre sı́, junto con una serie de servi-
cios, tı́picamente Web, que interactúan con dichos objetos. Entre algunas de las tecnologı́as
que soportan este nuevo enfoque se encuentran RFID (identificación por radio frecuen-
cia), sensores o los propios teléfonos móviles de última generación (smartphones).
Aunque algunos de estos escenarios puedan parecer innecesarios, o incluso frı́volos,
lo cierto es que este nuevo paradigma de comunicación puede proporcionar otros usos
realmente beneficiosos.
Es el caso de las redes de monitorización de pacientes en hospitales, que harı́an innece-
sarios los incómodos cables y permitirı́an tener a un paciente permanentemente moni-
torizado, incluso cuando pasea por el pasillo.
Como estas redes no necesitan de una infraestructura previa de comunicaciones,
pueden resultar muy útiles en casos de desastre natural o emergencias, donde es habit-
ual que las redes tradicionales resulten dañadas.
Otros usos menos altruistas, pero probablemente mucho más rentables económicamente,
incluyen una mejora sustancial en todo el proceso de manufactura de bienes, desde su
13
14 I. I NTRODUCCI ÓN
Las nuevas comunicaciones Todo esto ha sido y será posible gracias a la conjunción
de muchos factores, entre los que destaca el avance imparable de la miniaturización
electrónica, que permite crear dispositivos cada vez más capaces y, al mismo tiempo,
reducir su tamaño.
Pero parece claro que el verdadero factor detonante ha sido la evolución de las co-
municaciones inalámbricas que, aunque presentes y ubicuas desde hace décadas, sólo en
los últimos años han alcanzado el grado de sofisticación necesario para hacer realidad
los escenarios que hemos descrito.
De los múltiples criterios utilizados para clasificar las redes de comunicaciones, en-
tre los que se incluyen su escala, su método de conexión, la topologı́a que forman o los
protocolos que utilizan, en los últimos años ha cobrado especial importancia el medio
de transmisión.
Cuando el cable tradicional se sustituye por transmisión a través del aire se habla
de redes inalámbricas. En este caso la comunicación se lleva a cabo utilizando un medio
no guiado, mediante ondas electromagnéticas, y haciendo uso de antenas.
No cabe duda de que la tecnologı́a inalámbrica está ocupando rápidamente las
preferencias de todo tipo de usuarios. La telefonı́a móvil está cada vez más cerca de
convertirse en un sistema de comunicación personal universal en el mundo occiden-
tal y, desde hace unos años, todo tipo de ordenadores están librándose también de sus
ataduras cableadas. Cada vez son más los hogares, cafés, pequeñas empresas, aeropuer-
tos o grandes compañı́as en los que se dispone de redes inalámbricas de ordenadores.
Aunque las tecnologı́as que hacen posible las comunicaciones inalámbricas, como
el láser, los rayos infrarrojos o las ondas de radio, existen desde hace muchas décadas,
su implantación comercial y su aplicación a las comunicaciones no ha sido posible has-
ta fechas recientes. El primer servicio que se liberó del cable fue la telefonı́a y no lo
hizo hasta los años 80 en EEUU y bastantes años después en España. Desde aquellos
aparatos que pesaban varios kilos y costaban miles de dólares, la telefonı́a móvil no ha
dejado de crecer espectacularmente hasta superar a la telefonı́a fija en cuanto al número
de lı́neas.
En este sentido, dispositivos como el iPhone de Apple, un auténtico fenómeno de
masas, están redefiniendo los lı́mites de los teléfonos móviles tradicionales y evolu-
cionan hacia dispositivos ubicuos de computación [2, 3]. Cualquiera de estos teléfonos
de última generación podrı́a jugar un papel predominante en la Internet de las cosas, el
nuevo tipo de redes que se considera en esta tesis.
Modo
infraestructura
Modo ad-hoc
LAN cableada
Punto de acceso
inalámbrico
Nodos
Nodos
Las soluciones aportadas para estos escenarios por otros protocolos, como el estándar
802.11 o el más reciente 802.16 (WiMax), no resultan del todo adecuadas. El primero de
los protocolos, sin duda el más extendido en la actualidad, tiene dos modos básicos de
funcionamiento, llamados modo infraestructura y modo ad hoc, que aparecen esquemati-
zados en la Figura I.1 y analizados en [5, 6].
Ambos métodos tienen una serie de inconvenientes importantes en los escenarios
planteados. El primero de ellos necesita, como su nombre indica, una infraestructura
de comunicaciones pre-existente, que consiste habitualmente en un router. Este requer-
imiento lo hace inadecuado para, por ejemplo, situaciones de crisis donde es imposible
prever dónde será necesario implantar la red de comunicaciones.
Respecto al segundo método, el llamado modo ad-hoc, adolece de serios inconve-
nientes:
Nodo pasarela
Red de Sensores
Internet
Usuario
Nodo
Sensor objetivo
Movilidad de nodos
Baja Media Alta
Baja RFID
Capacidad de cómputo
Media
WSN
MANets VANets
Alta
Figura I.3: Taxonomı́a de los diferentes tipos de redes ad hoc, clasificadas en base a la
capacidad de proceso y movilidad de sus nodos
Capı́tulo II.
II ,
muestra una serie de carencias significativas.
La primera de ellas es que un alto porcentaje de los autores trabajan con supuestos
de partida que ’rompen’ claramente las reglas del juego, puesto que no respetan alguna
de las caracterı́sticas definitorias de estas redes.
Por un lado, existen una serie de propuestas, como [7, 8], que introducen esque-
mas con necesidad de una infraestructura previa y centralizada de comunicaciones.
Además, utilizan criptografı́a asimétrica, completamente fuera de las posibilidades
reales de la mayorı́a de los dispositivos que conforman este tipo de redes.
Otras asumen la existencia de hardware anti-manipulación en los dispositivos [7,
9, 10]. Aunque es un campo activo de investigación y puede sin duda aceptarse en
algunos escenarios, como la transmisión multimedia y la protección de contenidos dig-
itales, resulta sin embargo inviable en la mayorı́a de las situaciones, debido al impor-
tantı́simo incremento en coste que supone.
En resumen, el análisis anterior ha revelado la existencia de un hueco en la investi-
gación realizada hasta el momento dentro del área que pretende cubrir esta tesis. Este
espacio por desarrollar consiste en la inexistencia de buenas propuestas de protoco-
los de seguridad ligeros, que proporcionen tanto privacidad como autenticación, y que
puedan ser ejecutados sobre dispositivos de gama baja; es decir dispositivos con una
capacidad de cómputo limitada y que no dispongan de hardware anti-manipulación.
De esta forma, pretendemos encontrar soluciones realistas y económicas que puedan eje-
cutarse con el hardware que se encuentra fácilmente en el mercado.
La autenticación de dispositivos.
A los anteriores requisitos, los autores añadirı́an la necesidad de una mayor inves-
tigación en el ámbito de la privacidad de las comunicaciones, a través de algoritmos de
cifrado especialmente diseñados para ser ejecutados en dispositivos de baja capacidad
computacional. Dado el enfoque eminentemente criptográfico de esta tesis, el esfuerzo
principal se ha centrado en los mecanismos de cifrado y autenticación que, por otra
parte, constituyen los pilares básicos de toda solución de seguridad.
Por estas razones, y a grandes rasgos, los objetivos principales que se pretenden
alcanzar en este trabajo de tesis son:
A continuación se describen estos objetivos con mayor detalle, comenzando con los
relacionados con la protección de la privacidad de las comunicaciones.
Estudio del rendimiento obtenido por estos registros, que denominaremos LFSRs
extendidos, en comparación con los tradicionales. Se muestran los beneficios de
este enfoque, proporcionando datos empı́ricos que avalan los resultados, y que
demuestran que éste método resulta mucho más eficiente que los LFSRs tradi-
cionales.
21
22 II . A NTECEDENTES Y ESTADO DE LA CUESTI ÓN
II .1 Ejemplo. El conjunto de los números enteros Z y la operación suma definen un grupo abeliano.
El elemento neutro es el 0, mientras que el inverso de un elemento a ∈ Z es −a.
II .2 Ejemplo. Sin embargo, el mismo conjunto de los números enteros Z bajo la operación multipli-
cación no define un grupo abeliano, ya que ningún elemento excepto el par {+1, −1} tiene inverso.
II .3 Ejemplo. El orden del grupo abeliano aditivo Zn es n. Por otro lado, el orden del grupo multi-
plicativo Z∗n es φ(n), siendo φ la función de Euler.
II .8 Definición. (Cuerpo): Un cuerpo es una terna < F, ·, + > donde < F, ·, + > es un
grupo abeliano aditivo con elemento neutro 0, < F\{0}, · > es un grupo multiplicativo
con elemento identidad 1 y < F, ·, + > verifica la propiedad distributiva.
En otras palabras, dicho grupo forma un cuerpo si todo elemento distinto de 0 tiene
un inverso multiplicativo. Es fácil ver que el inverso multiplicativo de a es único, por
lo que podemos denotarlo con un sı́mbolo especial a−1 . Es decir, si a , 0:
aa−1 = a−1 a = 1
px = x + x + . . . + x = 0
| {z }
p veces
Un cuerpo < F, ·, + > suele denotarse Fpd , donde p es la caracterı́stica del cuerpo y pd
es el número de elementos del mismo. Si tal p no existe, entonces la caracterı́stica de F
es 0.
d
X
f (x) = bi · xi , bi ∈ Fp , bd , 0.
i=0
α(x) = a3 x3 + a2 x2 + a1 x1 + a0 x0 , a0 , a1 , a2 , a3 ∈ F3 = {0, 1, 2}
El número de elementos (polinomios) del cuerpo es 34 = 81.
φ
Z+ → Z+
n 7→ φ(n) = |{d ∈ Z+ : mcd(d, n) = 1, 1 ≤ d < n}|
II .8 Ejemplo. Ası́, φ(9)=6, ya que los seis números 1, 2, 4, 5, 7 y 8 son primos relativos con 9; esto
es, no comparten divisores comunes.
II .9 Ejemplo. El cuerpo finito GF(2) contiene únicamente los elementos 0 y 1, y satisface las sigu-
ientes tablas de suma y multiplicación.
+ 0 1
0 0 1
1 1 0
* 0 1
0 0 0
1 0 1
26 II . A NTECEDENTES Y ESTADO DE LA CUESTI ÓN
II .10Ejemplo. Por ejemplo, para GF(23 ), podemos utilizar cualquiera de los dos polinomios
irreducibles x3 + x2 + 1 y x3 + x + 1 como módulo. Si usamos el último de ellos, los elementos
de GF(23 ) pueden representarse como polinomios de grado menor que 3. De esta forma, quedarı́a:
x3 = −x − 1 = x + 1
x4 = x(x3 ) = x(x + 1) = x2 + x
x5 = x(x2 + x) = x3 + x2 = x2 − x − 1 = x2 + x + 1
x6 = x(x2 + x + 1) = x3 + x2 + x = x2 − 1 = x2 + 1
x7 = x(x2 + 1) = x3 + x = −1 = 1 = x0
Existen, sin embargo, otras formas, todas equivalentes, de representar los elementos
de un cuerpo finito. En el Cuadro II.1 pueden encontrarse estas formas resumidas. De
izquierda a derecha, las columnas muestran las representaciones que utilizan las difer-
entes potencias del elemento generador, la representación polinomial, la representación
en forma de n-tuplas binarias, que codifican los coeficientes de la representación poli-
nomial y, por último, la equivalencia decimal de la representación binaria.
El conjunto de polinomios de la segunda columna es cerrado respecto a las opera-
ciones de suma y multiplicación módulo x3 + x + 1 y forma, por tanto, un cuerpo finito.
Este cuerpo particular se denomina cuerpo extensión de grado 3 de GF(2), denotado
GF(23 ), donde el cuerpo GF(2) se llama cuerpo base.
Este concepto resulta esencial para este trabajo, por lo que será ampliado en la sigu-
iente sección.
II .11 Ejemplo. El conjunto de los números complejos, C, forma un cuerpo extensión de los números
reales R y éstos, a su vez, constituyen una extensión de los números racionales Q.
√
II .12Ejemplo. Como se ha visto en el ejemplo anterior, C es una extensión de Q. Como 2 es un
√
cero de x2 − 2, 2 es también un elemento algebraico sobre Q. Además, i es un elemento algebraico
sobre Q, pues es un cero de x2 + 1.
II .1.5. Generadores
El concepto de generador, y sus propiedades asociadas, representan otro de los pi-
lares básicos sobre los que se apoya el desarrollo de la propuesta realizada en esta tesis.
Los generadores son imprescindibles para la construcción de polinomios primitivos en
GF(2n )m y, éstos, a su vez, necesarios para el desarrollo de un LFSR definido sobre este
cuerpo extendido.
Por estas razones se describirán a continuación sus caracterı́sticas más importantes
y dos métodos diferentes para su obtención.
II .13 Ejemplo. Considérese Z12 con generador α = 1. Como el máximo común divisor de 3 y 12 es
3, 3=3·1 genera un subgrupo de 12/3 = 4 elementos:
Finalmente, puesto que el mcd de 12 y 5 es 1, 5 genera un subgrupo de 12/1 = 12 elementos. Esto es,
5 es un generador de todo el grupo Z12 .
Representación
Polinomio
decimal
x4 16
x + x2
6 68
x + x5 + x2
6 100
x7 128
x + x5 + x4
7 176
x7 + x6 192
x7 + x6 + x4 208
x + x6 + x5 + x4 + x3
7 248
Por ejemplo, para el cuerpo GF(232 ), que supone el caso más desfavorable, el número
de exponenciaciones necesarias se reduce en el peor de los casos a 5. En el Cuadro II.4
puede encontrarse una comparativa entre este método y el presentado en la sección
anterior. Puede encontrarse también la descomposición en factores primos del orden
II .1. F UNDAMENTOS DE LOS CUERPOS DE G ALOIS EXTENDIDOS 31
Factor de mejora
Método básico 28.66
Método de los factores primos 46.76
verifica que:
El cuerpo compuesto resultante se denota por GF(2n )m donde GF(2n ) se conoce como
el cuerpo base sobre el que se define el cuerpo compuesto.
Un cuerpo compuesto GF(2n )m es isomorfo al cuerpo GF(2k ), con k = nm [7]. Esto
significa que, por ejemplo, puede trabajarse indistintamente en GF(24 )4 o GF(216 ). Sin
1 El hardware utilizado es un PC de sobremesa estándar, de caracterı́sticas medias. Los detalles de su
embargo, a pesar de que los dos cuerpos de orden 2nm son isomorfos, la complejidad al-
gorı́tmica de sus operaciones básicas, como la suma y la multiplicación, son claramente
diferentes y depende principalmente de la elección de n y m y de los polinomios Q(y)
y P(x).
Por otra parte, una extensión GF(2n ) del cuerpo GF(2) puede interpretarse como un
espacio vectorial n-dimensional sobre GF(2). Por tanto, cada elemento de GF(2n ) puede
representarse como una combinación lineal de elementos del cuerpo base GF(2).
El conjunto {1, α, α2 , ..., αm−1 }, donde α es una raı́z del polinomio prim-
II .18 Definición.
itivo P(x) de grado m, se denomina base canónica o estándar.
De forma similar, asumiendo que ω es una raı́z de Q(y), α una de P(x) y que am-
bos polinomios son primitivos, los elementos del cuerpo base GF(2n ) pueden represen-
n
tarse como {1, ω, ω2 , . . . , ω2 −1 }. A su vez, los elementos del cuerpo compuesto GF(2n )m
nm
pueden representarse como {1, α, α2 , . . . , α2 −1 }.
De esta forma, un elemento A ∈ GF(2n )m puede escribirse como:
m−1
X
A= ai αi
i=0
II .14 Ejemplo. En este ejemplo se analizará cómo se define el cuerpo compuesto GF(23 )2 ). Sea Q(y) =
y + y + 1 un polinomio primitivo en GF(2), que se utilizará para formar el cuerpo base GF(23 ). Sea
3 2
Q(a) = a3 + a2 + 1 = 0
ω0 7→ 1
ω1 7→ ω
ω2 7→ ω2
ω3 7→ ω2 + 1
ω4 = ω3 ω = (ω2 + 1)ω = ω3 + ω 7→ ω2 + ω + 1
ω5 = ω3 ω2 = (ω2 + 1)ω2 = ω4 + ω2 = ω2 + ω + 1 + ω2 7→ ω + 1
ω6 = ω3 ω3 = (ω2 + 1)(ω2 + 1) = ω4 + ω2 + ω2 + 1 = ω2 + ω +
1 + ω2 + ω2 +
1 7→ ω2 + ω
Es fácil comprobar que, en efecto, ω7 =P 1, ya que ω7 = ω6 ω = (ω2 +ω)ω = ω3 +ω2 = ω2 +1+ ω2 = 1.
Si los elementos se representan como i ai α , para ai ∈ {0, 1} es posible asignar un código binario a
i
ω0 7→ 1
ω1 7→ ω
ω2 7→ ω2
ω3 7→ ω2 + 1
ω = ω ω = (ω + 1)ω = ω + ω 7→ ω2 + ω + 1
4 3 2 3
ω5 = ω3 ω2 = (ω2 + 1)ω2 = ω4 + ω2 = ω2 + ω + 1 + ω2 7→ ω + 1
ω6 = ω3 ω3 = (ω2 + 1)(ω2 + 1) = ω4 + ω2 + ω2 + 1 = ω2 + ω +
1 + ω2 + ω2 +
1 7→ ω2 + ω
En pocas palabras, y de una forma muy global, una red MANet es una red autónoma,
inalámbrica, formada por nodos con cierta capacidad de movimiento [11]. Por supuesto, puede
incluir nodos cableados y estáticos (que no son más que un caso particular de los
primeros).
Movilidad de nodos
Baja Media Alta
Baja RFID
Capacidad de cómputo
Media
WSN
MANets VANets
Alta
Figura II.1: Taxonomı́a de los diferentes tipos de redes ad hoc, clasificadas en base a la
capacidad de proceso y movilidad de sus nodos
Como caracterı́stica adicional, y a diferencia de las redes ad-hoc tradicionales, las re-
des MANet presentan lo que se denomina comportamiento multisalto, definido de forma
implı́cita e inserapable del diseño de la red. El aspecto multisalto, en contraposición al
tradicional enrutamiento punto a punto, otorga a la red la capacidad de utilizar a modo
de repetidores los nodos intermedios entre origen y destino. Esto confiere a este tipo
de redes una enorme robustez ante, por ejemplo, el fallo de uno o varios de sus nodos
[12].
Como hemos analizado en el capı́tulo de introducción, el creciente interés en las
redes MANet se sustenta en la diversidad y utilidad de las aplicaciones a las que este
tipo de redes se prestan. Otros de los múltiples ejemplos posibles los constituyen los
sistemas de difusión de anuncios y/o alertas en zonas usualmente frecuentadas por
multitud de usuarios (como los centros comerciales, las estaciones de trenes o los aerop-
uertos), o las aplicaciones de intercambio de información entre varios usuarios [13].
En principio, cualquier dispositivo con cierta capacidad de cómputo y de comu-
nicaciones puede formar parte de una MANet. Por ejemplo, una PDA, un ordenador
portátil o un simple teléfono móvil. Esta cualidad confiere a este tipo de redes un aban-
ico de posibilidades enorme, por lo que no resulta descabellado decir que la tecnologı́a
de las redes MANet puede considerarse una de las tecnologı́as con más futuro en los
próximos años. Los usos imaginables son prácticamente infinitos, en todos los ámbitos
de la tecnologı́a, desde el personal y del hogar hasta el industrial.
Pero, como no podı́a ser de otra manera, no todo en las redes MANet son ventajas
y caracterı́sticas favorables. El diseño de este tipo de redes presenta una alta dificul-
tad debido a su carácter espontáneo y dinámico. Máxime si tenemos en cuenta que
II .2. A NTECEDENTES TECNOL ÓGICOS 37
Composición de los nodos Por otro lado, un sensor suele estar compuesto por un
microcontrolador, memoria, algún tipo de sensor ambiental, como sensores de temper-
atura, humedad o presencia, y un transmisor de radio. La potencia de este transmisor
es la que define, en gran medida, el rango de distancias de comunicación que pueden
alcanzar los nodos de la red. En el Cuadro II.5 pueden encontrarse las potencias habit-
uales de los dispositivos tı́picos utilizados en este tipo de redes.
Las potenciales aplicaciones de las WSN son, como las de todos los tipos de re-
des ad-hoc móviles, prácticamente ilimitadas. Las más comunes incluyen escenarios
de guerra o de conflicto, con el fin de monitorizar un área enemiga o amiga, y la moni-
torización de edificios o de entornos industriales. Por supuesto, la seguridad es crucial
en estos escenarios, dada la importancia de la información que fluye por ellos.
Sin embargo, dados sus estrictos requisitos, proporcionar mecanismos de seguridad
efectivos para redes WSN es una tarea especialmente compleja y delicada. En general,
en este campo de investigación se considera que los retos globales a asumir son los
siguientes:
Naturaleza inalámbrica de la comunicación
38 II . A NTECEDENTES Y ESTADO DE LA CUESTI ÓN
II .2.1.3. RFID
Continuando hacia abajo en la escala de capacidad de proceso, encontramos la tec-
nologı́a RFID (Radio Frequency IDentification). La mayorı́a de los nodos de una red de
este tipo, denominados etiquetas (tags) RFID, son dispositivos de pequeño tamaño, en
ocasiones incluso en forma de una simple pegatina adhesiva, que pueden ser adheri-
das o incorporadas a un producto, animal o persona. De hecho, cualquier visitante de
un supermercado está familiarizado con esta tecnologı́a, que ha sido utilizada durante
años para evitar el hurto de productos.
Una etiqueta RFID es un dispositivo muy sencillo consistente en un pequeño cir-
cuito integrado que contiene un número identificador, único para dicha etiqueta (a
diferencia, por ejemplo, de los códigos de barras tradicionales, que identifican grupos
de productos). Para completar el sistema, es necesario un dispositivo lector, que consulta
las etiquetas situadas en sus proximidades y lee sus identificadores. Éstos se consul-
tan posteriormente en una base de datos que contiene información adicional sobre los
artı́culos asociados a las etiquetas.
Tipos de etiquetas RFID A grandes rasgos, existen dos grandes tipos de etiquetas
RFID, que se clasifican en función de su capacidad energética y, en consecuencia, com-
putacional:
(a) Detalle del minúsculo microprocesador (b) Etiqueta activa, de mayor tamaño y ca-
de la etiqueta pasiva, utilizadas habitual- pacidad computacional
mente para evitar el hurto en centros com-
erciales
Frecuencias de operación y usos Otro criterio habitual para la clasificación de los sis-
temas RFID consiste en el rango de frecuencias de operación que éstos utilizan. Hasta
el momento, se han aceptado cuatro tipos de sistemas:
De baja frecuencia: entre 125 ó 134,2 Kilohercios.
De alta frecuencia: 13,56 Megahercios.
UHF o de frecuencia ultraelevada: 868 a 956 Megahercios.
Microondas: 2,45 Gigahercios.
Los sistemas más extendidos son, sin lugar a dudas, los dos primeros, pues los
sistemas UHF, por ejemplo, no han sido regulados de forma global y común en todo el
mundo, de forma que existen ciertas restricciones en su uso.
Estas frecuencias de operación determinan también en gran medida el coste, el al-
cance y las aplicaciones posibles. En general, los sistemas que emplean frecuencias
bajas tienen asimismo costes bajos, pero también un rango de distancia de uso más
limitado. Por estas razones, las etiquetas de baja frecuencia se utilizan comúnmente
para la identificación de animales, seguimiento de stocks en almacenes o como llave de
automóviles con sistema antirrobo.
Por otro lado, los que emplean frecuencias más altas proporcionan distancias y ve-
locidades de lectura mayores. De esta forma permiten usos muy diversos, como el
control de libros en bibliotecas, seguimiento de palés, control de acceso en edificios,
seguimiento de equipaje en aerolı́neas, identificación de artı́culos de ropa o seguimien-
to de pacientes en centros hospitalarios. En este sentido, un uso muy extendido de este
tipo de etiquetas es la identificación de acreditaciones, substituyendo a las anteriores
tarjetas de banda magnética. Sólo es necesario acercar estas insignias a un lector para
autenticar al portador.
Por último, las etiquetas RFID de microondas se utilizan, por ejemplo, en el control
de acceso en vehı́culos de gama alta.
Seguridad vs privacidad Debido a que cada etiqueta RFID está asociada de forma
unı́voca a un artı́culo concreto, surgen inmediatamente cuestiones relacionadas con la
privacidad de su uso. Por ejemplo, es el caso de las prendas textiles que la persona lleva
consigo y que permite desde ese momento su seguimiento.
40 II . A NTECEDENTES Y ESTADO DE LA CUESTI ÓN
Técnica Descripción
Estos códigos especı́ficos desactivan de forma
permanente la etiqueta y, por tanto, evitan su posterior
lectura y seguimiento. Esta opción está especialmente
Códigos ’de la muerte’ indicada en aquellos artı́culos que requieren de una
monitorización durante su proceso de fabricación y
transporte, pero que no se desea que ésta siga siendo
posible una vez vendidos.
Introducir el producto que contiene la etiqueta RFID en el
interior de una jaula de Faraday2 lo que hace imposible su
lectura. Tiene la ventaja de que el usuario puede decidir
Jaula de Faraday cuándo la etiqueta puede ser leida o no (como en el caso
de un pasaporte). Por el contrario, sufre el inconveniente
de que, dependiendo del tamaño y objeto del producto,
puede resultar incómodo o, incluso, imposible.
El ’Bloquedador de etiquetas’ [19] consiste en un
dispositivo que provoca interferencias de forma artificial
y deliberada, y que hacen creer a los lectores no
Bloqueador
autorizados que un gran número de etiquetas RFID están
presentes. Ası́, el lector no autorizado no puede distinguir
la etiqueta legı́tima de las falsas.
Cuadro II.6: Comparación de los diferentes tipos de métodos fı́sicos para preservar la
privacidad de los sistemas RFID
Para tratar de solucionar estos problemas, pueden utilizarse dos enfoques básicos.
El primero consiste en utilizar medidas fı́sicas, con el fin de desactivar o destruir la eti-
queta, e impedir ası́ su funcionamiento y los problemas de privacidad que ello acarrea.
En el Cuadro II.6 puede encontrarse un resumen de los métodos propuestos hasta la
fecha.
El segundo enfoque propone el uso de diversas técnicas criptográficas con el fin
de conseguir que sólo las partes autorizadas puedan acceder al identificador real de la
etiqueta. Un buen resumen de estas técnicas puede encontrarse en [18].
Debido a las importantes diferencias en cuanto a la capacidad computacional de ca-
da tipo de etiqueta RFID, resulta necesario definir diversos mecanismos para propor-
cionar por un lado seguridad (es decir, la capacidad del sistema RFID para mantener
la información transmitida entre etiqueta y lector secreta) y, por otro, privacidad (la ca-
pacidad del sistema para mantener oculto el significado de la información entre etiqueta
y lector) que se adapten a estas caracterı́sticas.
El futuro del RFID Las previsiones de crecimiento del mercado RFID no dejan de au-
mentar año tras año. De los 1970 millones de etiquetas vendidas en 2008 y de los 5250
millones de dólares de negocio en 2008, se pasó a 2350 y 5560 millones de etiquetas y
negocio, respectivamente, en 2009 [20]. Sin embargo, la tendencia parece haberse acel-
erado en los últimos años y se espera que el mercado crezca aún a mayor ritmo en los
próximos años, a pesar de la crisis ecónomica.
La tecnologı́a RFID se convertirá en una parte importante de la futura y, ya presente
en ciertos aspectos, Internet de las cosas y será, sin duda, cada vez más ubicua hasta estar
presente en cada aspecto de la vida. Esta es una afirmación literal, pues la implantación
de pequeños dispositivos RFID bajo la piel se está convirtiendo en una práctica relati-
II .2. A NTECEDENTES TECNOL ÓGICOS 41
(a) Proceso de inserción de la etiqueta RFID (b) Resultado final: las manos se han con-
bajo la piel, para lo que se realiza una vertido en una tarjeta de crédito que nunca
pequeña incisión con anestesia local se olvida
II .2.1.4. VANets
Las redes VANet (Vehicular Ad-Hoc Network) conforman otro de los grandes tipos
de redes ad hoc móviles, con la particularidad de que los nodos son vehı́culos o el
propio equipamiento de tráfico, como por ejemplo señales verticales (véase la Figura
II .4).
El objetivo principal de estos sistemas es proporcionar un mejor conocimiento de
las condiciones de la carretera a los conductores, con el fin de reducir el número de
accidentes y hacer que la conducción sea más cómoda y fluida. Ası́mismo, estas re-
des permitirán el acceso a contenidos multimedia e Internet, como la compartición de
archivos entre diferentes vehı́culos.
En lo relativo a la seguridad, al ser una extensión de las redes ad hoc móviles tradi-
cionales, las VANets implican los mismos desafı́os, aunque si cabe aún más complica-
42 II . A NTECEDENTES Y ESTADO DE LA CUESTI ÓN
Protocolos reactivos: Estos protocolos establecen las rutas necesarias bajo deman-
da. Cuando un nodo quiere comunicarse con otro, con el que no existe una ruta
establecida, se activa el protocolo de establecimiento para generar una nueva. El
ejemplo más conocido de este tipo de protocolos es el denominado AODV [24].
II .2.2.1. AODV
El protocolo AODV (Ad-Hoc On-Demand Distance Vector), fue definido en 2003 por
la IETF y se describe con detalle en [26]. La filosofı́a de AODV, como la de todos los
protocolos reactivos, es que la información sobre la topologı́a de la red sólo se envı́a
cuando es necesario, es decir bajo demanda.
Cuando un nodo quiere enviar tráfico a otro con el que no existe ruta establecida, el
primero genera un mensaje de petición de ruta (Route request, RREQ), que es enviado
posteriormente de forma masiva a los nodos vecinos, como puede observarse en la
Figura II.5.
Se considera que un ruta ha sido establecida cuando el mensaje RREQ ha llegado al
destino o a un nodo intermedio con una ruta válida hasta el destino. Mientras la ruta
exista entre ambos extremos, el protocolo AODV no lleva a cabo acciones de manten-
imiento.
II .2. A NTECEDENTES TECNOL ÓGICOS 43
Ruta RREQ A
Ruta RREQ B
Ruta RREP
4
6
3
2 7
5
1 8
Nodo
objetivo
10
9
Figura II.5: Flujo tı́pico de mensajes RREQ y RREP. De las dos rutas disponibles (lı́nea
punteada y contı́nua negra), el sistema elige la segunda, más corta (en lı́nea continua
azul).
II .2.2.2. OLSR
El protocolo OLSR, Optimized Link State Routing, se describe con detalle en el RFC
3626 [27] y, a diferencia del AODV, mantiene la información sobre las rutas activas
constantemente actualizadas [28].
Esto permite que no haya un retardo inicial en el inicio de las transmisiones, a cam-
bio de un flujo constante de pequeños mensajes (que, en cualquier caso, son de unos
pocos bytes y completamente configurables).
Estos mensajes tratan de mantener actualizada la información sobre los nodos ve-
cinos, e incluyen información tal como direcciones IP o números de secuencia. Tras
recibir esta información, cada nodo construye y mantiene su propia tabla de rutas, de
forma que pueda calcular, con el algoritmo de rutas más cortas, el camino más eficiente
a cualquier otro nodo de la red.
La información almacenada en esta tabla sólo se actualiza cuando:
Otra de las caracterı́sticas más importantes del protocolo OLSR es el uso de heurı́sticas
especı́ficamente diseñadas para la reducción de mensajes de difusión duplicados. Esta
técnica recibe el nombre de multi-point relays, o MPR, y obtiene resultados muy desta-
cables [29, 30].
La idea central de su funcionamiento consiste en elegir una serie de nodos es-
pecı́ficos como “retransmisores” autorizados, de forma que sólo dichos nodos son los
44 II . A NTECEDENTES Y ESTADO DE LA CUESTI ÓN
(a) Esquema de conexiones entre nodos de (b) Comparación del flujo de mensajes
la red. El conjunto MPR aparece sombreado originado por un único mensaje de difusión
en gris oscuro, formado por los nodos N1 y original. A la derecha, sólo los nodos en
N6 verde están autorizados para la retrans-
misión
Figura II.6: Técnica de MPR, que reduce de forma significativa el número de retransmi-
siones, perteneciente al protocolo OLSR.
Durante los últimos años, los nodos tı́picos de las redes ad-hoc móviles han sido
habitualmente considerados como dispositivos demasiado restringidos para soportar
criptografı́a, pero esta suposición ha cambiado últimamente. Haciendo uso de los es-
quemas de curvas elı́pticas (ECC), más eficientes que su contrapartida basada en el
problema de la factorización, es posible obtener primitivas para cifrar datos (ECIES),
firmar y verificar firmas (ECDSA) o negociar claves (ECDH).
En cualquier caso, sigue siendo innegable que sólo los nodos más caros y de alta
gama disponen de estas capacidades y que, incluso en estos casos, los requerimientos
computacionales y de memoria de estos algoritmos siguen siendo altos: una firma uti-
lizando ECDSA necesita aproximadamente 2 segundos para completarse, requiriendo
un total de 17kB de memoria ROM y 1.5kB de RAM [42].
Como resulta lógico, los requisitos para las funciones hash y HMAC son menores.
Por ejemplo, la función SHA-1, esencial en el mecanismo de autenticación que propon-
dremos en el Capı́tulo V, puede implementarse en sólo 3kB de ROM.
Desfortunadamente, tanto el estándar 802.15.4 como el soporte de curvas elı́pticas
son soluciones ’elitistas’, en el sentido de que encarecen considerablemente el coste
de los nodos que las implementan. Por esta razón, no resultan adecuados en entornos
donde el número de nodos es muy alto y provocarı́a costes prohibitivos. En conclusión,
parece claro que, aún a dı́a de hoy, sigue existiendo la necesidad de aportar primitivas
criptográfivas, en este caso de cifrado, que no requieran de soporte hardware y puedan
correr sin modificación en todo tipo de plataformas existentes, especialmente en aque-
llas de menor coste y capacidad computacional.
IEEE 802.11
Contraseñas
Bluetooth
Cadena de claves
El patito resucitador
Simétricos
Pre-distribución de pares de claves
Híbridos
Esquemas de
CA distribuidas
autenticación
Basados en identidad
Subgrupo de confianza
Asimétricos
necesitar visión directa entre los dispositivos a comunicar y una menor distancia de
transmisión. Por tanto, puede decirse que la tecnologı́a IrDA está recomendada para
PANs, con el fin de conectar éstos con un ordenador. A pesar de que no se considera la
implementación de ningún tipo de seguridad en estos protocolos, el extremedamente
corto rango de comunicaciones y la necesidad de lı́nea de visión directa puede propor-
cionar una suerte de autenticación “fı́sica”.
un contacto fı́sico entre dispositivos, de forma que, una vez conectados, éstos no
respondan a nuevas peticiones que no provengan del dispositivo con el que se
vincularon inicialmente 3 . Sin embargo, este requisito es inviable en ciertos esce-
narios, como una simple red de sensores.
que ciertos animales consideran como un progenitor al primer ser vivo, incluso personas, que ven tras su
nacimiento. Este vı́nculo se mantiene para el resto de su vida, al estilo de la propuesto realizada en este
modelo
II .3. E STADO DEL ARTE 49
51
52 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
El objetivo es, por tanto, utilizar cuerpos finitos más apropiados para la arquitectura de
los actuales microprocesadores. En este sentido, las elecciones naturales son los cuerpos
de Galois extendidos, con 2n elementos, donde n está relacionado con el tamaño de los
registros del propio microprocesador, que normalmente serán bytes o palabras de 16 ó
32 bits.
De esta forma, los elementos del cuerpo encajan perfectamente en una unidad de
almacenamiento, de forma que puede ser manipulada de forma eficiente en software.
Además, la tasa de generación de secuencia de salida también se ve incrementada:
hasta 8, 16 ó 32 bits por cada pulso de reloj.
Desafortunadamente, las operaciones de multiplicación y división sobre cuerpos de
Galois extendidos son computacionalmente caras [5], especialmente cuando se com-
paran con la suma binaria en GF(2), que se implementa fácilmente con una simple
operación XOR. Por tanto para acelerar en lo posible estas operaciones la mayorı́a
de las implementaciones software que trabajan en el cuerpo GF(28 ) utilizan tablas de
búsqueda precomputadas [6, 7].
Por otro lado, el cuerpo de estructura adecuada y tamaño inmediatamente superior
a GF(28 ) es GF(216 ). Sin embargo, utilizar dicho cuerpo tiene un impacto muy significa-
tivo en las operaciones aritméticas como, por ejemplo, la multiplicación. En este caso,
una tabla de búsqueda completa para la operación multiplicación ocuparı́a 8 GB, muy
por encima de la capacidad de memoria de la mayorı́a de sistemas. En entornos con
memoria limitada, como redes de sensores o MANets, el problema se agrava aún más.
En este capı́tulo se propone el uso de técnicas que realizan las operaciones de mul-
tiplicación y división en un cuerpo extensión de GF(2n ). Ası́, los elementos del cuer-
po GF(2k ) se representan en términos de elementos de un subcuerpo GF(2n ), donde
k = n · m. El cuerpo compuesto GF((2n )m ) puede entenderse como una representación
de una extensión de grado m del cuerpo GF(2n ), denominado cuerpo base.
Por otro lado, el segundo gran bloque temático de este capı́tulo consiste en un estu-
dio exhaustivo sobre ciertas técnicas de implementación eficiente en software y, sobre
todo, cómo se adaptan éstas a los LFSRs.
Con este estudio se pretende extraer diversas conclusiones y responder a ciertas
preguntas, como qué técnica es más adecuada para su uso en LFSRs, qué grado máximo
de mejora cabe esperar de cada una de ellas y cómo les afectan, por ejemplo, la capaci-
dad de la plataforma hardware sobre la que se ejecutan.
Estructura del capı́tulo En la Figura III.1 pueden encontrarse esquematizados los dos
grandes enfoques propuestos a la hora de mejorar el rendimiento de los LFSRs, que
conforman el presente capı́tulo. El resto del mismo se organiza de la siguiente forma.
En la sección III.2 se introducen y describen brevemente los registros de desplaza-
miento extendidos, ası́ como las variaciones en su funcionamiento interno respecto a
los registros tradicionales. Estas diferencias radican esencialmente en la función de re-
alimentación, que ahora implica multiplicaciones sobre cuerpos extendidos. Por esta
razón, en la sección III.4 se introducen los diversos métodos de realizar multiplica-
ciones sobre estos cuerpos, analizándose los resultados obtenidos en el apartado III.4.1.
A continuación, en la sección IV.4.1.1, se describen diversas técnicas para la imple-
mentación eficiente de estos registros en software. Una detallada comparativa entre
los diversos métodos y el análisis de los resultados obtenidos puede encontrarse en el
apartado IV.4.3. Finalmente, en la sección III.7 se lleva a cabo un exhaustivo análisis
estadı́stico de las secuencias de salida generadas por este tipo de registro, que asegura
las buenas propiedades criptográficas del mismo.
El capı́tulo se completa con un análisis de todos los resultados obtenidos y unas
conclusiones finales en la sección IV.8.
III .1. I NTRODUCCI ÓN 53
l−1
X
st+l = cl ci st+i , ci ∈ GF(2n ),
i=0
• ""
ro
l
X
p(x) = c0 + c1 x + c2 x + ... + cl−1 x
2 l−1
+x =
l
ci xi , ci ∈ GF(2n ).
i=0
Tal y como se analizó en la sección II.1.2 (pág. 26 del Capı́tulo II), los elementos del
cuerpo GF(2n ) se representan habitualmente como polinomios de grado menor que n
con coeficientes en GF(2). De esta forma, por ejemplo, el elemento a de GF(24 ), notado
a = 0111, puede representarse por el polinomio a(x) = x2 + x + 1.
Con la representación polinomial las operaciones aritméticas se llevan a cabo ha-
ciendo uso de un polinomio irreducible R (no factorizable en factores no triviales) de
grado n. Este polinomio se define sobre un cuerpo binario de la siguiente forma:
La operación suma en este cuerpo sigue siendo simplemente la suma módulo dos,
u operación XOR, para cada par de elementos. Con la representación polinomial, el
proceso es tan sencillo como sumar los polinomios en la forma habitual y reducir sus
coeficientes según la caracterı́stica del cuerpo GF(2).
56 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Representación
n R
hexadecimal
8 x8 + x6 + x3 + x2 + 1 0x14D
16 x + x + x12 + x7 + x6 + x4 + x2 + x + 1
16 14 0x150D7
32 x32 + (x24 + x16 + x8 + 1)(x6 + x5 + x2 + 1) 0x165656565
III .1 Ejemplo. Un sencillo ejemplo permite ilustrar el proceso. La suma de dos elementos de GF(28 ),
representados como sendos polinomios p1 y p2 (de grado menor que 8), quedarı́a de la siguiente forma:
p1 + p2 = (x6 + x3 + x2 + 1) + (x7 + x6 + x5 + x2 + 1) =
= x7 + 6 + x5 + x3 +
2x 2 + 2 =
2x
= x7 + x5 + x3 .
p1 · p2 = (x6 + x3 + x2 + 1) · (x7 + x6 + x5 + x2 + 1) =
= x13 + x12 + x11 + x8 + x6 + x10 + x9 + x8 +
+ x5 + x3 + x9 + x8 + x7 + x4 + x2 + x7 + x6 + x5 + x2 + 1 =
= x13 + x12 + x11 + x10 + x8 + x4 + x3 + 1
En esto punto, es necesario reducir el resultado módulo R, de forma que x13 + x12 + x11 + x10 + x8 + x4 +
x3 +1 módulo x8 +x6 +x3 +x2 +1 = 11110100011001 módulo 101001101 = 1101001 = x6 +x5 +x3 +1.
Para que se comprenda con facilidad el resultado, se detallará el proceso de reducción modular a través
de la división paso a paso:
11110100011001
101001101 ⊕
1010010111001
101001101 ⊕
1101001
III .2. R EGISTROS DE DESPLAZAMIENTO EN GF(2n )m 57
III.3.1. Rendimiento
El aspecto más influyente en el rendimiento final del registro es, sin duda, la elec-
ción de la dimensión del cuerpo GF(2n ), con n=8, 16 ó 32, sobre el que funcionará el
LFSR.
Al incrementar el valor de n, el rendimiento global del LFSR aumentará, pues se
incrementará proporcionalmente el número de bits generados por el registro en cada
salida. Sin embargo, también aumenta el coste computacional de las operaciones im-
plicadas, especialmente el de la multiplicación, para la obtención de dicha salida.
Otro factor muy importante a tener en cuenta está relacionado con la posición y
número de realimentaciones, que influirán directamente en el rendimiento y, de forma
secundaria, en la seguridad.
En primer lugar, para conseguir un LFSR de periodo máximo sobre GF(2n )m , las
posiciones de realimentación deberı́an ser primas entre sı́, es decir no compartir di-
visores comunes. Por otra parte, el número de realimentaciones deberı́a ser pequeño
para minimizar el número de operaciones implicadas y maximizar ası́ el rendimiento.
Este problema se acentúa en la arquitectura propuesta, donde las multiplicaciones son
computacionalmente más costosas.
Sin embargo, un número demasiado reducido de realimentaciones también puede
llevar a un fácil criptoanálisis de las secuencias producidas por el LFSR, cuando éste
se utilice como pieza básica de un cifrador. Todos estos aspectos se analizará a contin-
uación.
III.3.2.1. FPDS
III .2 Definición. (FDPS) Un conjunto G forma un conjunto de diferencias completamente
positivas si todas las diferencias positivas entre los elementos de G son diferentes.
III .3. C ONSIDERACIONES DE DISE ÑO 59
Longitud
Periodo del
de clave
n m LFSR
efectiva
resultante
(bits)
8 17 136 2136 − 1
16 9 144 2144 − 1
32 5 160 2160 − 1
Cuadro III.2: Valores de los parámetros n y m adecuados para el uso de LFSRs extendi-
dos en aplicaciones criptográficas
Aplicado a los LFSRs, esto significa que las posiciones de las realimentaciones deben
estar situadas de forman que constituyan un FPDS.
III .3 Ejemplo. Sean dos conjuntos G0 = {0, 2, 4, 17} y G1 = {0, 2, 15}. El FPDS del primer conjunto
es Γ0 = {2, 4, 2, 17, 15, 13}. Como puede observarse, la diferencia 2 se repite una vez, lo que abrirı́a
la puerta a ciertos ataques criptográficos. Sin embargo, todas las diferencias de Γ1 = {2, 15, 13} son
distintas entre sı́, por lo que este LFSR resultará más seguro que el primero.
Como hemos visto, al ampliar el cuerpo algebraico sobre el que se apoya el fun-
cionamiento de los nuevos registros de desplazamiento, sus operaciones internas tam-
bién lo hacen. La más importante de todas es la función de realimentación que implica
diversas sumas y multiplicaciones.
En el cuerpo tradicional GF(2) estas operaciones resultan extremadamente sencil-
las, pero en el cuerpo GF(2n ) las multiplicaciones implicadas en la realimentación se
convierten en uno de los puntos crı́ticos del esquema propuesto. A diferencia del tradi-
cional cuerpo GF(2), las operaciones de multiplicación en GF(2n ) son muchos más cos-
tosas computacionalmente, por lo que podrı́a darse el caso, en último extremo, de que
los beneficios obtenidos por su uso no compensaran su mayor coste computacional.
En los siguientes apartados se estudiará en detalle esta cuestión, analizando las
diferentes estrategias existentes a la hora de implementar esta operación, sus ventajas
e inconvenientes y las peculiaridades de cada una de ellas.
Se estudiarán en concreto tres métodos, dos basados en el uso de tablas precom-
putadas, que hemos denominado MULTTABLE y LOGTABLE, y el algoritmo de mul-
tiplicación general, SHIFT, cuando los métodos anteriores no sean aplicables. Final-
mente, se analiza un cuarto método, SPLITW8, que puede considerarse una optimización
del algoritmo anterior. Para llevar a cabo esta evaluación, se ha escrito un software es-
pecı́fico en lenguaje C y se ha contado con el apoyo de unas librerı́as públicas de libre
uso, rápidas, eficientes y ampliamente utilizadas [12].
Tamaño de
Tamaño
n la tabla
en bytes
resultante
8 256 KB 218
10 4096 KB 222
12 64 MB 226
14 1 GB 230
16 16 GB 2 ≈ 1010
34
.. .. ..
32 64 EB 266 ≈ 1018
El método LOGTABLE, aunque supone una mejora muy importante respecto al pre-
sentado en primer lugar, tiene sin embargo unas necesidades de memoria poco realistas
para n = 32. En este caso, cuando las tablas no son prácticas, siempre queda el recurso
de la multiplicación de propósito general.
Ésta se implementa de manera eficiente convirtiendo el segundo factor, b, en una
matriz de bits de dimensión n × n y multiplicándola por un vector de bits correspondi-
ente al primer factor, a, para ası́ obtener el vector producto [14].
Aunque es significativamente más lento que los dos métodos anteriores, es un pro-
cedimiento que funciona siempre, para cualquier tamaño de n y necesita unos requisi-
tos de memoria mı́nimos.
III .4. I MPLEMENTACI ÓN EFICIENTE DE LA MULTIPLICACI ÓN EN GF(2n ) 63
Por último, para el caso especial de n = 32, puede utilizarse un método particular
únicamente válido para este valor de n.
El proceso comienza creando siete tablas de 256 KB cada una. Estas tablas se uti-
lizan para multiplicar los números de 32 bits, dividiéndolos en cuatro partes de 8 bits
cada una, y realizando entonces 16 multiplicaciones y sumas binarias para obtener el
resultado final.
Haciendo uso de esta optimización, el algoritmo es 7 veces más rápido que utilizan-
do el método SHIFT para el caso concreto de n = 32.
instrucciones y otra de datos. La caché de nivel 2, de mayor tamaño, se comparte entre los núcleos.
64 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Arquitectura Método
ATmega168 MULTTABLE LOGTABLE SHIFT SPLITW8
GF(28 ) - - 0.00079 -
GF(216 ) - - - -
GF(232 ) - - - -
PentiumIII MULTTABLE LOGTABLE SHIFT SPLITW8
GF(28 ) 31.73 27.77/0.87 1.39/0.04 -
GF(216 ) - 4.53 0.55/0.12 -
GF(232 ) - - 0.18 0.87/4.83
DualCore MULTTABLE LOGTABLE SHIFT SPLITW8
GF(28 ) 110.03 94.11/0.85 4.40/0.03 -
GF(216 ) - 60.25 0.55/0.02 -
GF(232 ) - - 0.47 8.03/17.085
Athlon MULTTABLE LOGTABLE SHIFT SPLITW8
GF(28 ) 89.62 78.76/0.87 5.52/0.06 -
GF(216 ) - 29.05 2.25/0.07 -
GF(232 ) - - 0.82 3.41/4.15
Cuadro III.6: Resultados de los diferentes métodos del multiplicación en diversas ar-
quitecturas (en millones de multiplicaciones por segundo).
Conclusiones Las conclusiones finales que pueden extraerse de los experimentos re-
alizados resultan, a la vista de los datos, bastante claras. Trabajando en el cuerpo GF(28 )
el método más eficiente para la multiplicación de elementos en GF(2n ) resulta sin duda
MULTTABLE, que utiliza tablas precomputadas de 256KB. El tamaño de estas tablas,
sin embargo, las hace prohibitivas cuando pasamos al cuerpo GF(216 ). En este caso
deben utilizarse otro tipo de tablas, las utilizadas por el método LOGTABLE. Éstas,
sin embargo, requieren pasos adicionales, lo que provoca que dicho método vea decre-
mentado ligeramente su rendimiento.
Finalmente, en GF(232 ), el método más adecuado es SPLITW8, que implementa una
mejora sobre el método general SHIFT, aún cuando requiera una memoria total de
1792KB para almacenar las tablas necesarias.
66 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
120
100
80
60
40
20 GF(2^32)
GF(2^16)
GF(2^8)
0
MULTTABLE LOGTABLE SHIFT SPLITW8
Por la misma razón, el acceso a cada bit del registro es muy costoso, pues deben
utilizarse máscaras y desplazamientos internos dentro de cada palabra que afectan
de forma muy significativa al rendimiento final.
P FIN: Indica el final del registro, es decir, la celda que recibe la realimentación
en cada ciclo, s0 .
P FeedBacki : Son una serie de punteros, uno por cada realimentación del registro.
Cada uno de ellos almacena la posición de cada realimentación, que, como el resto
de punteros, también se mueven en cada ciclo.
Utilizando los mismos principios de la técnica anterior es posible, sin embargo, evi-
tar alguno de sus inconvenientes haciendo uso de un búfer de longitud doble de la
necesaria. El esquema de funcionamiento se convierte, entonces, en el que sigue:
De esta forma, se puede acceder a todos los k−l valores intermedios en posiciones
fijas a la derecha del puntero.
pl pr
7 6 5 4 3 2 1 0
s5 s4 s5 s4
VENTANA
s3 s2 s1 s0 s3 s2 s1 s0 DESLIZANTE
3 2 1 0
s5 s4
BÚFER
s3 s2 s1 s0 CIRCULAR
El segundo de los aspectos citado es, sin duda, el más importante. En el ejemplo an-
terior el código sin optimizar no puede explotar el pipeline del microprocesador, pues
una instrucción de salto bloquea habitualmente este proceso, incluso en aquellas arqui-
tecturas que utilicen predicción de salto [22]. Sin embargo, el código optimizado puede
incluir las instrucciones de las lı́neas 5 a la 9 simultáneamente en las diferentes etapas
del pipeline, aumentado de esta forma el paralelismo y rendimiento de la ejecución.
Aunque es difı́cil de cuantificar y depende en gran medida de cada caso concreto,
en general esta técnica permite mejoras en el tiempo de ejecución que oscilan entre el
10 y el 30 % [23, 24].
72 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Tras analizar los aspectos subyacentes más importantes, como los diferentes métodos
de multiplicación y técnicas para la implementación eficiente en software, en este aparta-
do se unifican todos estos aspectos individuales y se analiza el rendimiento global de
un LFSR diseñado mediante las diversas técnicas propuestas en esta tesis. Concreta-
mente, se trata de un LFSR de 17 etapas, cuyos polinomios de realimentación corre-
spondientes son los definidos en la sección III.3.3.
El rendimiento de la implementación software de estos métodos ha sido analizado
en las plataformas anteriormente presentadas en el Cuadro III.5, con el fin de estudiar
su comportamiento en entornos reales. Este análisis ha sido dividido en dos grandes
apartados, en función de en qué parte de la ejecución de cada método se hace un mayor
énfasis: microanálisis y macroanálisis.
El primero de ellos mide, a muy bajo nivel, cuáles son los factores clave como
fallos de memoria caché, utilización de los buses o CPI3 en la ejecución de un LFSR
implementado en software. Por su parte, el macroanálisis se centra en las métricas
de rendimiento usuales como tiempo de ejecución, flujo de generación de secuencia
cifrante y otras.
Finalmente, se ha analizado el comportamiento de todas las técnicas anteriores en
cuatro cuerpos algebraicos diferentes: el tradicional cuerpo binario GF(2) y sus cuerpos
extendidos GF(28 ), GF(216 ) y GF(232 ). La operación de multiplicación se ha implemen-
tado utilizando el método más rápido en cada caso, según se analizó en III.4.
III.6.1. Microanálisis
El microanálisis del rendimiento incluye aspectos de bajo nivel, muy cercanos a la
estructura hardware del computador y al sistema operativo. Algunos de estos aspectos
incluyen medir el número de ciclos de CPU utilizados (y, en consecuencia, el CPI), los
fallos en los accesos a memoria, la utilización de los buses del sistema, etc...
Estos datos permitirán averiguar si la implementación realizada no está completa-
mente optimizada y tiene algunos cuellos de botella que disminuyan su rendimiento.
Estos datos serán obtenidos con el mecanismo conocido como unidades de monitorización
del rendimiento (Performance Monitoring Units, PMUs).
Para obtener todos estos valores se han utilizado dos herramientas de análisis: la In-
tel VTune profiling tool [26] y el interfaz perfmon2 [27]. Estas herramientas nos permitirán
obtener los datos necesarios y realizar un microanálisis pormenorizado de la ejecución
de un LFSR en software, a la vez que nos permitirá determinar los parámetros más
importantes que influyen en su rendimiento.
Recolección de los datos Para realizar una toma de datos correcta y fiable, es impor-
tante respetar escrupolosamente los siguientes aspectos:
Las medidas deben realizarse siempre con una carga en el sistema similar y repro-
ducible. De esta forma, el código bajo análisis tendrá un flujo de ejecución similar
cada vez. Para conseguir esto, hay que asegurarse de que no existen procesos in-
necesarios en ejecución y que el proceso analizado tiene a su disposición la may-
orı́a del tiempo de CPU. En este trabajo, para asegurar al máximo las condiciones
anteriores, el SO4 fue arrancando en el nivel de ejecución 3, sin entorno gráfico.
El código bajo análisis debe haber sido compilado utilizando las máximas op-
ciones de optimización permitidas por el compilador. En entornos UNIX, la op-
ción -O3 proporciona estas caracterı́sticas, incluyendo un uso agresivo del pipeline
(que, como se ha analizado anteriormente, aporta beneficios claros en el caso de
los LFSR).
Memoria RAM
Bus
Núcleo de la
Caché L1d
CPU
100000
Número de transacciones por segundo
80000
Fase de carga
60000
40000
Fase de funcionamiento
20000
0
0 200 400 600 800 1000 1200
Tiempo (ms)
Figura III.7: Evolución de la utilización de los buses del sistema. El eje de abscisas
indica el tiempo, en milisegundos, transcurrido desde el inicio de la ejecución del LFSR.
En el eje de ordenadas pueden encontrarse el número de transferencias por segundo
en los buses.
periodo, etiquetado como ’Fase de carga’, que se extiende durante los primeros 50 ms
aproximadamente.
En el segundo periodo, que dura desde los 50 ms en adelante (’Fase de funcionamien-
to’), es cuando realmente comienza la ejecución del LFSR. En ese momento, todos los
datos necesarios están ya en memoria caché y puede observarse que se producen muy
pocos fallos en L2, lo que implica que la mayorı́a de la actividad de la caché ocurre en
L1 y L2.
Por otro lado, también se han medido otros parámetros menores, como el tiem-
po medio de los accesos a memoria o el número de fallos en la predicciones de salto,
aunque sus valores concretos no se muestran puesto que son prácticamente cero en
todos los casos. Ambos parámetros parecen, de esta forma, confirmar las conclusiones
pues unos valores tan bajos, que pueden considerarse cero en la práctica, corresponden
a una alta eficiencia del programa analizado, en todas las configuraciones.
Finalmente, en la Figura III.8 puede encontrarse, de forma gráfica, un resumen de
todos los datos aportados en estos experimentos. En ella se compara, además, el com-
portamiento de estos LFSRs extendidos con otros algoritmos de referencia, como AES
funcionando en modo “cifrado en flujo” (AES-CTR) [29, 30] y RC4 [31]. De esta com-
parativa pueden extraerse interesantes conclusiones.
La primera es que el CPI de todas las implementaciones es sensiblemente menor
que el de AES-CTR. Este hecho resulta lógico hasta cierto punto, pues aunque AES sea
probablemente uno de los algoritmos más revisados y optimizados de la historia de la
criptografı́a, no deja de ser un cifrador en bloque, mucho más “pesado” y complejo que
76 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
3.5 6
CPI
Fallos en LD1
Utilización de buses 5.5
3 Fallos en LD2
5
4.5
2 3.5
CPI
1.5 2.5
2
1
1.5
1
0.5
0.5
0 0
Ninguna Búfers Ventanas Desdoblamiento AES−CTR RC4
circulares deslizantes de búcles
Técnica de implementación
III .4 Ejemplo. Veamos con un ejemplo cómo se han calculado los diferentes factores de mejora. Uti-
lizando los datos que pueden encontrarse en las Tablas III.7 y III.8, se observa que: para la arquitec-
tura Dual Core los tiempos que necesita para generar la secuencia de prueba con la configuración
tradicional, con ventanas deslizantes en GF(2), sin mejoras en GF(28 ) y con ventanas deslizantes en
GF(28 ), son respectivamente 1.58, 0.47, 0.56 y 0.44 segundos.
Ası́, el factor α que mide la relación entre los tiempos invertidos por la configuración tradicional y la
que utiliza cuerpos extendidos serı́a αGF(28 ) = 1.58/0.56 = 2.82.
Por otro lado, con el uso de ventanas deslizantes, trabajando en el mismo cuerpo, sólo son necesarios
0.44 segundos, por lo que el factor de mejora β serı́a, por tanto, β = 0.56/0.44 = 1.27.
Finalmente, el tiempo invertido utilizando ventanas deslizantes y un cuerpo extendido, GF(28 ) en este
caso, es de 0.44 segundos. Por tanto, el último factor de mejora, γGF(28 ) es de γGF(28 ) = 1.58/0.44 =
3.59.
14
12
10
Factor α
0
GF(2) GF(28) GF(216) GF(232)
Cuerpo de Galois
Figura III.9: Evolución del factor α frente al tamaño del cuerpo extendido base
La primera de las conclusiones que puede extraerse de los datos es que, tal y como
se esperaba, conforme el tamaño del cuerpo aumenta, el rendimiento también lo hace
en todas las arquitecturas. Sin embargo, un hecho significativo y llamativo es que el
beneficio que puede obtenerse es distinto en las diferentes arquitecturas. Tal y como
puede observarse en la Figura III.9, la arquitectura que obtiene mayor beneficio, con un
factor α máximo de 16.35 para GF(216 ), es la de Pentium III que constituye la de menor
complejidad y capacidad de cómputo. En otras palabras, puede decirse que las “peo-
res” plataformas se benefician más del uso de cuerpos extendidos que las arquitecturas
más modernas.
La razón de este comportamiento es que las plataformas como Pentium III cuentan
con un menor número de estructuras de optimización hardware internas, tales como
módulos de predicción de salto o pipeline de mayor número de etapas. Por tanto, el
beneficio del uso de los cuerpos extendidos es más notable y no queda “difuminado”
e incluido en el aumento de rendimiento proporcionado, de forma intrı́nseca, por las
técnicas de optimización hardware. En cierta manera, podrı́amos decir que lo que se
consigue es emular por software las estructuras anteriores.
En el resto de plataformas, más modernas y por tanto quizás más significativas, el
aumento del rendimiento es también muy notable. Por ejemplo, en el cuerpo GF(28 ) el
LFSR resultante es casi 3 veces más rápido que su equivalente tradicional sobre GF(2).
Este buen resultado es posible, en gran medida, gracias a que las operaciones de mul-
tiplicación se llevan a cabo utilizando tablas de pequeño tamaño, que caben completa-
mente en memoria RAM y cuyo acceso es muy rápido.
Sin embargo, conforme aumenta el tamaño del cuerpo, las operaciones matemáticas
involucradas se vuelven cada vez más costosas. Por esta razón, se produce un curioso
fenómeno: el factor de mejora se incrementa de forma lineal hasta GF(216 ) y, entonces,
en lugar de seguir aumentando como cabrı́a esperar, decrece ligeramente para GF(232 ).
La razón de este comportamiento se debe a que, en ese punto, el compromiso entre
III .6. A N ÁLISIS DEL RENDIMIENTO 79
GF(2)
Rendimiento Factor de
Arquitectura Segundos
(Mbytes/s) mejora α
ATmega168 4450 0.002 —
Pentium III 24.37 0.41 —
Dual Core 1.58 6.32 —
Athlon 1.14 8.77 —
GF(28 )
Rendimiento Factor de
Arquitectura Segundos
(Mbytes/s) mejora α
ATmega168 1650 0.006 3
Pentium III 3.89 2.57 6.25
Dual Core 0.56 21.27 2.80
Athlon 0.59 16.94 1.93
GF(216 )
Rendimiento Factor de
Arquitectura Segundos
(Mbytes/s) mejora α
ATmega168 — — —
Pentium III 1.49 6.71 16.35
Dual Core 0.24 41.66 6.60
Athlon 0.33 30.30 3.45
GF(232 )
Rendimiento Factor de
Arquitectura Segundos
(Mbytes/s) mejora α
ATmega168 — — —
Pentium III 1.79 5.58 13.57
Dual Core 0.27 37.03 5.85
Athlon 0.37 27.02 3.08
Cuadro III.7: Resultados numéricos del factor α. Este factor mide el incremento en el
rendimiento producido por el uso de cuerpos extendidos.
Los resultados numéricos de los experimentos realizados concluyen, por tanto, que
la forma más eficiente de implementar registros de desplazamiento en software es tra-
bajar en el cuerpo extendido GF(216 ), en lugar del cuerpo binario tradicional, y utilizar
la técnica de implementación de desdoblamiento de bucles, como muestra la Figura
III .10 (b). De esta forma es posible conseguir mejoras en el rendimiento espectaculares,
con un factor de mejora γ de 10.15, que supone un incremento de más del 900 %.
III .6. A N ÁLISIS DEL RENDIMIENTO 81
6
Factor β
1
Ninguna Búfers Ventanas Desdoblamiento
circulares deslizantes de búcles
Técnica de implementación
(a) Evolución del factor β en función de la técnica de mejora utilizada.
7
Factor γ
1
GF(2) GF(28) GF(216) GF(232)
Cuerpo de Galois
(b) Evolución del factor γ en función del tamaño del cuerpo extendido utilizado.
Cuerpo
Técnica de mejora
GF(2) GF(28 ) GF(216 ) GF(232 )
Tasa de salida
6.32 21.27 41.66 37.03
(MB/s)
Ninguna
Factor de
- - - -
mejora β
Factor de
- 2.80 6.60 5.74
mejora γ
Tasa de salida
9.70 22.72 58.82 43.47
(MB/s)
Búfers circulares
Factor de
1.30 1.01 1.18 1.00
mejora β
Factor de
1.28 2.87 7.76 5.73
mejora γ
Tasa de salida
24.39 27.02 62.5 47.61
(MB/s)
Ventanas deslizantes
Factor de
3.36 1.27 1.23 1.08
mejora β
Factor de
3.21 3.56 8.25 6.28
mejora γ
Tasa de salida
66.67 38.46 76.92 55.55
(MB/s)
Desdoblamiento de bucles
Factor de
8.87 1.86 1.62 1.28
mejora β
Factor de
8.82 5.07 10.15 7.33
mejora γ
Metodologı́a A grandes rasgos, este proceso se lleva a cabo tomando varias secuen-
cias proporcionadas por el generador y convirtiéndolas en entrada de los distintos tests,
cada uno de los cuales está diseñado para comprobar si cierto aspecto que una secuen-
cia aleatoria sı́ exhibirı́a está presente en la secuencia de entrada. Por ejemplo, uno de
los aspectos básicos de una secuencia binaria podrı́a ser que el número de 0’s y 1’s fuera
aproximadamente el mismo.
Los tests existentes en la comunidad cientı́fica se han ido generalizando con el tiem-
po, incluyendo cada vez más pruebas y abarcando más aspectos de las secuencias anal-
izadas. Para incluir también una perspectiva histórica, estos tests serán presentados de
forma cronológica y, por tanto, de menor a mayor complejidad y efectividad, como
puede observarse en la Figura III.11.
El estudio comienza con una breve exposición de los conceptos estadı́sticos básicos
necesarios para comprender el funcionamiento y las conclusiones de los tests posteri-
ores. A continuación se desarrollará una descripción de los postulados de Golomb, que
fueron el primer intento de establecer una serie de condiciones necesarias para medir
la bondad de una secuencia pseudoaleatoria periódica, para después presentar algunos
de los tests estadı́sticos básicos, como el test de frecuencias, el de series o el de rachas,
entre otros.
En los apartados III.7.4, III.7.5 y III.7.6 se describen elconjunto de tests utilizados y,
finalmente, en la sección III.7.7 se presenta un resumen de los resultados obtenidos.
1 x−µ2
−
f (x) = √ e 2σ2 , −∞ < x < ∞
σ 2π
Ası́, se dice que X es N(µ, σ). Si X es N(0, 1), entonces se dice que X tiene una dis-
tribución normal estándar.
La distribución normal posee ciertas propiedades importantes que conviene destacar:
84 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Tests
modernos
NIST
(1997) Test Universal
de Maurer
(1991)
os
s
Test
Diehard
básic
(1995) Postulados
Dieharder De Golomb
(2004) (1967)
Crypt-X
(1999)
Como se deduce de este último apartado, no existe una única distribución normal,
sino una familia de distribuciones con una forma común, diferenciadas por los valores
de su media y su varianza. De entre todas ellas, la más utilizada es la distribución
normal estándar, que corresponde a una distribución de media 0 y varianza 1.
0.9
µ=0, σ22=0.2
µ=0, σ2=1.0
µ=0, σ2=5.0
0.8 µ=0, σ =5.0
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
−5 −4 −3 −2 −1 0 1 2 3 4 5
v
−1 − x
1
Γ(v/2)2v/2 x 2 e 2
, 0≤x<∞
f (x) =
0
x<0
Z ∞
Γ(t) = xt−1 e−x dx, t>0
0
III .5 Ejemplo. En la distribución B(1; p) el campo de variación del parámetro p es el intervalo (0,1).
Una hipótesis nula puede ser la pertenencia de p al intervalo Θ0 = (0, 0.3] y la alternativa a Θ1 =
(0.3, 1), es decir, H0 = {0 < p ≤ 0.3}, H1 = {0.3 < p < 1}.
Decisión
Aceptar H0 Rechazar H0
H0 Correcta Errónea
Hipótesis cierta
H1 Errónea Correcta
con leche para representar la hipótesis defendida por este investigador: la posibilidad nula de que la dama
pudiera distinguir el orden en el que se vertieron el té y la leche.
III .7. T ESTS ESTAD ÍSTICOS 87
H0 : θ = θ0
Por otro lado, establecer la hipótesis alternativa, lo que puede realizarse de tres
maneras, dependiendo del problema analizado:
H1 : θ , θ0 , θ < θ0 , θ > θ0
En el primer caso se habla de contraste bilateral o de dos colas, y en los otros dos de
lateral (derecho en el 2o caso, o izquierdo en el 3o ) o de una cola.
2. Elegir un nivel de significación α y construir la zona de aceptación. A la zona de
rechazo la llamaremos región crı́tica, y su área es el nivel de significación.
3. Elegir un estadı́stico de contraste7 . Verificar la hipótesis extrayendo una muestra
cuyo tamaño se ha decidido en el paso anterior y obteniendo de ella el correspon-
diente estadı́stico.
4. Decidir si el valor calculado en la muestra cae dentro de la zona de aceptación, en
cuyo caso se acepta la hipótesis, o se rechaza en caso contrario.
7 Un estadı́stico es una función que opera sobre los elementos de una muestra aleatoria. Por ejemplo, podrı́a
III .6 Ejemplo. Este ejemplo ilustra de forma sencilla el procedimiento anterior. Partimos de la sigu-
iente situación: “Un estudio trata de establecer el efecto del estrés sobre la presión arterial. La hipótesis
de partida es que la presión sistólica media en varones jóvenes estresados es mayor que 18 cm de Hg.
Se estudia una muestra de 36 sujetos y se obtiene que la media de la presión es µ = 18.5 cm de Hg,
con una varianza de σ = 3.6. Con un nivel de significación de α = 0, 05, ¿qué puede decirse sobre la
hipótesis de partida?”.
Solución: Siguiendo los pasos del procedimiento anterior, puede establecerse que:
µ − H0
T= √
S/ n
donde la región crı́tica se define como T > tα . Si el contraste hubiera sido lateral izquierdo, la
región crı́tica se hubiera definido como T <1−α . En nuestro caso, el valor obtenido es t(36)0.05 =
1.69.
4. Calculamos el valor de t en la muestra, obteniendo:
18.5 − 18
√ = 0.833
3.6/ 36
y, como no es mayor que 1.69, la hipótesis no está en la región crı́tica y, por tanto, H0 no es
rechazada.
III .7 Ejemplo. Consideremos que se lleva a cabo un experimento para determinar si el lanzamiento
de una moneda es correcto, es decir, tiene un 50 % de probabilidades tanto de salir cara como cruz.
En este caso, la hipótesis nula H0 serı́a que la moneda no está trucada y que, por tanto, cualquier
desviación de la media puede ser achacado al azar. Los resultados del experimento son que la moneda
produce 14 caras en un total de 20 tiradas.
El p-valor del experimento serı́a, por tanto, la probabilidad, que denominaremos p0 , de que una mon-
eda perfecta produjera al menos 14 caras más la probabilidad, p1 , de que produjera 6 caras o menos.
Dado que el lanzamiento de una moneda sigue una distribución binomial, la probabilidad de que se
produzcan al menos 14 caras es de 0.0577. Por simetrı́a, p1 = p0 , por lo que, finalmente, el p-valor
serı́a 0.0577 × 2 = 0.1154.
Ni
Fn (xi ) = ,
n
donde Ni es la frecuencia absoluta acumulada, es decir, el número de observaciones
acumuladas menores o iguales a xi , Ni = n1 + . . . + ni . Si la hipótesis nula es que
90 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
la muestra procede de una población con función de distribución F(x), las diferen-
cias entre Fn (x) y F(x), para una muestra de tamaño suficientemente grande, es de
esperar que no sean significativas.
2. Se define el estadı́stico D, que se calcula como la mayor discrepancia vertical entre
Fn (x) y F(x), es decir: Dn = max | Fn (xi ) − F(xi ) |.
3. Se fija el valor de significación, α.
4. Si Dn < Dn,α se acepta la hipótesis. Para un número de observaciones grande (n >
100) el valor crı́tico de Dn,α se puede aproximar por:
p
−ln(α/2)/2n
académicas relevantes en realizar el test de inteligencia Mega IQ, diseñado por Ronald K. Hoeflin. Su
puntación en el test, considerado el más elitista del mundo, fue de 176, lo que supone una inteligencia sólo
poseı́da por una de cada millón de personas. Un rápido cálculo permite estimar que, estadı́sticamente, sólo
unas 6 000 personas en todo el mundo eran tan inteligentes como Golomb en el momento en el que éste
realizó el test.
III .7. T ESTS ESTAD ÍSTICOS 91
Test
Función que actúa sobre unos datos (una cadena binaria en
estadı́stico
nuestro caso), y que se utiliza para decidir si rechazar o no la
hipótesis nula, H0 .
Hipótesis
Una afirmación sobre determinada condición o propiedad de la
nula, H0
secuencia. Para los propósitos de este trabajo de tesis, la hipótesis
nula H0 sostiene que la secuencia en cuestión es aleatoria.
Test
Kolmogorov- Un estadı́stico que se utilizará para determinar si un conjunto de
Smirnov datos se ajusta a cierta distribución de probabilidad.
Nivel de
significación, La probabilidad de rechazar erróneamente la hipótesis nula; o
α lo que es lo mismo, la probabilidad de concluir que H0 es falsa
cuando es, en realidad, verdadera. Otros términos para referirse
a este concepto son error tipo I o error α.
p-valor Probabilidad, bajo la hipótesis nula, de que el azar proporcione
un resultado más discrepante del que ha dado la muestra.
Entropı́a Una medida del “desorden” de un sistema cerrado. Aplicada a
una cierta cantidad de información, la entropı́a asociada a una
variablePaleatoria X con probabilidades pi , ..., pn se define como
H(X) = ni=1 pi logpi
III .14 Definición. (PN-secuencia) Una secuencia binaria que cumpla los postulados de
Golomb se denomina pn-secuencia.
s15 = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1}
Puede comprobarse fácilmente que cumple los postulados de Golomb anteriormente citados y que, por
tanto, puede considerarse una pn-secuencia:
1. El número de 0’s en s15 es 7, y el número de 1’s es 8. Como difieren en uno, este postulado se
cumple.
2. s15 tiene 8 rachas. Hay 4 de longitud 1 (2 huecos y 2 bloques), 2 rachas de longitud 2 (1 hueco y
un bloque), una racha de longitud 3 (1 hueco) y una de longitud 4 (1 bloque).
3. Finalmente, la función de autocorrelación toma efectivamente dos valores: C(0) = 1 y C(t)= −115
para cada 1 ≤ t ≤ 14.
(n0 − n1 )2
X1 =
n
siendo n = n0 + n1 , que sigue una distribución χ2 con 1 grado de libertad. La aprox-
imación es suficientemente buena si n ≥ 10, aunque se recomiendan valores mucho
mayores, como n 10000.
4 2
(n200 + n201 + n210 + n211 ) − (n20 + n21 ) + 1
X2 =
n−1 n
donde ahora se verifica que n00 + n01 + n10 + n11 = n − 1. El estadı́stico X2 sigue una
distribución χ2 con dos grados de libertad si n ≥ 21.
III .7. T ESTS ESTAD ÍSTICOS 93
2(A(d) − n−d
2 )
X5 = √
n−2
que sigue, aproximadamente, una distribución N(0, 1), si n − d ≥ 10.
veces más para detectar una desviación significativa que un simple análisis de frecuen-
cias).
Sin embargo, esto no tiene porqué ser un problema en la práctica, pues el generador
deberı́a ser capaz de proporcionar grandes cantidades de secuencia rápidamente. Por
otra parte, una vez generada dicha secuencia, el test en sı́ mismo es muy eficiente, por
lo que este requisito no supone una desventaja importante respecto a otros tests.
Concretamente, la longitud de la secuencia necesaria es n, donde n es del orden de
10 · 2L + 1000 · 2L con 6 ≤ L ≤ 16. Los primeros Q = 10 · 2L bloques de L bits sirven como
bloques de inicialización, mientras que los últimos K = bn/Lc − Q bloques de longitud
L son los que realmente se comprueban. El tamaño de Q asegura que, con una alta
probabilidad, todas las posibles cadenas de L-bits están representadas en los bloques
de inicialización.
El test de Maurer mide, básicamente, la entropı́a por bit de la secuencia de entrada,
que es, según el autor, “la forma correcta de medir la calidad de una fuente de bits de aplicación
criptográfica”. La entropı́a tiene relación directa con la compresibilidad, por lo que el
test en esencia mide esta caracterı́stica. Si una secuencia es compresible de una manera
significativa, no puede ser considerada aleatoria.
El estadı́stico utilizado por Maurer es el siguiente:
Q+K
1 X
Xm = log2 ti
K
i=Q+1
donde ti denota el número de ı́ndices desde la ocurrencia anterior del sı́mbolo i-ésimo.
En otras palabras, el test consiste en inspeccionar la secuencia buscando coincidencias
con el bloque de test de L bits y anotando la distancia entre coincidencias.
Bajo la hipótesis nula de que el generador produce secuencias aleatorias, la esper-
anza de Xm viene dada por la siguiente expresión:
∞
X
E(Xm ) = 2−L (1 − 2−L )i−1 log2 i
i=1
c(L, K)
Var(Xm ) = Var(log2 G)
K
donde G denota una variable aleatoria distribuida geométricamente, con parámetro
1 − 2−L , y c(L, K) tiene el valor aproximado:
La razón esencial es que parece presentar una mayor sensibilidad para detectar de-
fectos estadı́sticos pequeños en las secuencias de bits que los tests tradicionales, como
χ2 , desviaciones o los tests de correlación y entropı́a.
Por esta razón los tests de Diehard están considerados como muy exigentes. De he-
cho, varios generadores comerciales de números pseudo-aleatorios, que se venden bajo
el reclamo de perfecta aleatoriedad, fallan en uno o varios de los tests de Diehard. Por
otro lado existen tipos completos de generadores, como los basados en congruencias
lineales (a menudo utilizados en software), que tampoco pasan el test de Diehard.
El test de Diehard original estaba compuesto por una baterı́a de 15 pruebas individ-
uales, aunque este número ha ido incrementándose hasta las 18 actuales.
Como una evolución de la suite Diehard, puede encontrarse el conjunto de tests
Dieharder, escrito por Robert G. Brown del departamento de Fı́sica de la Universidad
de Duke [38].
En palabras del propio autor, “Dieharder trata de englobar todos los tests de aleatoriedad
existentes, tales como el propio Dierhard, el desarrollado por el NIST FIPS o el de Donald
Knuth”. Cuenta con una estructura flexible y extensible, de forma que resulta sencillo
añadir nuevos tests al conjunto.
32x32 Binary Rank y 6x8 Binary Rank: Selecciona sólo algunos bits de algunos
número aleatorios para formar una matriz binaria. Seguidamente, calcula el ran-
go de la matriz y, finalmente, comprueba si los rangos de las sucesivas matrices
están distribuidos uniformemente.
bres propios, por no tener interés su traducción y para facilitar la identificación de las pruebas en los resul-
tados proporcionados por las mismas.
10 La paradoja del cumpleaños hace referencia al sorprendente resultado matemático que establece que
la probabilidad de encontrar a dos personas que celebren su cumpleaños el mismo dı́a es del 50.7 % en un
grupo de tan sólo 23 personas. Por supuesto, esto no es una paradoja estricta, sino que se refiere a que el
resultado contradice la intuición. La mayorı́a de la gente apostarı́a que la probabilidad es mucho más baja, y
que es necesario un número mucho mayor de personas para que se alcance la probabilidad real.
96 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Establecer la hipótesis nula. Por ejemplo, que la secuencia binaria bajo análisis es
aleatoria.
Calcular el estadı́stico.
Calcular el p-valor.
Comparar el p − valor obtenido con el nivel de significación establecido. Como
se ha comentado, en esta tesis utilizaremos un nivel de significación α = 0.01.
Finalmente, el test será considerado como válido si el p − valor es mayor que α. En
caso contrario, se determinará que la secuencia analizada no ha superado el test
satisfactoriamente.
En resumen, puede considerarse que la secuencia analizada es aleatoria con un nivel
de significación del 99 % si el p − valor obtenido por ella es mayor que 0.01 y menor que
0.99.
Tests Diehard La baterı́a Diehard necesita como entrada para cada uno de sus tests
individuales un fichero binario con, al menos, 80 millones de bits. Teniendo esto en
cuenta y para la obtención de resultados se han utilizado 10 secuencias de 100 millones
de bits cada una, utilizando diferentes valores iniciales en el LFSR y promediando los
valores obtenidos.
III .7. T ESTS ESTAD ÍSTICOS 97
Número
Nombre del test p-valor Resultado
del test
1 Birthdays 0.244780 Satisfactorio
Posiblemente
2 OPERM511 0.234550
débil
3 32x32 Binary Rank 0.584027 Satisfactorio
4 6x8 Binary Rank 0.752711 Satisfactorio
5 Bitstream 0.205423 Satisfactorio
6 OPSO 0.680878 Satisfactorio
7 OQSO 0.513476 Satisfactorio
8 DNA 0.714685 Satisfactorio
Count the 1s
9 0.986580 Satisfactorio
(stream)
10 Count the 1s (bytes) 0.447169 Satisfactorio
11 Parking Lot 0.551586 Satisfactorio
Minimum Distance
12 0.698957 Satisfactorio
(2D Spheres)
3D Spheres
13 0.871600 Satisfactorio
(minimum distance)
14 Squeeze 0.061987 Satisfactorio
15 Sums 0.197436 Satisfactorio
16 Runs 0.273377 Satisfactorio
17 Craps 0.807377 Satisfactorio
Marsaglia and Tsang
18 0.924185 Satisfactorio
GCD
Marsaglia and Tsang
19 0.073101 Satisfactorio
Gorilla
Tests Dieharder Por otro lado, la baterı́a Dieharder proporciona un total de 218 p-
valores para sus 18 tests. Aunque esta cantidad puede ser, en principio, suficiente para
una realizar una buena valoración de los resultados, se estimó conveniente aumentar
dicha cantidad, a través de la modificación del código fuente de los tests, para que se
mostraran p-valores que anteriormente no aparecı́an. De esta forma se consiguió elevar
los datos hasta 2 000, lo que resulta, sin duda, estadı́sticamente más significativo.
Este hecho facilita también la comprobación del requisito de distribución uniforme
para los p-valores, que puede valorarse de forma sencilla a través de una representación
gráfica de estos valore para todos los tests sobre el intervalo [0, 1). En el Cuadro III.10
pueden encontrarse los resultados de la ejecución del test. Puede observarse que las
excelentes propiedades estadı́sticas de los LFSR se preservan perfectamente, dado que
todos los tests proporcionan un resultado plenamente satisfactorio. En la Figura III.13
puede observarse, además, la distribución de p-valores que, como hemos comentado,
debe ser uniforme en el intervalo [0, 1).
11 Este test es incluido para respetar la completitud del test original Diehard. Sin embargo, según el autor
de Dieharder no debe ser usado, pues contiene errores importantes. Según sus propias palabras: “¡Atención!
Este test falla en TODOS los generadores de secuencia conocidos, incluyendo aquellos cuya fortaleza está sobradamente
demostrada. ¡No utilice este test para verificar generadores!. Es muy probable que contenga errores de implementación
o fallos de diseño que producen un estadı́stico no válido.”
98 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Distribución de p−valores
1
0.9
0.8
0.7
0.6
p−valor
0.5
0.4
0.3
0.2
0.1
0
0 500 1000 1500 2000 2500 3000 3500 4000
Número de test
En esta baterı́a de tests, el resultado proporcionado por cada uno de ellos es también
uno o más p-valores. Estos tests requieren unas secuencias de entrada de una longitud
bastante elevada. Para no encontrar ningún problema en este sentido y comprobar ade-
cuadamente la consistencia del generador, tal como se analizó en la sección III.7.1.5, se
generan para estas pruebas mil secuencias, con sus correspondientes valores iniciales,
de 1 millón de bits de longitud cada una.
Una vez realizados los tests, con el fin de interpretar correctamente el resultado de
los mismos, se sigue las indicaciones proporcionadas por el NIST en la documentación
oficial de la suite [39]. En esencia deben de verificarse dos condiciones:
Un porcentaje mı́nimo de secuencias debe pasar cada test.
Los p-valores obtenidos deben encontrarse, de nuevo, uniformemente distribui-
dos en el intervalo [0, 1).
En el Cuadro III.11 puede observarse el resultado proporcionado por cada test in-
dividual, junto con la media y varianza de los p-valores obtenidos. Como corresponde
a un test pasado satisfactoriamente, la media de estos debe estar cercana a 0.5, puesto
que éstos deben estar uniformemente distribuidos en el intervalo [0, 1).
Es importante también que esta distribución tenga una varianza muy pequeña,
alrededor de 0.08, lo que indica que no existen un número excesivo de valores extremos,
demasiado cercanos a 0 o a 1.
Condición 1: Proporción de secuencias que pasan cada test En los resultados propor-
cionados por esta suite estadı́stica, cada uno de los tests incluye un valor denominado
proporción, que hace referencia al número de secuencias que pasan satisfactoriamente
el test en cuestión. La proporción se calcula dividiendo el número total de secuencias
cuyo p-valor es mayor que el nivel de significación, α, por el número total de secuen-
cias, 1000 en nuestros experimentos.
El NIST especifica un rango concreto para los valores aceptables de la proporción
de secuencias válidas. Este rango se calcula utilizando la siguiente expresión:
p
p ± 3 p(1 − p)/m
donde p = 1 − α y m el número de secuencias comprobadas. Como ya se ha co-
mentado, en estos experimentos se utilizaron 1000 secuencias (m=1000) con 1 millón
100 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
Varianza
Número Media de
Nombre del test de Resultado
del test p-valores
p-valores
1 Frequency 0.5026 0.0807 Satisfactorio
2 Cumulative Sums 0.5095 0.0828 Satisfactorio
Longest Runs Of
3 0.5026 0.0823 Satisfactorio
Ones
4 Runs 0.5012 0.0859 Satisfactorio
5 Rank 0.4957 0.0809 Satisfactorio
6 Spectral 0.5978 0.0657 Satisfactorio
Non-overlapping
7 0.5018 0.0830 Satisfactorio
Template Matchings
Overlapping
8 0.4975 0.08198 Satisfactorio
Template Matchings
Maurer’s Universal
9 - - Satisfactorio
Statistical
10 Random Excursions 0.4966 0.03553 Satisfactorio
Random Excursions
11 - - Satisfactorio
Variant
Approximate
12 0.4673 0.0817 Satisfactorio
Entropy
13 Serial 0.5004 0.0843 Satisfactorio
Lempel-Ziv
14 0.4889 0.0784 Satisfactorio
Complexity
15 Linear Complexity 0.5148 0.0811 Satisfactorio
Test 1 2 3 4 5 6 7 8
pt − valor 0.432 0.546 0.325 0.033 0.356 0.681 0.174 0.392
Conclusión X X X X X X X X
Test 9 10 11 12 13 14 15 16
pt − valor 0.277 0.186 0.447 0.303 0.035 0.184 0.714 0.107
Conclusión X X X X X X X X
1.005
1 0.9994
Rango aceptable
Proporción de secuencias válidas
0.995
0.99
0.985
0.9805
0.98
0.975
0.97
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Número de test
Los resultados numéricos muestran como estas técnicas permiten obtener incre-
mentos en el rendimiento final realmente significativos. Comparados con los métodos
tradicionales, es posible conseguir factores de mejora de hasta 10.15, que supone un
aumento en la eficiencia de más de un 900 %.
El estudio ha revelado también otros hechos relevantes y llamativos. El primero es
que, tal y como se esperaba, el rendimiento obtenido por el LFSR aumenta conforme
lo hace el tamaño del cuerpo base GF(2n ) utilizado. Sin embargo, debido a diversos
factores, esta mejora no es lineal, como podrı́a indicar la intuición, sino que sufre un
pequeño decremento en GF(232 ) respecto a GF(216 ).
Las razones que explican este fenómeno están relacionadas con el equilibrio entre
beneficio proporcionado por el cuerpo base y el coste computacional de sus opera-
ciones. Básicamente, cuando el tamaño del cuerpo aumenta, también lo hace el coste
de sus operaciones de multiplicación y esto repercute, directamente, en la función de
realimentación del LFSR, cuyo cálculo se vuelve más costoso. De esta forma, la ventaja
de obtener en cada ciclo de funcionamiento del LFSR una salida de mayor tamaño, 8,
16 y 32 bits respectivamente, se pierde gradualmente. El lı́mite, de acuerdo a los datos
obtenidos, parece estar en GF(216 ) que es el cuerpo que mejor rendimiento obtuvo en
los experimentos realizados.
Por tanto, a pesar de que los cuerpos extendidos han sido propuestos para su uso en
LFSR, este trabajo demuestra que su uso no siempre resulta rentable. Cuerpos mayores
que GF(216 ) parecen no resultar eficaces, pues el coste de sus operaciones internas es
tan alto, que provoca que se pierdan sus ventajas.
Por otro lado, se ha mostrado cómo otras técnicas de mejora, como búfers circulares
o desdoblamiento de bucles se adaptan perfectamente a la implementación de LFSRs,
mejorando muy significativamente la tasa de generación de salida de los mismos. Los
resultados concluyen, también, que estas técnicas resultan más eficaces en cuerpos de
104 III . R EGISTROS DE DESPLAZAMIENTO DEFINIDOS SOBRE CUERPOS COMPUESTOS
pequeño tamaño, como GF(28 ), GF(216 ), incluso GF(2) y que van perdiendo eficacia para
cuerpos de mayor tamaño.
Los experimentos realizados concluyen, por tanto, que la forma más eficiente de im-
plementar registros de desplazamiento en software es trabajar en el cuerpo extendido GF(216 ),
combinando esta técnica con la de desdoblamiento de bucles.
Por último, se ha llevado a cabo un estudio estadı́stico profundo de las secuen-
cias generadas por estos nuevos registros de desplazamiento, con el fin de comprobar
que siguen manteniendo las excelentes propiedades exhibidas por sus contrapartidas
binarias. Para ello se han utilizado diversas baterı́as de tests estándar, utilizadas habit-
ualmente para estos propósitos por multitud de trabajos cientı́ficos en diversos ámbitos
no sólo criptográficos. Los resultados son concluyentes y muestran, sin lugar a dudas,
que las secuencias generadas pueden considerarse pseudoaleatorias y son válidas, por
tanto, para el gran número de aplicaciones tı́picas de los LFSRs.
Este último resultado justifica el uso de estos registros como parte del diseño de un
nuevo cifrador en flujo, que será presentado en el siguiente capı́tulo.
C AP ÍTULO IV
105
106 IV . C IFRADO DE LAS COMUNICACIONES
el objetivo del proyecto era demostrar la teórica superioridad de los cifradores en flujo
sobre los de bloque, al menos en aquellas áreas enunciadas por Shamir. Por este moti-
vo, ya durante la fase preliminar del mismo sólo se admitieron aquellos algoritmos que
demostraran ser más rápidos que AES funcionando en modo contador.
Finalmente el proyecto finalizó en abril de 2008, con un conjunto total de 4 cifradores
ganadores aptos para su implementación software, y otros 3 orientados al hardware
[7, 8].
Parece claro que, sobre la base de las conclusiones de este proyecto, los cifradores
en flujo constituyen sin duda una excelente opción sobre la que basar el diseño de una
solución al problema de la privacidad en redes ad-hoc. Particularmente, este tipo de
cifradores poseen una serie de caracterı́sticas que encajan perfectamente en el marco
de los requisitos de estas redes móviles:
Como se ha visto, los cifradores en flujo son habitualmente los esquemas de cifra-
do más rápidos. Este hecho cobra especial importancia en la transmisión multime-
dia, donde habitualmente se necesitan altas tasas de transferencia, entre 10kbps
y 500kbps [9], y no es admisible que el cifrado se convierta en el cuello de botella
del sistema.
Son, por otro lado, conceptualmente muy simples. Al margen de las ventajas ev-
identes que esto supone, sobre todo a la hora de su implementación hardware,
esta caracterı́stica se traduce directamente en esquemas energéticamente eficientes,
lo que resulta especialmente significativo en estos entornos.
Necesidad de una nueva solución A pesar de las ventajas expuestas, muchos de los
algoritmos ganadores del proyecto eSTREAM, tanto en sus vertientes hardware como
software, resultan demasiado complejos para ser implementados en algunos de los dis-
positivos de baja capacidad de cómputo considerados en este trabajo de tesis.
Por esta razón se decidió diseñar un nuevo algoritmo de cifrado en flujo, que hemos
denominado LFSRe (LFSR extendido), basado en el uso de los registros de desplaza-
mientos extendidos, presentados en el capı́tulo anterior, y los principios del generador
shrinking. Aunque LFSRe haga uso conceptualmente de algunas ideas de éste gener-
ador, ambos cifradores cuentan con importantes diferencias. Las principales aporta-
ciones realizadas a la idea original pueden resumirse de la siguiente forma:
El generador shrinking original trabaja sobre el cuerpo binario GF(2). Por con-
tra, la propuesta de este trabajo utiliza los registros de desplazamientos anterior-
mente presentados, que se definen sobre cuerpos algebraicos extendidos GF(2n ),
donde n puede definirse en función del tamaño de palabra del microprocesador
donde vaya a ejecutarse el cifrador.
Como consecuencia del cambio anterior, los antiguos criterios de decimación de-
jan de ser válidos. Es necesario, pues, definir un conjunto de nuevas funciones,
que serán descritas y analizadas detalladamente en la sección IV.3, evaluando las
ventajas e inconvenientes de cada una.
Cifrador
Módulo de
carga del IV
Módulo
Módulo de
Clave generador de Búfer de salida
cifrado
secuencia
Si bien la necesidad del uso de un búfer de salida, que ocultase la salida irregular
del generador shrinking, fue ya apuntada por los autores originales, las implica-
ciones del mismo no fueron convenientemente exploradas. En la sección IV.4 se
abordará esta cuestión, analizando detalladamente todos los aspectos relevantes.
Cada uno de estos módulos será analizado detalladamente en las secciones suce-
sivas. Se comenzará por el módulo de generación de secuencia cifrante, que será descrito
en la sección IV.2. A continuación en la sección IV.3, se presentarán los nuevos criterios
IV .1. I NTRODUCCI ÓN 109
GENERADOR DE
SECUENCIA
R1
DECIMACIÓN P
R2
CIFRADO
TEXTO CLARO
TEXTO CIFRADO
Este es el primero de los módulos que forman parte del cifrador y, sin duda, uno
de los más importantes. Su objetivo es proporcionar una secuencia pseudoaleatoria de
longitud arbitraria, con excelentes propiedades estadı́sticas, que será utilizada posteri-
ormente en el proceso de cifrado.
Este módulo está parcialmente basado en las ideas de funcionamiento del conocido
generador shrinking, que se describe brevemente a continuación.
IV .2.1.1. Funcionamiento
1. SI ai = 1 ENTONCES c j = bi .
2. SI ai = 0 ENTONCES bi es descartado.
IV .2. M ÓDULO DE GENERACI ÓN DE SECUENCIA CIFRANTE 111
Un simple cálculo, basado en el hecho de que cada estado de R2 coincide una vez
con cada estado de R1 , permite calcular fácilmente el número de 1’s en la secuencia de
salida. Este número es constante e igual a:
Comparando las ecuaciones anteriores IV.1 y IV.3, puede deducirse que la secuencia
de salida es una secuencia cuasi-equilibrada. Además, cuenta con unas propiedades
estadı́sticas muy deseables para su uso criptográfico [10], por lo que este generador es
adecuado para uso en criptosistemas y generadores de secuencia.
IV .2.1.3. Criptoanálisis
Sorprendentemente, a pesar de su simplicidad, el generador shrinking ha permaneci-
do inmune y resistente a los muchos intentos de criptonálisis realizados hasta la fecha
[12, 13]. De hecho, a dı́a de hoy, el mejor ataque conocido, que presupone el conocimien-
to de P1 y P2 , aunque no el contenido inicial de los registros, necesita de aproximada-
mente O(2L1 ·L32 ) operaciones. Por el contrario, si los polinomios se mantienen en secreto,
la complejidad del ataque anterior crece hasta las O(22L1 · L1 · L2 ) operaciones.
En este último supuesto, considerando que L1 ≈ l y L2 ≈ l, el nivel de seguridad
proporcionado por el generador es equivalente a 22l operaciones. Por tanto, si se con-
sideran longitudes del orden de L1 ≈ 64 y L2 ≈ 64, el generador puede considerarse
seguro contra todos los ataques conocidos hasta el momento. Ésta constituye, sin du-
da, otra de las razones para la elección de este esquema como base para el diseño del
nuevo cifrador.
Como consecuencia, LFSRe no tiene una especificación única, como suele ser el caso
en los algoritmos de cifrado. No sólo puede variar la longitud de sus claves, a través de
la longitud de sus registros internos, sino también el tamaño de palabra de los mismos.
LFSRe puede definirse, por tanto, utilizando diferentes configuraciones, que deno-
taremos P8 , P16 y P32 , según hagan uso de distintos cuerpos algebraicos definidos so-
bre GF(28 ), GF(216 ) y GF(232 ) respectivamente. Si bien la seguridad del cifrador no se
ve afectada, puesto que todas sus configuraciones son seguras, sı́ existen importantes
diferencias en el rendimiento de cada una de ellas, como se analizó con detalle en el
Capı́tulo III. Las distintas configuraciones presentadas se recogen en el Cuadro IV.1.
Teniendo en cuenta los resultados sobre rendimiento obtenidos con anterioridad,
nuestro cifrador se definirá utilizando P16 siempre que sea posible. Sin embargo, ciertas
arquitecturas, como la mayorı́a de dispositivos en las redes de sensores, utilizan un
tamaño de palabra de 8 bits, por lo que en estos casos se deberá utilizar P8 .
Como se ha analizado a lo largo del capı́tulo anterior, una de las propuestas real-
izadas en esta tesis es sustituir los registros de desplazamientos tradicionales, R1 y R2 ,
definidos sobre GF(2), por equivalentes sobre GF(2n ), con n=8, 16 y 32. De esta forma, la
salida producida por los mismos no será binaria sino que, en cada ciclo, se obtendrán
8, 16 y 32 bits, respectivamente.
Como resulta obvio, éste es un cambio muy significativo, que afecta profundamente
al funcionamiento interno del sistema. De hecho, puede considerarse que nos encon-
tramos ante un nuevo generador, puesto que éste debe ser redefinido en su totalidad y
su seguridad debe ser revisada.
Entre los aspectos más importantes que deben ser rediseñados se encuentra el cri-
terio o función de decimación, pilar esencial del cifrador, y que ahora tendrá que trabajar
sobre el cuerpo extendido GF(2n ). A continuación se analizan todos los aspectos rela-
cionados con el mismo.
IV .1 Ejemplo. Aunque, como se analizará en la siguiente sección, existen una serie de requisitos
deseables para la funciones de decimación, en principio éstas pueden tomar cualquier forma en su
dominio de definición.
Por ejemplo, una función FD podrı́a comprobar si un número entero es impar. La definición de esta
función quedarı́a:
impar
FD : Z → GF(2)
impar 1,
si x mód 2 , 0
FD (x) =
0,
en otro caso
Tamaño de los elementos: el tamaño de los elementos del cuerpo algebraico subya-
cente ha cambiado, por lo que las operaciones “nativas” deberı́an ser a nivel de
byte y superiores.
Por otro lado, en función de cuántos registros tengan en cuenta en sus decisiones,
los criterios serán clasificados en simples, cuando impliquen sólo a R1 , o compuestos, si
utilizan también a R2 .
A continuación se describirán, analizando su comportamiento y puntos fuertes y
débiles, los nuevos criterios de decimación aportados en este trabajo, que se han de-
nominado MITAD, MENOR, PAR y NO-LINEAL.
Sean ai , bi , ci ∈ GF(2n ) los elementos de las secuencias producidas por los registros
R1 , R2 y la secuencia de salida, respectivamente. Entonces, haciendo uso de este criterio,
el funcionamiento del generador queda finalmente:
Ası́, por ejemplo, para el caso de GF(28 ) el criterio toma la siguiente forma:
Para los cuerpos GF(216 ) y GF(232 ), los valores umbral para el criterio serán, clara-
mente, 215 = 32 768 y 231 = 2 147 483 648.
Como puede verse, éste puede clasificarse como un criterio simple, pues sólo tiene en
cuenta el valor de R1 y equilibrado, siempre que la secuencia producida por R1 también
lo sea. En el caso de que no lo sea, la secuencia de salida del generador no será de
calidad, pudiéndose producir casos extremos, en el que todos los valores de R1 sean
mayores que 2n−1 y el generador descarte todos los valores y no produzca ninguna
salida.
Éste, sin embargo, es un problema que no deberı́a producirse pues los registros de
desplazamiento producirán buenas secuencias, desde el punto de vista estadı́stico, sea
cual sea el contenido inicial de sus registros (exceptuando el caso de todos los valores
a cero).
Por otro lado, es también un criterio muy eficiente, pues trabaja a nivel de byte,
medias palabras (16 bits) o palabras (32 bits) y su implementación en software puede
realizarse en dos únicas instrucciones. En el Listado 9 puede encontrarse el código en-
samblador correspondiente. Como puede observarse, es el criterio más eficiente posi-
ble, pues consta únicamente de dos instrucciones máquina, una de comparación y otra
de salto.
Por último, en el Cuadro IV.2 pueden encontrarse otras caracterı́sticas de este crite-
rio, incluyendo los tiempos invertidos en procesar una serie de secuencias de diferente
longitud.
116 IV . C IFRADO DE LAS COMUNICACIONES
Longitud
Número
secuencia Tiempo
descartes
(bytes)
106 498 584 0.406s
107 4 998 626 2.711s
108 49 998 399 18.945s
SI ai < bi ENTONCES ci = bi
SI ai ≥ bi ENTONCES se descarta bi
El criterio resulta, por tanto, compuesto, puesto que tiene en cuenta en su decisión
el contenido de ambos registros, y equilibrado, pues descarta, en la ejecución a largo
plazo, la mitad de los elementos generados por R1 . Los resultados de los experimentos
realizados para comprobar estas caracterı́sticas pueden encontrarse en el Cuadro IV.3.
El criterio MENOR tiene, sin embargo, una implementación software algo menos
eficiente que MITAD, pues implica el uso de tres instrucciones en lugar de dos, como
puede observarse en el listado ensamblador correspondiente (Listado 10). Aunque la
diferencia no resulta especialmente significativa (ligeramente superior a un 7 % de in-
cremento), este hecho se refleja en los tiempos invertidos por este criterio para generar
la secuencia de prueba, algo superiores a los de MITAD.
Longitud
Número
secuencia Tiempo
descartes
(bytes)
106 496 631 0.437s
107 4 978 821 3.671s
108 49 807 252 19.821s
Longitud
Número
secuencia Tiempo
descartes
(bytes)
106 500 286 0.487s
107 5 001 594 3.952s
108 50 003 343 20.626s
SI ai es PAR ENTONCES ci = bi
SI ai es IMPAR ENTONCES se descarta bi
En cuanto a su clasificación, este criterio es simple, puesto que sólo R1 está involu-
crado en la toma de decisión. Por otro lado, el criterio presenta también, como todos los
analizados hasta el momento, una buena estabilidad y resulta correctamente equilibrado.
118 IV . C IFRADO DE LAS COMUNICACIONES
Longitud
Número
secuencia Tiempo
descartes
(bytes)
106 749 669 0.571s
107 7 498 460 4.882s
108 74 993 343 25.586s
1 Estos sistemas, cuya salida no es proporcional a la entrada, son de mucho interés para los fı́sicos, pues la
mayorı́a de los sistemas fı́sicos presentes en la Naturaleza se comportan de forma no lineal. Como ejemplo
paradigmático de estos sistemas suele citarse al tiempo metereológico, donde pequeños cambios en alguna
de las variables implicadas tienen grandes e impredecibles consecuencias, de forma que pueda analizarse el
comportamiento de este tipo de decimación.
IV .3. N UEVOS CRITERIOS DE DECIMACI ÓN 119
Tiempo
Equilibrado
Criterio Tipo por
( %)
decisión
MITAD Simple X (49.85 %) 0.406µs
MENOR Compuesto X (49.66 %) 0.437µs
PAR Simple X (50.02 %) 0.487µs
NO-
LINEAL
Compuesto % (74.96 %) 0.571µs
Cuadro IV.6: Tabla resumen de datos experimentales para los diferentes criterios pre-
sentados
IV .3.7. Conclusiones
En esta sección se han presentado una serie de nuevos criterios de decimación,
adaptados a los nuevos registros de desplazamiento utilizados en el diseño final del
cifrador, comprobando cuáles de ellos cumplen, y en qué medida, los requisitos im-
puestos en la sección IV.3.2.
En principio, todos los criterios, excepto aquel diseñado mediante una función no
lineal, resultan aptos para su uso, pues presentan buenas caracterı́sticas de estabilidad,
equilibrio y eficiencia.
Es, sin embargo, en este último aspecto donde podemos encontrar las diferencias
más significativas. Éstas radican en la complejidad de la definición de cada criterio y,
como consecuencia, en los diferentes rendimientos proporcionados por cada uno.
En este sentido, el claro ganador es el criterio MITAD, que necesita únicamente 2
instrucciones máquina, que hace que no parezca posible encontrar un criterio aún más
sencillo con menor coste computacional y que, por supuesto, siga siendo funcional.
Aunque las diferencia en el rendimiento entre criterios es mı́nima en una decisión
individual, ésta puede hacerse significativa conforme aumenta la cantidad de secuencia
de salida generada. En la Figura IV.3 pueden encontrarse los tiempos invertidos por
cada criterios en la generación de secuencias de salida de diferentes longitudes (106 , 107
y 108 elementos).
Por último, los datos experimentales obtenidos para cada uno de los criterios se
resumen en el Cuadro IV.6.
120 IV . C IFRADO DE LAS COMUNICACIONES
30
25
20
Tiempo (s)
15
10
5
MITAD
MENOR
PAR
NO-LINEAL
0
106 107 108
Longitud de la secuencia
Criptoanálisis de generadores con salida irregular Para llevar a cabo este ataque, un
atacante debe ser capaz de monitorizar la salida del generador y tener acceso a su señal
de reloj interna. Bajo estas condiciones, es posible recuperar total o parcialmente los
contenidos de los registros R1 y R2 .
En el caso de que el generador sea definido sobre el cuerpo tradicional GF(2), el
ataque es directo y definitivo. En efecto, si en un ciclo de reloj determinado el cifrador
no produce salida, el atacante puede inferir de inmediato que el bit correspondiente de
la secuencia generada por R1 era un 0. Por el contrario, si se produce salida, entonces
el bit correspondiente de R1 era 1 y el de R2 el que se entrega como salida.
De esta forma resulta trivial reconstruir, casi en su totalidad, los contenidos iniciales
de los registros, excepto unos pocos bits de R2 , que pueden, sin embargo, obtenerse
inmediatamente con algunos intentos por prueba y error (en término medio, unos L/2
intentos, siendo L la longitud de R2 ).
Si, por el contrario, el generador de secuencia ha sido definido utilizando cuerpos
extendidos, haciendo uso de algunos de los criterios presentados en la sección anterior,
el criptoanálisis se hace algo más difı́cil, aunque no imposible.
En efecto, si se utiliza, por ejemplo, el criterio de decimación MITAD, el atacante,
al observar un ciclo que no produce salida, sólo puede inferir que el valor correspon-
diente de R1 es menor que 2n−1 , siendo n el tamaño del cuerpo utilizado. Este hecho,
innegablemente, dificulta el ataque, sobre todo para valores de n de 16 y 32 bits, pero
en última instancia no lo hace imposible. El resto de criterios de decimación, como
MENOR, PAR Y NO-LINEAL, implican ataques de complejidades algorı́tmicas simi-
lares.
La gestión dinámica del ratio adapta el ratio de funcionamiento del sistema, re-
duciendo o aumentando su valor, a la ocupación del búfer en cada momento, con
el fin de evitar el agotamiento o desbordamiento del mismo.
tores en la fecha de publicación. Curiosamente, aunque es citado por multitud de artı́culos, no está disponible
actualmente en Internet y es necesario pedirlo directamente a los autores.
IV .4. B ÚFER DE SALIDA Y T ÉCNICAS PARA LA GESTI ÓN DE LA DECIMACI ÓN IRREGULAR 123
Resulta necesario, por tanto, el uso de dos señales de reloj diferentes, una para cada
una de los módulos implicados, con el fin de tratar de evitar que se produzcan faltas y,
simultáneamente, maximizar en lo posible el rendimiento del sistema.
IV .2 Ejemplo. Imagı́nese un sistema capaz de ejecutar seis veces la rutina del generador de secuencia
por unidad de tiempo. Su ratio a será, por tanto, a = 6. En cada una de estas ejecuciones, el sistema
tendrá una posibilidad de 1/2 de generar o no secuencia.
En esta misma unidad de tiempo, el sistema consume, de forma constante, 3 caracteres de la secuencia
generada en el proceso anterior, por lo que su ratio b será b = 3. De esta forma, el ratio de fun-
cionamiento global del sitema será α = a : b = 6 : 3 = 2, lo que significa que el módulo de generación
de secuencia funciona dos veces más rápido que el de cifrado.
Ratio a = 4
pulsos /
unidad tiempo
Ratio b = 3
Figura IV.4: La figura muestra un sistema con ratio α = 4 : 3. Los pulsos sombreados
indican aquellos en los que se produce salida. Aunque a = 4, en la unidad de tiempo
mostrada como ejemplo se producen sólo 3 caracteres de secuencia cifrante. Dado que
b = 3, también se consumen 3, de forma que el tamaño del búfer en esa unidad de
tiempo queda intacto.
Si a/2 < b, o, lo que es lo mismo, a < 2b, el sistema no será capaz de suministrar
secuencia suficientemente rápido y producirá faltas de forma constante.
Si a > 2b, el sistema genera secuencia más rápidamente de la que ésta se consume,
por lo que las faltas en el suministro de elementos para la secuencia cifrante final
serán poco numerosas.
A la vista de los datos anteriores, parece claro que, para evitar faltas del sistema, el
diseño final deberá hacer uso de ratios α > 2 (esta cuestión será analizada en mayor
profundidad en las secciones IV.4.3 y IV.4.4). En ese caso, el generador produce más
elementos de los que se consumen en el proceso de cifrado. Surge, por tanto, una pre-
gunta natural: ¿qué ocurre con los elementos no utilizados?. En este punto, planteamos
varias alternativas:
Estos elementos pueden almacenarse, para su uso posterior, cuando haya ciclos
en los que salida del generador de secuencia sea menor que la necesitada por el
módulo de cifrado.
Esta última opción, mucho más recomendable y eficiente, refuerza la hipótesis que
venimos planteando de que el uso de la contramedida del aumento del ratio de fun-
cionamiento está inevitablemente vinculada al uso de un búfer de salida, que almacene
los elementos sobrantes, y que ambas medidas se necesitan mutuamente.
Un búfer infinito Para ilustrar este punto, obsérvese la Figura IV.5, en la que puede
encontrarse una simulación realizada para mostrar el comportamiento de un módulo
generador funcionando a diferentes ratios α. La gráfica muestra cómo evolucionarı́a la
cantidad de elementos almacenados en un búfer imaginario, de tamaño teórico infinito,
colocado a la salida del generador de secuencia.
Como puede observarse, el ratio α = 1 conducirı́a inevitablemente al agotamiento
de dicho búfer en unas pocas iteraciones. Por el contrario, utilizando un ratio α = 3, el
comportamiento del sistema serı́a el opuesto: el tamaño del búfer crecerı́a sin lı́mites
y, sea cual sea éste en la práctica, terminará por desbordarse irremediablemente. Por
último, la situación de equilibrio se produce alrededor de α = 2, donde el sistema
podrı́a funcionar de forma estable, es decir, sin producir faltas y sin requerir tamaños
de búfer excesivamente grandes.
La pregunta obvia que surge a continuación es: ¿cuál es la combinación adecuada de
ratio α y tamaño de búfer para que el sistema sea estable?. Esta cuestión será abordaba
a continuación.
126 IV . C IFRADO DE LAS COMUNICACIONES
600
500 α=3:1
400
300
200
Tamaño del búfer
100 α=2:1
−100
−200
−300 α=1:1
−400
−500
0 200 400 600 800 1000
Iteración
MÓDULO
GENERADOR DE
SECUENCIA
Ratio = a pulsos/unidad
tiempo
R1
BÚFER DE
DECIMACIÓN P SALIDA
Tamaño: B
R2 elementos
Figura IV.6: Esquema de cifrador con búfer intermedio entre el módulo de generación
y el de cifrado
Problema 2 Dado que el tamaño del búfer utilizado es B, ¿cuál es el ratio mı́nimo
de funcionamiento que garantiza que la probabilidad de falta M(B, α) puede hacerse
arbitrariamente pequeña?
Para llevar a cabo este análisis, modelaremos el sistema realizando las siguientes
suposiciones:
El eje temporal del sistema está divido en unidades de tiempo de igual duración,
que denominaremos intervalos, sin que sea relevante la magnitud concreta de los
mismos.
Asimismo, durante cada uno de los intervalos, el sistema retira del búfer b ele-
mentos de forma sistemática.
En la Figura IV.7 puede encontrarse un esquema del modelo del sistema que se
utilizará para los cálculos posteriores.
La modelización matemática se llevará a cabo utilizando las denominadas cadenas
de Markov [19, 20], que se postulan como un candidato natural para afrontar este tipo
de problemas. El análisis comenzará obteniendo, en la siguiente sección, un resultado
que será necesario para los cálculos posteriores. A continuación, en la sección IV.4.2.2
se introducirán una serie mı́nima de conceptos acerca de las cadenas de Markov y,
128 IV . C IFRADO DE LAS COMUNICACIONES
Búfer de B bytes
Secuencia Datos cifrados
cifrante
..
Tasa = a bytes / Tasa = b bytes /
unidad de tiempo unidad de tiempo
Datos a cifrar
Figura IV.7: Modelo del sistema utilizado en la derivación del tamaño adecuado del
búfer en función del ratio de funcionamiento
finalmente, se presentan los cálculos realizados, juntos con los resultados obtenidos y
su correspondiente análisis.
1. Cada experimento tiene dos posibles salidas, que se denominan éxito y fracaso.
2. La probabilidad de éxito p es la misma en cada experimento, y ésta no se ve afecta-
da por el conocimiento del resultado de experimentos previos (se trata de sucesos
independientes). La probabilidad de fracaso viene dada por q = 1 − p.
IV .4 Ejemplo. Se lanza una moneda al aire seis veces. ¿Cuál es la probabilidad de que se obtengan
exactamente 3 caras? La respuesta, completamente anti-intuitiva, es:
6 1 3 1 3
!
1
b(6, 00 5, 3) = = 20 × = 00 3125
3 2 2 64
Teniendo en cuenta que un intervalo de tiempo está divido en a ciclos, queda fi-
nalmente que la probabilidad de que el sistema genere exactamente k elementos en un
intervalo de tiempo, que denominaremos Pk , es:
! a
a 1
(IV.4) Pk = b(a, 1/2, k) =
k 2
Una derivación alternativa, con la que llegaremos al mismo resultado anterior, con-
siste en utilizar una secuencia binaria, donde un bit ’1’ significa que, en ese ciclo de
reloj el generador produjo un elemento y un bit ’0’ significa que no lo hizo, y contar el
número de combinaciones que tienen exactamente k bits a ’1’.
Este número equivale a la cantidad de combinaciones con repetición de a elementos
tomados de k en k:
!
a
k
Dado que cada una de estas secuencias es equiprobable, con probabilidad 1/2, el
resultado final es que la probabilidad de que se produzcan exactamente k elementos en
un intervalo de tiempo es:
a !
1 a
(IV.5)
2 k
Cadenas de Markov Una cadena de Markov consta de una serie de estados, S = {s1 , s2 , . . . , sr }.
El proceso comienza en uno de estos estados y transita sucesivamente de un estado a
otro. Si la cadena está en un momento dado en el estado si , entonces transita al estado
s j con probabilidad pij . Estas probabilidades se denominan probabilidades de transición y
suelen escribirse en forma de matriz.
130 IV . C IFRADO DE LAS COMUNICACIONES
IV .5 Ejemplo. De acuerdo a su autor, J.R.R. Tolkien, el fantástico mundo de la Tierra Media fue
bendecido con muchos dones, pero entre ellos no se encontraba el del buen tiempo. De hecho, sus
habitantes nunca disfrutaban de dos dı́as seguidos de buen tiempo (BT). Si un dı́a lucı́a el sol, al
dı́a siguiente tendrı́an lluvia (Ll) o nieve (N) con seguridad e igual probabilidad. Si llovı́a o nevaba,
tendrı́an un 50 % de posibilidades de continuar igual al dı́a siguiente.
Con esta información, es posible formar una cadena de Markov P que modelice el desagradable clima
de la Tierra Media:
Ll BT N
Ll 1/2 1/4 1/4
P =BT
1/2 0 1/2
N 1/4 1/4 1/2
Es muy común también representar la cadena utilizando un diagrama de transiciones, como puede
observarse en la Figura IV.8.
Matriz de transición Se aborda ahora una cuestión esencial en el desarrollo, que con-
siste en calcular la probabilidad de que, dada una cadena en un estado si arbitrario,
transite a un estado s j en exactamente n pasos. Este importante concepto se denota por
(n)
pij y puede calcularse utilizando el siguiente resultado.
IV .6 Ejemplo. Si se calculan las sucesivas potencias de la matriz de transiciones del ejemplo anterior
(IV.5), se observa que las predicciones sobre el tiempo son independientes del tiempo del dı́a actual:
Ll BT N
Ll 0.4 0.2 0.4
P6 =BT
0.4 0.2 0.4
N 0.4 0.2 0.4
Como puede observarse, las predicciones para los tres tipos de tiempo, Ll, BT y N, son 0.4, 0.2 y
0.4 independientemente del estado en el que comenzara la cadena. Éste es un ejemplo de un tipo de
cadena de Markov muy importante denominada cadena regular, que será estudiada con más detalle a
continuación.
IV .4. B ÚFER DE SALIDA Y T ÉCNICAS PARA LA GESTI ÓN DE LA DECIMACI ÓN IRREGULAR 131
Como la segunda de las restricciones es más fuerte, resulta claro que toda cadena
regular es ergódica. Pero no toda cadena ergódica es necesariamente regular, como
puede observarse en el siguiente ejemplo.
A B
!
A 0 1
P=
B 1 0
Resulta claro que es posible transitar libremente entre cualesquiera estados, luego la cadena es
ergódica. Sin embargo, si n es impar, entonces no es posible moverse del estado A al estado A en n
pasos y, si n es par, no se puede transitar del estado A al B en n pasos. Por tanto, luego la cadena no
es regular.
IV .3 Teorema. (Teorema Fundamental del Lı́mite para cadena regulares) Sea P la matriz
de transición de una cadena regular. Entonces, conforme n → ∞, las sucesivas potencias Pn
tienden a una matriz lı́mite W cuyas filas son idénticas e iguales a un vector w. El vector w,
denominado vector fijo, es estrictamente positivo, es decir, todas sus componentes son positivas
y suman 1.
Más aún, el vector fijo se alcanza desde cualquier estado inicial, como demuestra el
siguiente resultado.
IV .4 Teorema. Sea P la matriz de transición de una cadena regular con vector fijo w. Entonces
para cualquier vector de probabilidad u (estado inicial), se cumple que uPn → w conforme
n → ∞.
Otros resultados y definiciones importantes que serán necesarias más adelante son
las siguientes.
W = lı́m Pn ,
n→∞
sea w la fila común de W, y sea c un vector columna cuyos componentes son todos 1.
Entonce se cumple que:
132 IV . C IFRADO DE LAS COMUNICACIONES
IV .10 Definición. Un vector fila w con la propiedad wP=w se denomina vector fila fijo
de P. De igual forma, un vector columna x tal que Px=x se llama vector columna fijo de
P.
IV .8 Ejemplo. Aplicando el Teorema IV .3, resulta fácil encontrar el vector lı́mite w partiendo del
hecho de que
w1 + w2 + w3 = 1
y que
1/2 1/4 1/4
(w1 , w2 , w3 ) 1/2 0 1/2 = (w1 , w2 , w3 )
1/4 1/4 1/2
La expresión anterior permite plantear las siguientes cuatro ecuaciones con tres incógnitas:
w1 + w2 + w3 = 1,
(1/2)w1 + (1/2)w2 + (1/4)w3 = w1 ,
(1/4)w1 + (1/4)w3 = w2 ,
(1/4)w1 + (1/2)w2 + (1/2)w3 = w3 ,
El teorema anterior garantiza que este sistema de ecuaciones tiene solución única. Resolviéndolo, se
obtiene la solución
w = (0.4, 0.2, 0.4)
que, por supuesto, coincide con lo predicho por P6 , dado en el ejemplo IV.6.
Resolviendo se obtiene:
IV .4.2.3. Estudio del tamaño del búfer de salida utilizando la teorı́a de cadenas de
Markov
En este punto, presentadas ya las herramientas matemáticas básicas necesarias, se
tratará de responder a las dos preguntas planteadas en IV.4.2. Para ello se utilizará
la teorı́a de cadenas de Markov para modelizar un búfer de salida, y analizar cómo
evolucionarı́a su ocupación cuando se modifican los ratios de funcionamiento α y los
tamaños del propio búfer.
De esta forma, se encontrarán las relaciones entre ambos parámetros y cómo el cam-
bio en el valor de uno de ellos afecta al otro. El objetivo final es encontrar aquella com-
binación de ratio de funcionamiento y tamaño de búfer que minimiza el valor de ambos
y, al mismo tiempo, sigue siendo segura y eficiente.
IV .10 Ejemplo. Ası́, supóngase que el sistema a analizar se encuentra en un instante de tiempo k,
en el que su búfer tiene 3 elementos, Bk−1 = 3, (de 5 elementos de tamaño máximo). Por otro lado,
el sistema funciona con un ratio α = 3 : 2. En dicho intervalo de tiempo el generador de secuencia
proporciona 3 elementos, de forma que las variables estadı́sticas anteriores tomarı́an los valores Ek = 2,
Lk = 3 − 2 = 1 y Bk = 4.
IV .11 Ejemplo. Sea X33:2 la cadena que modela el funcionamiento de un generador con ratio α = 3 : 2
y tamaño de búfer B = 3. Sus probabilidades de transición pueden encontrarse entonces en la Figura
IV .9. En ella la columna Secuencia simula la salida producida por el generador durante tres ciclos,
donde un ’1’ simboliza que se ha producido un elemento en dicho ciclo y un ’0’ que no. Ası́, la secuencia
’101’ significa que el generador produjo 2 elementos, en los ciclos primero y tercero.
134 IV . C IFRADO DE LAS COMUNICACIONES
Sı́mbolo Descripción
B Tamaño máximo del búfer
En cada uno de los intervalos de tiempo, se ejecuta a veces la
rutina de generación de secuencia, con una probabilidad de 1/2
a
de generar en cada ejecución un elemento e incorporándolo al
búfer
El sistema retira del búfer b elementos de forma sistemática en
b
cada intervalo de tiempo
α Relación entre las dos cantidades anteriores, α = a : b
Número de elementos proporcionados por el generador de
En
secuencia al final del intervalo de tiempo n
Número de elementos introducidos o eliminados del búfer al
Ln
final del intervalo n. Claramente, Ln = En − b
Tamaño (número de elementos) del búfer al final del intervalo
Bn
de tiempo n. Claramente, Bn = Bn−1 + Ln
Probabilidad de que el búfer se agote y se produzca una falta del
M(B, α) sistema. Es decir, que un intervalo tiempo el búfer no tengo
elementos que suministrar al módulo de cifrado
Cuadro IV.7: Resumen de los conceptos más significativos del modelo del búfer de
salida del sistema
Secuencia En Ln
0 0 0 0 -2
0 0 1 1 -1
Pr(Ln =-2)=1/8
0 1 0 1 -1
Pr(Ln =-1)=3/8
0 1 1 2 0
Pr(Ln =0)=3/8
1 0 0 1 -1
Pr(Ln =1)=1/8
1 0 1 2 0
1 1 0 2 0
1 1 1 3 1
Figura IV.9: Por ejemplo, sólo tres [(0, 0), (0, 1), (1, 0)] de las ocho posibles combinaciones
conducen a que el tamaño del búfer se decremente en un elemento, por lo que Pr(Ln =-
1)=3/8.
IV .4. B ÚFER DE SALIDA Y T ÉCNICAS PARA LA GESTI ÓN DE LA DECIMACI ÓN IRREGULAR 135
3/8
4/8
1/8
1/8 1 3/8
7/8 3/8 3
0 1 2 3 1/8 1/8
4/8
0 7/8 1/8 1/8 0
0 1/8 2 3/8
1 4/8 3/8 1/8 0 1/8
P=
2 1/8 3/8 3/8 1/8
3 0 1/8 3/8 4/8
Figura IV.10: Matriz y diagrama de transiciones para la cadena de Markov P que mod-
ela la evolución del tamaño del búfer de salida B.
del estado 0 al estado 0, es decir, permanecer en dicho estado tras un ciclo de reloj. El
estado 0 corresponde a un búfer con 0 elementos, o vacı́o. Por tanto, la entrada (0,0) de
la matriz de transición corresponde a la probabilidad de que un búfer vacı́o en el ciclo
n permanezca en ese estado en el ciclo n + 1.
Para calcular esta probabilidad, basta con tener en cuenta todos aquellos valores de
Ln compatibles con el estado final. En esta caso, dado que el estado final es el mismo, los
valores obvios son Ln = 0. A ellos hay que sumar aquellos que reducirı́an la ocupación
del búfer por debajo de cero, si eso fuera posible. Esta situación corresponde a una falta
del sistema. Según los valores de la Figura IV.9, estos valores son Ln = −1 y Ln = −2. Por
tanto, si la cadena está en el estado Xn3:2 = 0, es decir, el búfer está vacı́o en el instante
n, la probabilidad de permanecer en dicho estado al instante siguiente es:
! a
a 1
(IV.6) Pak = b(a, 1/2, k) =
k 2
b−i !
1 aX a
si j = 0
2 k
k=0
a X a !
1 a
si j = B
2 k=B+b−i k
P(i, j) =
(IV.7)
si −b > j − i > a − b
0
a !
1 a
resto de casos
j+b−i
2
(IV.8)
0 1 2 ... B−1 B
b ! ! ! ! a !
X a a a a X a
...
−a
0 2 2−a 2−a 2−a 2−a
b+1 b+2
k B−b−1 k
k=0 k=B+b
a ! ! ! ! a !
X a a a a X a
1 2
−a
2 −a
2−a
... 2 −a
2−a
b+1
k b B−b−2 k
k=B−b−1 k=B+b−1
a ! ! ! ! a !
X a a −a a a X a
...
−a −a
2−a 2−a
2 2
2 2
P= k b−1 b B−b−3 k
k=B−b−2 k=B+b−2
.. .. .. ..
.
. . ... ... ... ! .
a !
−a a a
X
B − 1 0 0 0 ... 2 2−a
b k
k=b+1
! a !
a a
X
... 2−a 2−a
B 0 0 0
b−1 k
k=b
Distribución estacionaria Sea w = (w0 , w1 , . . . , wB ) el vector fijo que define las proba-
bilidades estacionarias de X. De acuerdo con el Teorema IV.3, el vector w puede calcu-
larse resolviendo el siguiente sistema de ecuaciones:
IV .4. B ÚFER DE SALIDA Y T ÉCNICAS PARA LA GESTI ÓN DE LA DECIMACI ÓN IRREGULAR 137
w0 + w1 + . . . + wB = 1
0 = w0 · P(0, 0) + w1 · P(0, 1) + . . . + wB · P(0, B)
w
(IV.9) .
..
w = w · P(B, 0) + w · P(B, 1) + . . . + w · P(B, B)
B 0 1 B
Sin embargo, el cálculo anterior resulta engorroso y tedioso, incluso utilizando pro-
gramas especı́ficos, pues es necesario resolver un sistema de (B + 1) × (B + 1) ecuaciones.
En este caso suele utilizarse un método más eficiente y sencillo, derivado de la
Definición IV.10. Según esta definición, el vector fijo w puede también calcularse re-
solviendo el siguiente sistema de ecuaciones matriciales:
wP = w
w1 = 1
Método alternativo Haciendo uso del Teorema IV.4, puede derivarse un método difer-
ente para calcular la distribución estacionaria de P.
Éste consiste en elegir arbitrariamente un vector w0 cuyas componentes sumen 1.
Luego, de forma iterativa, y teniendo en cuenta que wi → w conforme i → ∞, se calcula
el vector wi = wi−1 P, hasta que, en una iteración dada j, la distancia entre los vectores
w j y w j−1 es menor que algún parámetro predeterminado .
Este método tiene la ventaja, respecto al presentado anteriormente, de que su imple-
mentación resulta más sencilla. Sin embargo, resulta más costoso computacionalmente,
pues el número de iteraciones necesario, y las multiplicaciones asociadas, puede hac-
erse alto si el valor del parámetro es muy bajo.
Ratio α
Tamaño
búfer 1.0 1.25 1.33 1.6 1.66 2.0 2.5 3.0
B
8 1.0 0.9624 0.9126 0.7639 0.6315 0.1111 7.9516 · 10−4 7.7786 · 10−6
16 1.0 0.9624 0.9126 0.7639 0.6312 0.0588 1.1060 · 10−6 7.5023 · 10−11
24 1.0 0.9624 0.9126 0.7639 0.6312 0.0400 1.5391 · 10−9 7.2359 · 10−16
32 1.0 0.9624 0.9126 0.7639 0.6312 0.0303 2.1418 · 10−12 6.9790 · 10−21
Cuadro IV.8: Probabilidades de falta (agotamiento del búfer) para distintos valores del
tamaño de búfer B y ratio de funcionamiento α.
Probabilidad
de fallo
0.8
0.6
0.4
0.2
5
10
10 15
1.5
2 20
2.5
3 25 Tamaño búfer
3.5
Ratio 4 30
4.5
5 35
1) = 1. Por supuesto, éste es un resultado ya conocido, y reconocido por los propios au-
tores, pero el método que hemos presentado permite obtener una justificación formal
del mismo.
Los resultados, sin embargo, se vuelven más interesantes conforme aumenta el ratio
α. En ese caso, se observa claramente cómo desciende gradualmente la probabilidad de
falta. De hecho, lo hace de forma abrupta a partir de un ratio de 1.25. Este efecto puede
observarse más claramente en la Figura IV.11, que muestra de forma gráfica la relación
entre tamaño de búfer, ratio y probabilidad de falta.
Como cabrı́a esperar, en general, si aumenta el tamaño del búfer, también dismin-
uye la probabilidad de falta. Sin embargo, este no es el caso para valores de α < 2,
donde un aumento del tamaño del búfer no reduce la probabilidad de falta, o lo hace
en una cantidad despreciable.
La razón estriba en el hecho de que, para esos ratios de funcionamiento, las proba-
bilidades de transición desde cualquier estado hacia el estado s0 , que modeliza el ago-
tamiento del búfer, se hacen gradualmente mayores conforme α disminuye. Por esta
razón, sea cual sea el tamaño de búfer, finalmente el estado s0 terminará siendo alcan-
zado.
Sin embargo, a pesar del efecto recién mencionado, la principal conclusión de los
140 IV . C IFRADO DE LAS COMUNICACIONES
Rellenar los faltas con valores arbitrarios Por ejemplo, con valores ’0’ y ’1’ de forma
alternativa, si el generador está definido sobre GF(2). En el caso del sistema presentado
en este trabajo, se propone comenzar en un valor arbitrario i del cuerpo GF(2n ) corre-
spondiente e incrementar este valor en cada falta, módulo el orden del cuerpo. De esta
forma, en el primer falta la salida del sistema serı́a i ≡ mód 2n , i + 1 ≡ mód 2n en el
segundo, etc...
Si suponemos que los parámetros del sistema han sido elegidos de forma cuidadosa
y que, por tanto, la tasa de faltas es muy pequeña, este método no tiene porqué reducir
sensiblemente la calidad de la secuencia cifrante producida. Por supuesto, si la tasa de
faltas fuera alta, la secuencia contendrı́a un alto número de elementos ”predecibles“ y,
por tanto, su complejidad lineal caerı́a drásticamente.
Por otro lado, la operación de reducción modular incrementa la complejidad de la
implementación, tanto software como hardware, y aunque se espera que se utilice de
forma excepcional, es costosa computacionalmente, lo que implicarı́a una ligera penal-
ización en el rendimiento.
Este enfoque tiene el problema de que necesita este segundo búfer, aunque si bien
éste podrı́a ser de unos pocos elementos y, por tanto, ocupar pocos bytes de almace-
namiento. Por contra, proporciona, en principio, una solución más elegante y segura
que el método anterior.
Ambos métodos pueden aplicarse por igual al caso del generador shrinking exten-
dido, pero por las razones anteriormente expuestas, los autores recomiendan el uso del
segundo método.
Índice de descarte Con el fin de facilitar el análisis de los resultados, hemos definido
una nueva magnitud, que denominaremos ı́ndice de descarte y denotaremos D(B, α). Este
ı́ndice pretende dar una estimación de la proporción de elementos generados que no
pueden ser almacenados en el búfer porque éste ha alcanzado su máxima capacidad y
que, por tanto, deben ser desechados.
La expresión para calcular este ı́ndice es la siguiente:
Cuadro IV.9: Índice de descarte para distintos tamaños de búfer B y ratios de fun-
cionamiento α.
Indice de descarte
1.6
1.4
1.2
1
0.8
0.6
0.4
5
0.2 4.5
4
3.5
50 3
10
15 2.5 Ratio
20 2
25 1.5
Tamaño búfer 30 1
35
Figura IV.12: Representación gráfica del ı́ndice de descarte, D(B, α), para los distintos
valores del tamaño de búfer B y ratio de funcionamiento α
1
1.5
0.8
1.25
1
0.6
Prob. fallo
descartes
Indice de
0.75
0.4
Punto B
0.5
0.2
0.25
Punto A
Prob. fallo
Indice descartes
0 0
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Ratio
algunos elementos, sea cual sea el criterio utilizado, siempre resulta en otra secuencia
estadı́sticamente perfecta. Puede decirse que se obtiene, simplemente, una secuencia
estadı́sticamente perfecta de menor longitud.
El resultado anterior puede demostrarse utilizando un sencillo razonamiento de re-
ducción al absurdo. En efecto, si existiera una transformación que, dada una secuencia
de entrada estadı́sticamente perfecta, produjera una secuencia de salida que no preser-
vara dichas propiedades, significarı́a que existirı́an porciones de la secuencia de entra-
da ”privilegiadas“ respecto a otras. Este hecho contradice la hipótesis de partida, luego
no puede existir tal transformación.
[...] If the ABSG outputs one bit when the buffer is full, then the newly
computed bit is not added into the queue, i.e. it is dropped. [...]
Zona crítica
superior
Bsup
BÚFER DE
SALIDA
Tamaño: B
elementos
Binf
Zona crítica
inferior
ergéticos. Aunque este hecho puede pasar prácticamente desapercibido en las platafor-
mas más potentes, puede suponer un gasto significativo en las más humildes, habitual-
mente alimentadas con baterı́as.
Para evitar este problema se presentan dos nuevas soluciones, que hemos denom-
inado ajuste dinámico del ratio y pausa de generación, que impiden en ambos casos dicho
desbordamiento y sus consecuencias.
Valores umbrales Los niveles de ocupación a los que deben dispararse el ajuste dinámico
del ratio α, se definen como valores o niveles umbrales superior e inferior, y los denotare-
mos como Bsup y Bin f .
Alcanzar el valor Bsup indica que el búfer está cerca de su lı́mite máximo de ocu-
pación y que, por tanto, debe rebajarse el ritmo de producción de elementos. Bin f , por
el contrario, muestra que el búfer sufre riesgo de vaciarse y producir una falta del sis-
tema. En la Figura IV.14 puede encontrarse una descripción gráfica de estos valores.
En general, los valores óptimos para el parámetro Bsup dependen del ratio de fun-
cionamiento α y del tamaño de búfer B. De forma intuitiva, cuanto mayor sea el valor
de α, menores pueden ser tanto Bin f como Bsup , puesto que la probabilidad de falta será
menor y, por tanto, el valor de Bin f podrá acercarse más a cero sin posibilidad de que,
finalmente, lo alcance.
Por otro lado, otro aspecto que debe ser tenido en cuenta es que los valores óptimos
de estos parámetros deben ser tales que permitan minimizar el tiempo total que el
módulo de generación de secuencia está en funcionamiento. De esta forma, en dis-
positivos embebidos o de baja capacidad de cómputo se reduce considerablemente el
consumo total debido al proceso de cifrado.
146 IV . C IFRADO DE LAS COMUNICACIONES
Ajuste del ratio α Por otro lado, el ajuste del ratio α debe realizarse de forma gradu-
al, para evitar un posible efecto rebote, que provoque problemas de desbordamientos o
agotamientos abruptos.
Sin embargo, incluso cuando el ajuste se realiza de forma conveniente, esta prop-
uesta adolece de ciertos inconvenientes, sobre todo cuando ésta se utiliza en una im-
plementación hardware del sistema.
En ese caso, serı́a necesario modular la señal de reloj del módulo de generación de se-
cuencia, incluyendo valores no enteros, como 2.25 o 2.5. Esto implica un coste adicional
en complejidad del diseño, que deberı́a incluir un módulo especial para gestionar estos
cambios en el ratio de funcionamiento.
Por otro parte, también provocarı́a que el módulo de generación y el de cifrado
desincronizasen sus relojes y funcionasen, por tanto, de forma ası́ncrona. Para evitar
estos inconvenientes se propone utilizar en las implementaciones hardware, exclusiva-
mente, ratios α de valor entero,
Afortunadamente, el ajuste dinámico de α resulta más sencillo cuando la imple-
mentación del cifrador se lleva a cabo en software. En ese caso, basta con ajustar con-
venientemente el número de iteraciones de los bucles que gobiernan los ratios a y b,
tal y como se describió en la sección IV.4.1.1. De acuerdo a estas sencillas directrices, el
valor de α se ajusta de forma efectiva a la ocupación del búfer. En la Figura IV.15 puede
encontrarse cómo evoluciona el valor del ratio durante una ejecución real del sistema.
Por último, en el Listado 15 puede encontrarse cómo quedarı́a la implementación
final de este método de ajuste.
IV .4. B ÚFER DE SALIDA Y T ÉCNICAS PARA LA GESTI ÓN DE LA DECIMACI ÓN IRREGULAR 147
4
Ratio α
0
0 200 400 600 800 1000
Iteración
Figura IV.15: Evolución del valor del ratio α durante 1 000 ciclos del generador (αmax =
6, αmin = 1)
Valores umbrales En esta solución son también necesarios los dos valores umbrales
definidos para la propuesta anterior aunque, en este caso, toman significados ligera-
mente diferentes.
Bsup hace referencia ahora al valor de ocupación del búfer que, una vez alcanzado,
provocarı́a la desactivación total del módulo de generación de secuencia. Por otro lado,
Bin f indica el nivel al que deberá reactivarse dicho módulo, con el fin de que no se
produzcan faltas.
Debido a su modo de funcionamiento, el valor óptimo para Bsup puede ser más
cercano, en esta caso, al 100 %. En efecto, dado que la generación de elementos se inter-
rumpe completamente y, por tanto, existe la seguridad de que el búfer no se desbordará
en los próximos ciclos, el valor de Bsup puede ser tan alto como un 99 %. Por otro lado,
el valor adecuado de Bin f no sufre cambios y se sitúa, de nuevo, en torno al 20 %.
Sin embargo, como se analizará a continuación, el nivel Bsup nunca se alcanza en la
práctica, debido al modo de funcionamiento del generador.
148 IV . C IFRADO DE LAS COMUNICACIONES
Ocupación
Ahorro en
mı́nima y
Método ciclos de
máxima del
reloj
búfer
Adaptación dinámica de α 19.62 % 12.50 %-89.06 %
Parada del generador 18.80 % 12.50 %-20.31 %
60 120
Ajuste dinámico de ratio Ajuste dinámico de ratio
Parada del generador de secuencia Parada del generador de secuencia
50 100
40 80
Tamaño del búfer
30 60
20 40
10 20
0 0
0 200 400 600 800 1000 0 200 400 600 800 1000
Iteración Iteración
Figura IV.16: Evolución del nivel de ocupación del búfer del sistema con el uso de las
dos medidas anti-desbordamiento presentadas.
del búfer. Este efecto se produce en ambos métodos, y provoca comportamientos lig-
eramente erráticos cuando el tamaño del búfer es pequeño, del orden de 32 elementos
o menos. Cuando el tamaño crece por encima de los 64 elementos el sistema alcanza
estabilidad, y el efecto es inapreciable.
Por último, el Cuadro IV.10 resume los datos experimentales obtenidos sobre ambos
métodos.
IV .4.5. Conclusiones
A la vista del análisis realizado y los datos experimentales obtenidos en las sec-
ciones previas, la primera de las conclusiones es que el diseño original del generador
shrinking, tal y como se propuso por sus autores en [10], resulta impecable en su
planteamiento teórico pero adolece de importantes inconvenientes cuando se lleva a
la práctica.
El principal de estos inconvenientes es que debe utilizar un búfer conectado al
módulo generador para ocultar su salida irregular. Con el fin de evitar su agotamiento,
lo que introducirı́a debilidad criptográfica en la secuencia generada, los autores pro-
pusieron incrementar la velocidad de funcionamiento del módulo generador respecto
al de cifrado.
Las consecuencias de este incremento habı́an permanecido inexploradas hasta la
fecha. Los análisis realizados en este trabajo indican que, si no se toman medidas, el
búfer se desbordará inevitablemente debido a dicho aumento de ratio. En otras pal-
abras, no resulta posible evitar el vaciado y desbordamiento del búfer simultáneamente. O bien
150 IV . C IFRADO DE LAS COMUNICACIONES
se reduce el ratio para aumentar el rendimiento y evitar que se llene, con lo que se pro-
ducen faltas, o bien se aumenta el ratio para evitar estos faltas y entonces, inevitable-
mente, el búfer se desbordará.
El desbordamiento del búfer, al igual que su agotamiento, debe evitarse a toda costa,
pues acarrea una serie de inconvenientes muy importantes:
Se reduce notablemente el rendimiento, pues se generan multitud de elementos que,
posteriormente, son descartados y no se aprovechan en el módulo de cifrado. Su
generación, por tanto, ha resultado inútil y completamente prescindible.
Los elementos descartados provocan que el periodo de la secuencia generada no sea
exactamente el estimado de forma teórica, pues hay una gran cantidad de elementos
que no llegan a formar parte de la secuencia cifrante. Obviamente, el periodo real
es menor que el teórico y, además, resulta difı́cil de calcular en la práctica, debido
a la multitud de factores que afectan al valor final del mismo.
Por último, el desbordamiento provoca que la secuencia cifrante no sea exactamente
la secuencia shrunken, que ha sido bien estudiada y analizada, sino que ésta es nue-
vamente decimada, en función de parámetros como el tamaño del búfer o el ratio
de funcionamiento. En cualquier caso, hemos demostrado que este hecho no de-
berı́a, en principio, afectar a la seguridad criptográfica de la secuencia generada.
Afortunadamente, se han presentado nuevos métodos con los que sı́ resulta posible
evitar estos problemas. Éstos consisten en medidas que evitan el desbordamiento del
búfer, y se basan en la gestión del módulo de generación de secuencia.
Dado que su uso resulta imprescindible, los datos sobre el funcionamiento del búfer,
tales como su tamaño o ratio de funcionamiento, se convierten en un parámetro más
del sistema del cifrado. Aunque no es necesario que éstos se mantengan en secreto, sı́
deben intercambiarse entre ambos comunicantes antes de comenzar la comunicación.
Esto no supone mayor problema, pues existen muchos algoritmos de cifrado con ciertos
parámetros configurables, como la longitud de clave variable de AES [5].
Valores óptimos de los parámetros del sistema De acuerdo a los datos obtenidos en
las secciones IV.4.1 y IV.4.2, puede concluirse que el ratio de funcionamiento mı́nimo
para un sistema viable en la práctica es α = 2.5. Combinando el valor de α con unos
tamaños adecuados del búfer, pueden conseguirse probabilidades de agotamiento del
mismo prácticamente nulas.
En cuanto este tamaño de búfer necesario, llama la atención que, incluso para el
ratio recomendado, sólo es necesario un tamaño de búfer B de unos pocos elementos,
alrededor de 32, para conseguir probabilidades de falta del orden de M(32, 2.5) = 2 ·
10−12 . Además, doblar el tamaño del búfer reduce dicha probabilidad de falta M en un
factor de 1 000 aproximadamente.
Los datos a cifrar se generan de forma continua, con una cierta tasa fija o variable.
Distintas latencias: la comunicación puede tener diferentes latencias entre las partes,
dependiendo de la congestión de la red en cada momento.
Paquetes fuera de orden: los paquetes pueden seguir diferentes rutas y llegar des-
ordenados a su destino.
Aunque estos problemas son corregidos de forma transparente por el protocolo del
nivel de transporte (TCP), es necesario que un algoritmo de cifrado robusto sea capaz
de hacerles frente, pues existen multitud de escenarios donde el protocolo TCP no actúa
o no resulta adecuado.
Debido a estas buenas propiedades, los cifradores en flujo sı́ncronos son mayorı́a.
De hecho, en el reciente proyecto eSTREAM, 31 de los 34 candidatos aceptados para
evaluación se engloban dentro de esta categorı́a.
Sin embargo, este tipo de cifradores adolecen de un inconveniente importante, que
cobra máxima importancia en una red como Internet, pues está relacionado con la sin-
cronización en la comunicación. Como resulta claro, emisor y receptor deben estar per-
fectamente sincronizados para que el proceso de descifrado funcione correctamente.
De otra forma, en cuanto un sı́mbolo se añada o elimine durante la transmisión, las
partes en comunicación perderán su sincronı́a y el resto del mensaje se descifrará de
forma incorrecta.
Para solucionar este problema se suele utilizar un mecanismo de sincronización, que
funciona, a grandes rasgos, como sigue:
1 2 3 n
...
Trama número m Datos cifrados ...
Por último, incluso cifradores que son ampliamente utilizados actualmente, han
sufrido los mismos inconvenientes, habitualmente con consecuencias desastrosas,
que han permitido su completo criptoanálisis. Es el caso del estándar GSM [15],
o el protocolo de comunicación inalámbrica WEP [29].
IV, producirı́a el mismo texto cifrado. Por tanto, una vez que se identifica uno, todos
los demás pueden ser también fácilmente detectados y, su contenido, intuido, aunque
no se haya obtenido la clave de cifrado.
El uso de vectores de inicalización puede utilizarse para mitigar este problema y
evitar ası́ que cifrar dos veces el mismo texto en claro con la misma clave produzca el
mismo texto cifrado. Por supuesto, deben utilizarse diferentes IV en cada proceso de
cifrado. Cuando estos cifradores se utilizan en protocolos reales, el IV suele cambiarse
por cada paquete enviado, por lo que, en la práctica, significa que el estado interno del
cifrador se modifica constantemente.
De esta forma es posible cifrar un total de 264 bits utilizando la misma clave. Suponien-
do que cada paquete de datos tiene la longitud máxima permitida, alrededor de unos
1500 bytes en Internet, esta cantidad equivale al envı́o de más de 10 5 ∗ 1015 paquetes,
antes de que sea necesario reemplazar la clave.
Durante la fase de inicialización del cifrador, antes de que éste esté en disposición de
generar secuencia cifrante válida.
Cada vez que sea necesario reiniciar el estado del cifrador, a través del IV, como
sucede cuando éste se utiliza en redes de comunicaciones basadas en conmutación
de paquetes.
Este proceso ha sido diseñado para resultar eficiente, lo que resulta especialmente
importante en las aplicaciones prácticas que requieren una reinicialización frecuente,
como las transmisiones móviles e inalámbricas, que suelen utilizar el número de tra-
ma o paquete como IV. En la sección IV.5.4 puede encontrarse una comparativa de
rendimiento con otros importantes cifradores.
m elementos IV
f1i k elementos R1
IV0 ... IVm-1
di IVi
…
Decimación
di
f2i R2 P
di
…
di IVi
l elementos
y R2 .
3. En otras palabras, se realizan m ciclos del cifrador con la conexiones indicadas en la
figura superior y con los elementos de realimentación di ⊕ IVi ⊕ f1i y di ⊕ IVi ⊕ f2i con
0 ≤ i ≤ m para R1 y R2 respectivamente
Salida = Nuevo estado para R1 y R2
Criterios de diseño Las principales caracterı́sticas del diseño de este proceso son las
siguientes:
Otro de los criterios esenciales de diseño ha sido la eficiencia del proceso, que per-
mitiera su uso en escenarios de frecuente inicialización. Los datos acerca del
rendimiento pueden encontrarse en la sección IV.5.4.
IV .5. M ÓDULO DE CARGA DEL VECTOR DE INICIALIZACI ÓN 161
Resultados Realizados los tests anteriores sobre el mecanismo de carga del IV presen-
tado, los resultados pueden considerarse muy satisfactorios, no observándose ninguna
debilidad estadı́stica que permitiera un ataque de IV escogido.
Es importante señalar que los tests se han realizado para un valor de m ≥ 8, lo que
implica que, para que el proceso de carga sea seguro, deben utilizarse longitudes de IV
superiores a los 8 ∗ 8 = 64 bits.
Conforme decrece el valor de m, el nivel de seguridad también lo hace. Por ejemplo,
para valores de m ≤ 5 (40 bits), los tests pueden distinguir la secuencia de salida de una
aleatoria con un margen de error muy pequeño, con una probabilidad P < 2−8 , aunque
para ellos necesitan utilizar un total de 218 IV diferentes.
En cualquier caso, no se recomienda el uso de IVs de longitud menor a 64 bits,
porque eso aumentarı́a considerablemente la posibilidad de que se repitiera el mismo
IV durante la vida útil de la clave K, lo que habilitarı́a el ataque descrito en IV.5.1.2.
Rendimiento
Cifrador proceso carga
(ciclos/byte)
Salsa20 34.90
Rabbit 292.38
SOSEMANUK 744.46
LFSRe 1225.33
HC-128 63349.83
Los datos fueron obtenidos durante la carga de 106 IVs, utilizando el procedimiento
habitual (10 ejecuciones, descartando los valores extremos mayor y menor y calculando
la media aritmética del resto). En el Cuadro IV.11 pueden encontrarse los datos defini-
tivos, expresados en ciclos/byte.
Como se desprende de dichos datos, el proceso de carga de IV de nuestro cifrador
es muy competitivo, resultando sólo 1.6 veces más lento que uno de los ganadores del
eSTREAM, SOSEMANUK, pero, simultáneamente, más de 51 veces más rápido que
otro de los candidatos, HC-128. Como puede verse, la variabilidad en el rendimiento
de los procesos de carga es altı́sima entre los distintos cifradores. Por ejemplo, HC-128
es más de 1800 veces más lento que el más rápido de los cifradores en este sentido,
Salsa20. Por supuesto, todos los cifradores comparados son de perfil software.
El rendimiento máximo que puede alcanzar el mecanismo de carga está determina-
do, en última instancia, por la estructura interna del cifrador. Por tanto, resulta difı́cil
poder mejorar sustancialmente la velocidad de carga del VI, debido a que los pilares
básicos del diseño del cifrador son los registros de desplazamiento. Éstos son, por
definición, de naturaleza lineal por lo que, a pesar del uso de una función de deci-
mación, que introduce el componente no lineal, es necesario realizar un número mı́nimo
de iteraciones para ocultar de forma efectiva la linealidad subyacente.
10
RC4
E0
9 A5/1
LFSRe
8
Factor de resincronización (FR)
0
100 1000 10000
Longitud del paquete (bits)
El factor de resincronización es mayor cuanto menor sea la longitud del paquete a cifrar,
siendo realmente importante cuando éste es menor de aproximadamente 1 000
bits. Dado que se estima que la mitad de los paquetes que circulan por Inter-
net son sólo de unos 512 bits de longitud, la eficiencia del mecanismo de sin-
cronización cobra especial importancia en ese tramo.
Existe una correlación clara entre el tamaño del estado interno del cifrador y el FR. Aque-
llos cifradores con mayor estado interno requerirán, habitualmente, un mayor
tiempo para la resincronización.
otro lado, A5/1 necesita 414 ciclos de reloj para cifrar un paquete, de los que 186,
casi la mitad, son empleados en el mecanismo de sincronización.
La razón de que se haya optado en estos casos por un cifrador en flujo, a pesar de
su menor rendimiento para estos tamaños de datos a cifrar, puede radicar en el
hecho de que, habitualmente, sus primitivas criptográficas básicas se implemen-
tan más eficientemente en hardware.
IV .6. M ÓDULO DE CIFRADO Y DISE ÑO FINAL 165
GENERADOR DE
SECUENCIA
BÚFER DE
SALIDA
MÓDULO DE
CIFRADO
TEXTO EN CLARO
TEXTO CIFRADO
Diseño final Este módulo de cifrado completa el diseño final del cifrador que hemos
ido analizando en las secciones anteriores. A modo de resumen, este diseño puede
encontrarse de forma gráfica en la Figura IV.21.
166
m elementos
IV
MÓDULO
GENERADOR DE
IV SECUENCIA
f1i
IV .
DECIMACIÓN P
di BÚFER DE
SALIDA
R2
di IVi
MÓDULO DE
CARGA DEL IV
MÓDULO DE
CIFRADO
C IFRADO DE LAS COMUNICACIONES
Finalmente, en esta sección, una vez completo el diseño del cifrador, se evalúa
el rendimiento del mismo comparándolo con el de otros cifradores en flujo de van-
guardia. Estos algoritmos son los candidatos del proyecto eSTREAM, ya mencionado,
finalmente elegidos como ganadores en la categorı́a del perfil orientado a software.
También se incluyen otros algoritmos, como RC4, considerado una referencia para
contrastar el rendimiento de nuevos algoritmos de cifrado en flujo, o AES-CTR, el mo-
do de flujo del conocido estándar de cifrado en bloque. Por último, también se con-
sidera en la comparativa el algoritmo Dragon, que si bien no fue elegido ganador del
proyecto, si alcanzó las últimas fases del mismo. La razón de su inclusión es que pre-
senta una estructura interna similar a la de LFSRe, pues hace uso también de registros
de desplazamiento, aunque con funciones de realimentación no lineales.
Velocidad de cifrado en bloque (40, 576 y 1500 bytes): hace referencia a la veloci-
dad de cifrado de multitud paquetes de 40, 576 y 1500 bytes de longitud, respec-
tivamente. Las longitudes no son arbitrarias, sino que han sido elegidas debido
a que constituyen las longitudes estadı́sticamente más frecuentes en la redes de
comunicaciones habituales. En este caso, sı́ se incluye el tiempo de carga y mezcla
de la clave e IV.
Carga IV: constituye el tiempo empleado en la carga inicial del IV, que se lleva a
cabo durante la inicialización del cifrador. Es más compleja y de mayor longitud
que la mezcla del IV, que se realiza en cada paquete a cifrar, y que se incluye en los
tiempos anteriores.
Velocidad de cifrado
Algoritmo Clave IV Carga IV
Flujo 40 bytes 576 bytes 1500 bytes
HC-128 128 128 2.86 587.00 43.19 18.43 23308.78
Salsa20 128 64 3.46 9.48 3.57 3.64 14.29
SOSEMANUK 128 64 5.81 52.37 12.52 9.62 1245.71
Rabbit 128 64 9.46 34.45 11.77 10.76 825.55
Dragon 128 128 11.37 74.09 26.07 23.23 1925.54
RC4 128 – 13.07 445.19 42.27 24.48 16737.80
LFSRe 128 128 17.19 80.45 28.73 24.54 1225.33
AES-CTR 256 128 26.67 37.65 27.09 26.91 59.04
También respecto a otra gran referencia en el campo, AES-CTR, el modo más rápido
de este estándar, LFSRe obtiene buenos resultados. Como cabrı́a esperar, en el proce-
samiento de flujos continuos de datos, nuestro cifrador es un 35.5 % más veloz que
AES-CTR. Las diferencias se ajustan conforme crece el tamaño del paquete, obtenien-
do, finalmente, rendimientos similares para paquetes de 1500 bytes.
En resumen, podemos concluir que el rendimiento mostrado por LFSRe, a pesar de
su extrema sencillez de diseño, es excelente. Aunque inferior al de los algoritmos más
rápidos del proyecto eSTREAM, nuestro cifrador supera claramente a RC4 y AES-CTR
en la mayorı́a de escenarios.
IV .8. C ONCLUSIONES 169
IV .8. C ONCLUSIONES
En este capı́tulo de la tesis se ha presentado un nuevo cifrador en flujo, denomi-
nado LFSRe, especialmente orientado a su uso en dispositivos con poca capacidad de
cómputo, como los que constituyen las redes de sensores y redes ad-hoc en general.
Por esta razón, el cifrador hace uso de los registros de desplazamientos extendidos,
presentados en el capı́tulo anterior, y los principios del generador shrinking. En este sen-
tido, se han presentado y analizado unos nuevos criterios de decimación, evaluando los
pros y contras de cada uno de ellos.
También se ha profundizado en ciertos aspectos relacionados con este generador
en particular, y con los de salida irregular en general, que no habı́an sido convenien-
temente aclarados hasta la fecha. Entre ellos se encuentra el problema de su salida
irregular, y la necesidad de un búfer de salida con el fin de ocultarla.
Hemos demostrado, a través de la modelización del búfer con cadenas de Markov,
que utilizando el planteamiento original del generador shrinking, es imposible evitar,
simultáneamente, el agotamiento y el desbordamiento de dicho búfer. Como resultado,
se ha obtenido asimismo que el ratio α de funcionamiento mı́nimo del sistema debe ser
superior a α = 2.5, con el fin de que la probabilidad de falta tome valores aceptable-
mente bajos. Por otro lado, el tamaño mı́nimo del búfer debe ser superior a B = 32
elementos con el fin de que éste se desborde el menor número de veces posible.
Sin embargo, se han aportado dos formas nuevas de gestionar esta salida irregular,
que hemos denominado pausa y gestión dinámica del ratio, que permiten evitar comple-
tamente los problemas anteriores.
Por otro lado, se ha añadido un módulo de carga y gestión del vector de inicialización,
que permite que LFSRe, que es un cifrador en flujo, pueda ser utilizado en las modernas
redes de conmutación de paquetes, como Internet. Se han analizado diversos aspectos
de su funcionamiento, como las dificultades asociadas al uso del IV, o la longitud ade-
cuada para el mismos.
Por último, se ha analizado el rendimiento que es capaz de proporcionar el cifrador
en diferentes escenarios, desde flujos continuos de datos a paquetes de diversa longi-
tud, obteniendo excelentes resultados, comparables a los de conocidas referencias en el
campo, como RC4 o AES-CTR.
170
C AP ÍTULO V
171
172 V. A UTENTICACI ÓN DE LAS COMUNICACIONES
El atacante puede estar presente en cualquier momento del ciclo de vida de la red,
incluyendo el despligue inicial. Tampoco existen restricciones sobre el número de
atacantes o su localización fı́sica.
V .1.2. Notación
A continuación se resume la notación que se utilizará en el resto del capı́tulo:
V .2.1. SPINS
SPINS está formado, a su vez, por dos protocolos, SNEP y µTESLA, que proporcio-
nan confidencialidad y autenticación en la difusión (broadcasting) de mensajes, respec-
tivamente.
Como se muestra en la Figura V.1, SPINS asume que el nodo A quiere establecer
una clave de sesión kAB con el nodo B a través de una tercera parte confiable S, de-
nominadado centro de distribución de claves (Key Distribution Center). Este nodo S es un
servidor, habitualmente con mayor capacidad de cómputo que el resto, que lleva a
cabo las operaciones criptográficas necesarias para la autenticación y la distribución de
claves.
Por otro lado, los nodos de SPINS tienen claves individuales, de forma que cada
nodo y el servidor S comparten una clave simétrica única, que se utiliza para autenticar
al propio nodo frente a S.
E D C
S
M1=IDA|NA|[IDA|NA]K
M
3
M4 M
2 F A B
A M1 B
G H I
M1 : NA |IDA
M1 : IDA |NA |[IDA |NA ]K
M2 : IDB |NA |NB |IDA KBS
M2 : IDB |NB |[IDB |NB ]K
M3 : {KAB |NA |IDB }KAS
KAB : [NA |NB ]K
M4 : {KAB |NB }KBS
V .2.2. BROSK
Comparado con SPINS, BROSK puede considerarse una propuesta más reciente y
mejorada de un protocolo de establecimiento de claves [11]. En este esquema no existe
ningún servidor ni tercera parte confiable, y cada nodo negocia su clave de sesión con
sus vecinos difundiendo un mensaje de negociación de clave.
Una vez que un nodo recibe este mensaje, deriva la clave de sesión compartida
generando el MAC de dos valores aleatorios. Por ejemplo, en la Figura V.1 todos los
nodos desde B hasta I recibirán el mensaje de negociación de clave de A. A su vez,
A también recibirá el del resto de nodos (M2 en la figura). En ese momento, pueden
utilizar KAB como su clave compartida.
Por otro lado, los autores de BROSK no especifican qué ocurre con la clave maestra
de red una vez que el proceso de difusión inicial ha finalizado, por lo que parece lógico
asumir que esta clave no es borrada ni procesada de alguna forma. Si esta suposición es
cierta, significa que BROSK serı́a vulnerable a una intrusión fı́sica, en la misma manera
que SPINS.
Con el fin de evitar esta vulnerabilidad, nuestro protocolo “olvida” la clave maestra,
pero, aún después, sigue siendo capaz de autenticar nuevos nodos, utilizando una es-
tructura que hemos denomidado operador de autenticación o autenticador, que será anal-
izado con profundidad en V.3.3.
176 V. A UTENTICACI ÓN DE LAS COMUNICACIONES
Fase de pre-distribución de claves (F0 ): se realiza antes del despliegue de la red, ha-
bitualmente durante el propio proceso de fabricación de los nodos.
Fase de inicialización de la red (F1 ): encargada de establecer los primeros parámetros
de seguridad de la red. Se lleva a cabo durante el despliegue inicial de la red sobre
su ubicación fı́sica.
Fase de autenticación (F2 ): se realiza cada vez que las fases anteriores han finalizado
y un nuevo nodo solicita ingresar en la red.
Esta fase comienza una vez que la etapa anterior F0 ha finalizado. Esta fase se realiza
durante el despliegue de la red, en el mismo entorno fı́sico y operativo que tendrá
durante su normal funcionamiento. En este proceso, cada nodo “descubre” sus nodos
vecinos que están en rango de comunicación y realiza los siguientes pasos:
i
1. Cada nodo i genera una clave única y simétrica, kenc , denominada clave de cifrado
del nodo i. Esta clave se obtiene generando un número aleatorio, ri , y calculando
i
kenc = [kM , ri ]. De esta forma, por ejemplo, la clave de cifrado de A se calcuları́a con
la siguiente operación: kenc A
= [kM , rA ].
2. Cada nodo difunde su valor aleatorio, ri , durante un breve periodo de tiempo, que
puede ser tan sólo de unos pocos segundos [16]. Una valor razonable podrı́a ser
alrededor de un minuto. De esta forma, si un atacante estuviera ya presente en esta
fase, sólo obtendrı́a una conjunto de números aleatorios.
3. Cada nodo recibe los números aleatorios de sus nodos vecinos y calcula sus claves
de cifrado correspondientes utilizando la clave maestra común a todos ellos. En
este punto, cada nodo almacena una lista con las claves de cifrado que le permiten
comunicarse con sus vecinos.
4. Cada nodo calcula el hash de la clave maestra y almacena el resultado como la
primera de las claves de autenticación, kauth 1
= [kM ]. El objetivo de esta operación
es que, claramente, almacenar la clave maestra en claro en la memoria del nodo
comprometerı́a la seguridad de toda la red si el nodo es capturado. Esta es, por
otra parte, la razón principal de la existencia del propio autenticador, que propor-
ciona una forma de autenticar otros nodos, verificando su conocimiento de la clave
maestra común, sin almacenar la propia clave.
i
5. Al final de esta fase, cada nodo almacena su propia clave de cifrado, kenc , el con-
junto de claves de cifrado de sus nodos vecinos, la clave del próximo ciclo de au-
1
tenticación, kauth , y el autenticador del ciclo actual, ∇0 , que está compuesto de un
conjunto de n tuplas. La estructura interna de un autenticador se discutirá con de-
talle en la sección V.3.3.
Alcanzado este punto, los nodos de la red pueden empezar a comunicarse entre sı́
utilizando las claves de cifrado obtenidas en los pasos previos.
178 V. A UTENTICACI ÓN DE LAS COMUNICACIONES
Utiliza una cadena de claves para la autenticación de nuevos nodos, que resulta
un mecanismo más sencillo y eficiente que una tercera parte confiable S y el con-
secuente intercambio de cuatro mensajes, necesarios en SPINS (sección V.2.1). Por
contra, nuestra propuesta alcanza el mismo objetivo haciendo uso de una clave
maestra y la transmisión de un único mensaje.
Autenticador ∇2
δ=3
(ro , [ro ]k2 ) USADA
auth
(r1 , [r1 ]k2 ) USADA
auth
(r2 , [r2 ]k2 ) ASIGNADA
auth
(r3 , [r3 ]k2 ) LIBRE
auth
... ...
Tamaño n del autenticador Una cuestión importante que debe ser analizada es las
implicaciones del tamaño o número de tuplas n del autenticador. Como un parámetro
del sistema, debe ser ajustado de acuerdo al número de nodos y, sobre todo, a la tasa
de nuevos nodos esperada.
Por supuesto, el valor de n puede ser ajustado de forma dinámica, conforme las
caracterı́sticas de la red cambian. Un valor tı́pico para n estará alrededor de 10, que se
considera un valor razonable teniendo en cuenta la tasa esperada de nuevas autentica-
ciones y el número tı́pico de vecinos en esta clase de redes [16].
A pesar de que no tiene consecuencias directas en la seguridad del sistema, un valor
excesivamente pequeño de n podrı́a llevar a problemas de rendimiento si la red tuviera
una alta tasa de autenticaciones. Para evitar este inconveniente, un nuevo ciclo del
autenticador actual puede ser calculado “lentamente”, en segundo plano. En función
de la tasa de autenticaciones, este cálculo podrı́a ser tan lento como generar una nueva
tupla cada varias horas o incluso en dı́as.
Un ejemplo de autenticador puede encontrarse en el Cuadro V.2, que contiene los
valores de un autenticador de segundo ciclo. En este caso, kauth 2
= [[kM ]] = [kM ]2 . Según
el valor del ı́ndice de tupla actual, δ, puede inferirse que este ciclo ha realizado ya dos
autenticaciones con éxito.
M1 = rA
A → B : rA
A ← B : rB , [rA ]k j−1 , {kenc
B
}k j
auth auth
A→B : [rB ]k j , {kenc
A
}k j
auth auth
Nodo Nodo
A B
M1 rA
1. Abre la primera tupla libre.
2. Responde el reto de A.
3. Cifra su clave de cifrado
utilizando kauth
B 4. Incluye en el mensaje el
M2 rB ,[rA ]k 3 ,{kenc}k 3 ,3
auth auth ciclo actual del autenticador,
j=3.
5. Marca la tupla como
1. Comprueba la ‘ASIGNADA’.
respuesta de B.
2. Responde al reto
de B. A
3. Genera su propia M 3 [rB ]k 2 ,{kenc }k 3
clave de cifrado y la auth auth
Otro tipo de retos son también posibles, como números de secuencia, en lugar de
los números aleatorios utilizados. Los sellos de tiempo, aunque podrı́an reducir
el número de mensajes intercambiados en uno, no resultarı́an prácticos en este
escenario, pues implicarı́an la necesidad de disponer de relojes sincronizados en
los nodos de la red.
Este protocolo ha sido diseñado para redes de sensores, que son escenarios estáticos
o cuasi-estáticos, con una tasa esperada de nuevos nodos baja. Por esta razón, los
casos en los que el número de ciclos del autenticador de un nodo supere unas
pocas decenas serán raros y, por tanto, el coste computacional asociado al proce-
so de sicronización realizado en el paso 2 por A será también bajo.
La Figura V.2 muestra un ejemplo de una ejecución completa del esquema de aut-
enticación propuesto entre dos partes A y B. Los parámetros del autenticador de B son
∇3 y δ = 2, lo que significa que el operador está en su tercer ciclo y, hasta el momento,
ha autenticado con éxito a dos nodos y ha utilizado el mismo número de tuplas. A es
un nuevo nodo que desea ingresar en la red y cuya autenticador no ha sido todavı́a
utilizado.
V .4. A N ÁLISIS DE SEGURIDAD 183
Los ataques de denegación de servicio tienen como objetivo agotar los recursos de
una red, como su ancho de banda, a su capacidad de proceso, con el fin de que ésta no
pueda atender las peticiones de clientes legı́timos [19].
Cuanto el ataque se aplicar a nuestro protocolo, un atacante podrı́a tratar de exten-
uar el conjunto de autenticadores iniciando continuamente un proceso de autenticación
contra un nodo y no respondiendo a los retos que éste proporciona o proporcionando
respuestas falsas (aleatorias, por ejemplo). De esta forma, el nodo atacado podrı́a agotar
rápidamente su conjunto de autenticadores, y no disponer de tuplas libres para atender
a nodos legı́timos.
Para resultar inmune a este ataque, o al menos mitigar lo suficiente sus efectos, la
implementación de nuestro protocolo dispone de un mecanismo de protección. Este
mecanismo se basa en el uso de un intervalo temporal, α, en el que el nodo que inicia
la autenticación debe responder correctamente al reto proporcionado. Si finalizado el
periodo α no se ha recibido una respuesta correcta, el reto se etiqueta como ’LIBRE’ y
pasa a estar disponible para su uso de nuevo.
Este parámetro puede ser ajustado dinámicamente si se detecta que un nodo se
encuentra bajo ataque, decrementando su valor en función de la severidad del ataque.
Por otro lado, se estudiará uno de los aspectos más importantes y uno de los crite-
rios básicos de diseño: la eficiencia energética de las soluciones.
Como hemos mencionado, la evaluación del rendimiento y la eficiencia energética
resultan especialmente importantes en entornos como las redes de sensores, cuyos re-
cursos computacionales y energéticos son muy limitados.
Para evaluar el coste energético de los protocolos de seguridad se utiliza un método
indirecto, en lugar de medidas directas de consumo. Este método consiste en calcular
el número total de bytes transmitidos de forma inalámbrica, a través del número y
tamaño de cada uno de los mensajes intercambiados por el protocolo. Este método es
el más utilizado por dos razones.
y asumiremos que cada nodo puede recibir los datos transmitidos por sus vecinos más
inmediatos (cada nodo tiene, por tanto, 8 nodos vecinos)
En este escenario, el número medio de transmisiones en el protocolo SPINS es de
aproximadamente 8, mientras que BROSK y nuestra propuesta únicamente requieren
una. En cualquier caso, cada una de estos mensajes transmitidos tiene una longitud
diferente, que puede afectar significativamente al resultado final.
Para obtener una evaluación más exacta, calculamos el número total de bits real-
mente transmitidos, asumiendo valores de nonce de 64 bits, valores identificadores de
14 bits, claves simétricas de 128 bits y resúmenes de HMAC de 160 bits. Los resultados
finales son que las longitudes de los mensajes son de 632 bits para SPINS (que necesita
8 de estos mensajes, haciendo un total de 8×632 =5.056 bits transmitidos), 238 bits para
BROSK y 78 bits para nuestra propuesta.
Por tanto, puede concluirse que nuestra propuesta permite disminuir los costes en-
ergéticos en un 98 % y 67 % respecto a SPINS y BROSK respectivamente. El número to-
tal de bits transmitidos, directamente proporcional al consumo energético final, puede
encontrarse en la Figura V.4.
V .5.2. Escalabilidad
1e+08
SPINS−Server
SPINS−Node
BROSK
Nuestra propuesta
1e+07
Número de bits transmitidos por nodo
1e+06
100000
10000
1000
100
10
64 256 1024 4096 16384
Número de nodos
Figura V.4: Consumo energético (bits transmitidos por nodo). El eje de ordenadas uti-
liza una escala logarı́tmica.
grande.
188 V. A UTENTICACI ÓN DE LAS COMUNICACIONES
V .6. C ONCLUSIONES
191
192 VI . I MPLEMENTACI ÓN Y APLICACI ÓN A ESCENARIOS DE TRANSMISI ÓN MULTIMEDIA
Datos
TCP Cifrado
Vector de
inicialización
IP En claro
VI .2.2. Funcionamiento
“...captura todos los paquetes de entrada cuyo puerto TCP de destino sea 23...”
De esta forma, todos los paquetes que cumplan esta regla serán entregados a nue-
stro código, que lleva a cabo, entonces, los siguientes pasos:
194 VI . I MPLEMENTACI ÓN Y APLICACI ÓN A ESCENARIOS DE TRANSMISI ÓN MULTIMEDIA
1. Se realizan una serie de comprobaciones rutinarias sobre el paquete, como que posee una
longitud mı́nima adecuada.
2. Si el paquete debe ser cifrado, se genera un nuevo IV y se añade tras la cabecera de nivel
de red (IP).
3. Si el paquete debe ser descifrado, se recupera el IV de la trama.
4. Se llama a función de cifrado (que es la misma que para el descifrado), que toma como
parámetros el IV y los datos a cifrar (la porción del paquete de nivel de transporte y
capas superiores).
5. Se deja continuar a la trama su viaje por la pila de comunicaciones. El sistema operativo
decidirá si es un paquete de salida, por lo que debe ser enviado a un receptor remoto, o
es de entrada, por lo que debe ser entregado a la aplicación correspondiente.
El objetivo de este sección es demostrar, una vez presentado el diseño del protocolo
de autenticación, la viabilidad del mismo en un entorno completamente real. Para ello
se ha llevado a cabo su implementación práctica en un entorno de laboratorio.
A pesar de que este enfoque resulta claramente más costoso que las habituales simu-
laciones, los autores creen que posee una serie de ventajas importantes. La primera, por
supuesto, es que supone una demostración innegable de la viabilidad de la propuesta.
Proporciona, por otro lado, datos fiables y exactos en cuanto al tiempo de ejecución,
consumo energético y otros aspectos, que no siempre son adecuadamente tratados en
las simulaciones.
De hecho, la principal de las razones que han hecho que los autores se decanten por
una implementación real de las propuestas es que, a pesar de que la simulación es la
herramienta por excelencia utilizada para la evaluación de las soluciones propuestas en
este tipo de redes, su aplicación puede no resultar siempre adecuada. Esta opinión es,
por otra parte, compartida por los propios autores y otros investigadores, como [1, 2],
que plantean serias dudas sobre la credibilidad de los resultados obtenidos en base a
simulaciones.
El proyecto Arduino es una de las primeras plataformas hardware libres del mundo.
Orientada al desarrollo electrónico, está basada en software y hardware flexible y fácil
de utilizar. De hecho, uno de los principales objetivos es servir de plataforma educativa
para estudiantes.
Todos los elementos del proyecto son abiertos y libres: la placa fı́sica puede mon-
tarse a mano o comprarse ya montada, y el software de desarrollo es gratuito. El diseño
hardware de la placa es, también, libre y los ficheros CAD están disponible bajo una
licencia de código abierto, de forma que pueden modificarse para adaptar el diseño a
las necesidades de cada proyecto.
En esta tesis, se ha trabajado con el modelo Diecimila3 de esta plataforma. Puede en-
contrarse una fotografı́a del diseño en la Figura VI.2 y un resumen de sus caracterı́sticas
técnicas más importantes en el Cuadro VI.1.
3
La palabra Diecimila significa diez mil en italiano y hace referencia al hecho de que las primeras diez mil
unidades de la plataforma habı́an sido ya fabricadas.
196 VI . I MPLEMENTACI ÓN Y APLICACI ÓN A ESCENARIOS DE TRANSMISI ÓN MULTIMEDIA
Microcontrolador ATmega168
Voltaje de operación 5V
Voltaje de entrada (máximo) 20 V
14 (6 de los cuales pueden producir
Pines de E/S digitales
salidas PWM)
Pines de entrada analógicos 6
Corriente disponible en pines E/S 40 mA
16 Kb (2 de los cuales son
Memoria FLASH
utilizados por el cargador)
SRAM 1 Kb
EEPROM 512 bytes
Velocidad de reloj 16 MHz
TEA Dada la situación, se hizo imprescindible, por tanto, considerar otras primiti-
vas criptográficas cuyo código y huella de memoria fueran mı́nimas. En este sentido,
destaca el algoritmo TEA (Tiny Encryption Algorithm), presentado en 1995 por David
Wheeler y Roger Needham, de la Universidad de Cambridge [5, 6]. La cualidad más
caracterı́stica de TEA es, sin duda, su mı́nimo tamaño, pues puede ser implementa-
do en unas pocas lı́neas de código C. En la Figura VI.3 puede encontrarse una imple-
mentación de referencia.
TEA opera en bloques de 64 bits y utiliza una clave de 128 bits. El proceso de cifra-
do consiste esencialmente en una estructura de Feistel, con 64 rondas recomendadas.
Cuenta con un mecanismo de mezcla de clave muy sencillo y efectivo, puesto que fun-
ciona de igual manera en todos los ciclos. Por último, hace uso de las denominadas
constantes mágicas, con valor 232 /φ, siendo φ el número áureo, con el fin de evitar
ataques sencillos basados en la simetrı́a de las rondas.
TEA sufre, sin embargo, de ciertas vulnerabilidades. La más importante consiste en
que cuenta con una serie de claves equivalentes, de forma que cada clave corresponde
a otras tres. Esto significa que, en la práctica, el espacio de claves se reduce de 2128 a
2128 /22 = 2126 . Debido a éste y otros inconvenientes [7, 8], los autores han desarrollado
nuevas versiones, que se describen brevemente a continuación, para solucionar estos
problemas.
Revisiones de TEA La primera de las revisiones se denominó Block TEA [9], aunque
el nombre más extendido es XTEA. Al margen de solucionar los problemas menciona-
dos, cuenta con la capacidad de operar sobre bloques de longitud arbitraria, en lugar
de los 64 bits de la propuesta original. Finalmente, en 1998, se publicó la que hasta la
fecha es la última revisión, denominada XXTEA, que será la utilizada en este trabajo, y
que incluye algunas mejoras adicionales.
198 VI . I MPLEMENTACI ÓN Y APLICACI ÓN A ESCENARIOS DE TRANSMISI ÓN MULTIMEDIA
Una vez seleccionado y analizado XXTEA como bloque básico con el que construire-
mos nuestra librearı́a criptográfica Cryptonite, resta definir cada una de las primitivas
criptográficas básicas, cifrado, hash y HMAC, a partir de TEA. Este proceso se analizará
en las siguientes secciones.
Puesto que XXTEA está definido como un algoritmo de cifrado, definir dicho pro-
ceso resulta una tarea trivial. Hay que realizar, sin embargo, algunas consideraciones,
sobre todo en lo concerniente al tamaño de los bloques de texto en claro.
Como se ha comentado anteriormente, XXTEA permite trabajar con bloques de en-
VI .3. I MPLEMENTACI ÓN DE LA AUTENTICACI ÓN 199
trada de longitud variable. Sin embargo, como suele ser habitual en criptografı́a, es
necesario encontrar un equilibrio para el tamaño de bloque entre rendimiento y seguri-
dad.
En cuanto al rendimiento, se pretendı́a que para cifrar un bloque de entrada dado, el
cifrador sólo necesitara llevar a cabo una ronda en la mayorı́a de los casos. Obviamente,
cuando mayor sea el tamaño de bloque interno del cifrador, mayor es su rendimiento.
Por ejemplo, para un texto de entrada de 512 bits y un tamaño de bloque de B = 128
bits, el cifrador necesitará realizar 512/128 = 4 rondas. Por otro lado, con B = 32 bits, el
número de rondas se incrementa hasta 16.
Sin embargo, un tamaño de bloque B grande, sobre todo en la plataforma en la
que trabajamos, tiene la contrapartida de que en el caso de que sea necesario cifrar un
bloque de datos menor a B, es necesario realizar un relleno del mismo hasta completar
la longitud de B, con el consiguiente gasto de tiempo y memoria.
Teniendo en cuenta todas las consideraciones anteriores, se decidió establecer el
tamaño de bloque B en 128 bits.
En el Cuadro VI.2 se resumen los ratios de cada uno de los enfoques existentes. Por
ejemplo, el enfoque Matyas-Meyer-Oseas y el algoritmo MDC-2 son la base de las dos
funciones hash definidas en el estándar ISO 10118-2 (“Information technology – Security
techniques – Hash-functions”), pudiendo hacer uso de cualquier cifrador E de n bits y
proporcionando salidas de longitud m ≤ n y m ≤ n, respectivamente.
Algoritmo 19 Implementación de una función hash basada en XXTEA, que hace uso
del enfoque Davies-Meyer
1 /* NOMBRE: calculateHash
2 * ARGUMENTOS ENTRADA:
3 * - inputText : puntero al texto de entrada
4 * - inputTextLength : longitud del texto de entrada (en bytes)
5 */
6 void Cripto::calculateHash(unsigned char *inputText,
7 unsigned int inputTextLength,
8 unsigned char *hash)
9 {
10 unsigned int numBlocks =
11 (inputTextLength <= HASH_LENGTH ? 1 : inputTextLength/HASH_LENGTH), i,j;
12 unsigned char H[HASH_LENGTH]={HASH_IV};
13 unsigned char tempBuffer[BLOCK_SIZE];
14
15 for (i=0; i<numBlocks;i++){
16 memcpy(&tempBuffer,inputText,BLOCK_SIZE);
17 XXTEA((unsigned char *)&tempBuffer,KEY_SIZE,(uint32_t *)&H);
18
19 // Se actualiza el puntero de la entrada, x_i
20 for (j=0; j<HASH_LENGTH;j++)
21 H[j]=tempBuffer[j]ˆ(*inputText++);
22 }
23
24 memcpy(hash,&H,HASH_LENGTH);
25
26 }
VI .3.3.1. Resultados
En una arquitectura tan limitada, un parámetro crı́tico a la hora de evaluar la validez
de un código es la huella de memoria del mismo, dada la escasez de dicho recurso. En
este sentido Cryptonite obtiene buenos resultados, pues ocupa 2108 bytes, que supone
poco más del 13 % de los 16Kb totales disponibles.
VI .3. I MPLEMENTACI ÓN DE LA AUTENTICACI ÓN 203
A → B : rA
A ← B : rB , [rA ]k j−1 , {kenc
B
}k j
auth auth
A→B : [rB ]k j , {kenc
A
}k j
auth auth
8
La librerı́a Ethernet permite conectar una placa Arduino a una red de este tipo y, por tanto a Internet.
LiquidCrystal, por su parte, sirve para utilizar pantallas de cristal lı́quido basadas en el chipset Hitachi
HD44780, o compatibles, utilizado por la mayorı́a de LCDs de texto del mercado. Ambas librerı́as están
disponibles en [Link]
204 VI . I MPLEMENTACI ÓN Y APLICACI ÓN A ESCENARIOS DE TRANSMISI ÓN MULTIMEDIA
Tiempo
Tamaño Rendimiento
Función operación
(bytes) (ciclos/byte)
(µs)
XXTEA 1330 — —
encrypt 132 1183 9464
decrypt 96 1183 9780
calculateHash 276 1222 9756
calculateHMAC 274 1689 13516
Total 2108
Tiempo
Rendimiento
Función operación
(ciclos/byte)
(µs)
Lectura 4 128
Escritura 8 64
Nótese que A es el nodo que desea ingresar en la red e inicia, por tanto, el proceso de
autenticación y B el nodo que ya pertenece a la misma y hace las veces de “anfitrión”.
Como puede observarse en el esquema anterior, A y B intercambian un total de tres
mensajes, que involucran el uso de unos retos precalculados.
En nuestra implementación, estos retos, que forman parte de los autenticadores de
A y B, ∇A y ∇B , respectivamente, son almacenados en la memoria EEPROM de la placa
Arduino. Por tanto, el primer paso de la evaluación final consistió en medir los tiempos
de acceso a esta memoria. Los resultados pueden encontrarse en el Cuadro VI.4. Como
puede apreciarse, estos tiempos, unos 4µs para la operación de lectura y 8µs para la
escritura, son prácticamente despreciables frente a las operaciones criptográficas, mu-
cho más costosas, de la librerı́a Cryptonite (suponen apenas un 0.08 % de la operación
criptográfica más rápida).
Con estos elementos, los resultados finales obtenidos para el protocolo de autenti-
cación se detallan en el Cuadro VI.5. Según los datos mostrados, cada nodo necesita
invertir algo menos de 20 ms en la generación y procesamiento de cada uno de sus
mensajes, lo que supone unos 38 ms para la ejecución completa del protocolo. Tenien-
do en cuenta que el protocolo ha sido diseñado para ser utilizado principalmente en
redes de sensores, donde la tasa de autenticaciones se estima baja, estos valores ofrecen
un rendimiento muy superior al que podrı́a considerarse mı́nimo.
VI .3. I MPLEMENTACI ÓN DE LA AUTENTICACI ÓN 205
Operación Tiempo
Nodo Mensaje
EEPROM HMAC Cifrado Parcial Total
M1 1 0 0 4
A 19224
M3 0 1 1 19220
B M2 1 1 1 19224 19224
VI .4.1. Apolo
El agente Apolo constituye el cliente del sistema, y ha sido desarrollado en forma
de plugin, o extensión, para la plataforma OLSRd [11, 12]. Ésta es, probablemente, la
implementación libre del protocolo OLSR (véase sección II.2.2.2, pág. 43) más utilizada
y extendida del mundo.
Formato de los mensajes Para ahorrar los valiosos recursos energéticos y el ancho de
banda disponibles, el agente Apolo no envı́a sus mensajes a Dafne a intervalos regu-
lares, sino únicamente cuando se produce un cambio en su vecindad (se ha detectado un
nuevo nodo, o alguno ha abandonado la red), o en la topologı́a (ha cambiado el enlace
entre dos nodos vecinos, por ejemplo).
De esta forma, cuando un agente Apolo dispone de nueva información, genera y
envı́a un mensaje al nodo Dafne con el siguiente formato:
Apolo Apolo
Apolo
Apolo
0.98
Nodo C
Nodo A Apolo
0.63 Apolo
0.75 Apolo
Nodo D
Nodo E
Dafne
Apolo Apolo
Nodo B Apolo
Apolo
Figura VI.5: Estructura de una red ad-hoc inalámbrica con los agentes Apolo y Dafne
instalados en sus nodos. El nodo que contiene a Dafne está señalado por un cı́rculo rojo.
Las etiquetas numéricas sobre los enlaces entre los nodos A, B, C y D indican la calidad
del mismo, en una escala de 0.0 (no hay enlace) a 1.0 (calidad de enlace máxima).
VI .4.2. Dafne
Como hemos comentado ya brevemente, Dafne constituye el servidor del sistema, y
su objetivo es recoger, normalizar y representar gráficamente la información topológica
que recibe de los agentes Apolo.
Esta representación cobra especial importancia debido a que cada nodo sólo posee
información local sobre sus vecinos más inmediatos y los enlaces que le unen con ellos.
Haciendo uso de nuestra herramienta es posible conocer, en todo momento, el estado
global de la red, con información sobre el número de nodos y la calidad de los enlaces
entre ellos, en otras.
Es importante señalar, sin embargo, que la topologı́a representada en el interfaz
gráfico sólo muestra la estructura “lógica”, y no la disposición fı́sica de los nodos en
el espacio. Para poder hacerlo de esta última forma, los nodos deberı́an disponer de
hardware especı́fico, como un módulo GPS, que encarecerı́a muy significativamente el
coste total de la red. En cualquier caso, ésta constituye una lı́nea de investigación futura
(más información sobre ella en la sección VII.2 del Capı́tulo VII).
Funcionamiento De acuerdo a una de las premisas básicas de las redes ad-hoc (“To-
dos los nodos deben ser iguales”), el nodo que acoge al servidor Dafne es un nodo
más de la red, que no debe cumplir ningún requisito ni poseer ninguna caracterı́stica
especial.
Dafne ha sido desarrollado en lenguaje Java, lo que permite el uso de la herramienta
en diferentes sistemas operativos y facilita el desarrollo de la interfaz gráfica.
Una vez instalado, Dafne abre un socket UDP, en el puerto 4447, y permanece a
la escucha. Cuando recibe un paquete de datos, con el formato correcto de acuerdo al
descrito en la sección anterior, la herramienta comienza la representación gráfica.
Figura VI.6: Herramienta Dafne en funcionamiento. Las aristas en color rojo indican
una calidad de enlace por debajo de 0.50.
210 VI . I MPLEMENTACI ÓN Y APLICACI ÓN A ESCENARIOS DE TRANSMISI ÓN MULTIMEDIA
VI .5. C ONCLUSIONES
Durante esta fase del trabajo hemos presentado los resultados obtenidos a partir la
implementación de las diferentes propuestas realizadas a lo largo de la tesis en entornos
reales.
El algoritmo de cifrado en flujo LFSRe ha sido dotado de toda la infraestructura
adicional necesaria para poder proteger todas las comunicaciones entrantes y salientes
de una máquina. Este desarrollo se ha llevado a cabo inicialmente para entornos Lin-
ux, donde, gracias a la disponibilidad de su código fuente, es posible profundizar con
mayor facilidad en la estructura interna de la pila de comunicaciones.
Este software de cifrado de tráfico con LFSRe ha sido probado con éxito en el con-
texto del proyecto Hesperia, donde actualmente forma parte de su núcleo de comu-
nicaciones y se encuentra en uso. Como parte de sus tareas habituales, se encarga del
cifrado de flujos de datos multimedia provenientes de los diferentes componentes de
la red, entre las que se incluyen cámaras de vigilancia, micrófonos o PDA’s portadas
por vigilantes de seguridad.
Por otro lado, el protocolo de autenticación propuesto en el Capı́tulo V ha sido tam-
bién implementado en un entorno real. Dadas las inherentes restricciones computa-
cionales y energéticas, la codificación de las primitivas criptográficas necesarias para
poder llevar a cabo el proceso de autenticación fue una tarea complicada, aunque al
mismo tiempo estimulante.
Tras barajar diversas alternativas, se optó por derivar todas las primitivas (cifra-
do, funciones hash y HMAC) de una única implementación de TEA, que se caracteri-
za por su pequeña huella de memoria. Como resultado, se ha desarrollado la librerı́a
Cryptonite, que constituye hasta la fecha, la primera librerı́a criptográfica libre para
la plataforma Arduino. Sin embargo, una de las lı́neas futuras de trabajo proyectadas
incluye el desarrollo de Cryptonite en otras plataformas tı́picas de redes de sensores.
Dado que esta librerı́a ha sido desarrollada completamente en ANSI C y es autocon-
tenida, este traslado no deberı́a suponer problemas importantes.
Por último, como consecuencia de todo el trabajo y experiencia acumulada durante
los desarrollos anteriores, se detectaron ciertas carencias en diversas áreas que han sido
también suplidas. La primera de ellas está relacionada con la dificultad existente para
visualizar, de forma fácil y global, la topologı́a de una red de sensores ya desplegada
y en funcionamiento. Para subsanar este problema, hemos desarrollado una solución
denominada Apolo y Dafne, que representa de forma gráfica la estructura de toda la
red a través de unos pequeños agentes instalados en cada nodo.
Otra de las carencias detectadas, que surgió de la necesidad de incluir el máximo
número posible de plataformas diferentes en nuestras redes MANet y de sensores, fue
la imposibilidad de ejecutar el software de enrutamiento OLSR, uno de los más conoci-
dos y utilizados, en la plataforma FreeRunner. Tras llevar a cabo el oportuno proceso de
compilación, este teléfono libre puede ser utilizado actualmente sin problemas, como
un nodo más, en este tipo de redes. Una vez finalizada esta tesis, éste código será liber-
ado con una licencia libre que permita su uso por otras universidades e instituciones.
C AP ÍTULO VII
Basta con detenernos unos instantes y echar un vistazo a nuestro alrededor, para
tomar conciencia de la espectacular revolución que la informática y la electrónica han
provocado en nuestras vidas en los últimos años. Internet ha irrumpido en ellas sin
ningún disimulo, prometiendo hacerlas más fáciles y divertidas, y, al margen de la
personal percepción de que lo haya conseguido o no, es innegable que resulta imposible
evitar su influencia en casi todos los aspectos de nuestra vida cotidiana.
Seguridad de las infraestructuras crı́ticas Nótese, además, que todas las infraestruc-
turas anteriores son crı́ticas para el funcionamiento normal de un paı́s, y que el fallo
o colapso de sólo una de ellas puede suponer una gran caos con repercusiones impre-
decibles. Y, curiosamente, no resulta difı́cil encontrar noticias sobre recientes ataques a
otras infraestructuras crı́ticas, como a la señalización ferroviaria en Alemania, o a los
paneles informativos de las carreteras en nuestro propio paı́s [1].
Por otro lado, aunque resulte difı́cil de creer, los expertos llevan años advirtiendo
de que este tipo de infraestructuras crı́ticas no están, a dı́a de hoy, adecuadamente
protegidas a pesar de su importancia estratégica y elevadı́simo riesgo.
211
212 VII . C ONCLUSIONES Y TRABAJO FUTURO
“...no basta con proteger fı́sicamente las infraestructuras sensibles sino que
es necesario hacer seguras e invulnerables sus redes de comunicaciones,
imprescindibles para su funcionamiento. El peligro del ciberterrorismo es
real y puede acarrear consecuencias dramáticas en servicios básicos como
la energı́a o el transporte.”
Nuevo enfoque Las respuestas a estas preguntas mostraron que el enfoque tradi-
cional, según el cual los LFSRs sobre el cuerpo algebraico binario GF(2), puede ser ade-
cuado en las implementaciones hardware, pero no en software. Dado que el tamaño de
VII .1. C ONCLUSIONES 213
los registros de los ordenadores actuales es de, como mı́nimo, 8 bits en las máquinas
menos potentes y de hasta 64 bits en las de mayor potencia, realizar implementaciones
orientadas a bit resulta claramente ineficiente.
En este sentido, nos plateamos utilizar cuerpos finitos más apropiados para la ar-
quitectura de los actuales microprocesadores y manipular registros de desplazamiento
definidos sobre cuerpos algebraicos compuestos, en contraposición a los tradicionales
GF(2).
Por supuesto, se llevó a cabo un estudio del rendimiento obtenido por estos reg-
istros, que denominaremos LFSR extendidos, en comparación con los tradicionales. Los
experimentos mostraron los claros beneficios de este enfoque, proporcionando datos
empı́ricos que avalan los resultados y demostrando que éste método resulta mucho
más eficiente que los LFSR tradicionales.
Asimismo, con el fin de optimizar al máximo su rendimiento, y hacerlos eficientes
también en plataformas como las redes de sensores, se ha realizado un análisis ex-
haustivo de los diferentes métodos para la implementación software de estos registros,
comparándolos entre sı́, enumerando las ventajas e inconvenientes de cada uno y pro-
porcionando un veredicto final en base a los datos empı́ricos obtenidos.
Esquemas existentes El estado del arte en el área en el momento de iniciar esta etapa
era variado. Por un lado, se encuentran aquellos esquemas diseñados para redes de
uso personal (PAN), que, en muchas casos, no contemplan en absoluto opciones de
autenticación o de privacidad, y que basan su seguridad en el extremadamente corto
rango de comunicaciones y la necesidad de lı́nea de visión directa puede proporcionar
una suerte de autenticación “fı́sica”.
Otra gran categorı́a incluye los esquemas simétricos, donde se enmarca también
la solución que aportamos en esta tesis. En este caso, las propuestas existentes en la
literatura adolecen de ciertos inconvenientes. Uno de los más comunes que muchos de
los esquemas hacen uso de un canal seguro pre-existente para la transmisión de dicho
secreto, lo que en ciertos escenarios, como el que nos ocupa, no resulta posible. Es el
caso del estándar IEEE 802.11, utilizado en muchas de las redes inalámbrica de ámbito
local (WLANs).
Por otro lado, esquemas como el de Bluetooth, dejando de lado que la seguridad
de su algoritmo de cifrado, E0 , se considera insuficiente [2], presentan el inconveniente
que no se adaptan convenientemente a un alto número de nodos, debido a la necesidad
de que el usuario teclee manualmente el secreto en cada dispositivo participante en la
comunicación. El modelo del “patito resucitador”, esquema serio de cómico nombre
propuesto por Stajano y Anderson [3], resuelve de forma imaginativa el problema del
VII .1. C ONCLUSIONES 215
intercambio de claves, pero adolece de los mismos problemas que Bluetooth, pues aún
necesita de un contacto fı́sico entre dispositivos. Este requisito invalida ambas solu-
ciones para uso en redes de sensores.
Finalmente, como ejemplo paradigmático de la última gran categorı́a de esquemas
de autenticación podemos citar a los modelos de pre-distribución de claves. Estos esquemas
proponen diferentes formas de realizar una distribución previa de las claves simétricas,
con el fin de no utilizar una única clave en toda la red. Este hecho es especialmente
importante en las redes de sensores, que disponen de una seguridad fı́sica débil, y cuyo
material de claves puede ser fácilmente recuperado. Sin embargo, el inconveniente de
estos esquemas es que suelen requerir una gran cantidad de memoria en cada nodo
que, como hemos visto, constituye un recurso realmente preciado y escaso.
Con el objetivo de superar gran parte de los problemas anteriores y aportar nuevas
ventajas, el análisis realizado en la etapa anterior concluye finalmente con la contribu-
ción de un nuevo protocolo de autenticación y gestión de claves, que destaca por
sus escasos requisitos computacionales, pues únicamente hace uso de primitivas crip-
tográficas sencillas y simétricas.
Otro de sus puntos fuertes se encuentra en que utiliza una clave maestra, que es
posteriormente eliminada de la memoria del nodo, para derivar de ella una serie de
claves simétricas. Este enfoque trata de aprovechar los beneficios del esquema de claves
simétricas, es decir, una mayor resistencia al compromiso, sin la necesidad de una pre-
distribución o almacenamiento de claves masivos.
Como consecuencia, nuestro esquema presenta una buena escalabilidad, una muy bue-
na resistencia a las consecuencias del compromiso fı́sico de los nodos y una gran eficiencia
energética.
Como se ha comentado a lo largo de toda la tesis, las restricciones energéticas son
uno de los grandes retos a superar en este tipo de redes, y cualquier esquema o protoco-
lo de seguridad debe destacar en este apartado si pretende ser viable en la práctica. En
este sentido, nuestro esquema presenta mejoras importantes, de alrededor del 98 % y
67 %, respectivamente, sobre dos conocidas propuestas existentes en la literatura como
SPINS y BROSK.
Este protocolo, al igual que el algoritmo LFSRe, ha sido también implementado en
dispositivos hardware reales, concretamente de la plataforma Arduino. Como consecuen-
cia, se ha desarrollado asimismo la primera librerı́a criptográfica existente para esta
plataforma hasta la fecha, que hemos denominado Cryptonite.
En lo relativo al rendimiento del protocolo, los resultados muestran que éste pre-
senta unas prestaciones excelentes. Por ejemplo, una ejecución completa del protocolo,
incluyendo la autenticación mutua del nodo iniciador y del anfitrión, puede llevarse a
cabo en menos de 40 ms.
216 VII . C ONCLUSIONES Y TRABAJO FUTURO
A lo largo del desarrollo del trabajo de esta tesis se han identificado una serie de
lı́neas investigación relacionadas con los aspectos que se han tratado. Algunas de ellas
se han incorporado al cuerpo principal de la tesis, ampliando los objetivos iniciales,
pero otras han quedado finalmente al margen de los mismos. La continuación del tra-
bajo en estas áreas estimula futuras tareas que complementarı́an las contribuciones re-
alizadas en esta tesis.
La localización de los nodos hace referencia al proceso según el cual éstos pueden
estimar su posición fı́sica en el espacio por diversos métodos. Ésta es una cualidad muy
interesante, pues abre todo un abanico de nuevas posibilidades.
En los últimos años, ésta se ha convertido en un área de intensa investigación en el
ámbito académico e industrial. La solución inmediata y obvia consiste en dotar a cada
sensor de un receptor GPS, de forma que éstos puedan calcular su posición con pre-
cisión. Ésta no es, sin embargo, una opción factible desde el punto de vista económico,
pues a menudo las redes de sensores están formados por un gran número de nodos y
el coste total serı́a prohibitivo. De hecho, es habitual que, a dı́a de hoy, un receptor GPS
para una mota tenga mayor coste que la propia mota [4].
Por estas razones, el proceso de localización en redes de sensores y ad-hoc se con-
vierte en un desafı́o. Cuando a esto se añade la necesidad de que el procedimiento sea
seguro, de forma que un nodo atacante no pueda inyectar información de localización
falsa en la red, encontrar una solución se complica aún más.
Éste serı́a, pues, el doble objetivo de esta lı́nea de investigación. Por un lado, es-
tudiar los mecanismos de localización segura existentes, analizándolos y apuntando
sus puntos fuertes y débiles. Y, por otro lado, tratar de definir un nuevo método, que
resulte novedoso y trate de superar los problemas identificados en el paso anterior. Es-
pecialmente interesante serı́a el hecho de que el proceso pudiera funcionar, con cierta
precisión, en interiores, sin necesidad de hardware adicional.
Por último, este trabajo permitirı́a dotar a Apolo y Dafne de la capacidad de mostrar
la posición real de los nodos en el espacio, lo que convertirı́a a esta herramienta en el
primer panel de control existente, de uso y licencia libre, de redes de sensores.
[1] H. Chaouchi, ed., The Internet of Things: Connecting Objects. Hoboken, NJ, London:
Wiley-ISTE, 2010.
[2] L. S. Barney, Developing hybrid applications for the iPhone: using HTML, CSS, and
JavaScript to build dynamic apps for the iPhone. Developer’s library, Boston, MA:
Pearson Education, 2008.
[3] Ji-Sun Kim, Denis Gracanin, Kresimir Matkovic, and Francis K. H. Quek,
“iPhone/iPod Touch as Input Devices for Navigation in Immersive Virtual En-
vironments.,” in VR, pp. 261–262, IEEE, 2009.
[4] M. Rahnema, “Overview of the GSM system and protocol architecture,” Commu-
nications Magazine, IEEE, vol. 31, no. 4, pp. 92–100, 1993.
[5] G. Anastasi, E. Borgia, M. Conti, and E. Gregori, “Wi-fi in ad hoc mode: a measure-
ment study,” Pervasive Computing and Communications, 2004. PerCom 2004. Proceed-
ings of the Second IEEE Annual Conference on, pp. 145–154, 2004.
[6] Dong Zhou, Lifei Huang, and Ten H. Lai, “On the scalability of IEEE 802.11 ad-
hoc-mode timing synchronization function,” Wirel. Netw., vol. 14, no. 4, pp. 479–
499, 2008.
[7] Wen Hu, Peter Corke, Wen Chan Shih, and Leslie Overs, “secFleck: A Public Key
Technology Platform for Wireless Sensor Networks,” in EWSN, pp. 296–311, 2009.
[8] Md. Mokammel Haque, Al-Sakib Khan Pathan, and Choong Seon Hong, “Se-
curing U-Healthcare Sensor Networks using Public Key Based Scheme,” CoRR,
vol. abs/0804.1184, 2008.
[9] C. Krauı́, M. Schneider, and C. Eckert, “On handling insider attacks in wireless
sensor networks,” Inf. Secur. Tech. Rep., vol. 13, no. 3, pp. 165–172, 2008.
[10] W. C. Shih, W. Hu, P. Corke, and L. Overs, “A public key technology platform for
wireless sensor networks,” in SenSys ’08: Proceedings of the 6th ACM conference on
Embedded network sensor systems, (New York, NY, USA), pp. 447–448, ACM, 2008.
[11] K. Hoeper and G. Gong, Models of Authentications in Ad Hoc Networks and Their
Related Network Properties, ch. 6. Springer, 2006.
[12] W. Peterson and E. Weldon, Error Correcting Codes. MIT press, 1972.
[13] H. Chan, A. Perrig, and D. Song, “Random key predistribution schemes for sensor
networks,” Proceedings of Symposium on Security and Privacy, 2003, pp. 197–213,
2003.
219
220
B IBLIOGRAF ÍA DEL C AP ÍTULO II
[1] W. Peterson and E. Weldon, Error Correcting Codes. MIT press, 1972.
[2] Rudolf Lidl and Harald Niederreiter, Finite fields, vol. 20 of Encyclopedia of Mathe-
matics and its Applications. Cambridge: Cambridge University Press, 2nd ed., 1997.
[3] R. J. McEliece, Finite field for scientists and engineers. Norwell, MA, USA: Kluwer
Academic Publishers, 1987.
[5] Daqing Wan, “Generators And Irreducible Polynomials Over Finite Fields,” Math-
ematics of Computation, vol. 66, pp. 1195–1212, 1997.
[6] Keith Conrad, Polynomials over a finite field. Deparment of Mathematics, University
of Connecticut, 2007.
[7] R. Lidl and H. Niederreiter, Finite Fields - Encyclopedia of Mathematics and its Appli-
cations, vol. 20. Addison-Wesley, 1983.
[8] Christof Paar, Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields.
PhD thesis, Institute for Experimental Mathematics, University of Essen, Ger-
many, 1994.
[9] J. Alanen and D. Knuth, “Tables of finite fields,” Sankhya, the Indian Journal of Statis-
tics, vol. Series A, 26(part 4):December, 1964, 1964.
[11] B. Ryu, T. Andersen, T. Elbatt, and Y. Zhang, “Multitier mobile ad hoc networks:
architecture, protocols, and perfomance,” vol. 2, pp. 1280–1285 Vol.2, 2003.
[12] Kwan-Wu Chin, John Judge, Aidan Williams, and Roger Kermode, “Implemen-
tation experience with MANET routing protocols,” SIGCOMM Comput. Commun.
Rev., vol. 32, no. 5, pp. 49–59, 2002.
[13] Elgan Huang, Wenjun Hu, Jon Crowcroft, and Ian Wassell, “Towards commercial
mobile ad hoc network applications: a radio dispatch system,” in In Proceedings of
the sixth ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc,
pp. 355–365, ACM Press, 2005.
[14] M. Sulleman Memon, Manzoor Hashmani, and Niaz A. Memon, “A review for
uniqueness and variations in throughput of MANET routing protocol due to per-
formance metrics, characteristics and simulation environments,” WTOC, vol. 7,
no. 5, pp. 459–468, 2008.
221
222 BIBLIOGRAF ÍA DEL CAP ÍTULO II
[15] Frank Stajano, Security for Ubiquitous Computing. John Wiley and Sons, Feb. 2002.
[16] A. Juels, “Minimalist Cryptography for Low-Cost RFID Tags (Extended Ab-
stract),” Security in Communication Networks, pp. 149–164, 2005.
[17] M. J. Robshaw, “An overview of RFID tags and new cryptographic develop-
ments,” Information Security Technical Report, vol. 11, no. 2, pp. 82–88, 2006.
[18] J. Biskup and J. Lopez, eds., Computer Security - ESORICS 2007, 12th European Sym-
posium On Research In Computer Security, Dresden, Germany, September 24-26, 2007,
Proceedings, vol. 4734 of Lecture Notes in Computer Science, Springer, 2007.
[19] A. Juels, R. L. Rivest, and M. Szydlo, “The blocker tag: selective blocking of RFID
tags for consumer privacy,” in CCS ’03: Proceedings of the 10th ACM conference on
Computer and communications security, (New York, NY, USA), pp. 103–111, ACM,
2003.
[20] Raghu Das and Dr Peter Harrop, “Complete RFID Analysis and Forecasts 2008-
2017,” tech. rep., IDTechEx, 2009.
[21] A. Mahajan, N. Potnis, K. Gopalan, and A. Wang, “Urban Mobility Models for
VANETs,” in Proc. of 2nd Workshop on Next Generation Wireless Networks, 2006.
[22] M. Fiore, J. Harri, F. Filali, and C. Bonnet, “Vehicular Mobility Simulation for
VANETs,” in Simulation Symposium, 2007. ANSS ’07. 40th Annual, pp. 301–309,
2007.
[23] Pandurang Kamat, Arati Baliga, and Wade Trappe, “An identity-based security
framework For VANETs,” in VANET ’06: Proceedings of the 3rd international work-
shop on Vehicular ad hoc networks, (New York, NY, USA), pp. 94–95, ACM, 2006.
[24] Charles E. Perkins, Elizabeth M. Belding Royer, and Samir R. Das, “Ad Hoc On-
Demand Distance Vector Routing Protocol,” internet-draft, IETF MANET Work-
ing Group, February 2003 2003. Expiration: August 17, 2003.
[25] Thomas Clausen and Philippe Jacquet, “Optimized Link State Routing Protocol
(OLSR),” RFC 3626, Internet Engineering Task Force, October 2003.
[27] T. Clausen, P. Jacquet, and L. Viennot, “Optimizing Route Length in Reactive Pro-
tocols for Ad Hoc Networks,” in Med-hoc-Net, september 2002. Sardaigne.
[29] C. Adjih, P. Jacquet, and L. Viennot, “Computing connected dominated sets with
multipoint relays,” Ad Hoc and Sensor Wireless Networks, vol. 1, no. 1-2, pp. 27–39,
2005.
[48] R. Stajano, F.; Anderson, “The Resurrecting Duckling: security issues for ubiqui-
tous computing,” Computer, vol. 35, pp. 22–26, April 2002.
[49] Laurent Eschenauer and Virgil D. Gligor, “A key-management scheme for dis-
tributed sensor networks,” in CCS ’02: Proceedings of the 9th ACM conference on
Computer and communications security, (New York, NY, USA), pp. 41–47, ACM,
2002.
[50] D. Liu and P. Ning, “Location-Based Pairwise Key Establishments for Static Sensor
Networks,” 2003.
[51] Cungang Yang, Celia Li, and Jie Xiao, “Location-based design for secure and ef-
ficient wireless sensor networks,” Comput. Netw., vol. 52, no. 16, pp. 3119–3129,
2008.
[52] A. Shamir, “Identity-based cryptosystems and signature schemes,” in Proceedings
of CRYPTO 84 on Advances in cryptology, (New York, NY, USA), pp. 47–53, Springer-
Verlag New York, Inc., 1985.
[53] A. Khalili, J. Katz, and W. A. Arbaugh, “Toward Secure Key Distribution in Truly
Ad-Hoc Networks,” in SAINT-W ’03: Proceedings of the 2003 Symposium on Appli-
cations and the Internet Workshops (SAINT’03 Workshops), (Washington, DC, USA),
p. 342, IEEE Computer Society, 2003.
[54] J.-P. Hubaux, L. Buttyán, and S. Capkun, “The quest for security in mobile ad hoc
networks,” in MobiHoc ’01: Proceedings of the 2nd ACM international symposium on
Mobile ad hoc networking & computing, (New York, NY, USA), pp. 146–155, ACM,
2001.
B IBLIOGRAF ÍA DEL C AP ÍTULO III
[1] Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot, Handbook of Ap-
plied Cryptography. Boca Raton, FL, USA: CRC Press, Inc., 1996.
[2] Don Coppersmith, Hugo Krawczyk, and Yishay Mansour, “The Shrinking Gener-
ator,” in CRYPTO ’93: Proceedings of the 13th Annual International Cryptology Confer-
ence on Advances in Cryptology, (London, UK), pp. 22–39, Springer-Verlag, 1994.
[3] Solomon W. Golomb, Shift Register Sequences. Laguna Hills, CA, USA: Aegean
Park Press, 1981.
[4] W. Peterson and E. Weldon, Error Correcting Codes. MIT press, 1972.
[5] Roberto Maria Avanzi and Nicolas Theriault, “Effects of Optimizations for Soft-
ware Implementations of Small Binary Field Arithmetic,” in WAIFI, pp. 69–84,
2007.
[6] S. Chowdhury and S. Maitra, “Efficient Software Implementation of LFSR and
Boolean Function and Its Application in Nonlinear Combiner Model,” Applied
Cryptography and Network Security - ACNS 2003, vol. Lecture Notes in Computer
Science 2846, pp. 387–402, 2003.
[7] S. Chowdhury and S. Maitra, “Efficient Software Implementation of Linear Feed-
back Shift Registers,” International Conference in Cryptology in India - INDOCRYPT
’01, vol. Lecture Notes in Computer Science 2247, pp. 397–407, 2001.
[8] Tore Herlestam, “On Functions of Linear Shift Register Sequences,” Advances in
Cryptology - EUROCRYPT ’85, vol. Volume 219/1986, pp. 119 – 129, 1985.
[9] P. Deepthi, Deepa Sara John, and P. Sathidevi, “Design and analysis of a highly
secure stream cipher based on linear feedback shift register,” Comput. Electr. Eng.,
vol. 35, no. 2, pp. 235 – 243, 2009.
[10] Jovan Dj. Golic, “On the Security of Nonlinear Filter Generators,” in Proceedings of
the Third International Workshop on Fast Software Encryption (L. N. I. C. Science, ed.),
vol. 1039, 1993.
[11] Philip Hawkes and Gregory G. Rose, “Guess-and-Determine Attacks on SNOW,”
in SAC ’02: Revised Papers from the 9th Annual International Workshop on Selected
Areas in Cryptography, (London, UK), pp. 37–46, Springer-Verlag, 2003.
[12] James S. Plank, Fast Galois Field Arithmetic Library in C/C++. Department of Com-
puter Science, University of Tennessee, 2007.
225
226 BIBLIOGRAF ÍA DEL CAP ÍTULO III
[30] W. Shi, H.-H. S. Lee, M. Ghosh, C. Lu, and A. Boldyreva, “High Efficiency Counter
Mode Security Architecture via Prediction and Precomputation,” SIGARCH Com-
put. Archit. News, vol. 33, no. 2, pp. 14–24, 2005.
[31] S. Fluhrer, I. Mantin, and A. Shamir, “Weaknesses in the Key Scheduling Algo-
rithm of RC4,” Lecture Notes in Computer Science, vol. 2259, pp. 1–??, 2001.
[32] Juan Soto, “Statistical Testing of Random Number Generators,” in In: Proceedings
of the 22nd National Information Systems Security Conference, 1999.
[33] Ueli M. Maurer, “A universal statistical test for random bit generators,” Journal of
cryptology, vol. 5, pp. 89–105, 1992.
[34] David Naccache, “An Accurate Evaluation of Maurer’s Universal Test,” in Pro-
ceedings of SAC ’98 (Lecture Notes in Computer Science), pp. 57–71, Springer-Verlag,
1998.
[35] J.-S. Coron and D. Naccache, “An Accurate Evaluation of Maurer’s Universal
Test,” in SAC ’98: Proceedings of the Selected Areas in Cryptography, (London, UK),
pp. 57–71, Springer-Verlag, 1999.
[36] G. Marsaglia, “Diehard battery of tests of randomness.” Florida State University,
1995.
[37] George Marsaglia and Wai Wan Tsang, “Some Difficult-to-pass Tests of Random-
ness,” Journal of Statistical Software, vol. 7, no. i03, 2007.
[38] Robert G. Brown, “Dieharder: A Random Number Test Suite.” Duke University
Physics Department, [Link] rgb/General/[Link],
2004.
[39] J. Andrew Rukhin, Juan Soto, A Statistical Test Suite for Random and Pseudorandom
Number Generators for Cryptographic Applications. NIST, special publication 800-22,
revision 1 ed., Agosto 2008.
228
B IBLIOGRAF ÍA DEL C AP ÍTULO IV
[2] V. Frias, G. Delgado, and M. Igartua, “Multipath Routing for video-streaming ser-
vices over IEEE 802.1le Ad hoc Networks,” International Conference on Software in
Telecommunications and Computer Networks, vol. 0, pp. 132–136, 2006.
[3] Helger Lipmaa, Phillip Rogaway, and David Wagner, “Comments to NIST Con-
cerning AES-modes of Operations: CTR-mode Encryption,” in Symmetric Key Block
Cipher Modes of Operation Workshop, (Baltimore, Maryland, US), 20 October 2000.
[4] Niels Ferguson, Doug Whiting, Bruce Schneier, John Kelsey, Stefan Lucks, and
Tadayoshi Kohno, “Helix - Fast Encryption and Authentication in a Single Cryp-
tographic Primitive,” in Proc. Fast Software Encryption 2003, volume 2887 of LNCS,
pp. 330–346, Springer-Verlag, 2003.
[5] William E. Burr, “Selecting the Advanced Encryption Standard,” IEEE Security and
Privacy, vol. 1, no. 2, pp. 43–52, 2003.
[10] Don Coppersmith, Hugo Krawczyk, and Yishay Mansour, “The Shrinking Gener-
ator,” in CRYPTO ’93: Proceedings of the 13th Annual International Cryptology Confer-
ence on Advances in Cryptology, (London, UK), pp. 22–39, Springer-Verlag, 1994.
[11] Solomon W. Golomb, Shift Register Sequences. Laguna Hills, CA, USA: Aegean
Park Press, 1981.
[12] Pino Caballero Gil, Amparo Fúster Sabater, and Maria Eugenia Pazo Robles, “New
Attack Strategy for the Shrinking Generator,” in WOSIS, pp. 59–67, 2008.
229
230 BIBLIOGRAF ÍA DEL CAP ÍTULO IV
[14] Eli Biham and Orr Dunkelman, “Cryptanalysis of the A5/1 GSM Stream Cipher,”
in INDOCRYPT, pp. 43–51, 2000.
[16] Gregory G. Rose and Philip Hawkes, “Turing, a Fast Stream Cipher,” in In T.
Johansson, Proceedings of Fast Software Encryption FSE2003, LNCS 2887, Springer-
Verlag, pp. 307–324, Springer-Verlag, 2003.
[17] Ilan Kessler and H. Krawczyk, “Minimum buffer length and clock rate for the
shrinking generator cryptosystem,” tech. rep., IBM T.J. Watson Research Center,
Yorktown Heights, NY 10598, 1995.
[19] S. Meyn and R. L. Tweedie, Markov Chains and Stochastic Stability. New York, NY,
USA: Cambridge University Press, 2009.
[21] R. Lidl and H. Niederreiter, Introduction to finite fields and their applications. New
York, NY, USA: Cambridge University Press, 1986.
[22] Hongjun Wu and Bart Preneel, “Cryptanalysis of the Stream Cipher DECIM,” in
FSE (M. J. B. Robshaw, ed.), vol. 4047 of Lecture Notes in Computer Science, pp. 30–
40, Springer, 2006.
[23] J. Bray and C. Sturman, Bluetooth 1.1: Connect Without Cables, Second Edition. Upper
Saddle River, NJ, USA: Prentice Hall PTR, 2001.
[25] Hkan Englund, Martin Hell, and Thomas Johansson, “Two General Attacks on
Pomaranch-Like Keystream Generators,” in FSE, pp. 274–289, 2007.
[27] Antoine Joux and Frédéric Muller, “A Chosen IV Attack Against Turing,” in Se-
lected Areas in Cryptography, pp. 194–207, 2003.
[28] Hongjun Wu and Bart Preneel, “Differential-Linear Attacks against the Stream
Cipher Phelix,” in In Proc. FSE 2007, LNCS, Springer, 2006.
[29] S. Fluhrer, I. Mantin, and A. Shamir, “Weaknesses in the Key Scheduling Algo-
rithm of RC4,” Lecture Notes in Computer Science, vol. 2259, pp. 1–??, 2001.
BIBLIOGRAF ÍA DEL CAP ÍTULO IV 231
[1] Frank Stajano, Security for Ubiquitous Computing. John Wiley and Sons, Feb. 2002.
[2] David D. Hwang, Bo-Cheng Charles Lai, and Ingrid Verbauwhede, “Energy-
Memory-Security Tradeoffs in Distributed Sensor Networks,” in ADHOC-NOW
2004, vol. 3158 of LNCS, 2004.
[5] H. Chan, A. Perrig, and D. Song, “Random key predistribution schemes for sensor
networks,” Proceedings of Symposium on Security and Privacy, 2003, pp. 197–213,
2003.
[6] Wenliang Du, Jing Deng, Yunghsiang S. Han, and Pramod K. Varshney, “A pair-
wise key pre-distribution scheme for wireless sensor networks,” in CCS ’03: Pro-
ceedings of the 10th ACM conference on Computer and communications security, (New
York, NY, USA), pp. 42–51, ACM, 2003.
[7] D. Liu and P. Ning, “Location-Based Pairwise Key Establishments for Static Sensor
Networks,” 2003.
[8] Laurent Eschenauer and Virgil D. Gligor, “A key-management scheme for dis-
tributed sensor networks,” in CCS ’02: Proceedings of the 9th ACM conference on
Computer and communications security, (New York, NY, USA), pp. 41–47, ACM,
2002.
[9] M. Bohge and W. Trappe, “An authentication framework for hierarchical ad hoc
sensor networks,” in WiSe ’03: Proceedings of the 2nd ACM workshop on Wireless
security, (New York, NY, USA), pp. 79–87, ACM, 2003.
[11] Bo-Cheng Charles Lai, David D. Hwang, Sungha Pete Kim, and Ingrid Ver-
bauwhede, “Reducing Radio Energy Consumption of Key Management Protocols
for Wireless Sensor Networks,” Low Power Electronics and Design, International Sym-
posium on, vol. 0, pp. 351–356, 2004.
[12] Y. Wang, “Robust key establishment in sensor networks,” SIGMOD Rec., vol. 33,
no. 1, pp. 14–19, 2004.
233
234 BIBLIOGRAF ÍA DEL CAP ÍTULO V
[14] K. Kabri and D. Seret, “An Evaluation of the Cost and Energy Consumption of
Security Protocols in WSNs,” in SENSORCOMM ’09: Proceedings of the 2009 Third
International Conference on Sensor Technologies and Applications, (Washington, DC,
USA), pp. 49–54, IEEE Computer Society, 2009.
[15] NIST, Recommendation for Key Management. Part 1: General Guideline. Special Publi-
cation 800-57, p. 63. 2007.
[16] Ross Anderson, Haowen Chan, and Adrian Perrig, “Key Infection: Smart Trust for
Smart Dust.” Proc. of ICNP’04, October 2004.
[17] Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot, Handbook of Ap-
plied Cryptography. Boca Raton, FL, USA: CRC Press, Inc., 1996.
[18] L. Lamport, “Password authentication with insecure communication,” Commun.
ACM, vol. 24, pp. 770–772, November 1981.
[19] Qijun Gu, Peng Liu, and Chao-Hsien Chu, “Analysis of area-congestion-based
DDoS attacks in ad-hoc networks,” Ad Hoc Networks., vol. 5, no. 5, pp. 613–625,
2007.
[20] Peter Gutmann, “Data remanence in semiconductor devices,” in SSYM’01: Pro-
ceedings of the 10th conference on USENIX Security Symposium, (Berkeley, CA, USA),
pp. 4–4, USENIX Association, 2001.
[21] R. J. Anderson, Security Engineering: A Guide to Building Dependable Distributed Sys-
tems. Wiley, January 2001.
[22] Peter Gutmann, Secure deletion of data from magnetic and solid-state memory, pp. 8–8.
Berkeley, CA, USA: USENIX Association, 1996.
[23] G. Bravos and A. G. Kanatas, “Energy efficiency comparison of MIMO-based and
multihop sensor networks,” EURASIP J. Wirel. Commun. Netw., vol. 2008, pp. 1–13,
2008.
[24] D. W. Carman, P. S. Kruus, and B. J. Matt, “CONSTRAINTS AND APPROACHES
FOR DISTRIBUTED SENSOR NETWORK SECURITY,” Tech. Rep. 010, NAI Labs,
The Security Research Division Network Associates, Inc., September 2000.
[25] M. Mallinson, S. Hussain, and J. H. Park, “Investigating Wireless Sensor Network
Lifetime Using a Realistic Radio Communication Model,” in MUE ’08: Proceed-
ings of the 2008 International Conference on Multimedia and Ubiquitous Engineering,
(Washington, DC, USA), pp. 433–437, IEEE Computer Society, 2008.
[26] G. Anastasi, M. Conti, M. Francesco, and A. Passarella, “Energy conservation in
wireless sensor networks: A survey,” Ad Hoc Networks, vol. 7, pp. 537–568, May
2009.
B IBLIOGRAF ÍA DEL C AP ÍTULO VI
235
236
B IBLIOGRAF ÍA DEL C AP ÍTULO VII
237