La computadora cuántica y sus problemas de seguridad

En junio de este año, Google comunicó a la prensa los resultados de los experimentos que está llevando a cabo con su computadora cuántica de 20 qubits. No satisfecho con eso, el gigante de Silicon Valley dice que, para fines del 2017, tendrá lista una computadora cuántica de 49 qubits.

Olvidémonos por un segundo de las fechas. Imaginemos que no es a fines del 2017 si no a mediados del 2018. O más lejos aún: a fines del año entrante. Lo que es seguro es que ese momento va a llegar y está a la vuelta de la esquina. Una pregunta que nos deberíamos hacer entonces es ¿esto es bueno o malo? O mejor aún: ¿de qué me tengo que cuidar? ¿Se viene Skynet? ¿Llegamos a la singularidad?

Se supone y se espera que la computación cuántica revolucione el mundo de los algoritmos de igual manera que la mecánica cuántica revolucionó el mundo de la física. ¿En qué consiste esa revolución?

Esto nos da la potencialidad de crear algoritmos que puedan realizar diversas pruebas en paralelo, con distintos estados de qubits. De esta manera, muchos problemas de la llamada “clase NP”[1] podrían ser resueltos millones de veces más rápido que en una computadora clásica. En particular, ya existe un algoritmo (teórico), conocido como el algoritmo de Shor, que permitiría romper en cuestión de minutos (en comparación a los siglos o milenios que podría tardar una computadora clásica) encriptaciones de clave pública o asimétrica (por ejemplo el algoritmo RSA, en el cual se basan gran parte de las comunicaciones en internet desde hace décadas).

Debido a la fragilidad del algoritmo RSA ante un ataque con una computadora cuántica, ya existe un activo campo de investigación teórica llamado «criptografía post-cuántica», que se está encargando de producir algoritmos de encriptación resistentes a las futuras computadoras cuánticas.

Recién nombramos el algoritmo de Shor. Este algoritmo logra obtener de manera eficiente los factores primos de un número entero extremadamente grande. Actualmente, con computadoras clásicas, esta tarea lleva un tiempo exponencial. Los algoritmos de encriptación de clave pública, o asimétrica, se han basado históricamente en la dificultad de factorizar números primos, ya que desde hace mucho tiempo se sabía que era un problema complejo. Sin embargo, el “creador” de la clave simplemente elige 2 números primos muy grandes y los multiplica entre sí para obtener su clave. Ahora bien, existe otra gran área en el mundo de la criptografía, que involucran los algoritmos de clave simétrica. Estos algoritmos, se basan en la selección de un número específico por parte de los 2 individuos que quieren comunicarse. No hay forma de obtener cuál es este número por ningún método simplemente porque ese número no es el resultado de una operación matemática sino que, simplemente, fue elegido de común acuerdo por los 2 individuos. En otras palabras, aun con computadoras cuánticas, los algoritmos de clave simétrica seguirán siendo seguros dado que por más veloces que sean, no son adivinas.

Para ser precisos, una computadora cuántica no puede ser programada para ser adivina, pero sí para ser “tozuda”: existe un algoritmo de búsqueda conocido como algoritmo de Grover, que podría intentar encontrar la clave simétrica probando todas las posibilidades, lo que sin duda tomaría muchísimo menos tiempo con computadoras cuánticas que con computadoras clásicas. Sin embargo, esa reducción de complejidad no llega a ser una reducción exponencial, sino que lo reduce a la raíz cuadrada. En otras palabras, sigue teniendo complejidad exponencial pero su exponente queda reducido a la mitad. Entonces, podemos lograr mantener el nivel de seguridad de la clave simétrica, simplemente duplicando la cantidad de bits de la clave.

La cadena de bloques (blockchain) es una tecnología relativamente novedosa, que se puso muy de moda últimamente por ser utilizada en la criptomoneda Bitcoin. Pero blockchain tiene además aplicación en muchas otras criptomonedas, contratos inteligentes, y bases de datos inmutables. Una de las tecnologías de base que utiliza blockchain, son los algoritmos de encriptación de clave asimétrica, ya que con la clave pública se puede especificar a quién enviarle las monedas, y el dueño de las mismas puede gastarlas utilizando la clave privada que se relaciona con la clave pública anterior. Así, gracias al algoritmo de Shor, un usuario podría llegar a gastar una moneda que no necesariamente fue enviada hacia él.

