La computación cuántica y el “futuro de la criptografía”: la criptografía post-cuántica
La computación cuántica es uno de esos conceptos que resuena cada vez más en medios generalistas haciéndose eco de un avance científico notorio en cuanto a un nuevo paradigma de computación. Cuáles son sus ventajas, limitaciones, inconvenientes y avances reales es lo que intentaremos abordar brevemente en este post.
De manera simplificada, la computación cuántica supone un cambio de paradigma con respecto a la computación clásica, funcionando con cúbits o bit cuánticos (habitualmente denominados “qubits”), permitiendo una enorme capacidad de cómputo utilizando la propiedades de la mecánica cuántica y la superposición de estados. En computación clásica un bit puede tener los valores 0 o 1, en computación cuántica el valor 0 y 1 a la vez, o mejor dicho probabilidades de ambos valores a la vez (superposición cuántica de estados).
Este hecho que podría ser “anecdótico” presenta una gran utilidad al desarrollarse algoritmos teóricos específicos, que aprovechan esa superposición, para tratar problemas computacionalmente complejos de resolver con ordenadores clásicos. Y si en papel es posible desarrollar algoritmos con gran capacidad para resolver problemas computacionalmente intratables, el reto recae en construir ordenadores que los puedan ejecutar de manera adecuada. Este es el motivo del interés y avance en la computación cuántica.
En 1998, se consiguió por primera vez probar un algoritmo cuántico usando 2 qubits en la Universidad de Oxford. En 2000, se consiguieron ordenadores con 4, 5 y 7 qubits. En 2006, 12 qubits en un ordenador cuántico del Institute for Quantum Computing, Perimeter Institute for Theoretical Physics y MIT. La disponibilidad e interés para acceder a este tipo de ordenadores ha ido en aumentando hasta nuestros días. Empresas como IBM permiten programar tus propios algoritmos cuánticos y poder probarlos tanto en simuladores como ordenadores cuánticos reales a través de su plataforma IBM Q o utilizar su primer ordenador cuántico comercial el IBM Q System One con 20 qubits. Otras empresas como AWS también permite probar algoritmos cuánticos a través de su servicio Amazon Quantum Solutions Lab, pudiéndose probar en distintos tipos de ordenadores cuánticos como D-Wave, Rigetti o IonQ. Por ejemplo, BBVA ha firmado un acuerdo con el CSIC para investigar el potencial de la computación cuántica en el sector financiero.
El primer ordenador comercial, IBM Q System One. Fuente: IBM
La supremacía cuántica
En los últimos meses ha tenido una gran repercusión que Google había logrado la supremacía cuántica, esto es, un problema que los ordenadores cuánticos pueden resolver pero que los ordenadores clásicos no en un tiempo “razonable”. En el artículo publicado por Google en la revista Nature, los autores reclaman que han logrado la supremacía cuántica al lograr resolver un problema en un ordenador cuántico infinitamente más rápido que haciéndolo en un ordenador clásico. El procesador desarrollado por Google, de nombre Sycamore, tiene 54 qubits, resolviendo el problema en sólo 200 segundos. Los autores estiman que resolver este problema en un superordenador clásico hubiera tardado 10000 años, logrando así la supremacía cuántica.
Procesador Sycamore. Fuente: Google
La respuesta de IBM no se hizo esperar y en un post publicado en su blog, argumentan que, donde Google estima un tiempo de cómputo de 10000 años, ellos consideran que podría hacerse con un superordenador clásico en 2.5 días, por lo que la supuesta supremacía cuántica no sería tal, pero quedaría en una gran proeza científica.
Este enfrentamiento que podría ser anecdótico, o asumible en una contienda comercial tradicional por la venta de nuevas capacidades de computación, deja de relieve algo importante en cuanto a la computación cuántica, la dificultad a la hora de evaluar el potencial de un ordenador cuántico comparado con otro, porque no es exclusivamente una cuestión de qubits (esto tiene implicaciones en seguridad informática). Todos los ordenadores cuánticos no son iguales. Los ordenadores cuánticos de Rigetti son universales, basados en circuitos en el modelo de computación de puertas lógicas cuánticas, mientras que los ordenadores cuánticos de D-Wave no son de propósito general, ya que se basan en el temple cuántico (quantum annealing, en inglés) y no permiten resolver todos los problemas con propósito general sino sólo algún subconjunto de ellos. De esta forma, por ejemplo, este tipo de ordenadores no debería permitir romper la criptografía asimétrica actual haciendo uso de los algoritmos teóricos. Por tanto, el número de qubits es importante, pero mucho más la calidad de los mismos (qubits en superposición, con ruido controlable y estable) y el diseño y arquitectura del ordenador concreto. Aunque no es la única tendencia esta aproximación, como demostraron los investigadores Craig Gidney y Martin Ekera sobre el potencial de los qbits ruidosos con unas ciertas propiedades (How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits – https://arxiv.org/pdf/1905.09749.pdf), eso sí, si se pueden generar en una enorme cantidad de ellos, algo que hasta ahora parece que no es posible.
¿Qué consecuencias tendrá la computación cuántica en la seguridad informática?
A día de hoy nadie sabe exactamente cuándo existirá un ordenador cuántico con la suficiente capacidad (diseño y qubits) para anular procedimientos que facilitan mecanismos de seguridad en las comunicaciones y redes digitales, típicamente mediante el uso de criptografía. El rango de fechas es muy holgado desde unos pocos años, para los muy optimistas, hasta varias décadas. Lo que está claro es que difícilmente dispondremos de estos ordenadores a nivel particular en las próximas décadas con lo que es un asunto que quedará restringido a grandes países con capacidad económica y científica para llevar este complejo proyecto adelante. Este asunto no es baladí ya que es importante para una correcta gestión de expectativas, contramedidas y gestión del riesgo. Una de las estimaciones a menudo referenciadas postula un ordenador con estas características aproximadamente para el 2030 con un coste de 1000 millones de euros y una planta nuclear (PQCrypto 2014, Matteo Mariantoni).
En el caso de existir un ordenador cuántico con la suficiente potencia se podrían ejecutar algoritmos cuánticos conocidos con impacto en la protección de datos y comunicaciones digitales como por ejemplo el algoritmo de Grover y el algoritmo de Shor.
El algoritmo de Grover, publicado en 1996, permite realizar una búsqueda en una secuencia no ordenada de datos con N elementos en un tiempo O(√N), mientras que el mismo problema con un ordenador clásico, la búsqueda se realizaría en un tiempo O(N). Por ejemplificar, si buscáramos en un conjunto de datos (no ordenados) de 1 millón de elementos con un algoritmo clásico se requeriría 1 millón de operaciones, mientras que utilizando el algoritmo de Grover en un ordenador cuántico, sólo se requerirían 1000 operaciones, bastante más rápido que los algoritmos clásicos de búsqueda.
El algoritmo de Shor, publicado en 1994, permite factorizar un número N en tiempo O((log N)3) en un ordenador cuántico, sustancialmente más rápido que usando la criba general del cuerpo de números (GNFS, por sus siglas en inglés) que tiene una complejidad subexponencial, y es el algoritmo más rápido conocido hasta la fecha para este tipo de problema.
¿Qué consecuencias tendrán estos algoritmos a la criptografía que hoy conocemos?
El algoritmo de Grover afectará a la criptografía simétrica (algoritmos de cifrado simétrico como AES y funciones hash) ya que reducirá su nivel de seguridad a la mitad. La solución será aumentar el tamaño de las claves o la salida de las funciones hash al doble del tamaño actual (actualmente se están estudiando más restricciones adicionalmente el aumento del tamaño de bloque o clave). Así, por ejemplo, si en la actualidad tenemos una clave AES de 128 bits, la seguridad en bits de la clave con la presencia de un ordenador cuántico que ejecute el algoritmo de Grover sería de 64 bits, por lo que incrementando el tamaño de clave a 256 bits se obtendría una seguridad de 128 bits, igual a la actual sin la presencia de un adversario cuántico.
Esto no sucede así con el algoritmo de Shor, que tiene unas consecuencias devastadoras en la criptografía asimétrica que conocemos a día de hoy: todos los algoritmos serían rotos con la presencia de un adversario cuántico que ejecutara el algoritmo de Shor. Así pues, algoritmos como RSA, la criptografía de curva elíptica, los criptosistemas basados en el problema del logaritmo discreto como Diffie-Hellman o DSA quedarían obsoletos y no serían seguros. La estimación actual, por ejemplo, para romper un RSA-2048 bits recae en unos poco miles de qubits “de calidad” (algo muy alejado todavía de los ordenadores cuánticos actuales) y unos cientos de millones de puertas lógicas en la construcción del ordenador.
Criptografía afectada por los algoritmos cuánticos. Fuente: NIST
La criptografía post-cuántica y el proceso de estandarización del NIST
Ante este eventual problema, los investigadores de todo el mundo buscan algoritmos que sean resistentes frente a adversarios cuánticos, dando lugar a una rama de la criptografía llamada criptografía post-cuántica. Estos algoritmos reciben el nombre de post-cuánticos. Destacar a modo de curiosidad, especialmente para los medios generalistas, que criptografía post-cuántica no tiene nada que ver con criptografía cuántica (distribución de claves aleatorias).
La criptografía postcuántica tiene distintas aproximaciones cada una con sus ventajas y desventajas, y ninguna de ellas parece ser perfecta: criptografía basada en retículos, criptografía multivariante, basada en hashes o en códigos. Una desventaja de este tipo de algoritmos post-cuánticos es que requieren claves más largas que los algoritmos previos. La siguiente tabla muestra una comparativa entre los tamaños de clave entre distintos algoritmos post-cuánticos y pre-cuánticos para una seguridad de 128 bits post-cuánticos.
| Algoritmo | ¿Post-cuántico? | Clave pública (bytes) | Clave privada (bytes) |
| NTRU-HPS | ✔ | 699 | 935 |
| NewHope-CCA-KEM | ✔ | 928 | 1888 |
| qTESLA-Provably Secure | ✔ | 14880 | 5184 |
| SPHINCS+ Fast | ✔ | 32 | 64 |
| 3072-bit Logaritmo discreto | ❌ | 384 | 32 |
| 256-bit Curva elíptica | ❌ | 32 | 32 |
Fuente: PQC Wiki. Florida Atlantic University. Cryptographic Key Length Recommendation.
Se puede observar que los tamaños de claves para varios algoritmos post-cuánticos son significativamente más grandes que sus antecesores pre-cuánticos. Este hecho debe tenerse en cuenta especialmente en el diseño de arquitecturas o productos comerciales que requieran mantener la compatibilidad con el formato/tamaño de los mensajes aceptados en una organización o red corporativa.
Teorema de Mosca. Fuente: Michele Mosca
En 2017 empezó el proceso de estandarización y a día de hoy todavía continúa en la ronda 2, y no se espera que los primeros borradores de estándar estén hasta el año 2022-2024.
Los requisitos de evaluación del NIST de las propuestas enviadas son los siguientes:
- Seguridad: contra ataques clásicos y cuánticos. Se definen 5 niveles de seguridad, de menor a mayor nivel de seguridad. El NIST pide a las distintas propuestas que se centren en sólo los niveles 1, 2 y 3. La tabla siguiente describe los 5 niveles de seguridad.
| Nivel | Descripción | |
| I | Al menos tan difícil como romper AES128 (búsqueda exhaustiva de la clave) | |
| II | Al menos tan difícil como romper SHA256 (búsqueda de colisiones) | |
| III | Al menos tan difícil como romper AES192 (búsqueda exhaustiva de la clave) | |
| IV | Al menos tan difícil como romper SHA384 (búsqueda de colisiones) | |
| V | Al menos tan difícil como romper AES256 (búsqueda exhaustiva de la clave) | |
Fuente: NIST PQC Standardization Process
- Rendimiento: medido en distintas plataformas.
- Otras propiedades: Perfect forward secrecy, resistencia a ataques de canal lateral, simplicidad y flexibilidad, resistencia frente al mal uso, etc.
Inicialmente, se presentaron 82 propuestas de las que 69 fueron aceptadas (aunque 5 fueron retiradas). Las propuestas por tipo de aproximación se pueden ver la siguiente tabla.
| Firma digital | Cifrado/KEM | Total | |
| Basados en retículos | 5 | 21 | 26 |
| Basados en códigos | 2 | 17 | 19 |
| Multivariante | 7 | 2 | 9 |
| Basados en clave simétrica | 3 | 3 | |
| Otros | 2 | 5 | 7 |
| Total | 19 | 45 | 64 |
Fuente: NIST PQC Standardization Process
Después de un tiempo para encontrar y solucionar errores, proponer ataques, optimizaciones, se pasó a la ronda 2, en la cual se eliminaron algunas de las propuestas y algunas de ellas se juntaron debido a su similitud. A día de hoy, quedan 26 propuestas (ver tabla inferior), y se espera que esta ronda dure de 12 a 18 meses y que haya una ronda 3. En esta ronda 2 se busca un aumento del rendimiento de los algoritmos, teniendo en cuenta las distintas plataformas existentes.
| Firma digital | Cifrado/KEM | Total | |
| Basados en retículos | 3 | 9 | 12 |
| Basados en códigos | 0 | 7 | 7 |
| Multivariante | 4 | 0 | 4 |
| Basados en clave simétrica | 2 | 2 | |
| Otros | 0 | 1 | 1 |
| Total | 9 | 17 | 26 |
Fuente: NIST PQC Standardization Process
Todavía parece pronto para implementar estos nuevos algoritmos en producción (quizás robustos frente a un hipotético ordenador cuántico pero no frente a uno clásico), pero ya existen distintas iniciativas que ya están implementando o probando en entornos reales algoritmos post-cuánticos. Una de ellas es OPEN QUANTUM SAFE, que ofrece implementaciones de distintos algoritmos y cuyo objetivo es prototipar y evaluar criptografía post-cuántica. Otra librería es s2n, la librería TLS de AWS Labs que implementa algoritmos post-cuánticos como BIKE y SIKE. Otras iniciativas van encaminadas a cómo se integrarían algoritmos post-cuánticos en protocolos estándar como TLS o cómo impactarán los nuevos algoritmos en el consumo de energía.
Conclusiones. Siguientes pasos
En este punto la pregunta importante a realizarse es: ¿qué decisión debo tomar para proteger mejor mis comunicaciones digitales o datos? La respuesta fácil sería confiar en que el proceso de estandarización por el NIST (2022-2024) finalice con éxito y los algoritmos puedan ser accesibles por librerías y productos comerciales antes de la teórica llegada de un ordenador cuántico. Por desgracia, en función del escenario en el que nos encontremos esto será suficiente o no.
Se debe asumir que un atacante con la capacidad de construir un ordenador con la capacidad de computación indicada podría almacenar las comunicaciones previas para descifrarlas después (supongamos que la información sigue teniendo valor) o acelerar la inversión en desarrollo y tener un ordenador de estas características antes y en secreto un tiempo. En estas circunstancias, se recomienda apoyarse en la medida de lo posible en criptografía simétrica y en las siguientes recomendaciones:
Algoritmos de clave pública (cifrado y firma)
▪ Criptografía postcuántica
▪ McEliece, con códigos Goppa, n=6960, k= 5413, y t=119
▪ NTRU, basado en retículos, versión de Stehlé-Steinfeld
▪ XMSS (Extended Merkle Signature Scheme)
▪ SPHINCS-256
Algoritmos simétricos y autenticación (simétrica)
- Cifrado en bloque: AES-256
- Cifrado en flujo: Salsa20, clave de 256 bits
- GCM: Galois Counter Mode, nonce de 96 bits, autenticador de 128 bits
- Poly1305, MAC basado en AES
Ante la espera de este hito tecnológico y computacional solo nos queda seguir la evolución de los acontecimientos, realizar una adecuada política de gestión de riesgos y aplicar las medidas y recomendaciones tradicionales de seguridad en profundidad para minimizar el impacto de posibles roturas o vulneraciones en algoritmos criptográficos. Años apasionantes nos esperan.
Comentarios
Publicar un comentario