💻 computer science

Full-Key Recovery and Forgery from One MQOM v2.1 Signature

Este artículo presenta un ataque de recuperación de clave completa y de falsificación contra el candidato de firma MQOM v2.1 de la Ronda 3 de NIST, demostrando que una sola firma aceptada es suficiente para derivar la clave secreta completa y falsificar nuevas firmas, con costos computacionales por debajo de los parámetros de seguridad de NIST para todas las categorías.

Autores originales: José Luis Delgado

Publicado 2026-08-11

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: José Luis Delgado

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás intentando enviar un mensaje secreto a un amigo, pero vives en un mundo donde podrían existir algún día computadoras superrápidas (llamadas computadoras cuánticas). Estas máquinas del futuro podrían romper la mayoría de los cerrojos que usamos hoy para mantener nuestros secretos seguros. Para prepararse para esto, los científicos están construyendo nuevos cerrojos digitales superfuertes llamados "firmas post-cuánticas". Piensa en esto como un tipo especial de sello de cera en una carta. Incluso si un ladrón tiene un martillo mágico que puede destrozar cerrojos normales, este nuevo sello de cera está hecho de un material que debería resistir.

Uno de los nuevos cerrojos más prometedores que se están probando es llamado MQOM. Funciona de forma un poco similar a un rompecabezas gigante y complejo. Para firmar una carta, el remitente utiliza un "testigo" secreto (una clave oculta) para resolver un problema matemático que involucra muchas variables. Para demostrar que resolvió el problema sin mostrar el secreto, utiliza un trucción ingeniosa llamada "MPC-en-la-cabeza" (MPC-in-the-head). Imagina que el remitente finge ser todo un equipo de personas, cada una con una pequeña pieza del secreto. Juegan un juego donde revelan lo justo para demostrar que el equipo resolvió el rompecabezas juntos, pero no lo suficiente como para revelar las piezas reales del secreto. Si las matemáticas resultan correctas, la firma es válida. Nos importa esto porque si estos nuevos cerrojos tienen una grieta oculta, nuestra seguridad digital futura podría desmoronarse antes de que siquiera lleguemos a ella.

Ahora, hablemos de la historia de este artículo. Un investigador llamado José Luis Delgado examinó de cerca una versión específica de este cerrojo MQOM (versión 2.1) y encontró una forma sorprendentemente simple de romperlo. El artículo argumenta que si un atacante obtiene tan solo una firma válida del sistema, puede descubrir la clave secreta completa y falsificar nuevas firmas para cualquier mensaje que desee. Es como si un ladrón viera cómo abres la puerta de tu casa una vez, y ese solo vistazo fuera suficiente para que construyera una llave maestra que abre todas las cerraduras de tu casa.

Así es como funciona el "truco de magia", explicado a través de una historia. Imagina que la clave secreta es un largo y oculto mapa del tesoro. El sistema MQOM esconde este mapa dentro de un árbol gigante hecho de ramas. Cuando firmas un mensaje, el sistema te muestra un camino hacia arriba en el árbol hasta una hoja específica y oculta (un punto en el mapa), pero mantiene la hoja misma cubierta. Sin embargo, también te da un "camino hermano" (sibling path): una lista de las ramas que están junto a la hoja oculta. Debido a cómo está construido el árbol, si conoces las ramas junto a la hoja, puedes averiguar exactamente qué sería la hoja oculta si conocieras un pequeño prefijo del mapa secreto.

El artículo descubrió que el sistema también deja un "compromiso" (commitment), que es como un sobre sellado que contiene la hoja oculta. El investigador se dio cuenta de que, al combinar el camino hermano (las ramas) con el sobre sellado, podrían escribir una única y gigante ecuación. Esta ecuación tiene una incógnita: el pequeño prefijo del mapa secreto. El atacante no necesita adivinar todo el mapa; solo necesita resolver esta única ecuación para encontrar ese pequeño prefijo.

Una vez que encuentran este prefijo, la firma que ya poseen les proporciona un "sufijo de corrección" (correction suffix): una pequeña nota que dice: "Aquí está el resto del mapa para acompañar al prefijo que acabas de encontrar". Al unir el prefijo y la nota, el atacante reconstruye el mapa secreto completo (la clave de firma completa). Con esta clave, puede firmar cualquier mensaje nuevo, y el sistema lo aceptará como real.

