Como decíamos ayer...
Fases de establecimiento de una sesión TLS (https). Cifrado híbrido :
Autenticación de servidor mediante intercambio de certificados (criptografía asimétrica, RSA/ECDSA)Acuerdo de los parámetros de seguridadEstablecimiento de clave compartida mediante criptografía asimétrica. Opciones: Diffie-Hellman o Encapsulación de clave (RSA, DSA)Cifrado simétrico de la comunicación AES/ChaCha con la clave anterior
La criptografía asimétrica es fundamental para establecer una conexión segura
La seguridad de la Criptografía asimétrica se basa en que no conocemos algoritmos rápidos para resolver problemas matemáticos como la factorización de números primos:
El algoritmo conocido para los computadores actuales es GNFS :
Factorizar este número con un computador actual lleva miles de años...
149802948092842184098210482184208402814092814092814902882314802
840182098201895139476316917369371469130591039583109734876139819
538591385031850135124214213434125103691373140750917604137601347
603176031760317603176136913701364316013860319760193760931707097
017436013760317460316703176031786136498314691376931763176931876
981376938176931876931769137693187613768713867136873187513769316
013463160316039187683714681397689713489671390486791837609138769
013876089317693187690137691374603918768931769137631769137691301
346871306871384761937693814708173468713689317693176814758134761
376134786139671396731467318967348769831476837639176913476931763
196731769317691384768931476831746083174687138671397613476317613
769347476138976831769831746983176731976913876091376891376981376
913476983174691347683476193769134769314769137693147691347691347
691387683147693147683148761364706946013746013681141213083928139
Pero... ¿y si existiesen otro tipo de computadoras que lo factorizasen en horas?
Computación Cuántica
Una introducción a vista de pájaro
Computación cuántica
La computación cuántica utiliza principios de la mecánica cuántica para realizar cálculos
Richard Feynman sugirió (~1980) que se podrían aprovechar comportamientos cuánticos para realizar cálculos de manera más eficiente que las computadoras clásicasHa sido un estudio solo teórico durante 50 años, pero ahora empezamos a poder construirlas
¿Qué es y cómo funciona la COMPUTACIÓN CUÁNTICA?
Q-bit
La unidad de la computación cuántica es el Q-bit, que puede existi en múltiples estados simultáneamente. 0 y 1 a la vez: superposición
Pueden empaquetar más información:
Intuitivamente: podemos aprovechar la superposición para probar muchas soluciones a la vez con un solo q-bit: trabajo en paralelo
Computación Cuántica: la Guía completa WIRED
Comparación con la computación tradicional
La computación cuántica permite resolver problemas complejos con una rapidez que no sabemos alcanzar con computación tradicional: supremacía cuántica
Cuidado: ¡no todos los problemas son complejos!
La computación cuántica da un resultado probabilístico . Es decir, "esto es una solución, probablemente"
¿Qué es lo que NO MEJORAN las computadoras cuánticas?
No traerán juegos con mejores gráficas
No nos traerán mejores aplicaciones informáticas
No traerán una Internet más rápida
Tardarán lo mismo en realizar la mayor parte de las tareas, pero son astronómicamente más caras
Es poco probable que tengamos una computadora cuántica en nuestros escritorios
La computación cuántica NO ES criptografía cuántica
La criptografía cuántica usa la física cuántica para crear un canal seguro
¡No es necesario tener un computador cuántico para usar criptografía cuántica!
Ejemplo: distribución de claves cuántica (QKD)
En esta clase no hablaremos de criptografía cuántica sinó de la post-cuántica, que definiremos más adelante
https://en.wikipedia.org/wiki/Quantum_cryptography
Entonces... ¿qué hacen las computadores cuánticas?
La computación cuántica permite ejecutar algoritmos de búsquedas más rápidamente que la computación tradicional
Entrenamientos de inteligencia artificial
Sistemas de optimización industrial
Sistemas de recomendación de compras y finanzas
Resolve los problemas matemáticos en los que se basa la criptografía actual mucho más rápido de lo esperado
Top 20 Quantum Computing Use Cases & Applications in 2024
Recordatorio: la seguridad actual está basada en la fuerza bruta
AES-128: fortaleza 128: hay que probar
Crecimiento exponencial de la fortaleza:
Aumentar 1 bit el tamaño de clave dobla el número de claves a probar
Aumentar 2 bits, número de claves x4
Aumentar n bits, número de claves x
En RSA, el equivalente son claves públicas de 2048 bits
¿Aumenta la potencia de los PCs? No pasa nada, aumentamos el tamaño de la clave
Pero esto no nos sirve con computación cuántica: la dificultad de la fuerza bruta ya no crece exponencialmente con el tamaño de la clave
Algoritmos ejecutados por computadoras cuánticas
Algoritmos de interés para criptogafía:
Estos algoritmos tienen el potencial de romper la criptografía que estamos utilizando actualmente
Cuando tengamos un computador cuántico... ¡los malos ya sabrán usarlo!
Inconvenientes de las computación cuántica
Solo mejora algunos problemas, otros los calculará tan rápido como la tradicional
Es muy cara
Decoherencia: un qbit es muy sensible al entorno y puede perder sus propiedades cuánticas
Muchos qbits hacen el sistema inestable
Necesitan temperaturas cercanas al cero absoluto
La respuesta es probabilística: probabilidad de error
No se ha demostrado que haya supremacía / ventaja cuántica
What Are The Remaining Challenges of Quantum Computing? Matt Swayne. March 24, 2023
Estado actual
Es probable que se alcance la supremacía cuántica en un futuro cercano
Criptografía Post-cuántica
Criptografía post-cuántica
Algoritmos criptográficos que tendrán que usar las computadoras actuales/clásicas cuando existan las computadoras cuánticas
Observa:
Estos algoritmos criptográficos ya existen y sustituirán a RSA, ECDH o ECDSA
Los ejecutarán los computadores tradicionales, no las cuánticas
Los puedes usar ya en tus protocolos
Los tienes que empezar a usar antes de que llegue la computación cuántica
Problemas matemáticos en los que se basa la criptografía post-cuántica
Códigos correctores de errores
Retículos
Funciones de hash con y sin estado
Polinomios multivariantes cuadráticos
Isogenias definidas sobre curvas elípticas
Familia
Ventajas
Inconvenientes
Retículos
Rápido y claves pequeñas
Son muy nuevas
Isogenias
Claves pequeñas, texto cifrado pequeño
Muy lentas
Códigos
Rápidas y texto cifrado pequeño, muy estudiadas
Claves muy grandes
Basadas en hash
Clve pequeña, muy estudiadas
Firmas muy grandes, lentas
Multivariante
Rápidas y claves privadas pequeñas
Clave pública muy grande
Concurso del NIST
En 2016, el NIST (instituo de estandarización de EEUU), convocó un concurso para evaluar los mejores algoritmos post-cuánticos que le presentasen. Se centró en:
Mecanismos de encapsulación de claves o KEM (Key Encapsulation ), para sustituir a Diffie-Hellman
Firmas digitales, para sustituir a RSA
El NIST ya ha publicado (agosto de 2024) los estándares post-cuánticos:
ML-KEM : Module-Lattice-Based Key-Encapsulation Mechanism . FIPS 203 . Estándar de intercambio de clave basado en CRYSTALS-Kyber. Reemplaza ECDH.ML-DSA : Module-Lattice-Based Digital Signature Algorithm . FIPS 204 . Estándar principal para firmas digitales post-cuánticas. Usa el algoritmo CRYSTALS-Dilithium. Reemplaza RSA, ECDSASLH-DSA : Stateless Hash-Based Digital Signature Algorithm . FIPS 205 . Basado en Sphincs+. Es un "backup" para ML-DSA
https://www.linkedin.com/pulse/nist-releases-first-3-finalized-post-quantum-cryptography-fhpbe/
Algoritmos
Tipo
Nombre
Problema matemático
Notas
KEM
CRYSTALS-Kyber
Retículo estructurado
Seleccionado por el NIST: FIPS 203 . Ahora llamado ML-KEM
KEM
FrodoKEM
Retículo no estructurado
KEM
BIKE
Códigos cuasi-ciclicos
No presentado en tercera ronda, pero será evaluado
KEM
HQC
Códigos cuasi-ciclicos
No presentado en tercera ronda, pero será evaluado
KEM
Classic McEliece
Códigos de Goppa
KEM
SIKE
Isogenias
Roto con computación tradicional en 2022
Firma
CRYSTALS-Dilithium
Retículo estructurado
Seleccionado por el NIST: FIPS 204
Firma
Falcon
Retículo estructurado
Firma
SPHINCS+
Funciones de hash
Seleccionado por el NIST: FIPS 205
Firma
XMSS
Funciones de hash
Comparativas
Comparativa con RSA-2048: intercambio de claves
Algoritmo
Tamaño clave
Tamaño cifrado
Tiempo cifrado
Tiempo KeyGen
Kyber512
x4
x4
x1
x4000
Comparativa con Ed25519 (ECDA) : firmas
Algoritmo
Tamaño clave
Tamaño cifrado
Tiempo firmado
Tiempo verificar
Dilithium2
x40
x40
x5
x0.5
Falcon512
x30
x10
x8
x0.5
SPHINCS+128
x1
x100
x500
x7
Observa: buscamos las curvas elípticas para conseguir una criptografía asimétrica eficiente, y los nuevos protocolos son aún más ineficientes
Fuente: charla "Criptografía postcuántica: presente y futuro" de Adrián Ranea en Jornadas CCN-CERT 2023
Ejemplo: ML-KEM
Module-Lattice-Based Key-Encapsulation Mechanism . FIPS 203
ML-KEM (CRISTALS Kyber) - FIPS 203
Nombre oficial: Module-Lattice-Based Key-Encapsulation Mechanism
Nombre común: CRISTALS Kyber
Mecanismo de encapsulación de clave: dos personas que no se han visto nunca pueda tener una clave común que luego usarán en AES (o similar)
"Sustituto" postcuántico de Diffie-Hellman / ECDH
Basado en el problema "Aprendizaje con errores"
CRYSTALS-Kyber . Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, Damien Stehlé. Agosto 4, 2021Learning with errors: Encrypting with unsolvable equations Chalk Talk, 2023. Explicación sencillaCRYSTALS Kyber : The Key to Post-Quantum Encryption , Udara Pathum, 2024. Explicación completa
Aprendizaje SIN errores
Observa que se usa también la aritmética del módulo
Es un sistema lineal y dada la clave pública cualquiera podría sacar la privada
Aprendizaje CON errores
Observa que ahora hemos introducido ligeros errores en la igualdad. Por ejemplo, la primera ecuación resulta en 8 en vez de 11
Ya no es un sistema lineal y obtener la clave privada a partir de la pública no es fácil, ni siquiera para un computador cuántico
Cifrado y descifrado
Cifrar un 0: el emisor escoge varias ecuaciones de la clave pública al azar y las suma (recuerda: mod 89)
Cifrar un 1: el emisor escoge varias ecuaciones de la clave pública al azar, las suma y añade 44 (recuerda: mod 89, 44 es la mitad de 89)
Descifrar un 0: el receptor sustituye los valores de su clave privada y comprueba si el error está "cerca" de 0
Descifrar un 1: el receptor sustituye los valores de su clave privada y comprueba que si el error está "cerca" de 44
El receptor descifra "0" si el error está cerca de 0 y "1" si el error está cerca de la mitad del módulo. Hay una pequeña probabilidad de que el error sera mayor que la mitad del módulo y el descifrado sea incorrecto
Uso y comparación de D-H
De esta manera, bit a bit, un emisor puede enviar qué clave AES se utiliza el resto de la comunicación: encapsulación de clave
Valores reales: 256 variables, módulo 3329
Comparado con ECDH...
Hay una pequeña probabilidad de descifrar incorrectamente
Le lleva el doble de tiempo
El triple de procesado / energía
70 veces más datos intercambiados
Clave de tamaño x4
Resistente a la computación cuántica
https://en.wikipedia.org/wiki/Kyber
Migración a criptografía post-cuántica
¿Qué tenemos que migrar?
Los mecanismos que firman firmware en los dispositivos físicos
Los mecanismos de intercambio de claves simétricas
Los mecanismos de firma digital
Cifrado simétrico: doblar el tamaño de la clave
The state of the post-quantum Internet , Bas Westerbaan. Marzo 2024
Tiempo de transición
Aún no existe una computadora cuántica con la potencia suficiente como para romper RSA, ni se sabe cuándo la tendremos: Quantum threat timeline report
Existe una "carrera cuántica" que están llevando China, USA, Europa por ser los primeros en tener una tecnología útil
Problema: store now, decrypt later
Históricamente, las transiciones son lentas: 3DES, MD5, TLSv1 aún están entre nosotros más de una década después de que no se recomiende su uso
Ya sabemos qué algoritmos post-cuánticos vamos a utilizar
Retos de implementación
Los nuevos algoritmos no están soportados por sistemas antiguos: servidores, clientes, hardware...
No son tan eficientes como los algoritmos clásicos
Los nuevos algoritmos son más complejos, y eso también significa que son más difícil de implementar y proteger
Retículos: pequeña probabilidad de fallos en el descifrado
Retículos: necesitan generadores aleatorios gaussianos
FALCON: aritmética en coma flotante
BIKE: descifra en tiempo variable
XMSS: necesita guardar estado entre firmas
Plan de migración
Determinar la información que debo proteger y hasta cuándo.
Cifrado: largos periodos
Firma: hasta caducidad de certificado (unos 2 años)
Realizar un inventario exhaustivo de productos y cifradores que empleo para proteger mi información y mis activos.
Analizar si tales productos y cifradores son o no resistentes a la computación cuántica.
Establecer un plan de migración a las soluciones híbridas
Decidir qué nuevos productos necesito y cuánto tiempo requiero para su adquisición y despliegue.
Determinar cuánto tiempo tengo disponible
Recomendaciones para una transición postcuántica segura . CCN-TEC 009. Diciembre 2022
No sabemos cuándo llegará la computación cuántica, pero ya podemos usar criptografía post-cuántica
Ejemplos de migración
AWS, Signal y otros ya permiten conectarse a sus servidores usando criptografía post-cuántica
Resumen
La computación cuántica permite resolver ciertos problemas más rápidamente de lo que sabemos hacerlo con computación tradicional
Cuando llegue la computación cuántica:
AES, ChaCha, criptografía simétrica: deberá doblar el tamaño de las claves usadas
SHA, funciones de hash: deberán casi doblar los bits de salida
RSA, D-H, curvas elípticas, criptografía asimétrica, intercambio de claves y firmado: obsoleta , hay que buscar alternativas
Criptografía post-cuántica : sistemas criptográficos que usarán las computadoras clásicas para protegerse de las hipotéticas computadoras cuánticasAgosto de 2024: el NIST ya ha estandarizado los algoritmos post-cuánticos que recomienda, y se espera que el resto de agencias tengan opiniones similares
No sabemos cuándo llegará la computación cuántica, pero ya podemos usar criptografía post-cuántica
El periodo de transición puede ser muy largo y se recomienda empezar ya la migración a criptografía post-cuántica
Referencias
Criptografía post-cuántica:
Generales sobre computación cuántica:
Previous slide Page 1 of 50 Next slide Toggle fullscreen Open presenter view
Una clave pública RSA tiene entre el doble y el cuadruple de esta longitud
Nota: no pretenderé explicar cómo funciona la computación cuántica, sinó cómo afectará a la criptografía del futuro próximo
Recordatorio: "problema complejo" no significa necesariamente problema difícil. Hay una rama de las matemáticas que estudia los problemas complejos, y tienen que ver con cuánto aumementan los recursos necesarios para resolver un problema (tiempo, memoria = dinero) cuando aumenta el tamaño del problema.
Por ejemplo, factorizar números primos es un problema complejo. No porque sea difícil (no lo es), sino porque el tiempo necesario para factorizar un número aumenta exponencialmente con su tamaño
Si un problema no es complejo, utilizar computación cuántica para solucionarlo en "matar moscas a cañonazos"
Por eso es poco probable que veamos computadoras cuánticas en nuestros hogares: en nuestra vida diaria no necesitamos resolver problemas matemáticamente complejos
La criptografía cuántica utiliza los principios cuánticos para crear un canal de comunicaciones seguro. ¡No se necesita una computadora cuántica para usar la criptografía cuántica
En el ejemplo, se usa un canal cuántico para distribuir una clave criptográfica tradicional que se puede usar, por ejemplo, para AES. En un canal cuántico, "el acto de medir cambia lo que se mide" (principio de incertidumbre), así que Alice y Bob se darán cuanta si hay alguien escuchando el canal, y no usarán esa clave para cifrar
En esta clase no hablaremos de criptografía cuántica
En la imagen, IBM-Q quantum computer en la conferencia Supercomputing 18 de Dallas, Texas
Para pensar: ¿realmente necesitamos resolver algoritmos de optimización tan rápido? ¿No nos valen los algoritmos tradicionales?
Observa: ya teníamos algoritmos antes de tener el primer computador cuántico!
Fíjate: da igual que aumentemos el tamaño de la clave, llega un momento en que resolver RSA se vuelve casi constante, independientemente de cuántos bits tenga la clave
El vídeo contiene detalles físicos y matemáticos de cómo funciona en algoritmo de Shor en sistemas cuánticos y es razonablemente sencillo
Sabemos que la computación cuántica es posible. Ahora, ¿es realmente más rápida que la tradicional?
El consenso en la comunidad científica es que sí, que acabará teniendo ventaja/supremacía frente a la computación tradicional antes o después. Y tenemos que estar preparados para ello.
Fíjate:
- son anuncios, no demostraciones
- segutamente estos números estarán obsoletos cuando leas esto
Recuerda:
- el cifrado simétrico (AES, ChaCha hash) se puede romper simplemente buscando qué texto original daría un cifrado. Eso es una búsqueda exhaustiva, y la computación cuántica puede hacer más rápidamente que la tradicional
- La seguridad de RSA se basa en que no sabemos hacer factorización de números primos rápidamente con computadoras clásicas, pero sí que sabremos resolverlo muy rápidamente con computadoras cuánticas
- D-H se basa en el problema del logaritmo discreto y tiene el mismo problema
- Los sistemas de curvas elípticas también tendrán el mismo problema
Aunque la criptografía simétrica resistirá, necesitamos sustituir la criptografía asimétrica
Fíjate bien: llamamos criptografía post-cuántica a la criptografía que ejecutarán las computadoras clásicas, no las cuánticas
EL intercambio de claves clásico podría hacerse acordando una clave (Diffie-Hellman) o simplemente enviando una clave simétrica cifrada con RSA. Esto último es lo que se llama "encapsulamiento de clave"
Todos estos algoritmos están bajo un estudio constante y se están descubriendo ataques existosos a algunos de ellos. Cada uno tiene ventajas y desventajas: manejo de estados, tiempos muy largos, claves largas...
A continuación vamos a explicar muy por encima en qué consiste el problema del aprendizaje con errores, dejándo detalles fuera.
El primer enlace es la propuesta que se envió al NIST, el segundo enlace es una explicación sencilla en la que hemos basado esta sección, el tercer enlace incluye una versión más completa
La intención de esta sección es introducir y entender aproximadamente en qué se basa este sistema, no entender todos los detalles
Imagen: https://blog.cloudflare.com/content/images/2022/10/image3.png
En la figura, esquema híbrido de generación de clave: la clave es una combinación de generación tradicional y post-cuántica
Para firmar las actualizaciones de firmaware se recomienda utilizar ya firmados post-cuánticos. El hardware puede estar funcionando durante décadas, muy posiblemente hasta después de que existan las computadoras cuánticas
Los sitemas híbridos utilizan tanto criptografía cuánticas como post-cuántica, adaptando primero los algoritmos que puedan ser más sencillos (como D-H)