El futuro post-cuántico está a la vuelta de la esquina y aún no estamos preparados

Que cada año contemos con ordenadores más potentes con capacidad de cálculo cada vez mayor: ¿es bueno o malo? Piénsalo bien antes de responder. 

Depende, si la seguridad de la información de todo el planeta se basa en la complejidad computacional de ciertas funciones, que los ordenadores se vuelvan cada vez más rápidos será una muy, muy mala noticia.

De hecho, la espada de Damocles se cierne sobre nuestros sistemas de cifrado de clave pública: RSA, DSA, ECDSA. Su seguridad depende de la dificultad de resolver ciertos problemas matemáticos considerados hoy en día intratables, como la factorización de grandes números enteros o el logaritmo discreto. La gran promesa de la computación cuántica es que dichos problemas matemáticos se resolverán con rapidez. ¿Está herida de muerte la criptografía? ¿Hay esperanza para el mundo? ¿Podremos seguir comunicándonos de manera segura tras los primeros ordenadores cuánticos? Vayamos por partes.

¿Qué queremos decir cuando afirmamos que un ordenador cuántico es más rápido que uno clásico?

En las ciencias de la computación se busca encontrar el algoritmo más eficiente (es decir, el más rápido) para resolver un problema computacional dado. Con el fin de comparar la eficiencia de distintos algoritmos, se necesitan mecanismos para clasificar los problemas computacionales de acuerdo con los recursos necesarios para resolverlos. Esta clasificación debe poder medir la dificultad intrínseca del problema, con independencia de cualquier modelo computacional particular. Los recursos a medir pueden incluir tiempo, espacio de almacenamiento, número de procesadores, etc. Normalmente el enfoque principal es el tiempo y, a veces, el espacio.

Por desgracia, suele ser difícil predecir el tiempo de ejecución exacto de un algoritmo ante cualquier tipo de entrada. En tales situaciones, este tiempo se aproxima. Se estudia cómo aumenta el tiempo de ejecución del algoritmo a medida que aumenta sin límite el tamaño de la entrada.

Para representar estos tiempos de ejecución y facilitar su comparación, se suele utilizar la notación O grande: O(f(n)). Esta notación asintótica viene a decirnos que, para n suficientemente grande, el tiempo de ejecución crece como máximo al ritmo de la función f(n) multiplicada a lo sumo por una constante, aunque por supuesto puede crecer más lentamente. La función f(n) representa el caso peor. Para hacernos una idea más clara de eficiencia, la siguiente lista de funciones en notación asintótica está ordenada desde las que crecen más lentamente hasta las que crecen más rápidamente:

El secreto de la velocidad de los futuros ordenadores cuánticos residirá en los algoritmos cuánticos, capaces de sacar partido a la superposición de los qubits. Como queda dicho, tanto en algoritmos clásicos como cuánticos, el tiempo de ejecución se mide por el número de operaciones elementales usadas por un algoritmo. En el caso de la computación cuántica, esta eficiencia puede medirse usando el modelo de circuito cuántico. Un circuito cuántico es una secuencia de operaciones cuánticas elementales llamadas puertas cuánticas, cada una aplicada a un pequeño número de qubits.

La némesis de la criptografía es el famoso algoritmo de Shor: el algoritmo cuántico exponencialmente más rápido a la hora de calcular logaritmos discretos y factorizar números enteros y, por tanto, capaz de romper RSA, DSA y ECDSA. En el problema de la factorización, dado un entero n = p × q para algunos números primos p y q, la tarea del criptoanalista consiste en determinar p y q. El mejor algoritmo clásico conocido para factorizar enteros mayores de 100 dígitos es la criba general del cuerpo de números, que se ejecuta en el tiempo exp(O(ln n)^1/3(ln ln n)^2/3)). El algoritmo cuántico de Shor resuelve este problema a velocidad sustancialmente más rápida: en el tiempo O((log n)³). 

Se habla mucho también del algoritmo de Grover, capaz de agilizar las búsquedas en secuencias de datos no ordenadas de n elementos. En efecto, uno de los problemas más básicos en informática es la búsqueda no estructurada. Este problema se puede formalizar de la siguiente manera: dada la capacidad de evaluar una función f: {0, 1}ⁿ → {0, 1}, encuentra x tal que f(x) = 1, si tal x existe; de lo contrario, devuelve «no se encuentra».

