Anlisis de Primitivas Criptogrcas para Redes de Sensores

Cristina Alcaraz, Rodrigo Roman, Javier Lpez Departamento de Lenguajes y Ciencias de la Computacin Universidad de Mlaga E-mail: {alcaraz, roman, jlm}@lcc.uma.es

Abstract Security in wireless sensor networks is very limited due to highly-constrained hardware of sensor nodes. To protect services is necessary to use secure foundations, known as security primitives, like part of a protocol. Theses primitives must assure at least condentiality in the communication channel, authentication of the peers involved in an information exchange, and integrity of the messages. There are many primitives such as symmetric encryption, hash functions and public key cryptography, but not all of them can be supported by sensor nodes since require high resource levels, for example memory. This paper contains a deep analysis of available and suitable security primitives for sensor nodes, as well as an analysis of hardware and software implementations. Besides, it has been developed an experiment with two implementations, and it has been created a new and improved version using the optimizations of each.

1.

Introduccin

Una red de sensores inalmbrica est compuesta por la agrupacin de dispositivos pequeos (nodos sensores) que interaccionan entre s para alcanzar un objetivo comn. Su tarea principal es la de monitorizar un evento fsico (aire, humedad, luz, etc.), aunque tambin pueden enviar o recibir mensajes de avisos, o recibir mensajes de consultas (estado de la red o una determinada propiedad) de alguna estacin base, la cual es un dispositivo con mayores recursos que los nodos sensores, y funciona como mediador entre stos y el usuario nal. Este tipo de red presenta muchos problemas en la parte relacionada con la seguridad, y ms an, cuando esta tecnologa, tan reciente, es muy demandada para mltiples aplicaciones, independientemente del tipo de informacin que se gestione en ella. De hecho, uno de los desafos propuestos por la comunidad cientca [1] es proveer seguridad en todos los niveles, desde la informacin hasta protocolos y servicios. Sin embargo, proveer y garantizar seguridad no es una tarea sencilla cuando la naturaleza de los nodos est muy limitada en cmputo, almacenamiento y energa. Por ejemplo, el nodo Telosb [2] posee un microcontrolador a 8Mhz, con 48kB de ROM y 10kB de RAM, y el nodo Micaz [3] posee un microcontrolador a 8Mhz, con 128kB de ROM y 4kB de RAM. Debido a que el principal soporte para la seguridad son las primitivas criptogrcas, en este artculo se analizan las que existen actualmente, y aquellas que pueden ser soportadas por los nodos sensores. Tambin, es importante saber qu tipo de implementacin

(hardware o software) debe aplicarse, ya que dependiendo de la arquitectura del nodo, puede ser soportada o no, y qu tipo de investigaciones se estn desarrollando en la actualidad. A parte de este anlisis, se ha desarrollado un experimento con dos tipos de implementaciones asimtricas (TinyECC y WMECC), en los nodos Telosb y Micaz, para cuanticar la sobrecarga en tiempo y espacio al ejecutar las primitivas en dichos nodos. Adems, se ha obtenido una implementacin optimizada (TinyWMECC) por la unicacin de aquellas partes optimizadas de cada una de las implementaciones anteriores. El artculo est organizado de la siguiente manera: en la seccin 2 se describen los motivos por los que es necesario garantizar seguridad en este tipo de redes, en la seccin 3 se analizan las caractersticas de las primitivas criptogrcas existentes, identicando las que mejor se ajustan a los nodos sensores, en la seccin 4 y 5 se muestra un anlisis de implementaciones hardware y software, respectivamente, de las primitivas apropiadas para esta red, en la seccin 6 se encuentran las conclusiones, y por ltimo, los agradecimientos.

2.

Necesidad de Seguridad en las Redes de Sensores

Proteger lgicamente (ataques pasivos o activos) y fsicamente (daos en la arquitectura fsica) a los nodos, ante malas acciones de adversarios, no es una tarea sencilla. El nmero de ataques presentes en estos tipos de redes, en comparacin con las convencionales, es mayor al existir vulnerabilidades en los nodos, en la

comunicacin y en el entorno. Los motivos por los que existen estas debilidades son, en primer lugar, las restricciones hardware y software de los nodos, que dicultan la incorporacin de mecanismos seguros. En segundo lugar, el tipo de comunicacin (inalmbrica) donde cualquier dispositivo con antena puede acceder, y por ltimo, al ser un medio distribuido en el que ofrecer un servicio implica la cooperacin de todos los nodos, cualquier fallo en un nodo podra interrumpir la continuidad del servicio. Para garantizar seguridad en cualquier instante de tiempo, es necesario utilizar los elementos criptogrcos bsicos, a n de proporcionar proteccin en la informacin, protocolos y servicios de red. Estos elementos son las primitivas de Criptografa de Clave Simtrica (SKC), de funciones hash, y de Criptografa de Clave Pblica (PKC), que se pueden considerar como el alma de cualquier protocolo de seguridad. Estas primitivas aseguran condencialidad e integridad (evitar que individuos sin permiso puedan realizar lecturas y/o alteraciones en los paquetes), y autenticacin de ambas partes de la comunicacin. Aunque, stas no garantizan la proteccin absoluta, es necesario utilizarlas, ya que sin ellas no existira seguridad.

