TFM y herramienta: Estado de la criptografía post-cuántica y simulaciones de algoritmos post-cuánticos

Recientemente hemos vuelto a arrancar nuestra iniciativa anual de Retos de Ciberseguridad, Big Data e Inteligencia Artificial donde establecemos contacto directo con estudiantes que realizan su TFG o TFM con nosotros, aportándoles nuestra visión y acercándoles a las necesidades del mercado a través de una tutorización continua. En la edición anterior, además de JAWS, contamos con un estudiante que es bien conocido en nuestro blog, Álvaro Reyes, ganador de dos de nuestros retos. En esta ocasión ha realizado el TFM titulado «Estado de la criptografía post-cuántica y simulaciones de algoritmos post-cuánticos», un trabajo orientado a facilitar la comprensión y experimentar con algunos algoritmos post-cuánticos mediante un simulador útil para ejercicios y actividades académicas.

La criptografía lleva mucho tiempo ayudándonos a proteger nuestros secretos. Con cada algoritmo que se ha roto, han ido apareciendo nuevos para evitar que los secretos sean divulgados a aquellos que no deberían conocerlos. Con la aparición de los primeros computadores electrónicos la criptografía pasó a ser una herramienta de uso obligado para salvaguardar la información confidencial almacenada de forma electrónica y ahora que los computadores cuánticos ya son una realidad (aunque aún faltan años para su desarrollo en masa) representan un riesgo que está siendo abordado con bastante preocupación, ante las nuevas capacidades que proporciona a los atacantes. Podemos ver un poco las diferentes propuestas del uso de algoritmos cuánticos en criptografía en la siguiente figura:

Contexto
De los criptosistemas de clave pública que más se utilizan en la actualidad como RSA o ECDH basados en el problema de la factorización de enteros (dado un número N averiguar qué valores P y Q cumplen que P*Q=N) y el problema del logaritmo discreto (dados g y a, averiguar k para la ecuación g^k=a, siendo g un elemento de un grupo abeliano finito de orden n que cumple que 0≤k≤n-1), pasarán a un estado obsoleto en cuanto exista un computador cuántico con suficiente potencia como para romper sus claves utilizando el algoritmo de Shor. Este algoritmo reduce la complejidad de ambos problemas a un problema computacionalmente tratable y de rápida ejecución si es ejecutado en un computador cuántico, por lo que toda la tecnología que utilice criptosistemas cuyos algoritmos deriven de estos problemas corre el riesgo de ser catalogada como insegura de la misma forma que se ha hecho con otros algoritmos como MD5 y SHA-1. Los criptosistemas simétricos tampoco evitan verse afectados por los computadores cuánticos a causa del algoritmo de Grover, pero de momento la duplicación del tamaño de las claves es suficiente para no considerarlo un problema crítico. 

Ante el panorama que presentan estos algoritmos, se está llevando a cabo actualmente la estandarización por parte del NIST de un nuevo criptosistema que pueda resistir ataques cuánticos. La premisa de esas investigaciones conforma lo que se conoce como criptografía post-cuántica: el desarrollo de criptosistemas cuyos problemas matemáticos subyacentes no puedan ser resueltos por computadores normales o cuánticos en un tiempo polinomial. Entre los mecanismos que se utilizan para crear criptosistemas post-cuánticos están los retículos, las funciones polinómicas multivariable y los códigos correctores de errores entre otros.
Para aquellos a los que pueda interesarle el estado actual de la competición del NIST deben saber que se ha abierto recientemente la segunda ronda de participación, con lo cual ha habido cambios significativos en el número de criptosistemas que siguen participando y podemos ver el listado actual de propuestas.

McEliece y Niederreiter
En 1978, años antes de la aparición del algoritmo de Shor en 1994, Robert McEliece propuso un criptosistema basado en códigos correctores de errores. Este algoritmo hace uso de una matriz construida en base a tres matrices: una matriz S de ofuscación no singular e invertible (Scrambler matrix), una matriz G generadora de códigos lineales (Generator matrix) y una matriz P de permutación (Permutation matrix). La multiplicación de estas matrices (S*G*P) junto con el número de errores que pueden ser corregidos por el código lineal utilizado, dan como resultado la clave pública del criptosistema, mientras que las matrices por separado forman la clave privada.

