Computación cuántica, ¿un Armagedón criptográfico?

[El_Andaluz]

La criptografía es una de las bases fundamentales de la seguridad de la información. Se utiliza para codificar y decodificar datos de modo que cumplan con los requisitos de confidencialidad, integridad, autenticación y no repudio de la información. En general se suele usar la frase "servicios criptográficos" para referirse a todos estos conceptos juntos.

Los avances en el criptoanálisis, la informática y la ingeniería extienden constantemente los límites de lo que se considera seguro. Por ejemplo, el sistema criptográfico RSA en una época se consideraba seguro porque usaba claves de 129 bits; sin embargo, hoy en día una clave segura debe tener más de 2.048 bits.

Otro ejemplo es el algoritmo MD5, diseñado en 1992. A pesar de que su función de hash fue una de las más utilizadas, en 2004 se comprobó que la clave se podía descifrar (mediante ataques de colisiones de hash).

Del mismo modo, en las conferencias de Eurocrypt 2016 se demostraron y publicaron los ataques de colisión denominados Freestart contra SHA-1 (que son un poco más fáciles de encontrar que las colisiones estándar).

Computación cuántica: la física aplicada a la informática

Uno de los recursos que se incluyen en el kit de herramientas para criptoanalistas es la computación cuántica. Para realizar las operaciones, las computadoras cuánticas se basan en las propiedades de la física cuántica, cuyo comportamiento es diferente a las propiedades electrónicas que estamos acostumbrados a encontrar en los equipos de hoy en día, y su unidad básica de información, en lugar de bits, se llama bit cuántico o qubit. Comenzó a utilizarse en ataques teóricos contra los sistemas criptográficos ya en el año 1994, cuando Peter Shor publicó un algoritmo cuántico para encontrar los factores primos de un entero dado.

Este algoritmo permite resolver la factorización de enteros y algunos problemas de logaritmos discretos, que conforman la base de la mayoría de los algoritmos criptográficos de clave pública más ampliamente utilizados (por no decir de todos). Con un impacto menos devastador, pero aún así de suma importancia, el algoritmo cuántico de Grover aumenta en gran medida la velocidad de los algoritmos de búsqueda, lo que afecta la seguridad de muchos sistemas criptográficos, incluyendo AES. Esto nos lleva a hacer una declaración bastante sorprendente: todos los algoritmos criptográficos más importantes que se usan en la actualidad quedarán (virtualmente) obsoletos.

Hoy en día, el único factor de mitigación es la falta de una computadora cuántica lo suficientemente grande como para ejecutar este tipo de ataque contra los parámetros que los algoritmos criptográficos usan en la actualidad.

Sin embargo, como es de esperar, en el ámbito de la computación cuántica todo evoluciona con rapidez. En abril de 2016, la Comisión Europea anunció un plan para invertir mil millones de euros en una "iniciativa emblemática de desarrollo de tecnologías cuánticas a gran escala para toda la UE". Así como se puso en marcha este programa, hay muchos otros que tienen el objetivo de financiar el desarrollo de computadoras cuánticas a gran escala.

También en abril de 2016, investigadores de Canadá establecieron un nuevo récord en la factorización con computadoras cuánticas, después de factorizar el número 200.099 usando un procesador D-Wave 2X, aunque no está claro si D-WAVE produce computadoras cuánticas universales capaces de ejecutar el algoritmo de Shor. Por otra parte, 200.099 solo es un número de 18 bits: es demasiado pequeño para obtener la potencia de cálculo necesaria para factorizar un número entero de 2.048 bits para descifrar los parámetros actuales de RSA.

La etapa actual de despliegue a gran escala de sistemas criptográficos de clave pública se basa en algoritmos bastante antiguos, como Diffie-Hellman (1976), RSA (1977) y Curvas Elípticas (1985). Este último se publicó por primera vez hace más de 30 años, pero recientemente empezó a desplegarse a gran escala.

Para hacer frente al Armagedón criptográfico impuesto por las computadoras cuánticas a gran escala, los criptógrafos de todo el mundo han estado trabajando durante al menos una década para diseñar y mejorar los sistemas criptográficos de modo que sean resistentes a los ataques cuánticos. Esto se conoce como la criptografía post cuántica o PQCrypto.

Son muchos los sistemas criptográficos que se diseñaron y hasta estandarizaron, como NTRU; sin embargo, lleva tiempo confiar en estos nuevos sistemas criptográficos, ya que se deben analizar a fondo una y otra vez hasta que se comprueba que están listos para un despliegue a gran escala.

¿Cuál es el estado actual de PQCrypto?

En 2006, se llevó a cabo la primera Conferencia de PQCrypto, que reunió a investigadores interesados en buscar alternativas seguras contra los ataques de la computación cuántica. En ese momento, ya estaban disponibles algunas alternativas, como el cifrado de McEliece (1978),  y desde ese entonces se han puesto en marcha muchos programas con el objetivo de financiar la investigación de PQCrypto.

Por ejemplo, el programa SAFECrypto de la Comisión Europea orientado al desarrollo de criptografía basada en retículos resistente a la computación cuántica, o el programa canadiense CryptoWorks21 para desarrollar herramientas de seguridad de criptografía cuántica de última generación para el siglo XXI. El resultado de todos estos esfuerzos hacia el desarrollo de PQCrypto es un gran avance en el campo y ya ha proporcionado candidatos post cuánticos que cumplen con todas las características deseadas de eficiencia y tamaño de clave comparables a los algoritmos clásicos.