3.

Requisitos de las Primitivas de Seguridad

Cada primitiva posee unas propiedades particulares, y obliga al sistema que la vaya a soportar a cumplir unas exigencias (capacidad de cmputo o memoria). Por consiguiente, no todas pueden ser soportadas por los nodos sensores, y por lo tanto, el objetivo de esta seccin es analizar e identicar las primitivas ms apropiadas para las redes de sensores.

3.1.

Primitivas de Criptografa Clave Simtrica

de

En SKC, las primitivas hacen uso de una misma clave tanto para encriptar como para desencriptar. En esta seccin, se analizarn algoritmos sencillos y apropiados para dispositivos con recursos restringidos, clasicados en algoritmos de cifrado de bloque y de ujo. En el cifrado de ujo, la entrada de datos a cifrar posee una longitud variable. Para poder cifrar un mensaje es necesario una transformacin de bits mediante la utilizacin de una clave y un vector de inicializacin. Estos dos elementos generan un ujo de clave pseudoaleatorio que ser combinado (XOR) bit a bit con el ujo de entrada de datos. Un ejemplo de algoritmo de

cifrado de ujo que destaca por su sencillez es el RC4 [4], el cual utiliza operaciones como sumas e intercambios, y otras a nivel de bits como AND y XOR. Dichas operaciones se realizan sobre bloques de 8 bits, con lo cual, no requiere mucha memoria para operar. Es importante usar adecuadamente RC4 para evitar problemas como los existentes en el protocolo WEP [5], al no realizar correctamente la inicializacin. En el cifrado de bloque, la entrada de datos posee un tamao de longitud ja, la cual va a sufrir una serie de transformaciones para obtener un mensaje cifrado de igual longitud que la entrada. Estas transformaciones se consiguen mediante el uso de una clave y un modo de operacin (Electronic Codebook (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB), o Counter (CTR)). No existe una clara distincin entre cifrado de ujo y cifrado de bloque, ya que un cifrado de bloque puede actuar en modo cifrado de ujo que opera a nivel de bits en lugar de a nivel de bloques. Skipjack [6] es un algoritmo de cifrado de bloques de 64 bits, rpido y simple. Encripta bloques de datos de 4 palabras utilizando una clave de 80 bits, y alcanzando 32 iteraciones. Para las transformaciones emplea dos reglas (A y B), las cuales se pueden ver como un registro de desplazamiento con retroalimentacin lineal y permutaciones G (cifrado Feistel de cuatro iteraciones), que se van aplicando alternadamente. El planicador de clave es sencillo, ya que repite la clave tantas veces como sea necesario para completar el buer. Sin embargo, la longitud de la clave empleada es muy pequea. Un algoritmo algo ms complejo que el anterior es el RC5 [7], el cual puede poseer un tamao de bloque, un tamao de clave y un nmero de iteraciones variable. No obstante, se recomienda utilizar un bloque de 64 bits, una clave de 128 bits y 20 iteraciones. El algoritmo est compuesto por tres operaciones (suma de enteros, XOR y rotacin variable) sobre dos registros de b/2 bits. Un algoritmo muy similar a RC5 es el RC6 [8], que se distingue por la realizacin de multiplicaciones enteras y la utilizacin de cuatro registros de tamao b/4 bits. El tamao de clave puede ser 128, 192 y 256 bits, el tamao de bloque de 128 bits y 20 iteraciones. El algoritmo Estndar de Encriptacin Avanzada (AES) o Rijndael [9], tiene un bloque de 128 bits, y el nmero de interacciones (10, 12, 14) depender del tamao de clave que puede ser de 128, 192 o 256 bits. Todas las operaciones en AES se desarrollan sobre un matriz de bytes de 4 4 y sobre un campo nito. Para encriptar un mensaje es necesario pasar por cuatro estados en cada iteracin (excepto la ltima): AddRoundKey (la clave es combinada mediante un XOR con el estado), SubBytes (cada byte en el estado es reemplaza-

do con su entrada tomada de una tabla predeterminada de 8 bits), ShiftRows (los bytes de cada la del estado son desplazados cclicamente hacia la izquierda) y MixColumns (cada columna del estado es multiplicada con un polinomio determinado c(x)). Por ltimo, el algoritmo de cifrado Twosh [10] es muy similar al AES, y usa un bloque de 128 bits, con una clave de 256 bits y 16 iteraciones. Twosh utiliza cuatro operaciones biyectivas diferentes, posee un planicador de claves complejo, se basa de las denominadas S-boxes de 8 8 bits de claves dependientes, y emplea algunos de los elementos de otras familias de cifrado, como por ejemplo, la transformacin pseudoHadamard de la familia SAFER, o la matriz de de distancia mxima separable (MDS) de 4 4 sobre GF (28 ).

