💻 computer science

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

Este artigo apresenta um ataque de recuperação de chave completa e de falsificação contra o candidato de assinatura da rodada 3 do NIST, MQOM v2.1, demonstrando que uma única assinatura aceita é suficiente para derivar a chave secreta completa e falsificar novas assinaturas, com custos computacionais abaixo dos parâmetros de segurança do NIST para todas as categorias.

Autores originais: José Luis Delgado

Publicado 2026-08-11

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: José Luis Delgado

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você esteja tentando enviar uma mensagem secreta para um amigo, mas vive em um mundo onde computadores super-rápidos (chamados de computadores quânticos) podem um dia existir. Essas máquinas futuras poderiam quebrar a maioria das fechaduras que usamos hoje para manter nossos segredos seguros. Para se preparar para isso, cientistas estão construindo novas fechaduras digitais superfortes chamadas "assinaturas pós-quânticas". Pense nelas como um tipo especial de selo de cera em uma carta; mesmo que um ladrão tenha um martelo mágico capaz de esmagar fechaduras normais, este novo selo de cera é feito de um material que deve resistir.

Uma das novas fechaduras mais promissoras sendo testadas é chamada MQOM. Ela funciona de forma semelhante a um quebra-cabeça gigante e complexo. Para assinar uma carta, o remetente usa uma "testemunha" secreta (uma chave oculta) para resolver um problema matemático envolvendo muitas variáveis. Para provar que resolveu o problema sem mostrar o segredo, eles usam um truque inteligente chamado "MPC-in-the-head" (MPC na cabeça). Imagine o remetente fingindo ser uma equipe inteira de pessoas, cada uma segurando uma pequena parte do segredo. Eles jogam um jogo onde revelam apenas o suficiente para provar que a equipe resolveu o quebra-cabeça junta, mas não o suficiente para revelar as peças reais do segredo. Se a matemática estiver correta, a assinatura é válida. Nós nos importamos com isso porque, se essas novas fechaduras tiverem uma rachadura oculta, nossa segurança digital futura poderá desmoronar antes mesmo de chegarmos lá.

Agora, vamos falar sobre a história deste artigo. Um pesquisador chamado José Luis Delgado examinou de perto uma versão específica desta fechadura MQOM (versão 2.1) e encontrou uma maneira surpreendentemente simples de quebrá-la. O artigo argumenta que, se um atacante obtiver apenas uma assinatura válida do sistema, ele pode descobrir toda a chave secreta e forjar novas assinaturas para quaisquer mensagens que desejar. É como se um ladrão visse você abrir a porta da sua frente uma única vez, e esse único olhar fosse o suficiente para ele construir uma chave mestra que abre todas as fechaduras da sua casa.

Eis como o "truque de mágica" funciona, explicado através de uma história. Imagine que a chave secreta é um longo mapa do tesouro oculto. O sistema MQOM esconde esse mapa dentro de uma árvore gigante feita de galhos. Quando você assina uma mensagem, o sistema mostra a você um caminho subindo a árvore até uma folha específica e oculta (um ponto no mapa), mas mantém a folha em si coberta. No entanto, ele também lhe dá um "caminho irmão" — uma lista dos galhos ao lado da folha oculta. Devido à forma como a árvore é construída, se você souber os galhos ao lado da folha, pode descobrir exatamente o que a folha oculta seria se você conhecesse um pequeno prefixo do mapa secreto.

O artigo descobriu que o sistema também deixa um "compromisso" (commitment), que é como um envelope lacrado contendo a folha oculta. O pesquisador percebeu que, ao combinar o caminho irmão (os galhos) com o envelope lacrado, eles poderiam escrever uma única equação gigante. Esta equação tem uma incógnita: o pequeno prefixo do mapa secreto. O atacante não precisa adivinhar o mapa inteiro; ele só precisa resolver esta única equação para encontrar esse pequeno prefixo.

Uma vez que encontram esse prefixo, a assinatura que já possuem fornece um "sufixo de correção" — uma pequena nota que diz: "Aqui está o resto do mapa para acompanhar o prefixo que você acabou de encontrar". Ao juntar o prefixo e a nota, o atacante reconstrói o mapa secreto inteiro (a chave de assinatura completa). Com essa chave, ele pode assinar qualquer nova mensagem, e o sistema a aceitará como real.

