A Novel Memory-Efficient MitM Attack on Ascon-Hash

En el mundo digital, la seguridad suele depender de un delicado equilibrio entre la fortaleza y la eficiencia. Para los miles de millones de dispositivos diminutos, alimentados por baterías, que conforman el Internet de las Cosas —sensores en fábricas, medidores inteligentes y monitores médicos— la potencia de cálculo es escasa, y la memoria es incluso más escasa. Estos dispositivos necesitan herramientas criptográficas que sean lo suficientemente robustas para mantener seguros los datos, pero lo suficientemente ligeras como para funcionar sin agotar una batería o llenar un chip diminuto. Ascon es una solución líder para este desafío, una familia de métodos de cifrado y hashing diseñados específicamente para estos entornos con recursos limitados. Para asegurar que Ascon se mantenga seguro, los investigadores lo prueban constantemente contra ataques sofisticados, intentando encontrar el camino más corto para romper su código. Una de las herramientas más poderosas en este arsenal es el ataque de "encuentro en el medio" (meet-in-the-middle), una estrategia donde un atacante trabaja hacia atrás desde el resultado final y hacia adelante desde el punto de partida, con la esperanza de encontrarse en el medio con una coincidencia. Sin embargo, esta estrategia tradicionalmente requería una cantidad masiva de memoria para almacenar los millones de pasos intermedios, un requisito que a menudo hacía que el ataque fuera impracticable para los mismos dispositivos que Ascon pretende proteger.

Un equipo de investigadores ha desarrollado ahora una nueva forma de ejecutar este ataque que reduce drásticamente la memoria necesaria, haciendo que la prueba sea mucho más realista para sistemas ligeros. En un estudio centrado en la función Ascon-Hash, los autores demostraron que podían realizar el ataque en una versión reducida del sistema utilizando significativamente menos espacio de almacenamiento de lo que se creía posible, sin sacrificar la velocidad del cálculo. Al tratar el problema como un complejo rompecabezas de restricciones lógicas, encontraron una forma de filtrar los datos innecesarios antes de que siquiera fuera necesario almacenarlos. Su trabajo muestra que, para una versión de tres rondas del hash, la memoria requerida puede reducirse de una complejidad de 2^24 a 2^14. Para una versión de cuatro rondas, la reducción es aún más dramática, bajando el requisito de una complejidad de 2^34 a 2^12. Este logro no solo reduce el costo del ataque; proporciona una imagen más nítida y precisa de qué tan segura es realmente Ascon cuando se enfrenta a un adversario con recursos limitados.

Los investigadores comenzaron reconociendo que los intentos previos de romper Ascon utilizando herramientas de búsqueda automatizada habían chocado con un muro de uso de memoria. Si bien las computadoras se habían vuelto más rápidas al encontrar el camino correcto a través del cifrado, el proceso aún exigía que el atacante mantuviera una vasta biblioteca de resultados intermedios en memoria, de forma muy similar a intentar resolver un laberinto anotando cada uno de los giros que das en un papel separado. Si el laberinto es lo suficientemente grande, te quedas sin papel mucho antes de encontrar la salida. El equipo se dio cuenta de que la clave para resolver esto no era solo encontrar el camino más rápido, sino ser más inteligente sobre lo que anotaban. Utilizaron un método llamado resolución de satisfacibilidad (satisfiability solving), que es esencialmente una forma de pedirle a una computadora que encuentre un conjunto de condiciones que haga que una declaración lógica compleja sea verdadera. Esto les permitió mapear los puntos específicos en el proceso de cifrado donde los cálculos hacia adelante y hacia atrás podrían potencialmente encontrarse.

Una vez que habían mapeado estos posibles puntos de encuentro, los investigadores aplicaron una serie de filtros algebraicos para limpiar los datos. Notaron que muchas de las restricciones que gobiernan el cifrado podían separarse en relaciones lineales simples y otras más complejas y no lineales. Las partes lineales eran sencillas; podían simplificarse utilizando técnicas matemáticas estándar para eliminar información redundante, reduciendo efectivamente la lista de posibilidades que la computadora tenía que rastrear. Las partes no lineales eran más complicadas, pero el equipo desarrolló un método para reorganizarlas en una forma triangular, permitiéndoles resolver ciertas variables basándose en otras. Este proceso eliminó la necesidad de calcular y almacenar explícitamente esas variables específicas, reduciendo aún más la huella de memoria.

La innovación más significativa surgió en cómo manejaron las restricciones complejas restantes que no podían simplificarse fácilmente. En lugar de almacenar cada resultado posible, los investigadores utilizaron estas restricciones restantes para crear un "índice residual", una especie de etiqueta o distintivo digital. A medida que generaban la lista de posibles caminos hacia adelante, asignaban a cada uno una etiqueta basada en sus propiedades específicas. Crucialmente, se dieron cuenta de que el camino hacia atrás solo podía coincidir con un camino hacia adelante si sus etiquetas eran compatibles. Esto significaba que la computadora no necesitaba mantener cada uno de los caminos hacia adelante en la memoria; solo necesitaba mantener aquellos que portaban una etiqueta que el camino hacia atrás pudiera alcanzar posiblemente. En las configuraciones específicas que probaron, este filtrado fue tan efectivo que redujo toda la lista de caminos hacia adelante necesarios a un solo y diminuto cubo de datos.

Los resultados de este nuevo enfoque fueron sorprendentes. Cuando se aplicó a una versión de tres rondas de Ascon-Hash, el método mantuvo la misma velocidad que los ataques anteriores pero redujo el requisito de memoria de una complejidad de 2^24 a 2^14. Para la versión de cuatro rondas, la reducción fue aún más profunda, recortando la necesidad de memoria de una complejidad de 2^34 a 2^12 en comparación con el mejor método anterior. Los investigadores verificaron que este filtrado agresivo no descartaba accidentalmente soluciones válidas; comprobaron que los datos restantes aún satisfacían todas las reglas originales del sistema de cifrado. El estudio confirma que, al analizar cuidadosamente la estructura del cifrado y aplicar estos filtros lógicos, es posible realizar pruebas de seguridad profundas con una fracción de los recursos que antes se consideraban necesarios. Este trabajo sugiere que el margen de seguridad de Ascon en entornos de recursos limitados está siendo evaluado con mayor precisión, asegurando que los estándares criptográficos que protegen nuestro mundo conectado sean tan robustos como parecen ser.