3.2.

Primitivas de Funciones Hash

Las funciones hash se utilizan para comprimir datos de entrada con longitud variable (e-bits) a uno con un tamao jo (s-bits), conocido con el nombre de valor hash h. Estas funciones deben de satisfacer dos propiedades principales: (1) debe ser extremadamente complicado encontrar un mensaje m, tal que hash(m) = h, y (2) debe ser difcil encontrar dos mensajes m1 y m2 , tal que hash(m1 ) = hash(m2 ). Un ejemplo, es la funcin hash SHA-1 [11], la cual tiene e = 512 bits y s = 160 bits, utilizando operaciones XOR, AND, OR, NOT, sumas, y rotaciones. Como la probabilidad de colisin tiende a tener una complejidad del orden 263 , se recomienda la funcin hash SHA-256 con e = 512 bits y s = 256 bits. Tambin, existen otras funciones como RIPEMD-160 [12], con e = 512 bits y s = 160 bits, que usa operaciones de rotacin, permutacin y desplazamiento. Otras primitivas criptogrcas, como por ejemplo, los Cdigos de Autenticacin de Mensajes (MAC), utilizan las funciones hash para conseguir integridad en los mensajes y autenticidad. Aunque tambin pueden ser obtenidas mediante el modo de operacin CBCMAC perteneciente a SKC.

3.3.

Primitivas Criptogrcas de Clave Pblica

La PKC, o criptografa de clave asimtrica, es apropiada en canales de comunicacin donde se requiere autenticacin e integridad de los datos. Se basa de la utilizacin de dos claves (privada y pblica). La clave privada es slo conocida por su propietario, y la clave pblica es conocida por toda la red. Ambas estn relacionadas matemticamente, pero inferir una a partir de la otra supone un clculo impracticable. De-

safortunadamente, el coste de computacin requerido en sus primitivas, diculta su aplicacin en dispositivos con altas restricciones, como los nodos sensores. A pesar de que el algoritmo asimtrico ms popular es el RSA [13] al ofrecer operaciones de encriptacin y rma digital, su clculo operacional es bastante alto, y aplicarlo en contextos restringidos como en las redes de sensores supone un mayor coste. Por estas razones, se recomiendan otros algoritmos ms sencillos y adecuados para este tipo de redes, como es la Criptografa de Clave Elptica (ECC) [14]. sta se basa de conceptos algebraicos relacionados con curvas elpticas cuya estructura se corresponde con la ecuacin y 2 = x3 + ax + b sobre un campo nito Fp o F2m . Dado a y c, la seguridad de este tipo de criptografa radica en la computacin de la ecuacin ab = c, conocido como el problema del logaritmo discreto. Su operacin bsica es la multiplicacin en punto escalar, la cual puede ser obtenida realizando sumas y desplazamientos repetidamente, y adems, se requiere de la inversin de un entero calculado sobre coordenadas anes. Debido a que el coste computacional es bastante elevado, se han desarrollado algunas optimizaciones, usando el mtodo de Shamir para reducir el tiempo de vericacin, o coordenadas proyectivas para evitar las operaciones de inversin. El tamao de las claves en ECC es signicativamente menor que en RSA, proveyendo la misma seguridad con menos recursos. Adems, ECC posee dos primitivas, una para establecer una clave compartida mediante el protocolo Curva Elptica de Die-Hellman (ECDH), y otra para la generacin (una multiplicacin de punto) y vericacin (dos multiplicaciones de punto) de rmas digitales mediante la Curva Elptica DSA (ECDSA). Otro algoritmo asimtrico es Rabin [15], un esquema rpido al encriptar datos utilizando la potencia al cuadrado. Su seguridad se encuentra en la dicultad de resolver la raz cuadrada del cifrado, similar al problema de la factorizacin de primos grandes, como en el RSA. Aunque, la desencriptacin genera cuatro salidas, tres de ellas falsas y una correcta, lo que supone una complejidad mayor. Por otro lado, tanto el algoritmo NtruEncrypt [16] como su correspondiente de rma digital, conocido como NtruSign, estn basados en conceptos aritmticos. Concretamente, en un anillo polinomial R = Z(x)/((xN 1), q ), cuyas operaciones bsicas son multiplicaciones polinomiales, que lo hacen ms rpido que otros esquemas. Su seguridad se encuentra en resolver el problema del vector ms corto y el ms cercano. Por ltimo, los criptosistemas de clave pblica multivariada, tambin conocido como MQ-esquemas [17] son uno de los ms recientes, y se caracterizan por su velocidad de generacin de rmas digitales. Su

