Criptografía Post-Cuántica: tesis de maestría

Publicado por Diego Córdoba en

Un resumen muy escueto de lo que fue el desarrollo de mi Tesis de Maestría en Teleinformática sobre Criptografía Post-Cuántica! Aquí describo mi trabajo, y al final enlazo el documento de la tesis y los recursos adicionales.

Sí, luego de tantos años de esfuerzo y trabajo, logré terminar y presentar mi tesis de posgrado… podría decirse que soy «Magíster en Teleinformática» 😀

El tema elegido: Criptografía Post-Cuántica aplicada a entornos de Producción Open Source. Parece chino básico, pero en este post voy a intentar dar una introducción, y luego ampliaré detalles técnicos en un post dentro de la serie sobre Criptografía Aplicada que estoy escribiendo.

Seguramente en un futuro cercano publique un video (o varios :P) en el canal de youtube de JuncoTIC explicando el tema, y ampliando detalles.

¿Por qué elegí Criptografía Post-Cuántica?

Cuando terminé de cursar, allá por el 2016, quería hacer algo relacionado a la seguridad informática. Uno de los temas que más me apasionan en este aspecto es la criptografía aplicada, y la seguridad en los protocolos TCP/IP, así que me puse a investigar.

Uno de los tópicos más novedosos en aquella época (y que siguen siendo novedosos hoy), es la computación cuántica, y el nuevo paradigma de algoritmos que esto supone.

Entre las preocupaciones de seguridad al respecto me encontré algo que desconocía hasta ese momento: una computadora cuántica podría romper algoritmos criptográficos.

Toda la seguridad en comunicaciones sobre Internet se basa en criptografía simétrica y asimétrica, y enterarme que una computadora cuántica puede romper esa criptografía subyacente me hizo plantearme la pregunta: ¿cómo podemos protegernos?

Aquí el inicio de mi búsqueda: usando algoritmos criptográficos que sean resistentes a ataques realizados desde computadoras cuánticas: criptografía post-cuántica.

Ahora bien, sí, existen algoritmos resistentes al criptoanálisis cuántico, pero esos algoritmos necesitan implementaciones de software para funcionar, y esas implementaciones, ¿podrían adaptarse a SSL/TLS?

Y he aquí el tema de mi tesis. Estuve buscando implementaciones de código, e integraciones con OpenSSL (mi intención siempre fue trabajar con código abierto y software libre). Encontré varias, seleccioné algunas, y analicé el estado del arte de su integración con TLS y algunos protocolos de capa de aplicación.

Como objetivos específicos me centré en las siguientes implementaciones e integraciones:

  • Realizar un análisis minucioso de las implementaciones de SSL/TLS post cuánticas que se encuentran en un estado de desarrollo más avanzado y activo, a saber, OQS-OpenSSL y wolfSSL, con la intención de determinar su nivel de estabilidad, bugs y vulnerabilidades, respecto de la última release de OpenSSL.
  • Montar las pruebas de concepto de servicio HTTPS con cifrado post-cuántico utilizando Apache y/o Nginx integrado con las implementaciones OpenSSL antes mencionadas.
  • Montar prueba de concepto de servicio de VPN en capa 7 basado en OpenVPN con cifrado post-cuántico mediante la combinación con las suites OQS-OpenSSL antes mencionadas.

Complejidad computacional

Muchos de los algoritmos modernos hacen uso de complejidad computacional para garantizar su seguridad. Esto es, se fundamentan en operaciones matemáticas muy simples de calcular, pero extremadamente difíciles de revertir.

Imaginemos un producto de dos números primos grandes, se trata de una operación relativamente simple para cualquier procesador tradicional. Ahora, la factorización del resultado para hallar los dos números que fueron multiplicados es extremadamente difícil de calcular, incluso para una supercomputadora.

Los algoritmos de factorización actuales se ejecutan en un tiempo exp(n), donde n es la cantidad de bits del número. Es decir, el crecimiento de tiempo es exponencial respecto del tamaño del número.