O artigo não apenas supõe que isso funciona; eles realmente fizeram a matemática e o trabalho computacional para provar isso. Eles calcularam exatamente quanta capacidade de computação seria necessária para resolver essa equação para os diferentes níveis de força da fechadura (chamados de Categorias I, III e V). Eles descobriram que, para todas as três categorias, o esforço necessário é menor do que o limite de segurança que o NIST estabeleceu para essas fechaduras.

Para o nível mais fácil (Categoria I), o ataque leva cerca de $2^{142.335112}$ operações. Para o nível médio (Categoria III), leva cerca de $2^{206.774558}$ ou $2^{206.988685}$ operações, dependendo de quanto do mapa eles escaneiam. Para o nível mais difícil (Categoria V), leva cerca de $2^{271.794162}$ operações. Em todos os casos, o número de etapas que o atacante precisa realizar é inferior ao número de etapas que a fechadura deveria exigir para ser segura.

Os pesquisadores não pararam apenas na matemática. Eles construíram um programa de computador que realmente executou o ataque. Eles pegaram uma assinatura real, resolveram a equação, recuperaram a chave secreta exata byte por byte e, em seguida, usaram essa chave para assinar uma nova mensagem. O verificador do sistema checou a nova assinatura e disse: "Sim, isto é válido!". Isso provou que o ataque funciona no mundo real, não apenas no papel.

O artigo também analisou se mudar algumas configurações resolveria o problema. Eles descobriram que simplesmente adicionar um "sal" (um número aleatório) ao processo altera os números na equação, mas não impede o ataque. A equação ainda existe; ela apenas parece ligeiramente diferente. Para realmente consertar isso, os designers teriam que mudar como o caminho da árvore se relaciona com o segredo, como a folha é comprometida ou como a nota de correção é gerada.

Em resumo, este artigo mostra que a versão atual da fechadura MQOM tem um buraco grande o suficiente para se atravessar caminhando. Ele transforma uma única assinatura em uma chave mestra, permitindo que um atacante forje mensagens com menos esforço do que a fechadura foi projetada para suportar. O autor compartilhou seu código e resultados para que outros possam verificar seu trabalho, e sugere que os designers do MQOM precisam corrigir essas partes específicas do sistema antes que ele possa ser considerado seguro para o futuro.

Resumo Técnico: Recuperação de Chave Completa e Falsificação a partir de uma Única Assinatura MQOM v2.1

Declaração do Problema
Este artigo apresenta um ataque criptanalítico ao MQOM v2.1, um candidato da Rodada-3 no processo de assinaturas adicionais do NIST. O ataque demonstra que uma única assinatura aceita é suficiente para recuperar a chave de assinatura de longo prazo completa. Uma vez recuperada, esta chave permite que um adversário falsifique assinaturas em novas mensagens que são aceitas pelo verificador de referência. A vulnerabilidade surge da interação entre as árvores de sementes (seeds) GGM correlacionadas, o mecanismo de compromisso de folha oculta e o sufixo de correção de testemunha contido no transcrito da assinatura.

Metodologia
O ataque procede através de uma reconstrução determinística da testemunha de assinatura com base nos campos públicos do transcrito. A metodologia central envolve as seguintes etapas:

