Criptografía Post-Cuántica con Python y Linux

Post-Quantum Cryptography with Python and Linux

Una guía para principiantes

Si creemos en Edward Snowden, el cifrado es “la única protección real contra la vigilancia” [1]. Sin embargo, los avances en tecnología cuántica podrían poner en peligro esta salvaguardia. Nuestro artículo analiza por qué la computación cuántica representa una amenaza para la seguridad de los datos y qué hacer al respecto. En lugar de un análisis puramente teórico, nos basamos en ejemplos de código utilizando Python, C y Linux.

Conceptos básicos de la cuántica

Cuando los científicos de Google informaron del primer caso de supremacía cuántica en 2019, causaron gran emoción. Una área donde la computación cuántica podría tener un impacto significativo es en el cifrado. Para entender este problema, necesitamos discutir algunos conceptos básicos.

A diferencia de las computadoras clásicas, los algoritmos para computadoras cuánticas no se basan en bits, sino en qubits. Un bit puede tener el estado 0 o 1. Cuando medimos un bit varias veces, invariablemente obtenemos el mismo resultado. Con los qubits, las cosas son diferentes. Por extraño que parezca, un qubit puede tener el valor 0 y 1 al mismo tiempo. Cuando lo medimos repetidamente, solo hay una cierta probabilidad de obtener el resultado 0 o 1. En el estado inicial de un qubit, la probabilidad de medir 0 es comúnmente del cien por ciento. Sin embargo, a través de la superposición, se pueden generar diferentes distribuciones de probabilidad. Las causas se encuentran en la mecánica cuántica, que sigue otras leyes que la vida “normal”.

La principal ventaja de las computadoras cuánticas es su naturaleza probabilística. Las computadoras clásicas son excelentes para problemas en los que necesitamos confiablemente un único resultado. Las máquinas cuánticas, por otro lado, son excelentes para lidiar con probabilidades y combinatorias. Cuando realizamos una operación en un qubit en un estado superpuesto, se aplica simultáneamente a ambos valores 0 y 1. A medida que aumenta el número de qubits, aumenta la ventaja sobre una computadora clásica. Una máquina cuántica con tres qubits puede procesar hasta ocho valores (2³) simultáneamente: es decir, los números binarios 000, 001, 010, 011, 100, 101, 110 y 111.

La literatura científica coincide en que las computadoras cuánticas ayudarán a resolver problemas que anteriormente parecían intratables. Sin embargo, no hay máquinas cuánticas óptimas disponibles. La generación actual de computadoras cuánticas se denomina cuántica de escala intermedia ruidosa (NISQ, por sus siglas en inglés). Estas máquinas tienen una potencia de procesamiento limitada y son sensibles a los errores. Los dispositivos modernos ofrecen hasta varios cientos de qubits. Un ejemplo es el chip Osprey de 433 qubits que IBM presentó en 2022. Ahora, la empresa planea desarrollar una máquina con 100,000 qubits para 2033.

• Investigadores de DeepMind presentan AlphaStar Unplugged Un avance ...
• Fuerza en números NVIDIA y el Desafío del Equipo Rojo Generativo li...
• Reto aceptado GeForce NOW enciende la nube con el desafío supremo y...

Nuestro artículo explica por qué esta evolución representa una amenaza para la seguridad de los datos. Utilizando ejemplos de código, mostramos por qué las computadoras cuánticas podrían romper ciertos métodos de cifrado y discutimos soluciones alternativas. El código fuente está disponible en GitHub. Fue desarrollado en Kali Linux 2023.2 utilizando Anaconda con Python 3.10.

Cifrado y factores primos

Cuando se cifra un mensaje, una forma relativamente sencilla es aplicar un algoritmo simétrico. Este método utiliza la misma clave tanto para el cifrado del texto plano como para el descifrado del texto cifrado. Un desafío importante con este enfoque es el intercambio seguro de la clave entre el remitente y el destinatario. Una vez que la clave privada se conoce por parte de un tercero, tienen la oportunidad de interceptar y descifrar el mensaje.

La criptografía asimétrica parecía ser la solución a este problema. Métodos como RSA utilizan claves diferentes para el cifrado y el descifrado. Aquí, el cifrado se realiza con una o más claves públicas que el destinatario pone a disposición de todos. Para el descifrado, el destinatario utiliza una clave privada, que solo ellos conocen. De esta manera, el remitente puede obtener la clave pública sin riesgo, ya que de todos modos no es secreta. Solo la clave privada del destinatario debe estar protegida. Pero ¿cómo se puede fortalecer este procedimiento cuando posibles atacantes conocen la clave pública? Para ello, los algoritmos asimétricos se basan en problemas matemáticos como la factorización de números primos.