El mejor algoritmo conocido para factorizar es GNFS (General Number Field Sieve), y se ejecuta en tiempo sub-exponencial. Esto significa que es más eficiente que los demás, pero no llega a una eficiencia de tiempo polinómico, lo que permitiría a un procesador tradicional su ejecución en un intervalo de tiempo acotado.

Así, algoritmos como RSA, DSA o ECDSA se basan en complejidad, tareas de factorización o de cálculo de logaritmos discretos.

Se dice que, en computación clásica, para aumentar la velocidad de ejecución de un algoritmo deben:

  • Acelerarse la ejecución de tareas simples.
  • Reducir la cantidad de tareas simples requeridas por el algoritmo.
  • Utilizar paralelismo.

A esto se lo denomina Tesis de Church-Turing Extendida, y los algoritmos tradicionales la respetan, lo que marca una limitación de procesamiento.

La amenaza de la computación cuántica

IBM-Q (2018)

La computación cuántica, por sus características intrínsecas de funcionamiento, puede ejecutar algoritmos cuánticos, que no pueden correrse en computadoras tradicionales.

Entre estos algoritmos se encuentra el Algoritmo de Shor. Se trata de un algoritmo cuántico no trivial de factorización que puede ejecutarse en tiempo polinómico n^3.

Este algoritmo viola la tesis de Church-Turing Extendida, por lo que puede resolver problemas de factorización en un tiempo menor al que requieren los algoritmos tradicionales.

Este algoritmo podría servir para romper cifrados seguros hoy en día, como RSA o DSA/ECDSA, y mecanismos de intercambio de claves como Diffie-Hellman y su variante de curva elíptica (ECDH).

¿Toda la criptografía está perdida?

No, de los algoritmos actuales únicamente son vulnerables al criptoanálisis cuántico los algoritmos asimétricos más comunes (RSA o DSA) y mecanismos de intercambio de claves basados en Diffie-Hellman, ya que también se basan en factorización.

Algoritmos simétricos como Rijndael (conocido como AES) se consideran seguros, ya que incrementar el tamaño de la clave hace que sea difícil de romper, incluso para una computadora cuántica.

Algoritmos de hash con seguridad igual o superior a SHA-256 también se consideran seguros.

El problema igual es que los algoritmos vulnerables se usan casi en cualquier mecanismo de seguridad actual, por lo que deberían hallarse reemplazos.

Criptografía Cuántica

No voy a extenderme mucho en este tópico ya que sería necesario incursionar en conceptos de comunicaciones cuánticas y propiedades de física cuántica.

No obstante, durante el año 2021 realicé un curso de Computación cuántica e Información cuántica, dictado por la Sociedad Argentina de Informática, SADIO, y como trabajo final escribí un ensayo sobre este tema. Pueden descargarlo desde este enlace.

Para resumirlo: lo que se conoce como criptografía cuántica es un mecanismo de distribución de claves, y se lo denomina Distribución de claves cuánticas (QKD – Quantum Key Distribution) o Intercambio de claves cuánticas (QKE – Quantum Key Exchange).

Este mecanismo sirve para realizar el intercambio de la clave, y lo lleva a cabo sobre un medio cuántico, como una fibra óptica o el aire, utilizando hardware especializado.

No se trata de un mecanismo de encriptación propiamente dicho, por lo que no serviría para reemplazar algoritmos vulnerables, sino para complementar la criptografía tradicional.

El problema que tiene es, precisamente, el uso de hardware especializado, por lo que no puede utilizarse sobre una infraestructura tecnológica tradicional.

Criptografía Post-Cuántica

Bajo este título se encuentran una serie de algoritmos criptográficos que no se basan en complejidad computacional, por lo que (se cree) son resistentes a ataques realizados desde computadoras cuánticas.

La ventaja sobre el QKD es que estos algoritmos pueden ejecutarse en computadoras tradicionales.

Estos algoritmos se basan en otras técnicas matemáticas y de codificación que se supone son invulnerables al criptoanálisis cuántico.