Es fácil ver que, sin información previa sobre f, cualquier algoritmo clásico que resuelva el problema de búsqueda no estructurada con certeza debe evaluar f un total de N = 2ⁿ veces en el peor de los casos. Incluso si buscamos un algoritmo aleatorio que tenga éxito, digamos, con probabilidad ^1/2 en el peor de los casos, entonces el número de evaluaciones requeridas es de orden N. Sin embargo, el algoritmo cuántico de Grover resuelve este problema utilizando O(N1/2) evaluaciones de f en el peor de los casos. A la vista está que no es tan espectacularmente rápido como el algoritmo de Shor ni supone una amenaza tan seria, ya que se puede contrarrestar sin más que doblar la longitud de la clave.

Hoy por hoy, no parece haber más algoritmos en el arsenal del criptoanalista cuántico. Así que, veamos cómo Shor y Grover afectarían a la criptografía presente si pudieran ejecutarse ya.

¿Qué pasaría de verdad si tuviéramos hoy un ordenador cuántico superpotente?

En la entrada anterior vimos que se estima un mínimo de 10 años antes de que puedan construirse los primeros ordenadores cuánticos con corrección de errores y miles de qubits lógicos. ¿En qué estado quedaría la criptografía clásica ante ataques cuánticos?

• Criptografía de clave asimétrica

Para poner los datos en contexto, romper una clave RSA de 1.024 bits exigiría un ordenador cuántico de unos 2.300 qubits lógicos y menos de 4 horas de tiempo de cómputo. El asunto es tan serio que el Instituto Nacional de Estándares y Tecnología estadounidense (NIST) ha lanzado el proyecto Post-Quantum Cryptography para buscar reemplazos a los algoritmos actuales. Se espera que el proceso de selección de los candidatos haya finalizado en 5 ó 6 años.

• Criptografía de clave simétrica

El estándar actual para cifrado simétrico es el algoritmo AES-GCM (Advanced Encryption Standard-Galois/Counter Mode), que utiliza un tamaño de clave variable: 128, 192 ó 256 bits. Por ejemplo, para una clave de 128 bits, un ataque de fuerza bruta exige probar todos los posibles valores de la clave o, lo que es lo mismo, 2¹²⁸ combinaciones. El algoritmo de Grover es capaz de acelerar esta búsqueda de forma cuadrática, es decir, necesitaría 2⁶⁴ operaciones. Ejecutarlo en un ordenador cuántico requeriría unos 3.000 qubits y más de 10¹² años, un tiempo extremadamente largo. Incluso aunque existiera ya tal ordenador cuántico, la solución sería tan sencilla como doblar el tamaño de clave, algo que podría hacerse de forma práctica en cualquier momento.

Por supuesto, alguien podría descubrir un algoritmo cuántico mucho más eficiente que el algoritmo de Grover, en cuyo caso AES-GCM habría de ser reemplazado.

• Hash

Las funciones hash se usan en todo tipo de aplicaciones: hashes de contraseñas en bases de datos, problemas matemáticos para minar bitcoins, construcción de estructuras de datos como los árboles de Merkle, resúmenes de mensajes para firmar digitalmente, funciones de derivación de claves basadas en contraseñas, etc. El algoritmo más usado en estos momentos sigue siendo SHA256. No se espera que los algoritmos de hashing actuales se vean afectados por la computación cuántica, ya que se considera que el algoritmo de Grover no puede romper un hash como SHA256.

Sin embargo, el hashing de contraseñas sí que corre mayor peligro debido al menor espacio de contraseñas. Por ejemplo, considerando un alfabeto de 100 símbolos, el conjunto de todas las posibles contraseñas de 10 caracteres de longitud tiene un tamaño de tan solo 100¹⁰ ≈ 2⁶⁶. Mediante Grover, el espacio de búsqueda se reduce a 2³³, lo que le llevaría a un hipotético ordenador cuántico unos pocos segundos. La sombra de la amenaza cuántica es otro argumento más para migrar hacia alternativas a las contraseñas, como algunos de los proyectos en los que estamos trabajando en el Laboratorio de Innovación de ElevenPaths: CapaciCard, SmartPattern, PulseID; o como Mobile Connect.

Otra aplicación muy extendida de los hashes son los sistemas de prueba de trabajo, utilizados por criptomonedas como Bitcoin o Ethereum. Para validar un bloque de la cadena, los mineros deben resolver un puzle matemático que implica calcular millones de hashes. Por fortuna para Blockchain, un ordenador cuántico tardaría más de 10 minutos en resolver los retos usados en la actualidad, así que las criptomonedas seguirán a salvo, al menos por ese lado (no por el lado de la criptografía de curvas elípticas).

El largo y tortuoso sendero de las migraciones criptográficas