La factorización de números primos se comprende mejor con un ejemplo. En Python, podemos usar la función factorint de la biblioteca SymPy para determinar los factores primos de un cierto número entero.

>>> import sympy>>> sympy.factorint(10){2: 1, 5: 1}>>> 2**1 * 5**110>>> sympy.factorint(1000){2: 3, 5: 3}>>> 2**3 * 5**31000>>> sympy.factorint(55557){3: 2, 6173: 1}>>> 3**2 * 6173**155557>>>

La salida de consola anterior ilustra que todo número natural puede ser expresado como un producto de números primos. Estos se llaman factores primos. Recordando los días de escuela, un número primo es divisible solo por 1 y por sí mismo. Por ejemplo, el número 10 puede ser expresado como 10=2¹ * 5¹. Por lo tanto, los factores primos de 10 son 2 y 5. De manera análoga, el número 55557 puede ser expresado por la ecuación 55557=3² * 6173¹. Entonces, los factores primos de 55557 son 3 y 6173. El proceso de encontrar los factores primos de un número entero dado se llama factorización prima.

Con computadoras clásicas, la factorización prima es simple para números pequeños, pero se vuelve cada vez más difícil para enteros grandes. Cada número adicional aumenta drásticamente la cantidad de combinaciones posibles. Más allá de cierto punto, se vuelve virtualmente imposible para una computadora clásica determinar los factores primos. Por ejemplo, considera el siguiente número (RSA-260) del Desafío de Factorización RSA, finalizado en 2007. Al momento de escribir esto, aún no ha sido factorizado.

#!/usr/bin/env pythonimport sympyrsa_260 = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199print("Comenzando factorización...")factors = sympy.factorint(rsa_260)# Probablemente no se llegue a esta línea de códigoprint(factors)

Los algoritmos asimétricos como RSA utilizan la dificultad computacional de la factorización prima y problemas similares para asegurar la encriptación. Desafortunadamente, el mundo cuántico sigue sus propias leyes.

Algoritmos cuánticos

En cuanto a la criptografía, dos algoritmos cuánticos son de particular preocupación. El algoritmo de Shor proporciona una forma eficiente de factorización prima. Cuando se realiza en un gran dispositivo cuántico, teóricamente puede romper métodos asimétricos como RSA. Desde una perspectiva práctica, este escenario está en el futuro. Un artículo de Nature de 2023 menciona que se requieren al menos 1,000,000 de qubits. Además del hardware, también es difícil encontrar implementaciones del algoritmo que se escalen de manera confiable en máquinas cuánticas grandes. El marco de trabajo Qiskit de IBM intentó implementar una función, pero la degradó en la versión 0.22.0. Sin embargo, se pueden encontrar implementaciones experimentales del algoritmo de Shor en línea.

El algoritmo de Grover plantea una amenaza para la encriptación simétrica. También conocido como algoritmo de búsqueda cuántica, ofrece una aceleración para la búsqueda no estructurada de la entrada de una función dada. Las computadoras cuánticas pueden utilizarlo para acelerar ataques de fuerza bruta en información encriptada simétricamente. Sin embargo, a diferencia del algoritmo de Shor, la aceleración ofrecida no es exponencial. En términos simples, esto significa que aumentar la longitud de la clave utilizada para la encriptación hace que la búsqueda sea excesivamente más costosa. Por ejemplo, realizar un ataque de fuerza bruta en una clave de 128 bits requiere un máximo de 2¹²⁸ iteraciones. Suponiendo que la búsqueda de Grover reduce este número a 2⁶⁴, duplicar la longitud de la clave a 256 bits lo aumenta nuevamente a 2¹²⁸ iteraciones. Esto abre la puerta a posibles soluciones alternativas.

Solución alternativa simétrica

Bajo ciertas condiciones, la encriptación simétrica es una forma lista para usar y simple de contrarrestar los algoritmos cuánticos. La razón es que la búsqueda de Grover no se escala de manera exponencial y el algoritmo de Shor solo amenaza los enfoques asimétricos. Según el conocimiento actual, se considera que los algoritmos simétricos con un alto grado de dificultad son resistentes a los ataques cuánticos. En la actualidad, tanto el NIST estadounidense como el BSI alemán incluyen AES-256 en esta categoría [2][3]. El acrónimo AES significa Estándar de Encriptación Avanzada y el número 256 representa la longitud en bits de la clave. En Linux, AES-256 está implementado por GNU Privacy Guard (GnuPG). El siguiente script de shell muestra cómo se puede encriptar un archivo y luego desencriptarlo usando AES-256.