seguridad se encuentra en resolver w = V 1 (z ) = (1 , ..., n ) K n , dado un mapa polinomial cuadrtico V = (1 , ..., m ) : K n K m . No obstante, existe un coste de almacenamiento en memoria considerable, es decir, se necesita reservar 879 bytes para la clave privada, y 8680 bytes para la clave pblica.

4.

Implementaciones Hardware de Primitivas de Seguridad

Una forma ptima de aplicar primitivas de seguridad se conseguira mediante el uso de dispositivos hardware, ya que se obtendra mayor eciencia, rapidez, y adems, se podran soportar algoritmos criptogrcos ms complejos, en lugar de usar implementaciones software.

3.4.

Primitivas de Seguridad Apropiadas

4.1.

Soporte Hardware Existente

Como se ha comentado en las secciones anteriores, existe una amplia variedad de primitivas de seguridad, aunque no todas pueden ser compatibles con las limitaciones de los nodos. Una de las ms adecuadas dentro de las primitivas de SKC es RC4, por su tamao de bloque y sencillez de sus operaciones. RC4 es apropiado para cualquier microcontrolador con altas restricciones. Tambin el Skipjack se adeca bastante a microcontroladores limitados pero con una arquitectura de 16 bits, al tener un diseo simple tanto en sus operaciones como en la planicacin de claves. Sin embargo, RC5 y RC6 no son tan adecuados como los anteriores, ya que sus registros son de 32 bits y requieren demasiadas iteraciones (20), aunque sus bloques de construccin sean simples. Tambin, son menos adecuados AES y Twosh por su complejidad, a pesar de tener pocas iteraciones y poder calcular algunas de las operaciones en registros de 8 bits (rpidas de operar). Con respecto a las primitivas hash, todos los algoritmos nombrados han sido optimizados para procesadores de 32 bits, con lo cual no son apropiados para microcontroladores de 8 o 16 bits. Por otro lado, los bloques de construccin son simples, y por lo tanto, el software resultante es pequeo y rpido. De todas formas, sera interesante desarrollar funciones hash en microcontroladores de 8 y 16 bits. En PKC, todas las primitivas presentan una complejidad considerable, que las hace inadecuadas para microcontroladores restringidos. Sin embargo, stas poseen ciertas ventajas, como en ECC, el cual alcanza la misma seguridad que cualquier otro criptosistema de PKC, con una clave mucho menor. El algoritmo NTRUEncrypt ejecuta operaciones de encriptacin o desencriptacin, y el esquema Rabin, encriptacin y vericacin, muy veloces. El MQ-esquema genera rmas digitales en tiempos ptimos, y adems, si se consigue almacenar las claves en RAM, se asegura un excelente tiempo de vericacin.

Actualmente, existen varias implementaciones, una de ellas, se encuentra en el estndar 802.15.4 (implementado por el transceptor CC2420). Este estndar incluye primitivas criptogrcas, como es el AES, el cual est compuesto por AES-CTR, por AES-CBCMAC que combina AES con el modo de operacin CBC-MAC, y por AES-CCM con un tamao MAC de 64 bits para proveer condencialidad y autenticacin. An as, existen varios problemas a tener en cuenta [18], por ejemplo, el AES-CTR no es capaz de detectar ataques de reenvo de paquetes, pudiendo derivar en otros ms serios como el de Denegacin de Servicio (DoS). Adems, los paquetes ACK pueden ser fcilmente falsicados al no estar protegidos por un MAC. Para gestionar las entradas y las salidas, los transceptores poseen una lista de control de acceso (ACL) que contiene el tipo de seguridad establecido en una comunicacin. De esta forma, cuando el receptor reciba un paquete, podr aplicar la seguridad que se encuentra especicada en la lista. Sin embargo, estas implementaciones hardware suelen tener problemas. Por ejemplo, el CC2420 slo posee dos entradas en su ACL, por lo que slo provee funcionalidad a dos de sus vecinos. Por otro lado, es posible conseguir un nivel de paralelismo en el procesamiento de primitivas, mediante instrucciones SIMD (extensin MMX) pertenecientes a la familia del microcontrolador PXA27X de Intel. Esta extensin est compuesta de 16 registros de datos de 64 bits, y de 8 registros de control de 32 bits, permitiendo el cmputo de mltiples operaciones en una misma instruccin. Concretamente, AES posee un paralelismo interno muy elevado, as que es un candidato perfecto para optimizacin. En cambio, la transformacin pseudo-Hadamard de Twosh diculta el paralelismo.

4.2.

Soporte gacin

Hardware

en

Investi-

La comunidad cientca est intentando balancear la carga de ejecucin de primitivas criptogrcas y dems