Cabe notar que PQCrypto no requiere ningún hardware especial. Es similar a la criptografía clásica, pero se basa en problemas que son irrealizables incluso para las enormes computadoras cuánticas. Los algoritmos de PQCrypto se diseñaron para abarcar los servicios provistos por la criptografía clásica y muchos de ellos son capaces de funcionar incluso en las plataformas más limitadas.

¿Cómo evolucionará PQCrypto?

Incluso en un mundo cuántico, los protocolos de seguridad actuales seguirán siendo tan seguros como lo son hoy, si su diseño se verifica mediante el uso de sistemas criptográficos post cuánticos. Por lo tanto, en los próximos años seguramente notemos que los protocolos existentes comienzan a adoptar los algoritmos de PQCrypto modernos en forma gradual.

Veremos que disminuye el uso de los algoritmos de clave pública más utilizados hoy en día, tales como RSA y las Curvas Elípticas; en los casos de la criptografía simétrica y las funciones de hash, se tendrán que volver a revisar los parámetros actuales (por lo general se tendrán que duplicar) para asegurar que sigan siendo seguros en un mundo cuántico. Este cambio a algoritmos modernos debería ocurrir en forma transparente para los usuarios finales. Sin embargo, la persona responsable del desarrollo o la configuración de aplicaciones de seguridad deberá estar lista para los cambios que se aproximan: en particular, en lo que respecta al uso de estas funcionalidades en sistemas heredados.

A modo de especulación sobre el tiempo que tendremos que esperar para que las grandes computadoras cuánticas sean capaces de realizar ataques a sistemas criptográficos configurados con los parámetros de hoy, vamos a suponer que la ley de Moore es válida para todo el desarrollo de la computación cuántica. El algoritmo de Shor requiere aproximadamente 3 log2(N) qubits para factorizar un número entero N (lo que significa que los algoritmos de Shor requieren aproximadamente 6K qubits para descifrar una clave RSA-2048), mientras que la ley de Moore establece que el número de bits (o qubits en este ejemplo) que se puede empaquetar en un circuito se duplica cada 12-24 meses.

Un pequeño ejercicio cuántico

Como ejercicio, tomemos una computadora cuántica de 5 qubits como a la que IBM puso a disposición de los usuarios este mes. La cantidad total de qubits disponibles para ejecutar el algoritmo de Shor después de M ciclos de la ley de Moore se puede calcular como 5 * 2M, por lo tanto, si tomamos 18 meses como promedio del ciclo de la ley de Moore, transcurrirán aproximadamente dieciséis años a partir de ahora para que los ataques contra RSA-2048 se conviertan en una posibilidad, dado que se necesitan 16,5 años para pasar por 11 ciclos de la ley de Moore.

Esto significa que, después de este período, habrá 10K qubits disponibles (más precisamente 10240=5*211), lo que será capaz de suministrar los 6K qubits necesarios para ejecutar el ataque antes mencionado. La misma magnitud de qubits aplica para el algoritmo de Grover ("entre alrededor de 3.000 y 7.000 qubits lógicos") para atacar sistemas AES, por lo que el nivel de seguridad se reduciría a la mitad dentro de ese mismo período de tiempo.

Por lo tanto, si nuestras suposiciones son correctas, en dieciséis años AES-256 será tan seguro como AES-128 lo es hoy, y AES-128 ya no servirá. Por lo tanto, si recordamos el tiempo de preparación requerido por las Curvas Elípticas hasta su despliegue a gran escala, podemos darnos cuenta de que el tiempo ya está corriendo para PQCrypto.

¿De qué debo preocuparme y qué tengo que hacer?

Un tema que va a tener un gran impacto junto con el avance de la computación cuántica es la seguridad a largo plazo, que puede estar relacionada con:

-La autenticidad a largo plazo; como la vida útil de un contrato firmado digitalmente.

-La confidencialidad a largo plazo; por razones legales (por ejemplo, el Código Legal alemán determina que los registros médicos deberán seguir siendo confidenciales incluso tras la muerte del paciente) o por razones estratégicas, como los secretos de una organización o del gobierno.

La autenticidad a largo plazo se puede lograr mediante técnicas sencillas, como volver a firmar un documento con algoritmos seguros por el tiempo que sea necesario. No obstante, esta posibilidad tiene que estar prevista y garantizada por las leyes subyacentes o cualquier reglamentación vigente; de lo contrario, también se verá amenazada por el avance de la computación cuántica.

Pero por el contrario, lograr la confidencialidad a largo plazo es una tarea mucho más difícil. No existe un modo establecido de abordar esta cuestión y ninguno de los actuales sistemas criptográficos de claves públicas es capaz de cumplir esta tarea.

Podría ser una buena opción cifrar estos datos con fuertes sistemas de cifrado simétrico que utilicen claves de al menos 192 bits para mantenerlos seguros incluso aunque las computadoras cuánticas reduzcan su nivel de seguridad a la mitad.

Por último, si esperas contar con seguridad a largo plazo para tu información, debes empezar a buscar alternativas o a planificar estos cambios de inmediato. Sin embargo, los adversarios que en el presente todavía no logran derribar la seguridad de tu información al tratar de descifrar tus datos o falsificar tu firma pueden volver a probar suerte cuando consigan computadoras cuánticas.

http://www.welivesecurity.com/la-es/2016/06/14/computacion-cuantica-armagedon-criptografico/