# Encriptargpg --output encrypted.gpg --symmetric --cipher-algo AES256 plain.txt# Desencriptargpg --output decrypted.txt --decrypt encrypted.gpg

El script anterior encripta el contenido del archivo “plain.txt”, escribe el texto cifrado en el documento “encrypted.gpg”, lo desencripta nuevamente y finalmente guarda la salida en el archivo “decrypted.txt”. Antes de la encriptación, GnuPG solicita una frase de contraseña para generar la clave privada. Por razones de seguridad, es vital elegir una frase de contraseña fuerte y mantenerla en secreto. GnuPG puede almacenar en caché la frase de contraseña y no volver a solicitarla al desencriptar. Para borrar la caché, se puede ejecutar el siguiente comando de shell.

gpg-connect-agent reloadagent /bye

Integrar GnuPG en Python es relativamente simple con el módulo subprocess. Una implementación prototipo de encriptación con AES-256 se muestra en el fragmento de código a continuación.

#!/usr/bin/env pythonimport subprocessimport getpass# Leer la contraseñacontraseña = getpass.getpass("Contraseña:")contraseña2 = getpass.getpass("Contraseña:")if contraseña != contraseña2:  raise ValueError("¡Las contraseñas no son idénticas!")# Realizar encriptaciónprint("Encriptando...")args = [  "gpg",  "--batch",  "--passphrase-fd", "0",  "--output", "encrypted.gpg",  "--symmetric",  "--yes",  "--cipher-algo", "AES256",  "plain.txt",]result = subprocess.run(  args, input=contraseña.encode(),  capture_output=True)if result.returncode != 0:  raise ValueError(result.stderr)

Para obtener una contraseña, el script anterior utiliza el módulo getpass. Después de la confirmación, la contraseña se transfiere a GnuPG a través de la entrada estándar. Esto se indica mediante el argumento passphrase-fd 0. Alternativamente, las contraseñas se pueden enviar a GnuPG como una cadena o mediante un archivo con argumentos de línea de comandos. Sin embargo, como estos argumentos son visibles para otros usuarios, ambas opciones fueron rechazadas para el prototipo. Otra manera más segura sería usar el GPG-Agent. Qué opción tomar depende del nivel de seguridad deseado. Se proporciona un ejemplo de concepto que incluye encriptación y desencriptación aquí. Como alternativa a GnuPG, existen otras implementaciones de AES-256. Elegir una fuente confiable es vital aquí.

Solución asimétrica

En busca de una solución asimétrica, el programa de Estandarización de Criptografía Post-Cuántica del NIST es un buen punto de partida. Desde 2016, ha evaluado múltiples candidatos para algoritmos resistentes a los ordenadores cuánticos. Uno de los ganadores es Kyber. El sistema implementa un mecanismo de encapsulación de clave seguro. Al igual que otros algoritmos, Kyber se basa en un problema difícil de resolver para proteger el intercambio de claves entre dos partes. En lugar de la factorización de números primos, se basa en un problema llamado “aprendizaje con errores”. El nivel de protección que ofrece Kyber depende de la longitud de la clave. Por ejemplo, Kyber-1024 apunta a un nivel de seguridad “aproximadamente equivalente a AES-256” [4].

Una implementación de referencia de Kyber, escrita en C, está disponible en GitHub. En Linux, podemos clonar y construir el marco ejecutando los comandos de shell que se muestran a continuación. Se requieren algunos requisitos previos para la instalación, que se documentan en el archivo README del proyecto.

git clone https://github.com/pq-crystals/kyber.gitcd kyber/ref && make

Hay varias formas de integrar la implementación de referencia en Python. Una de ellas es escribir un programa en C y llamarlo. La función en C a continuación utiliza Kyber para realizar un intercambio de claves entre dos partes ficticias, Alice y Bob. Para ver el código fuente completo, consulte aquí.

#include <stddef.h>#include <stdio.h>#include <string.h>#include "kem.h"#include "randombytes.h"void round_trip(void) {    uint8_t pk[CRYPTO_PUBLICKEYBYTES];    uint8_t sk[CRYPTO_SECRETKEYBYTES];    uint8_t ct[CRYPTO_CIPHERTEXTBYTES];    uint8_t key_a[CRYPTO_BYTES];    uint8_t key_b[CRYPTO_BYTES];    // Alice genera una clave pública    crypto_kem_keypair(pk, sk);    print_key("Clave pública de Alice", pk);    // Bob deriva una clave secreta y crea una respuesta    crypto_kem_enc(ct, key_b, pk);    print_key("Clave compartida de Bob", key_b);    print_key("Clave de respuesta de Bob", ct);    // Alice usa la respuesta de Bob para obtener su clave compartida    crypto_kem_dec(key_a, ct, sk);    print_key("Clave compartida de Alice", key_a);}