tareas, en un nodo con altas limitaciones. Actualmente, existen varios prototipos, pero nada tangible. Lo ideal sera disponer de un dispositivo que sea externo o est adherido al microcontrolador, pero que conjuntamente, reduzca el cmputo de cualquier operacin. Desde que se demostr la posibilidad de aplicar PKC (ver seccin 5.2) en redes de sensores mediante ECC, ha existido un gran inters en disear dispositivos que la soportasen. De hecho, Wolkerstorfer et. al. [19] y Kumar junto con Paar [20] desarrollaron un chip integrado para generar rmas digitales usando ECDSA. El primer chip opera a 68.5Mhz, tiene 23000 puertas implementadas bajo 0,35m en tecnologa CMOS, siendo capaz de computar una multiplicacin de punto sobre el campo nito F2191 en 6,67ms. En cambio, el chip de Kumar y Paar opera a 13Mhz, posee alrededor de 12000 puertas, y computa una multiplicacin de punto sobre el campo F2131 en 18ms. A pesar de que existe alto coste computacional en ambas implementaciones, los nodos con microcontroladores PIC18F6720, PXA271, y ARM920T son capaces de soportarlos. Por otro lado, se encuentra la optimizacin obtenida por Gaubatz et. al. [21], los cuales tuvieron en cuenta las reducciones modulares, los costes involucrados en las inversiones, e implementaron todas las primitivas aritmticas en un chip especial denominado bitserial fashion. El dispositivo desarrollado opera a 500kHz, con 18720 puertas bajo 0,13m en tecnologa CMOS, y opera sobre el campo Fp100 para la multiplicacin de punto escalar. Requiere de 410ms para generar una rma digital con ECDSA o desencriptar mensajes con Curva Elptica de Menezes Vanstone (ECMV), mientras que para vericar o encriptar con ECMV requiere de 820ms, consumiendo en general menos de 400W. Una mejora surge en el ao 2006, donde Batina et. al. [22] presentan un procesador de curva elptica con una unidad lgica aritmtica modular (MALU) para realizar sumas modulares y multiplicaciones, obtener la potencia al cuadrado a partir de mutliplicaciones, y anular las inversiones usando coordenadas proyectivas. El chip opera a 500kHz, con 8104 puertas bajo 0,13m en tecnologa CMOS, computando una operacin de multiplicacin de punto sobre F2131 en 115ms, y consumiendo menos de 30W. Tambin, Gaubatz et. al. presentaron en [21] una implementacin para soportar la primitiva asimtrica Rabin, con menos de 17000 puertas, encriptando y desencriptando mensajes en 2.88ms, y consumiendo una media de 148,18W. Sin embargo, requera de 1.089s para las operaciones de desencriptacin y generacin de rma digital. Los mismos autores en [21] propusieron una implementacin que soportara la primitiva asimtrica NtruEncrypt, con 3000 puertas, operando a 500kHz, y

consumiendo alrededor de 20W. Para vericar y encriptar mensajes requera de 58ms, para desencriptar 117ms, y para generar una rma digital 234ms. Por ltimo, Yang et. al. [23] presentaron una implementacin para criptosistemas de clave pblica multivariada, operando a 100kHz con 17000 puertas bajo 0,25m en tecnologa CMOS. Est pensado para etiquetas de RFID, y slo puede generar rmas digitales (en 44ms) mediante el mtodo Lanczos, y consumiendo alrededor de 25A.

5.

Implementaciones Software de Primitivas de Seguridad

Pese a que los microcontroladores de los nodos sensores estn muy limitados en recursos, en esta seccin se va a mostrar que stos pueden ser capaces de computar primitivas criptogrcas a nivel de software.

5.1.

Criptografa de Clave Simtrica y Funciones Hash

El objetivo principal en la computacin de primitivas SKC y funciones hash es la de alcanzar un tiempo de encriptacin, tal que ste no deba ser superior al tiempo de transmisin de un byte por radio. Por ejemplo, si el nodo posee un transceptor CC1000 con 19.2kbps, el tiempo de transmisin es alrededor de 420s, o para un transceptor CC2420 con 250kbps, el tiempo de transmisin es aproximadamente de 32s. Las primeras investigaciones realizadas para analizar la sobrecarga de encriptacin de primitivas de clave simtrica y hash en microcontroladores fue en el ao 2003 por Ganesan et. al. [24]. Ellos demostraron que encriptar un texto plano de 1 byte con RC5 requera un tiempo de 26s, con IDEA 21s y con RC4 6s. Tambin, analizaron que a pesar de que la funcin hash SHA-1 necesitaba 7777s para comprimir 64 bytes, el espacio reservado de memoria no superaba los 4000 bytes. Hasta el siguiente ao no se lleg a conrmar la posibilidad de utilizar las primitivas criptogrcas en redes de sensores, con la introduccin del paquete TinySec [25] implementado en nesC (lenguaje orientado a componentes), y funcionado sobre el Sistema Operativo TinyOS 1.x, y slo en los nodos Mica y Mica2. Este paquete provee primitivas como: Skipjack (tiempo de encriptacin de 48s), y un optimizado RC5 (tiempo de encriptacin de 33s). Para conseguir integridad en los datos, ste no utiliza funciones hash, sino CBC-MAC. En 2006, Wei Law et. al. [26], y Jun Chio y Song [27] volvieron a analizar la sobrecarga de encriptacin

