Criptografía Post-cuántica en Sistemas con Recursos Limitados

Las soluciones de tipo “Internet de las cosas” (IoT) cada vez son más comunes tanto en empresas como hogares. Dichas soluciones frecuentemente manejan información sensible, por lo que es deseable que manejen un canal de comunicación cifrado. Sin embargo, así como la tecnología tiende al cambio, la seguridad de la información también está presentando cambios, y el cómputo cuántico presenta una amenaza significativa. Dada su naturaleza, una computadora cuántica puede realizar millones de operaciones en paralelo y fácilmente descifrar información protegida con criptografía tradicional.

Una solución ante este problema es el uso de algoritmos post-cuánticos, capaces de soportar ataques de ordenadores cuánticos. El uso de este tipo de algoritmos ya es relativamente común en el cómputo empresarial y móvil. Sin embargo, las soluciones IoT típicamente utilizan dispositivos con recursos limitados, que no necesariamente cuentan con la capacidad necesaria para ejecutar estas cargas de trabajo.

Ante esto, los autores han realizado una investigación para estudiar la viabilidad y desempeño de algoritmos de criptografía post-cuántica dentro de sistemas con recursos limitados. En este artículo se presenta la evaluación del desempeño de un algoritmo que preserva el servicio de integridad dentro de sistemas con procesadores ARM.

Un poco de historia

Históricamente hablando, la criptografía puede clasificarse en 4 etapas: clásica, moderna, cuántica y post-cuántica. El primer uso reconocido de la criptografía data de hace cerca de 4 mil años, en unos jeroglíficos no estándar encontrados en una tumba egipcia. La criptografía clásica, de una u otra manera continuó usándose conforme la civilización humana continuó su evolución.

La segunda guerra mundial marca un hito importante para la criptografía. Ante la necesidad de proteger los mensajes enviados a las tropas, aviones y submarinos a distancia, se realizaron grandes avances tanto en la construcción de máquinas criptográficas (ej. Enigma) como en el análisis para ingeniería inversa y construcción de máquinas capaces de descifrar dichos mensajes.

La siguiente gran revolución aparece a finales de los años 60 con el desarrollo de la criptografía asimétrica donde se utiliza una llave conocida por el público para cifrar los mensajes y otra llave privada para descifrarlos.

En los años 70’s se tienen las primeras ideas relacionadas con la criptografía cuántica, destacando los algoritmos de Shor y Grover. Sin embargo, fue hasta los 80’s cuando se muestran las primeras publicaciones de nuevos protocolos que basaban su seguridad en los principios de la mecánica cuántica —como el de incertidumbre o el de superposición— utilizando láseres para emitir información en un fotón.

Cuando los algoritmos de la criptografía de llave pública empiezan a verse comprometidos por el cómputo cuántico, surge la criptografía post-cuántica, que hace referencia a los algoritmos diseñados para resistir ataques de computadoras cuánticas. En ella se aprecian varias ramas que se diferencían por la forma en cómo operan, siendo estas: algoritmos basados en rejillas, algoritmos basados en ecuaciones multivariables, algoritmos basados en curvas elípticas isogeneas supersingulares, algoritmos basados en hashes, y algoritmos basados en códigos.

Desde el punto de vista del uso y desempeño de este tipo de algoritmos, se ha explorado su ejecución en sistemas de propósito específico en entornos controlados, como lo son: los FPGA, AVR y ASIC, por mencionar algunos, dejando pendiente un análisis del comportamiento y desempeño en sistemas de recurso limitado, de gama media y baja, como lo son: Raspberry Pi, Beaglebone o Banana Pro con arquitectura ARM. De ahí que los antecedentes relacionados con este trabajo exhiben trabajos con algoritmos post-cuánticos que podrían dividirse en: ejecuciones en dispositivos FPGAs, en dispositivos de uso específico y trabajos de algoritmos post-cuánticos en la arquitectura ARM, los cuales radican en cifrado, firmas digitales y acuerdos de llave, dejando abierta la posibilidad de explorar la primitiva de hash, enfocada al servicio de integridad, así como su comportamiento en sistemas con recursos limitados.

Desempeño de un algoritmo post-cuántico para el servicio de integridad