El artículo no solo supone que esto funciona; realmente hicieron las matemáticas y el trabajo computacional para probarlo. Calcularon exactamente cuánta potencia de cómputo se necesitaría para resolver esta ecuación para los diferentes niveles de fuerza del cerrojo (llamados Categorías I, III y V). Encontraron que, para las tres categorías, el esfuerzo requerido es menor que el límite de seguridad que el NIST estableció para estos cerrojos.

Para el nivel más fácil (Categoría I), el ataque toma aproximadamente $2^{142.335112}$ operaciones. Para el nivel medio (Categoría III), toma aproximadamente $2^{206.774558}$ o $2^{206.988685}$ operaciones, dependiendo de cuánto escaneen el mapa. Para el nivel más difícil (Categoría V), toma aproximadamente $2^{271.794162}$ operaciones. En cada caso, el número de pasos que el atacante necesita es inferior al número de pasos que el cerrojo debería requerir para ser seguro.

Los investigadores no se detuvieron solo en las matemáticas. Construyeron un programa informático que realmente ejecutó el ataque. Tomaron una firma real, resolvieron la ecuación, recuperaron la clave secreta exacta byte por byte y luego usaron esa clave para firmar un mensaje nuevo. El verificador del sistema revisó la nueva firma y dijo: "¡Sí, esto es válido!". Esto demostró que el ataque funciona en el mundo real, no solo en el papel.

El artículo también analizó si cambiar algunas configuraciones solucionaría el problema. Encontraron que simplemente añadir una "sal" (salt) (un número aleatorio) al proceso cambia los números en la ecuación, pero no detiene el ataque. La ecuación sigue existiendo; solo se ve ligeramente diferente. Para solucionar esto verdaderamente, los diseñadores tendrían que cambiar cómo el camino del árbol se relaciona con el secreto, cómo se compromete la hoja o cómo se genera la nota de corrección.

En resumen, este artículo muestra que el actual cerrojo MQOM tiene un agujero lo suficientemente grande como para atravesarlo caminando. Convierte una sola firma en una llave maestra, permitiendo a un atacante falsificar mensajes con menos esfuerzo del que el cerrojo fue diseñado para resistir. El autor ha compartido su código y resultados para que otros puedan verificar su trabajo, y sugiere que los diseñadores de MQOM necesitan parchear estas partes específicas del sistema antes de que pueda considerarse seguro para el futuro.

Resumen Técnico: Recuperación de la Clave Completa y Falsificación a partir de una Única Firma de MQOM v2.1

Planteamiento del Problema
Este documento presenta un ataque criptanalítico contra MQOM v2.1, un candidato de la Ronda 3 en el proceso de firmas adicionales de NIST. El ataque demuestra que una sola firma aceptada es suficiente para recuperar la clave de firma a largo plazo completa. Una vez recuperada, esta clave permite a un adversario falsificar firmas sobre mensajes nuevos que son aceptadas por el verificador de referencia. La vulnerabilidad surge de la interacción entre los árboles de semillas GGM correlacionados, el mecanismo de compromiso de hoja oculta y el sufijo de corrección del testigo contenido en el transcrito de la firma.

Metodología
El ataque procede mediante una reconstrucción determinista del testigo de la firma basado en los campos públicos del transcrito. La metodología central implica los siguientes pasos:

Derivación de una Ecuación Pública:
La firma revela un camino de hermanos en un árbol de semillas binario correlacionado. Debido a la construcción del árbol (donde el padre es el XOR de sus hijos), la hoja oculta $s_e$ puede expresarse como una función afín del prefijo del testigo a largo plazo $\delta = \text{FirstBits}_\lambda(x)$ y los valores de ruta públicos $A_e$ :
$s_e = \delta \oplus A_e$
La firma también contiene un compromiso de esta hoja oculta: $C_{e,c} = \text{Enc}_{K_{e,c}}(s_e) \oplus \text{LinOrtho}(s_e)$ . Sustituyendo la identidad afín en el compromiso, se obtiene una ecuación pública donde $\delta$ es la única incógnita:
$\text{Enc}_{K_{e,c}}(\delta \oplus A_e) = T_{e,c} \oplus \text{LinOrtho}(\delta)$
Aquí, $K$ , $T$ y $A$ se derivan enteramente del transcrito aceptado.
Enumeración de Candidatos mediante el Recorrido de Estado Retenido:
Para resolver $\delta$ , el atacante debe evaluar la ecuación sobre el dominio de $\lambda$ bits. En lugar de reevaluar el circuito AES/Rijndael fijo para cada candidato, el documento emplea un recorrido de código Gray reflejado. Al retener el estado del circuito entre candidatos adyacentes (que difieren en solo un bit), el atacante actualiza únicamente el cono de dependencia del bit de entrada modificado. Este "cómputo de estado retenido" reduce significamente la cuenta agregada de puertas requerida para el escaneo.
Reconstrucción del Testigo y Recuperación de la Clave:
Para cada candidato $\hat{\delta}$ que satisface la ecuación pública, el atacante utiliza el sufijo de corrección publicado ( $\text{NextBits}_\lambda(\Delta x)$ ) y el camino de hermanos para reconstruir el testigo MQ completo $\hat{x}$ . Se evalúa entonces la relación MQ pública $Q(\hat{x}) = y$ . Si la relación se cumple, $\hat{x}$ se serializa en una clave secreta válida.
Falsificación:
La clave recuperada se utiliza para firmar un nuevo mensaje. El verificador de referencia acepta esta firma, confirmando una recuperación de clave completa y una ruptura de la Existencial Inimputabilidad bajo Ataque de Mensaje Elegido (EUF-CMA).

Contribuciones Clave y Resultados

Recuperación de la Clave Completa desde una Sola Firma: El documento prueba que para las Categorías I, III y V de NIST (usando representantes fast-r3 de F256), una sola firma rompe el esquema.
Evaluación de Costos Concretos: El autor proporciona conteos exactos de puertas booleanas para el ataque, utilizando circuitos de sintaxis fuente generados independientemente para las permutaciones AES/Rijndael.
- Categoría I: $2^{142.335112}$ puertas (Referencia: $2^{143}$ ).
- Categoría III: $2^{206.774558}$ puertas (cobertura media) y $2^{206.988685}$ puertas (cobertura alta) (Referencia: $2^{207}$ ).
- Categoría V: $2^{271.794162}$ puertas (Referencia: $2^{272}$ ).
  Todos los costos de ataque se encuentran estrictamente por debajo de los parámetros de seguridad de NIST correspondientes.
Validación de la Falsificación: Las ejecuciones de referencia recuperaron exitosamente testigos y claves byte-exactos en todas las tres categorías, produciendo falsificaciones de mensajes frescos aceptadas por el verificador de referencia.
Límites Teóricos: El documento establece un límite exacto de momento factorial para el número de falsos positivos (preimágenes de la ecuación adicional) que alcanzan la etapa de validación MQ pública. Bajo el Modelo de Cifrado Ideal (ICM), la probabilidad de exceder 64 validaciones en un dominio completo está acotada por $1/64!$ , asegurando que el ataque siga siendo computacionalmente factible.

Significado y Reclamaciones
El documento afirma que el diseño de la interfaz específica de MQOM v2.1 —específicamente la combinación de la identidad de ruta-a-prefijo, el predicado de compromiso de la hoja oculta y el mapa de corrección-al-testigo— crea un "canal de recuperación de una sola firma".

Independencia del Transcrito: El ataque es aplicable a transcritos generados mediante el Modelo de Oráculo Aleatorio (ROM), el Modelo de Oráculo Aleatorio Cuántico (QROM) o instancias concretas de SHAKE, ya que la ecuación depende solo de campos públicos fijos.
Persistencia de la Limitación de la Sal (Salt-Bound): El autor demuestra que incluso si la expansión de la raíz global está ligada a la sal de la firma (cambiando las constantes públicas $A_e$ y $T_{e,c}$ ), la forma de la ecuación de recuperación permanece sin cambios, preservando el vector de ataque.
Implicaciones de Diseño: El documento concluye que prevenir este ataque requiere modificar los mapas fundamentales: cambiar las identidades de ruta-a-prefijo (por ejemplo, usando aperturas no afines), alterar el predicado de la hoja oculta (por ejemplo, usando un estado secreto por firma) o desacoplar la corrección de la recuperación del testigo a largo plazo.

El autor proporciona un artefacto público que reproduce todos los resultados computacionales y el código fuente para el ataque y la generación de circuitos.

Más como este