Sin entrar en detalles, se puede ver que Kyber utiliza múltiples claves públicas y privadas. En el ejemplo anterior, Alice genera una clave pública (pk) y una clave privada (sk). Luego, Bob usa la clave pública (pk) para derivar una clave compartida (key_b) y una clave de respuesta (ct). Esta última se devuelve a Alice. Finalmente, Alice usa la clave de respuesta (ct) y su clave privada (sk) para generar una instancia de la clave compartida (key_a). Mientras ambas partes mantengan sus claves privadas y compartidas en secreto, el algoritmo ofrece protección. Al ejecutar el programa, obtenemos una salida similar al texto siguiente.

Clave pública de Alice: F0476B9B5867DD226588..Clave compartida de Bob: ADC41F30B665B1487A51..Clave de respuesta de Bob: 9329C7951AF80028F42E..Clave compartida de Alice: ADC41F30B665B1487A51..

Para llamar a la función C en Python, podemos utilizar el módulo subprocess. Alternativamente, es posible construir una biblioteca compartida e invocarla con el módulo ctypes. La segunda opción se implementa en el siguiente script de Python. Después de cargar la biblioteca compartida, generada a partir del código C de Kyber, se llama al procedimiento round_trip como cualquier otra función de Python.

#!/usr/bin/env pythonimport osimport ctypes# Cargar biblioteca compartidalibname = f"{os.getcwd()}/execute_round_trip1024.so"clib = ctypes.CDLL(libname, mode=1)print("Biblioteca compartida cargada exitosamente:")print(clib)# Llamar a la función round_tripprint("Ejecutando round trip:")clib.round_trip()

Además de la implementación de referencia de Kyber, otros proveedores han implementado el algoritmo. Ejemplos son los proyectos de código abierto Botan y Open Quantum Safe.

Conclusión

Como revela nuestro análisis, la tecnología cuántica aún está en sus etapas iniciales. Pero no debemos subestimar la amenaza que representa para la encriptación y otros métodos criptográficos como las firmas. La innovación disruptiva puede impulsar el desarrollo en cualquier momento. Los atacantes pueden almacenar mensajes ahora y descifrarlos más tarde. Por lo tanto, se deben tomar medidas de seguridad de inmediato. Especialmente porque hay soluciones disponibles. Cuando se utilizan correctamente, los algoritmos simétricos como AES-256 se consideran resistentes a la cuántica. Además, las soluciones asimétricas como Kyber están progresando. Qué alternativas utilizar depende de la aplicación. Siguiendo un modelo de Confianza Cero, una combinación de enfoques brinda la mejor protección. De esta manera, la amenaza cuántica podría terminar como el problema del Y2K, como una profecía autodestructiva.

Sobre los autores

Christian Koch es un Arquitecto Empresarial en BWI GmbH y Profesor en el Instituto de Tecnología Georg Simon Ohm de Nuremberg.

Lucie Kogelheide es la Líder Tecnológica en Criptografía Post-Cuántica en BWI GmbH y es responsable de iniciar el proceso de migración de la compañía a la criptografía segura cuántica.

Raphael Lorenz es el Fundador y CISO de Lorenz Systems y se especializa en soluciones de seguridad holísticas.

Referencias

1. Snowden, Edward: Permanent Record. Macmillan, 2019.
2. Instituto Nacional de Estándares y Tecnología: Criptografía Post-Cuántica del NIST: Preguntas frecuentes. 29 de junio de 2023. Accedido el 02 de agosto de 2023.
3. Oficina Federal de Seguridad de la Información (BSI): Criptografía segura cuántica: fundamentos, desarrollos actuales y recomendaciones (PDF). Octubre de 2021. Accedido el 02 de agosto de 2023.
4. CRYSTALS – Suite Criptográfica para Redes Algebraicas: Kyber Home. Diciembre de 2020. Accedido el 02 de agosto de 2023.

Descargo de responsabilidad

Tenga en cuenta que la seguridad de la información es un tema crítico y que los autores no ofrecen ninguna garantía sobre el contenido publicado.

• Cybersecurity
• Encryption
• Linux
• Python
• Quantum computing