observando, que por ejemplo, tanto Twosh como AES consiguen un tiempo de encriptacin medio de 50s, y Skipjack (optimizado) necesitaba 25s. Con respecto al tamao medio de memoria, ellos analizaron que RC4 era el algoritmo ms optimizado al reservar tan slo 428 bytes. En cambio, Skipjack necesitaba de 2600 bytes de ROM, y el resto de algoritmos alrededor de 8000 bytes.

5.2.

Criptografa de Clave Pblica

ROM RAM Inic. ECC Inic. ECDSA Gen. Clave Pub. Firma Digital Vericacin

TinyECC Micaz Telosb 28266 26048 2306 2327 1.837s 3.550s 5.225s 1.788s 1.916s 4.361s 2.431s 5.448s

WMECC Micaz Telosb 57982 46156 1685 1657 1.809s 1.744s 0s 0s 1.261s 1.425s 1.348s 1.498s 2.017s 2.207

Hasta en el ao 2004, la posibilidad de usar primitivas de clave asimtrica en las redes de sensores se consideraba imposible. La causa que hizo cambiar de idea, fueron los estudios realizados por Gura et. al. [28], los cuales determinaron que mediante ECC era posible implementar PKC. De hecho, Malan et.al. [29] presentaron la librera EccM 2.0 con las primeras primitivas de ECC sobre el campo F2p , con 163 bits de tamao de clave, y un tiempo medio de 34s para computar sus operaciones. Sin embargo, 34s era un periodo de tiempo de ejecucin considerable, por eso fue optimizado por Gura et. al. [28] al reducir las inversiones con coordenadas proyectivas y utilizando primitivas ECC sobre el campo Fp para mejorar el rendimiento de su mdulo. Estas optimizaciones y otras fueron implementadas por Liu y Ning con TinyECC [30] (actualmente se encuentra la ltima versin-0.3 soportada por Micaz, Telosb e Imote2), y Wang y Li con WMECC [31] sobre el Sistema Operativo TinyOS. El diseo de sus implementaciones presenta ciertas caractersticas en comn, como por ejemplo: ambos hacen uso del p = 2n c, como primos pseudo-Mersenne, con el n de obtener una reduccin en las multiplicaciones y cuadrados modulares. Adems, ambos aplican coordenadas proyectivas, hacen uso del mtodo de ventana deslizante para realizar agrupaciones de escalares y para precomputar las multiplicaciones de punto escalar, y usan el mtodo de Shamir para reducir el tiempo de vericacin mediante la multiplicacin simultnea de puntos. No obstante, ambos presentan ciertas discrepancias en sus diseos, que les hace ser un tanto diferentes. Concretamente, WMECC usa una mezcla de representaciones Jacobianas (X, Y, Z, aZ 4 ) y coordenadas anes (X, Y ), aplica un valor de ventana pequeo, tanto para el mtodo de ventana deslizante s = 4, como para el mtodo de Shamir w = 1, con el n de evitar la precomputacin. En cambio, TinyECC utiliza representaciones Jacobianas (X, Y, Z ), ejecuta la fase de precomputacin para inicializar el sistema ECDSA, y utiliza un mtodo denominado mltiplicacin hbrida para gestionar mltiples tamaos de claves. El cuadro 1 y 2 muestran los resultados obtenidos por un experimento realizado con 20 iteraciones sobre

Cuadro 1: Sobrecarga en TinyECC y WMECC TinyWMECC Micaz Telosb 29734 25774 1643 1599 1.809s 1.744s 0s 0s 1.261s 1.425s 1.348s 1.498s 2.019s 2.209s

ROM RAM Inic. ECC Inic. ECDSA Gen. Clave Pub. Firma Digital Vericacin