No existe una forma no técnica para explicar que el cifrado de los mensajes se realiza multiplicando el mensaje por la clave pública y sumando un vector que contiene un número de errores menor o igual al parámetro que indique la clave pública. El descifrado pasa por revertir el proceso de la multiplicación del mensaje con la clave pública utilizando las matrices inversas de la clave privada. Sin embargo, el proceso no consiste simplemente en aplicar las inversas para obtener el mensaje, sino que hay que tener en cuenta el código elegido para el criptosistema. En el caso de códigos sencillos como Hamming, no requiere mucho esfuerzo crear una tabla de decodificación y utilizarla para corregir el error del mensaje, pero esto no es tratable a la larga y se debe utilizar un algoritmo de decodificación rápido. En el caso de Hamming se utiliza el algoritmo de decodificación del síndrome, con el cual no es necesario generar una tabla de decodificación y es computacionalmente eficiente. De igual forma tenemos el algoritmo de Patterson para los códigos Goppa binarios, para los cuales se ha demostrado que este criptosistema es resistente a ataques cuánticos inicializado con determinados parámetros, pero tiene la desventaja de que sus claves son muy grandes, no permitiendo un esquema de firma y la comunicación es unidireccional.

En 1986 Harald Niederreiter propuso una mejora del criptosistema de McEliece utilizando las matrices de verificación de paridad (parity-check matrix, comúnmente anotada como H) en lugar de las matrices generadoras, requiriendo una codificación previa para su funcionamiento, pero mejorando el algoritmo en tiempo y espacio además de permitir esquemas de firma.

¡Tenemos aplicación!
Como parte de la realización del TFM se ha desarrollado una aplicación con el objetivo de mostrar, paso a paso y de forma visual, cómo funcionan dichos criptosistemas para el cifrado con códigos Hamming (7,4) que son los más fáciles de interpretar e incluso calcular manualmente, y con códigos Goppa binarios irreducibles, que hasta el momento siguen siendo seguros. La aplicación está dividida en cinco secciones: las dos primeras muestran el funcionamiento de ambos criptosistemas utilizando códigos Hamming (7,4), el tercero muestra cómo se realizaría McEliece con códigos Goppa binarios utilizando para la decodificación el algoritmo de Patterson, el cuarto muestra la implementación de Niederreiter con los códigos Goppa, y el último es una interfaz de un toolkit criptográfico de Java que permita comparar los resultados finales de codificación frente a los pasos documentados y secuenciales de la aplicación.

En la imagen se muestra el proceso que se ha descrito antes para ejecutar McEliece. En el caso de Niederreiter, el proceso es similar pero no aparece la opción para añadir el vector de error. Para cifrar mensajes solo es necesario multiplicar el mensaje por la clave pública. Al recibir este mensaje el proceso de descifrado se realiza de forma similar al anterior.

En la imagen se muestra de nuevo la utilización de McEliece pero esta vez utilizando códigos Goppa. La parte de generación de clave pública y envío de mensaje se simplifica para mostrar el proceso automático del descifrado utilizando el algoritmo de Patterson. Solo hay que arrancar el proceso para ver cómo se va generando el descifrado del mensaje.

De la misma forma que con el algoritmo anterior, podemos utilizar Niederreiter pero utilizando los códigos Goppa. El proceso es idéntico al de Hamming, lo único que ha cambiado es el código lineal utilizado, pero el mecanismo es el mismo. Sin embargo, aquí en lugar de crear la tabla de decodificación, se utiliza el algoritmo de Patterson para averiguar rápidamente el error y corregirlo, en este caso el error se detecta en las posiciones para las cuales el polinomio corrector de error del algoritmo se evalúa a cero.

La última función del simulador utiliza la implementación original de FlexiProvider, que es un toolkit de módulos criptográficos para Java, para cifrar y poder visualizar, en hexadecimal, cómo difieren los algoritmos. De esta forma, podemos comparar y experimentar entre la implementación que hemos reproducido paso a paso con las diferentes formas en las que se puede utilizar un proveedor de seguridad externo, como es el caso de FlexiProvider.

Conclusión
Este TFM ofrece una herramienta, que, aun requiriendo cierto conocimiento del campo de la criptografía cuántica, permite experimentar con dos de los principales criptosistemas propuestos que existen en el mercado, el de McEliece y el de Niederreiter cada uno de ellos en dos de sus variantes, usando códigos Hamming (7,4) y Goppa. Con un carácter claramente académico, esta herramienta quiere servir de ayuda para entender cómo funcionan los algoritmos poder comparar las ventajas de uno y otro durante el proceso de aprendizaje. Con este software podemos explicar los fundamentos algebraicos de las distintas fases que definen estos algoritmos para entender por qué estos criptosistemas están preparados para resistir los riesgos de la computación cuántica y suponen, de momento, la base de la nueva era post-cuántica.

Este trabajo se encuentra publicado en el Repositorio O2 de la Universitat Oberta de Catalunya, al que se puede acceder mediante el siguiente enlace: http://hdl.handle.net/10609/89026.

Álvaro Reyes
En colaboración con Innovación y Laboratorio en ElevenPaths