Puede decirse que la criptografía moderna nace a mediados de los 70, con algoritmos como DES, para cifrado simétrico, y Diffie-Hellman, para establecimiento de claves. Desde entonces, solo ha habido un puñado de transiciones de un algoritmo ampliamente implantado a otro. Algunas de estas migraciones han sido: desde DES y Triple-DES hasta AES; de MD5 y SHA-1 a la familia SHA-2; desde el transporte de claves RSA y el campo finito Diffie-Hellman hasta la curva elíptica de intercambio de claves Diffie-Hellman; y de los certificados RSA y DSA a los certificados ECDSA.

Algunas de estas transiciones han salido bie. A AES se lo ve casi en todas partes y los protocolos de comunicación modernos utilizan predominantemente el intercambio de claves ECDH. Ahora bien, las transiciones que involucran infraestructura de clave pública han obtenido un éxito desigual: los proveedores de navegadores y las Autoridades de Certificación han tenido un largo período de transición de SHA-1 a SHA-2 en certificados, con repetidos retrasos en los plazos, la transición a los certificados de curva elíptica ha sido aún más lenta y, aun así, hoy la gran mayoría de los certificados emitidos para la web siguen utilizando RSA.

En el medio plazo, es probable que nos veamos forzados a otra transición, hacia la criptografía de clave pública post-cuántica.

Hay vida criptográfica más allá de RSA y de DSA y de ECDSA

Antes de nada, es importante matizar que una cosa es «el fin de RSA, DSA y ECDSA» y otra bien distinta es «el fin de la criptografía». Hay vida criptográfica más allá de RSA, DSA y ECDSA. Ya desde mediados de los 80 existen algoritmos criptográficos basados en la dificultad de resolver problemas matemáticos distintos de la factorización de enteros y del logaritmo discreto. Las tres alternativas mejor estudiadas son:

• Criptografía basada en Hashes: como su nombre indica, utilizan funciones hash seguras, que resisten a los algoritmos cuánticos. Su desventaja es que generan firmas relativamente largas, lo que limita sus escenarios de uso. Leighton-Micali Signature Scheme (LMSS) constituye uno de los candidatos más sólidos para reemplazar a RSA y ECDSA. 
• Criptografía basada en códigos: la teoría de códigos es una especialidad matemática que trata de las leyes de la codificación de la información. Algunos sistemas de codificación son muy difíciles de decodificar, llegando a requerir tiempo exponencial, incluso para un ordenador cuántico. El criptosistema mejor estudiado hasta la fecha es el de McEliece, otro prometedor candidato para intercambio de claves.
• Criptografía basada en celosías: posiblemente se trate del campo más activo de investigación en criptografía post-cuántica. Una celosía es un conjunto discreto de puntos en el espacio con la propiedad de que la suma de dos puntos de la celosía está también en la celosía. Un problema difícil es encontrar el vector más corto en una celosía dada. Todos los algoritmos clásicos requieren para su resolución un tiempo que crece exponencialmente con el tamaño de la celosía y se cree que lo mismo ocurrirá con los algoritmos cuánticos. Actualmente existen numerosos criptosistemas basados en el Problema del Vector más Corto.

Por consiguiente, la gran dificultad no radica en la falta de alternativas. El doloroso problema será la transición a tiempo hacia alguna de estas alternativas anteriores:

• En primer lugar, los algoritmos post-cuánticos deben ser seleccionados y estandarizados por organismos como el NIST.
• Después, el estándar debe incorporarse a las bibliotecas criptográficas en uso por los lenguajes de programación más populares, por los chips criptográficos y por los módulos hardware.
• A continuación, deberán integrarse dentro de los estándares y protocolos criptográficos, tales como PKCS#1, TLS, IPSec, etc.
• Luego, estos estándares y protocolos deberán ser incluidos por todos los vendedores en sus productos: desde los fabricantes de hardware, hasta los de software.
• Una vez actualizados todos los productos software y hardware, será necesario reemitir todos los certificados, recifrar toda la información almacenada, refirmar y redistribuir todo el código, destruir todas las copias antiguas, etc. ¿Cuánto puede llevar todo este proceso? A juzgar por migraciones anteriores, como la de SHA-1 a SHA-2, y teniendo en cuenta la complejidad adicional, no menos de 20 años. ¿Y para cuándo se esperan los primeros ordenadores cuánticos capaces de atacar RSA, DSA y ECDSA? No antes de 15 años.

Así está el panorama. Esperemos que el proceso de transición se acelere. Nadie sabe a ciencia cierta cuán lejos quedan los ordenadores cuánticos. Pero, por si acaso, más nos vale que nos pillen preparados.