Este artículo se publica en colaboración con MIT News.
“La ofuscación indistinguible” es un concepto potente que daría lugar a versiones demostrablemente seguras de todos los sistemas criptográficos que hemos desarrollado y de todos los que no hemos sido capaces de desarrollar. Pero nadie sabe cómo llevarlo a la práctica.
La semana pasada, en el Simposio IEEE sobre Fundamentos de la Informática, investigadores del MIT demostraron que el problema de la ofuscación indistinguible es, en realidad, una variante de otro problema criptográfico, denominado cifrado funcional eficiente. Y aunque los informáticos tampoco saben cómo lograr un cifrado funcional eficiente, creen que están cerca, mucho más cerca de lo que pensaban estar de la ofuscación indistinguible.
“Este tema se ha estudiado durante más tiempo que la ofuscación, y hemos tenido una progresión muy buena de resultados que logran esquemas de cifrado funcional cada vez mejores”, afirma Nir Bitansky, becario posdoctoral en el Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT, quien redactó el artículo de la conferencia junto con Vinod Vaikuntanathan, profesor asociado de ingeniería eléctrica e informática. “La gente pensaba que se trataba de una brecha pequeña. La ofuscación es otra dimensión. Es mucho más potente. Hay una brecha enorme ahí. Lo que hicimos fue reducir considerablemente esa brecha. Ahora, si quieres hacer ofuscación y obtener toda la criptografía, todo lo que puedas imaginar, a partir de supuestos estándar, todo lo que tienes que hacer es resolver este problema muy específico: hacer el cifrado funcional un poco más eficiente.”
En informática, “ofuscación” significa disfrazar los detalles operativos de un programa informático para que no pueda someterse a ingeniería inversa. Se han propuesto muchas técnicas de ofuscación, y muchas han sido vulneradas.
Así que los informáticos empezaron a investigar la idea desde el punto de vista teórico. El esquema de ofuscación ideal tomaría el código fuente de un programa y lo reescribiría de forma que siguiera produciendo un programa funcional, pero fuera imposible determinar qué operaciones estaba ejecutando.
Los teóricos demostraron rápidamente que la ofuscación ideal permitiría casi cualquier esquema criptográfico que pudieran imaginar. Pero casi con la misma rapidez demostraron que era imposible: siempre hay una forma de construir un programa que no puede ofuscarse perfectamente.
Detalles imprecisos
Así que empezaron a investigar principios teóricos menos estrictos, uno de los cuales era la ofuscación indistinguible. En lugar de exigir que un adversario no tenga ni idea de qué operaciones está ejecutando el programa, la ofuscación indistinguible solo exige que el adversario no pueda determinar cuál de dos versiones de una operación está ejecutando.
La mayoría recuerda del álgebra, por ejemplo, que a x (b + c) es lo mismo que (a x b) + (ax c). Para cualesquiera valores dados, ambas expresiones dan el mismo resultado, pero se ejecutarían de forma distinta en un ordenador. La ofuscación indistinguible permite al adversario determinar que el programa realiza uno de esos cálculos, pero no cuál.
Durante años, la idea de la ofuscación indistinguible permaneció inactiva. Pero en los últimos años, los informáticos han mostrado cómo construir esquemas de ofuscación indistinguible a partir de objetos matemáticos llamados mapas multilineales. Sorprendentemente, también demostraron que incluso la noción más débil de ofuscación indistinguible podría dar lugar a toda la criptografía.
Pero los mapas multilineales no se comprenden bien, y no está claro que ninguna de las técnicas propuestas para construirlos vaya a ofrecer las garantías de seguridad que exige la ofuscación indistinguible.
La punta del iceberg
El cifrado funcional, por otra parte, ha sido durante décadas un tema de investigación popular en criptografía. Es un método para realizar alguna operación sobre un archivo cifrado, con un resultado inteligible, pero sin filtrar información adicional sobre el contenido del archivo. Podría, por ejemplo, permitir que un servidor que aloja una gran cantidad de correos electrónicos cifrados descifre solo los nombres de los remitentes, con fines de búsqueda.
Con un esquema de cifrado estándar, el tiempo de cifrado es proporcional a la longitud del archivo que se cifra. Eso es lo que Bitansky y Vaikuntanathan quieren decir con “eficiente”. Pero los mejores esquemas de cifrado funcional no son tan buenos: su eficiencia de cifrado también incluye un factor proporcional al tamaño del resultado de la operación. Si la operación fuera el descifrado del nombre del remitente, ese factor sería bastante pequeño. Pero, en principio, podría ser mucho mayor.
Bitansky reconoce que los investigadores podrían haber subestimado la dificultad de eliminar ese factor adicional. “Podría ser que nuestra visión inicial del mundo fuera falsa”, afirma. “Quizá este no sea un problema tan fácil. Quizá esta sea la verdadera brecha, y podría tardar mucho tiempo en resolverse. Pero soy optimista.”
“Nuestras construcciones candidatas actuales para IO [ofuscación indistinguible] se basan todas en supuestos muy nuevos y poco comprendidos, que muy bien podrían quedar invalidados en un futuro próximo; de hecho, muchos ya lo han sido”, afirma Rafael Pass, profesor asociado de informática en la Universidad de Cornell. “El cifrado funcional es una primitiva de apariencia significativamente más sencilla, así que este trabajo abre una nueva vía para obtener construcciones seguras de IO.”
“El enfoque técnico es sencillo y elegante, y espero que tenga muchas otras aplicaciones”, añade Pass.
La publicación no implica el respaldo de los puntos de vista del Foro Económico Mundial.
Para estar al día con la Agenda, suscríbase a nuestro boletín semanal.
Autor: Larry Hardesty trabaja en la Oficina de Noticias del MIT.
Imagen: una ilustración muestra una proyección de código binario sobre un hombre que sostiene un ordenador portátil. REUTERS/Kacper Pempel.