Cuadro 2: Sobrecarga en TinyWMECC los nodos Micaz y Telosb. Tales resultados representan la sobrecarga (espacio y tiempo) generada por la implementacin secp160r1 correspondiente a TinyECC y a WMECC. Dicha implementacin est basada en el dominio de curvas elpticas siguiendo las recomendaciones del Grupo de Criptografa Eciente para Estndares (SECG) [32]. Las dos primeras las en ambos cuadros representan el espacio ocupado en la ROM y RAM del sistema por las primitivas y el test de programa, y el resto de las representan el tiempo invertido en la ejecucin de stas. Observando, el cuadro 1 se puede analizar, por un lado, que el Telosb es algo ms ineciente que el Micaz, y por otro lado, que el paquete WMECC es mejor en rendimiento que el TinyECC, ya que no existe un proceso de inicializacin de ECDSA, y el tiempo de generacin de rma digital y su correspondiente vericacin es rpida. Sin embargo, como WMECC utiliza una funcin SHA-1 no optimizada y compleja, reduce el espacio libre de memoria de instrucciones del Telosb, impidiendo la ejecucin de otras aplicaciones. En cambio, TinyECC se caracteriza por una funcin SHA-1 optimizada. Por estas razones, el cuadro 2 muestra la sobrecarga (espacio y tiempo) generada por la implementacin TinyWMECC, la cual se puede considerar como un hbrido de las optimizaciones de ambas implementaciones. Esta nueva versin ha sido posible por las caractersticas inherentes del lenguaje orientado a componentes, que ha permitido extraer una componente de

TinyECC para aadirla en el cdigo de WMECC. Adems, gracias a la sugerencia realizada por los autores de este artculo, el paquete WMECC ha sido actualizado para contemplar la nueva versin, TinyWMECC.