En mi tesis doy más detalles de cada una de estas categorías, así que solamente voy a mencionarlas aquí, y a nombrar algunos de los algoritmos candidatos en cada una.

  • Criptografía basada en Hash:
    Como muchas funciones Hash se consideran seguras, existen mecanismos criptográficos basados en ellas, que también se consideran seguros ante el criptoanálisis cuántico.
    Algoritmos representativos: Firmas Merkle.
  • Criptografía basada en Código:
    Existen mecanismos de codificación de datos cuya tarea inversa, la decodificación, es sumamente difícil de realizar, incluso para computadoras cuánticas.
    Algoritmos representativos: McEliece, Cake.
  • Criptografía basada en retículos (Lattice):
    Entre los problemas de retículo más conocidos se encuentran encontrar el vector más corto en una grilla. Estos problemas son difíciles de resolver, tanto para computación clásica como para computación cuántica, y esto da lugar al desarrollo de algoritmos criptográficos resistentes.
    Algoritmos representativos: NTRU, RLWE (NewHope, Frodo), Dilithium, Kyber, QTesla.
  • Criptografía basada en ecuaciones cuadráticas muiltivariable:
    Los problemas basados en este tipo de ecuaciones son NP-Completos, lo que los hace candidatos resistentes a algoritmos cuánticos como Shor o Grover.
    Algoritmos representativos: HFE, Rainbow.
  • Criptografía basada en Isogenias supersingulares:
    Los gráficos de isogenia supersingular son gráficas de expansión provenientes de la teoría de números computacionales, y se aplican mucho en criptografía de curva elíptica. Se considera que los algoritmos basados en isogenia supersingular son post-cuánticos.
    Algoritmos representativos: SIDH, SIKE.
  • Criptografía de clave secreta:
    Como mencioné antes, los algoritmos simétricos actuales se consideran seguros ante el criptoanálisis cuántico.
    Algoritmos representativos: AES.

El NIST y la estandarización de la criptografía post-cuántica

El NIST es la entidad que está llevando a cabo el proceso de estandarización de nuevos algoritmos. Realiza rondas de propuestas de nuevos algoritmos, los investigadores y criptógrafos evalúan las propuestas, y los candidatos pasan a la siguiente ronda.

Se han realizado 4 rondas hasta el momento:

  • Primera ronda: 2017
  • Segunda ronda: 2019
  • Tercera ronda: 2020
  • Cuarta ronda: 2022 (presente)

Los algoritmos se clasifican en 5 niveles de seguridad, a saber:

  • L1: inseguros a largo plazo. Se consideran algoritmos seguros hoy, pero no cuando las computadoras cuánticas sean escalables con un control de ruido eficiente.
  • L2 y L3: previsiblemente seguros. Algoritmos en estos niveles se consideran seguros si se mantiene el ritmo de desarrollo de la computación cuántica actual.
  • L4 y L5: se consideran seguros ante el criptoanálisis realizado desde cualquier computadora cuántica futura, aunque su implementación resulta más difícil de realizar.

En general las propuestas se presentan para los niveles L1, L3 y L5.

Ya se han publicado los primeros algoritmos candidatos para estandarización. Puede seguirse el proceso de estandarización en el sitio del NIST.

Implementaciones de software

Estuve analizando varias implementaciones de código, algunas de las cuales ya quedaron obsoletas (ver conclusiones). El objetivo de la tesis era analizar librerías criptográficas que incorporaran algoritmos post-cuánticos, su integración en dos suites de TLS: OpenSSL y wolfSSL, y la integración de estas con servicios de capa 7 que requirieran seguridad, particularmente HTTPS y OpenVPN.

Proyecto Open Quantum Safe (OQS)

open quantum safe oqs criptografía post-cuántica

En primer lugar analicé la biblioteca liboqs, provista por el Proyecto OQS. Esta biblioteca de código está escrita en C, y provee implementaciones de gran cantidad de algoritmos post-cuánticos.