La función hash SHA-3 es el último miembro de la familia de estándares Secure Hash Algorithm, cuyo propósito es sustituir las aplicaciones actuales de su predecesor SHA-2 en caso de ser necesario, puesto que esta mejora la solidez del algoritmo hash.

La familia de las funciones SHA-3 es capaz de enfrentar ataques realizados por computadoras cuánticas, destacando entre ellos: el uso del algoritmo de Grover, ataques de preimagen, de segunda preimagen y de resistencia a colisiones, así como el ataque de cumpleaños. Esto, dado que la seguridad proporcionada por el algoritmo SHA-3 ante ataques cuánticos recae en las grandes salidas de datos que este genera, puesto que está comprobado matemáticamente que es resistente a la colisión cuántica. Hablando en términos de bits, la seguridad que genera cada una de sus variantes, es del mismo tamaño de bits que la salida, en los ataques a preimagen y 2da preimagen, y a la mitad de los bits en ataques de resistencia a colisiones.

Desde el punto de vista de la codificación, a la fecha se han desarrollado códigos en distintos lenguajes para utilizar las fortalezas que presenta esta familia. De hecho, el proyecto de investigación "Open Quantum Safe", ha puesto al alcance de la comunidad una biblioteca de funciones con dos líneas de trabajo principales. La primera línea consiste en el desarrollo y mantenimiento de liboqs, una biblioteca de código abierto en C que implementa algoritmos criptográficos resistentes a ataques cuánticos. La segunda línea consiste en el prototipado de integraciones en protocolos y aplicaciones comunes, tales como la biblioteca OpenSSL.

Para la investigación descrita en este artículo, se adecuó liboqs para poder usarla en procesadores con arquitectura ARM. Se modificó un constructor para que pudiera hacer uso de la función SHA-3 y de todas las opciones que brinda la biblioteca. El programa diseñado tiene como propósito la obtención de las mediciones en los tiempos de procesamiento. Esto, considerando el tiempo que tardan tanto el embebido como la computadora personal para resolver las operaciones de las funciones hash de la familia de SHA-3.

Ejecución en sistemas con recursos limitados

Para las pruebas de desempeño, se ejecutó cada uno de los miembros de la familia SHA-3 con salidas de 224, 256, 384 y 512 bits. Esto, con la finalidad de obtener una comparativa de los tiempos de procesamiento que se tienen entre el sistema embebido Raspberry Pi 1 modelo B, con un procesador de un solo núcleo, 700 MHz de velocidad y 256 MB de memoria RAM y una arquitectura x64. Además, se observó el desempeño en las funciones de salida variable SHAKE128 y SHAKE256, con salidas de tamaño 512, 1024, 2048, 4096 y 8192 bits, respectivamente. Para finalizar, se comparó el desempeño que mostraba la función hash SHA-3 al ejecutarse en el sistema embebido y las funciones hash antecesoras, SHA-1 y SHA-2.

Sin embargo, el reto presentado al estudiar el desempeño del algoritmo SHA-3 se presentó al querer ejecutarlo en un dispositivo de poder limitado de cómputo, ya que el embebido en cuestión fue un sistema Raspberry Pi modelo B, lo que no impidió la ejecución del algoritmo aunque tardara tiempo considerable. Dicho tiempo de respuesta, mejoró con el uso de un sistema embebido con un poco más de poder de cómputo, pero de la misma familia. El embebido escogido posteriormente fue un Raspberry Pi 3 con un chipset Broadcom BCM2837, procesador ARMv8 de cuatro núcleos a 1.2GHz y 1GB de memoria RAM. Con estas nuevas características en el sistema embebido, se pudo ejecutar igual de rápido que en una computadora personal.

Es decir, el algoritmo post-cuántico de la familia SHA-3 se pudo ejecutar en dispositivos de recurso limitado con una velocidad de respuesta lenta, lo cual mejoró con el aumento en la capacidad del cómputo.

Resultados

Los resultados de la primera prueba se observan en la Tabla 1, en donde la entrada a la función SHA-3 es un archivo que contiene un millón de veces el mismo carácter, y dejan observar los tiempos de ejecución en milisegundos para el procesamiento de las funciones SHA-3 con salidas de longitud 224, 256, 384 y 512, lo cual se muestra en la Tabla 1. También, la Tabla 2 muestra los valores resultantes para las funciones de salida SHAKE. De igual forma el valor de entrada de la función es un archivo que contiene un millón de caracteres.