Pero blockchain tiene una capa de protección adicional para las claves públicas, que además nos permite establecer los mecanismos de consenso tan necesarios en esta tecnología insipiente. La protección es gracias a los algoritmos de hashing criptográficos, por ejemplo el SHA256.

Un algoritmo de hashing obtiene un valor (al cual llamamos “hash”) que representa una entrada dada, y que frecuentemente ocupa mucho menos espacio que la entrada original. Así, por ejemplo para un archivo en pdf, luego de pasarlo por un algoritmo de hashing, se puede obtener una pequeña cadena de caracteres (unos pocos cientos de bytes, que para un observador descuidado podrían parecer casi aleatorios). Se dice que este hash “representa” al archivo original ya que es poco probable que, para otro archivo diferente, se obtenga exactamente la misma cadena al pasarlo por el mismo algoritmo. Esto es conocido como “colisión”, y para los algoritmos de hashing conocidos como criptográficos esta probabilidad es aún mucho menor. Así, es posible mantener integridad en datos, ya que en caso de modificarse el dato original (por ejemplo reemplazar el pdf por otro) se podría calcular el hash del nuevo dato y detectar que hubo alguna alteración de manera casi inmediata (sin tener que comparar los archivos completos, que pueden llegar a ser muy grandes).

Esto es una de las principales fortalezas de blockchain, ya que evita que un atacante conectado a la cadena, pueda violarla y modificar su contenido sin el consenso del resto de los individuos conectados a la misma cadena. Así, por ejemplo en el caso del bitcoin, se impide que un atacante se quede con todas las monedas circulantes, a menos que tenga un gran poder computacional y logre ser más rápido que el resto de los individuos honestos.

Para lograr romper un algoritmo de hashing, es necesario obtener una colisión, y hay una ínfima probabilidad de que esto ocurra. De todas formas, el problema en el blockchain es aún más difícil, ya que no alcanza con cualquier colisión. Es decir, no alcanza con, por ejemplo, encontrar 2 archivos pdf diferentes que produzcan un mismo hash. En el caso del blockchain, ya tenemos el hash que se produce para una entrada dada (por ejemplo una moneda que le mandaron a un individuo A). El atacante necesita entonces encontrar otra entrada diferente pero que produzca ese mismo hash específico [2]. De esta manera, el atacante podría modificar la cadena de bloques, insertando la nueva entrada (por ejemplo diciendo que la moneda se la mandaron a él) y eliminando todo rastro de la existencia de la entrada original.

Este problema es muy similar al problema de las claves simétricas. El atacante tiene que buscar un valor que, aplicado a una función (de hashing criptográfico), produzca un valor determinado. Sabemos que esto puede mantener el mismo nivel de seguridad con solo duplicar el tamaño de la clave. En nuestro caso, alcanzaría con duplicar el largo de los valores de hash producidos por el algoritmo. Es decir, las cadenas de caracteres que representan las entradas originales ocuparían el doble, y así mantendrían el mismo nivel de probabilidad de colisión.

Esto implicaría una actualización de las máquinas virtuales que corren sobre cada blockchain. Pero esto no es algo imposible ni mucho menos, sino que es en efecto algo que está contemplado en los mecanismos de actualización, para ir constantemente escalando y proveyendo nuevas características, tanto de funcionalidad como de seguridad. Cuando la computadora cuántica esté, en efecto, cerca de convertirse en una realidad, podría efectivamente ponerse en práctica esta actualización para dejar tranquilos a todos los que confían en la utilidad de blockchain y que teman lo que la computadora cuántica podría significar.

Como con todo avance tecnológico, las computadoras cuánticas se enfrentan a otros grandes avances recientes, como por ejemplo, la tecnología de blockchain. Desde su nacimiento, blockchain se encumbró como una gran alternativa al internet actual, y no precisamente por su aplicación más popularmente conocida (bitcoin) sino por su gran poder de mantener un consenso en la integridad de los datos almacenados, lo que trajo grandes progresos a las tecnologías de almacenamiento y distribución de datos. No sería deseable que otro gran avance como la computadora cuántica atente contra esto. En síntesis: según el estado del arte de la investigación actual y lo que pudimos ver en este artículo, no pareciera que la computación cuántica represente un peligro en un futuro cercano.