El Proyecto OQS también realizó una integración de liboqs con OpenSSL llamada OQS-OpenSSL. Lo hicieron con la v1.0.2 y la v1.1.1 de OpenSSL. En mi tesis analicé un poco de ambas, pero hoy en día la v1.0.2 se encuentra discontinuada.

La v1.1.1 incorpora algoritmos post-cuánticos de intercambio y de encapsulamiento de claves dentro de TLS v1.3, por lo que lo aconsejable sería partir desde esta versión.

En la tesis también analicé la integración de OQS-OpenSSL con un par de implementaciones de HTTP: Apache y NGINX.

Para OQS-OpenSSL en ambas versiones también analicé la VPN PQCrypto-VPN. Esta VPN fue un proyecto de código abierto creado por Microsoft, en el que combinaba OQS-OpenSSL con OpenVPN para lograr una VPN de capa 7 con criptografía post-cuántica integrada en TLS. El proyecto quedó discontinuado luego de su publicación.

wolfSSL y Criptografía post-cuántica

Otra de las implementaciones que analicé fue wolfSSL, una suite TLS ligera pensada para dispositivos embebidos e IoT.

Si bien esta implementación no incorporaba criptografía post-cuántica de manera nativa, sí permitía su integración con libntru, una biblioteca de código que implementa el algoritmo de retículo NTRU mediante las primitivas NTRUEncrypt y NTRUSign.

Realicé la integración de NTRU con wolfSSL, y la posterior incorporación de Apache. Aquí tuve que jugar con el código de Apache para adaptarlo a wolfSSL, ya que de manera predeterminada está pensado para OpenSSL.

Esta integración la realicé sobre la versión 4.3.0 de wolfSSL, y un par de meses después quedó obsoleta porque para la v5.0.0 decidieron discontinuar el soporte NTRU e incorporar a liboqs, lo cual me pareció un paso lógico.

Conclusiones: Mi tesis!

Como habrán visto, muchas de las cosas que investigué se van quedando obsoletas. Esto fue uno de los problemas que tuve con el desarrollo: los repositorios de código se actualizan todo el tiempo, cada semana encontraba cambios y nuevas versiones.

Sin ir más lejos, presenté la integración de wolfSSL+NTRU+Apache en la Ekoparty 2021, en octubre, y para noviembre había quedado obsoleto :P.

Igual el video está bueno, así que pasen y vean en el canal de youtube de la Eko:

Otro dato, cuando el NIST liberó los primeros estándares, uno de los algoritmos candidatos, SIKE, fue vulnerado utilizando una computadora de un sólo núcleo fabricada en el 2013… de más está decir que los proyectos son altamente experimentales.

Ya llegando al final, les comparto mi tesis de maestría! Está escrita en LaTeX, y tanto los fuentes como los recursos adicionales los he subido a un repositorio GIT, pueden acceder vía:

https://gitlab.com/d1cor/mti_thesis

El PDF está enlazado dentro, pero si quieren solamente eso, puede bajarlo desde acá.

Si bien la tesis quedó congelada ahí, mi intención es transformar esa documentación en un apunte/libro sobre Criptografía aplicada y seguridad informática, incorporando el capítulo sobre QKD que eliminé de la versión final de la tesis.

La idea es mantener actualizada la información, incorporar nuevos experimentos, y contribuir con la comunidad.

Las novedades sobre esto quedarán enlazadas en este artículo, así que agregalo a bookmarks 🙂


Y hemos llegado al final! Quedó largo, pero resumiendo una tesis de caso 200 páginas. Si llegaste leyendo hasta acá: MUCHAS GRACIAS!

Como siempre, cualquier duda o consulta que tengas espero tu comentario!


¿Preguntas? ¿Comentarios?

Si tenés dudas, o querés dejarnos tus comentarios y consultas, sumate al grupo de Telegram de la comunidad JuncoTIC!
¡Te esperamos!


Diego Córdoba

- Ingeniero en Informática - Mg. Teleinformática - Tesis pendiente - Docente universitario - Investigador