Referencias
[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci (2002). Wireless sensor networks: a survey. Computer Networks: The International Journal of Computer and Telecommunications Networking, vol. 38, no. 4, pp. 393-422, March 2002. [2] Moteiv Corporation. http://www.moteiv.com [3] Crossbow Technology, Inc. Wireless Measurement Systems. http://www.xbow.com [4] B. Schneier. Applied Cryptography, 2nd edition. Wiley, ISBN 0-471-12845-7, 1996. [5] S. Fluhrer, I. Mantin, A. Shamir. Weaknesses in the Key Scheduling Algorithm of RC4. In proceedings of the 8th Annual Workshop on Selected Areas in Cryptography (SAC 2001), Toronto (Canada), August 2001. [6] NIST-CSRC. SKIPJACK and KEA Algorithm Specications, version 2. 29 May 1998, http://csrc.nist.gov/CryptoToolkit/ [7] R. L. Rivest. The RC5 Encryption Algorithm. Proceedings of the 2nd International Workshop on Fast Software Encryption (FSE 1994), Leuven (Belgium), December 1994. [8] R. L. Rivest, M. J. B. Robshaw, R. Sidney, Y. L. Yin. The RC6 Block Cipher, v1.1. August 1998, http://theory.lcs.mit.edu/ rivest/ [9] J. Daemen, V. Rijmen. The Design of Rijndael. Springer, ISBN 3-540-42580-2, 2002. [10] B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, N. Ferguson. The Twosh Encryption Algorithm: A 128-Bit Block Cipher. Wiley, ISBN 0-47135381-7, 1999. [11] D. Eastlake, P. Jones. US Secure Hash Algorithm 1 (SHA1). RFC 3174. [12] H. Dobbertin, A. Bosselaers, B. Preneel. RIPEMD-160, a strengthened version of RIPEMD. Proceedings of the 3rd International Workshop on Fast Software Encryption (FSE 1996), Cambridge (UK), February 1996. [13] R. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, vol. 21, no. 2, pp. 120126, 1978.

6.

Conclusiones

A pesar de las altas limitaciones presentes en los nodos sensores, y las vulnerabilidades que poseen estos tipos de redes, existe una forma de proteger la comunicacin y el medio, mediante primitivas criptogrcas. Sin embargo, el uso de una primitiva en un nodo sensor est determinado por varios parmetros, como por ejemplo, la sobrecarga espacial y temporal que puede producir sta. Por ello, se ha realizado un anlisis de las caractersticas de cada una de las primitivas, identicando cules son las ms adecuadas para un nodo sensor. Por otro lado, usar PKC en redes de sensores se puede considerar un hecho y no un mero concepto terico, debido a que la ECC aporta mejor rendimiento en cmputo y almacenamiento de claves que otros criptosistemas como el RSA. Adems, trabajar en el dominio de curvas elpticas, y concretamente, usando ECDSA proporciona a la red operaciones relacionadas con rmas digitales, y esto a su vez, permite la posibilidad de dotar al sistema de servicios correspondientes a Infraestructuras de Clave Pblica [33]. Sin embargo, no todas las primitivas PKC se reducen a ECC, sino que dependiendo del tipo de arquitectura del nodo y del rol que desempea en la red, pueden usarse otros tipos de criptosistemas. Un ejemplo, sera el MQ-esquema, en el caso de que el nodo tuviera suciente recursos de memoria, como una estacin base. Por ltimo, se ha realizado un experimento sobre los nodos Micaz y Telosb, para probar dos implementaciones basadas en el dominio de curvas elpticas (TinyECC y WMECC), y bajo el Sistema Operativo orientado a eventos, TinyOS. Se ha observado en funcin de los resultados, que WMECC es mejor en rendimiento que TinyECC, pero su funcin hash es bastante compleja. Por estas razones, se han fusionado las optimizaciones de ambas implementaciones, para obtener una nueva versin optimizada.

7.

Agradecimientos

Este trabajo forma parte de las investigaciones realizadas en el proyecto Europeo SMEPP (FP6 IST5-033563) y el proyecto Espaol CRISIS (TIN200609242).

[14] I. Blake, G. Seroussi, N. P. Smart. Elliptic Curves in Cryptography. Cambridge University Press, ISBN 0-521-65374-6, 2000. [15] M. O. Rabin. Digitalized Signatures and Public Key Functions as Intractable as Factorization. Technical Report MIT/LCS/TR-212, Massachusetts Institute of Technology (1979). [16] J. Hostein, J. Pipher, J. H. Silverman. NTRU: a Ring based Public Key Cryptosystem. In proceedings of the 3rd Algorithmic Number Theory Symposium (ANTS 1998), Portland (USA), June 1998. [17] C. Wolf, B. Preneel. Taxonomy of Public Key Schemes Based on the Problem of Multivariate Quadratic Equations. Cryptology ePrint Archive, Report 2005/077. [18] N. Sastry, D. Wagner. Security considerations for IEEE 802.15.4 networks. In Proceedings of 2004 ACM Workshop on Wireless security (Wise 2004), Philadelphia (USA), October 2004. [19] J. Wolkerstorfer. Scaling ECC Hardware to a Minimum. In ECRYPT workshop - Cryptographic Advances in Secure Hardware - CRASH 2005. Leuven (Belgium), September 2005. Invited Talk. [20] S. Kumar, C. Paar. Are standards compliant elliptic curve cryptosystems feasible on RFID?. In Proceedings of Workshop on RFID Security, Graz (Austria), July 2006. [21] G. Gaubatz, J.-P. Kaps, E. ztrk, B. Sunar. State of the Art in Ultra-Low Power Public Key Cryptography for Wireless Sensor Networks. In Proceedings of the 2nd IEEE International Workshop on Pervasive Computing and Communication Security (PerSec 2005), Hawaii (USA), March 2005. [22] L. Batina, N. Mentens, K. Sakiyama, B. Preneel, I. Verbauwhede. Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks. In Proceedings of the 3rd European Workshop on Security and Privacy in Ad hoc and Sensor Networks (ESAS 2006), Hamburg (Germany), September 2006. [23] B.-Y. Yang, C.-M. Cheng, B.-R. Chen, J.-M. Chen. Implementing Minimized Multivariate PublicKey Cryptosystems on Low-Resource Embedded Systems. In Proceedings of the 3rd International Conference on Security in Pervasive Computing (SPC 2006), York (UK), April 2006. [24] P. Ganesan, R. Venugopalan, P. Peddabachagari, A. Dean, F. Mueller, M. Sichitiu. Analyzing and

Modeling Encryption Overhead for Sensor Network Nodes. In Proceedings of the 2nd ACM International Conference on Wireless Sensor Networks and Applications (WSNA 2003), San Diego (USA), September 2003. [25] C. Karlof, N. Sastry, D. Wagner. TinySec: a link layer security architecture for wireless sensor networks. Proceedings of 2nd International Conference on Embedded Networked Sensor Systems (SenSys 2004), Baltimore (USA), November 2004. [26] Y. W. Law, J. Doumen, P. Hartel. Survey and Benchmark of Block Ciphers for Wireless Sensor Networks. ACM Transactions on Sensor Networks, vol. 2, no. 1, pp 65-93, February 2006. [27] K. Jun Choi, J.-I. Song. Investigation of Feasible Cryptographic Algorithms for Wireless Sensor Network. Proceedings of the 8th International Conference on Advanced Communication Technology (ICACT 2006). Phoenix Park (Korea), February 2006. [28] N. Gura, A. Patel, A. Wander. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Proceedings of the 2004 Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), Cambridge (USA), August 2004. [29] D. J. Malan, M. Welsh, M. D. Smith. A Publickey Infrastructure for Key Distribution in TinyOS Based on Elliptic Curve Cryptography. In Proceedings of 1st IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON 2004), Santa Clara (USA), October 2004. [30] An Liu, Peng Ning, TinyECC: Elliptic Curve Cryptography for Sensor Networks (Version 0.3). http://discovery.csc.ncsu.edu/software/TinyECC/, September 2006. [31] H. Wang, Q. Li. Ecient Implementation of Public Key Cryptosystems on MICAz and TelosB Motes. Technical Report WM-CS-2006-07, College of William & Mary, October 2006. [32] SECG - Standards for Ecient Cryptography Group. http://www.secg.org/ [33] J. Lopez. Unleashing Public-Key Cryptography in Wireless Sensor Networks. Journal of Computer Security, vol 14, no. 5, pp 469-482, 2006.