Derivação de uma Equação Pública:
A assinatura revela um caminho de irmãos em uma árvore de sementes binária correlacionada. Devido à construção da árvore (onde um pai é o XOR de seus filhos), a folha oculta $s_e$ pode ser expressa como uma função afim do prefixo da testemunha de longo prazo $\delta = \text{FirstBits}_\lambda(x)$ e dos valores de caminho públicos $A_e$ :
$s_e = \delta \oplus A_e$
A assinatura também contém um compromisso com esta folha oculta: $C_{e,c} = \text{Enc}_{K_{e,c}}(s_e) \oplus \text{LinOrtho}(s_e)$ . Substituindo a identidade afim no compromisso, obtém-se uma equação pública onde $\delta$ é a única incógnita:
$\text{Enc}_{K_{e,c}}(\delta \oplus A_e) = T_{e,c} \oplus \text{LinOrtho}(\delta)$
Aqui, $K$ , $T$ e $A$ são derivados inteiramente do transcrito aceito.
Enumeração de Candidatos via Travessia de Estado Retido:
Para resolver por $\delta$ , o atacante deve avaliar a equação sobre o domínio $\lambda$ -bit. Em vez de reavaliar o circuito fixo AES/Rijndael para cada candidato, o artigo emprega uma travessia de código Gray refletido. Ao reter o estado do circuito entre candidatos adjacentes (que diferem por apenas um bit), o atacante atualiza apenas o cone de dependência do bit de entrada alterado. Esta "computação de estado retido" reduz significativamente a contagem agregada de portas necessária para a varredura.
Reconstrução da Testemunha e Recuperação de Chave:
Para cada candidato $\hat{\delta}$ que satisfaz a equação pública, o atacante utiliza o sufixo de correção publicado ( $\text{NextBits}_\lambda(\Delta x)$ ) e o caminho de irmãos para reconstruir a testemunha MQ completa $\hat{x}$ . A relação MQ pública $Q(\hat{x}) = y$ é então avaliada. Se a relação for válida, $\hat{x}$ é serializado em uma chave secreta válida.
Falsificação:
A chave recuperada é usada para assinar uma nova mensagem. O verificador de referência aceita esta assinatura, confirmando uma recuperação de chave completa e uma quebra de Existencialmente Não-Falsificabilidade sob Ataque de Mensagem Escolhida (EUF-CMA).

Contribuições Principais e Resultados

Recuperação de Chave Completa a partir de Uma Assinatura: O artigo prova que para as Categorias NIST I, III e V (usando representantes fast-r3 F256), uma única assinatura quebra o esquema.
Avaliação de Custo Concreta: O autor fornece contagens exatas de portas booleanas para o ataque, utilizando circuitos de sintaxe de fonte gerados independentemente para as permutações AES/Rijndael.
- Categoria I: $2^{142.335112}$ portas (Referência: $2^{143}$ ).
- Categoria III: $2^{206.774558}$ portas (meia cobertura) e $2^{206.988685}$ portas (alta cobertura) (Referência: $2^{207}$ ).
- Categoria V: $2^{271.794162}$ portas (Referência: $2^{272}$ ).
  Todos os custos de ataque situam-se estritamente abaixo dos benchmarks de segurança do NIST correspondentes.
Validação de Falsificação: Execuções de referência recuperaram com sucesso testemunhas e chaves byte-exatas em todas as três categorias, produzindo falsificações de novas mensagens aceitas pelo verificador de referência.
Limites Teóricos: O artigo estabelece um limite de momento fatorial exato para o número de falsos positivos (pré-imagens de equações adicionais) que atingem a etapa de validação MQ pública. Sob o Modelo de Cifra Ideal (ICM), a probabilidade de exceder 64 validações em um domínio completo é limitada a $1/64!$ , garantindo que o ataque permaneça computacionalmente viável.

Significado e Alegações
O artigo alega que o design da interface específica do MQOM v2.1 — especificamente a combinação da identidade caminho-para-prefixo, o predicado de compromisso da folha oculta e o mapa de correção-para-testemunha — cria um "canal de recuperação de uma assinatura".

Independência de Transcrito: O ataque aplica-se a transcritos gerados via Modelo de Oráculo Aleatório (ROM), Modelo de Oráculo Aleatório Quântico (QROM) ou instanciamções concretas de SHAKE, pois a equação depende apenas de campos públicos fixos.
Persistência do Limite de Sal (Salt-Bound): O autor demonstra que mesmo se a expansão da raiz global estiver vinculada ao sal da assinatura (alterando as constantes públicas $A_e$ e $T_{e,c}$ ), a forma da equação de recuperação permanece inalterada, preservando o vetor de ataque.
Implicações de Design: O artigo conclui que prevenir este ataque requer a modificação dos mapas fundamentais: alterar a identidade caminho-para-prefixo (ex: usando aberturas não-afins), alterar o predicado da folha oculta (ex: usando estado secreto por assinatura) ou desacoplar a correção da recuperação da testemunha de longo prazo.

O autor fornece um artefato público reproduzindo todos os resultados computacionais e o código-fonte para o ataque e geração de circuitos.

Mais como este