La paralelización del analizador de protocolo criptográfico Maude-NPA reduce el tiempo de análisis, hace que Internet sea más seguro

La seguridad de Internet es una preocupación importante, pero las herramientas de análisis de protocolo criptográfico a menudo requieren mucho tiempo debido a su complejidad computacional. El profesor Kazuhiro Ogata y el Profesor Asistente Canh Minh Do del Departamento de Ciencias de la Computación en el Instituto Avanzado de Ciencia y Tecnología de Japón (JAIST) han paralizado con éxito dos pasos clave: la subsunción de reducción de la transición y la transición, en Maude-NPA, lo que resulta en lo que llaman PAR-MAUDE-NPA.

Par-Maude-NPA mejora el rendimiento del tiempo de ejecución de Maude-NPA en aproximadamente un 52% en promedio para casos complejos, reduciendo significativamente el tiempo de análisis y mejorando la capacidad de analizar protocolos criptográficos grandes y complejos de manera eficiente.

Esta investigación es el resultado de una colaboración internacional con el profesor Santiago Escobar de la Universidad Politécnica de Valencia y el profesor asociado Adrián Riesco de la Universidad Complutense de Madrid en España. Fue publicado en Transacciones IEEE en computación confiable y segura el 16 de julio de 2025.

Asegurar la seguridad de las comunicaciones de Internet requiere la verificación de fallas de diseño y vulnerabilidades de seguridad en protocolos criptográficos, como la seguridad de la capa de transporte (TLS), que protege la información personal como números de tarjetas de crédito del acceso no autorizado durante las transacciones en línea. Para apoyar la verificación formal de estos protocolos, se han desarrollado varias herramientas y técnicas.

Además de Maude-NPA, se han introducido varios otros analizadores formales, incluidos Proverif, Tamarin y Scyther. Sin embargo, hasta hace poco, no había habido una paralelización exitosa de analizadores formales para protocolos criptográficos.

Maude-NPA comienza desde un estado de ataque y utiliza un análisis de accesibilidad de estrechamiento hacia atrás para encontrar fallas de seguridad en protocolos criptográficos. Si se puede alcanzar el estado inicial desde el estado de ataque, se muestra el posible ataque. Por el contrario, si no existe tal camino, se puede concluir que el ataque es inviable. Sin embargo, esta técnica sufre un rápido aumento en el número de estados que deben analizarse, un problema conocido como explosión estatal.

Para abordar esto, Maude-NPA introduce la subsunción de transición, que elimina los estados innecesarios que pueden ser subsumidos por otros estados explorados previamente en el espacio de búsqueda. En esta investigación, el equipo de investigación es paralelado tanto al estrechamiento atrasado como la subsunción de transición para hacer el mejor uso de los recursos informáticos de alto rendimiento.

«Maude-NPA utiliza una estrategia de búsqueda de amplitud para atravesar el espacio de estado accesible. A partir de un conjunto de estados en la capa L (que representa la profundidad L del estado de ataque, que se encuentra en la capa 0), realiza un paso reducido hacia atrás en cada estado para generar sus estados sucesores en la capa L+1. Esta operación se remite al paso 1», Dr. Canh Minh explica.

Esta búsqueda de estrechamiento hacia atrás de cualquier estado dado se puede realizar de forma independiente, lo que abre una oportunidad para la paralelización para mejorar el rendimiento de Maude-NPA.

«Además, tan pronto como los estados sucesores en cada capa se obtienen del Paso 1, Maude-NPA lleva a cabo la subsunción de transición para descartar estados innecesarios que pueden ser subsumidos por los estados explorados previamente. Este proceso se conoce como Paso 2», agrega el Dr. Canh Minh Do.

Aunque la subsunción de transición juega un papel fundamental en la reducción del espacio estatal, es computacionalmente costoso. En lugar de verificar la subsunción de cada estado uno por uno, muchos estados pueden considerarse simultáneamente para mejorar el rendimiento del tiempo de ejecución de Maude-NPA.

El equipo de investigación paraleló con éxito el estrechamiento atrasado en el Paso 1 y la subsunción de transición en el Paso 2 y probó en una variedad de protocolos criptográficos complejos. El Dr. Canh Minh hace comentarios: «Presentamos resultados experimentales en diversos protocolos criptográficos que demuestran que Par-Maude-NPA mejora el rendimiento del tiempo de ejecución de Maude-NPA en un promedio de 52% para estudios de casos complejos con una gran cantidad de estados en cada capa».

Los estudios de caso también han demostrado que PAR-MAUDE-NPA puede realizar un análisis formal de manera efectiva de no solo protocolos criptográficos convencionales como TLS, sino también de TLS resistentes a la cantidad, que permitirá un uso seguro, seguro y sostenible de Internet incluso cuando las computadoras cuantianas a gran escala estén disponibles.