Tabla 1. Resultados con SHA-3

Tabla 2. Resultados con SHAKE

Para ambas Tablas la primera columna muestra las diferentes longitudes de salida del algoritmo de SHA-3 y SHAKE, respectivamente. La segunda columna expone los tiempos de ejecución, dentro de una PC, de cada una de las opciones de longitud de SHA-3. La tercera columna presenta los tiempos de ejecución, dentro del embebido Raspberry Pi de primera generación. Por último, la cuarta columna expone la relación que define cuántas veces es más lento el sistema embebido en comparación con un ordenador personal.

La Tabla 3 muestra la comparación, en tiempos de ejecución, entre las tres diferentes familias del algoritmo SHA dentro del embebido Raspberry Pi de primera generación. La primera columna muestra las diferentes longitudes de salida para las funciones SHA. La segunda columna muestra los resultados obtenidos de las familias SHA-1 y SHA-2 con cada una de las longitudes de salida. La tercera columna expone los tiempos de ejecución obtenidos de la familia de SHA-3 con las mismas longitudes de salida utilizadas para SHA-1 y SHA-2. Por último, la cuarta columna muestra la relación existente entre los tiempos de ejecución de SHA-1 y SHA-2 contra SHA-3, exponiendo el tiempo que tarda más la ejecución de la familia SHA-3 comparada con sus antecesores.

Tabla 3. Resultados de comparación.

De ahí, que los parámetros de salida de estas pruebas, permitieron determinar, por medio de un promedio de tiempos, qué tan posible o no es la ejecución de la familia de funciones SHA-3 dentro de sistemas embebidos con recursos limitados.

Conclusión

Los resultados obtenidos al ejecutar las funciones SHA-3 con salidas 224, 256, 384 y 512, dejan ver que el tiempo utilizado para ejecutar el proceso promedia entre uno y tres segundos, por lo que, a nivel computacional, es posible ejecutar una función hash post-cuántica dentro de un embebido de recursos limitados.

Los valores promedio obtenidos con los resultados dejan ver que sin importar la longitud de la salida obtenida, el dispositivo podrá tener en promedio, el mismo resultado.

Los valores obtenidos en la prueba tres, dejaron ver que una función post-cuántica puede ser ejecutada de manera exitosa dentro de los embebidos de bajos recursos computacionales, dado que al hacer la comparación con las familias previas SHA-1 y SHA-2, se puede observar que los tiempos de ejecución de la función SHA-3 no poseen un comportamiento tan distante de sus antecesoras, por lo que es posible utilizar e implementar aplicaciones que utilicen algoritmos post-cuánticos en vez de sus antecesoras.

Agradecimientos

Los autores agradecen al Instituto Politécnico Nacional dado que este trabajo fue financiado a través del proyecto SIP 20180505 y SIP 1917.

Referencias

[1] Mahmoud, Moustafa, et.al. (2017). A power resistant FPGA implementation of NTRUEncrypt.USA:IEEE.

[2] Basu Roy, Debapriya, et.al. (2018). Minimalistic perspective to public key implementations on FPGA. USA:IEEE.

[3] Dai, Wei, et.al. (2016). NTRU modular lattice signature scheme on Cuda CPUs. USA:IEEE.

[4] Chang, Yun-An, et.al. (2014). Post-Quantum SSL/TLS for emdedded systems. USA:IEEE.

[5] Jalali, Amir, et.al. (2017). Supersingular isogeny Diffie-Hellman key exchange on 64-bit ARM. USA:IEEE.

[6] Streit, Silvan, et.al. (2017). Post-Quantum key exchange on ARMv8: A New Hope for NEON made simple. USA:IEEE.

[7] Ghani, Aziz, et.al. (2013). Hash MD5 Function Implementation at 8-bit Microcontroller. Indonesia:IEEE.

[8] Kahri, Fatma, et al. (2013). An FPGA implementation of the SHA-3: The BLAKE Hash Function. Túnez:IEEE.

[9] Kahri, Fatma, et al. (2015). Efficient FPGA Hardware Implementation of Secure Hash Function SHA-256/Blake-256. Túnez:IEEE.

[10] F Dworkin, Morris J. "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions". Federal Inf. Process. Stds. (NIST