💻 computer science

Beyond the Finite Variant Property: Extending Symbolic Diffie-Hellman Group Models (Extended Version)

Este artigo apresenta uma extensão ao provador Tamarin que implementa um procedimento de semidecisão para suportar a teoria completa de Diffie-Hellman, incluindo adição de expoentes, permitindo, desta forma, a verificação simbólica de protocolos criptográficos como ElGamal e MQV que anteriormente estavam fora do alcance das ferramentas de estado da arte.

Autores originais: Sofia Giampietro, Ralf Sasse, David Basin

Publicado 2026-01-30

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Sofia Giampietro, Ralf Sasse, David Basin

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ê é um segurança tentando verificar se um protocolo de aperto de mão secreto entre duas pessoas é verdadeiramente seguro contra um intruso astuto. Por décadas, as ferramentas que usávamos para verificar esses apertos de mão (chamadas de "verificadores de protocolos simbólicos") tinham um ponto cego. Elas conseguiam entender que, se a Pessoa A tem um número secreto $x$ e a Pessoa B tem um número secreto $y$ , elas podem combiná-los para fazer $x \times y$ . Mas elas não conseguiam lidar com a matemática de somar esses números secretos dentro do aperto de mão.

No mundo da criptografia (especificamente em grupos Diffie-Hellman), multiplicar dois números juntos é como somar seus "expoentes" secretos. As ferramentas existentes eram como uma calculadora que conseguia multiplicar, mas que tinha o botão "+" quebrado. Isso significava que elas não podiam analisar totalmente protocolos complexos como a criptografia ElGamal ou a troca de chaves MQV, que dependem dessa adição "quebrada".

Aqui está o que os autores deste artigo fizeram, explicado de forma simples:

1. O Problema: O "Quebra-Cabeça Irresolúvel"

Os autores explicam que tentar provar matematicamente que esses protocolos são seguros usando métodos padrão é como tentar resolver um quebra-cabeça onde as peças podem mudar de forma infinitamente. A matemática por trás desses grupos envolve regras para adição, multiplicação e distribuição (como $a(b+c) = ab + ac$). Quando você mistura todas essas regras, o computador fica preso em um loop infinito tentando descobrir se duas expressões complexas são iguais. É um problema de "decidibilidade" — o computador não pode garantir que terminará o cálculo.

2. A Solução: Uma Estratégia de Detetive de Duas Etapas

Em vez de tentar resolver todo o quebra-cabeça infinito de uma só vez, os autores (Sofia Giampietro, Ralf Sasse e David Basin) criaram uma nova estratégia para o Tamarin prover (uma ferramenta de análise de segurança de alto nível): Eles dividiram o trabalho em duas fases distintas:

Fase 1: A Verificação do "Esqueleto" (Simbólica)
Primeiro, eles ignoram a matemática complexa de somar e multiplicar. Eles olam para o "esqueleto" da mensagem. Eles perguntam: "Os blocos básicos de construção desta mensagem existem?" Eles usam as ferramentas de unificação existentes e rápidas para verificar se os ingredientes secretos estão lá.
- Analogia: Imagine verificar se uma receita de bolo tem farinha, ovos e açúcar. Você não se preocupa com como eles se misturam ainda; você apenas verifica se os ingredientes estão sobre a mesa.
Fase 2: A Verificação da "Mistura" (Algébrica)
Uma vez que sabem que os ingredientes estão lá, eles mudam para uma ferramenta diferente. Eles tratam os números secretos não como símbolos, mas como variáveis algébricas (como $x$ e $y$ na matemática do ensino médio). Eles usam a eliminação de Gauss (um método para resolver sistemas de equações lineares) para ver se o intruso poderia ter misturado esses ingredientes para criar o segredo final.
- Analogia: Agora que você tem a farinha e os ovos, você usa uma fórmula matemática para calcular: "Se o intruso tem 2 xícaras de farinha e 1 ovo, ele consegue assar exatamente o bolo que estamos procurando?"

3. A Regra de "Não-Cancelamento"

Existe um porém. Este método funciona melhor se os ingredientes secretos não se cancelarem mutuamente. Por exemplo, se a receita exige que você adicione um número secreto e depois imediatamente subtraia o mesmo número, o resultado é zero (ou nada). Os autores assumem que, em um protocolo seguro, as partes secretas não desaparecem simplesmente no nada. Se elas desaparecerem, a ferramenta sinaliza para um humano verificar manualmente.

4. O Que Eles Alcançaram

Ao combinar essas duas etapas, eles estenderam a ferramenta Tamarin para lidar com a matemática "total" de Diffie-Hellman pela primeira vez. Eles testaram isso em dois protocolos famosos:

Criptografia ElGamal: Eles provaram com sucesso que este método de criptografia é seguro, mesmo quando o intruso pode usar todos os truques matemáticos avançados. Esta é a primeira vez que uma ferramenta de computador verificou automaticamente esta propriedade de segurança específica.
Troca de Chaves MQV: Eles testaram um protocolo mais complexo. A ferramenta encontrou rapidamente um "ataque" conhecido (uma maneira de um intruso enganar os usuários). Isso provou que a ferramenta funciona porque redescobriu uma falha que os humanos já conheciam.

Resumo

Pense nos autores como alguém que está atualizando um scanner de segurança. O scanner antigo conseguia ver apenas o contorno de um pacote. O novo scanner consegue ver o contorno e também realizar uma análise química do conteúdo para ver se eles podem ser misturados para criar uma bomba. Eles não apenas encontraram uma nova maneira de olhar; eles construíram uma ferramenta que agora pode verificar protocolos de segurança complexos do mundo real que eram matematicamente difíceis demais para computadores lidarem anteriormente.

Conceito Chave: Eles construíram uma ponte entre a lógica simbólica (verificar se as peças existem) e a álgebra (verificar se as peças podem ser combinadas), permitindo que computadores finalmente verifiquem protocolos de segurança que usam todo o poder dos grupos Diffie-Hellman.

Resumo Técnico: Além da Propriedade de Variante Finita: Estendendo Modelos de Grupos Diffie-Hellman Simbólicos

Definição do Problema
Os grupos Diffie-Hellman (DH) são fundamentais para os protocolos criptográficos modernos, mas os verificadores de protocolos simbólicos de última geração (como Tamarin, ProVerif e Maude-NPA) carecem de suporte total para suas propriedades algébricas. Embora essas ferramentas possam modelar a exponenciação e a multiplicação de expoentes, elas geralmente não conseguem modelar a multiplicação de elementos de grupo, o que corresponde à adição de expoentes. Essa limitação surge porque a teoria equacional que descreve grupos DH completos (envolvendo distributividade, associatividade e comutatividade) torna o problema de unificação indecidível e infinitário. Consequentemente, as ferramentas existentes não podem raciocinar sobre protocolos que constroem elementos de grupo compostos (ex: criptografia ElGamal ou troca de chaves MQV), onde o adversário ou as partes honestas utilizam a estrutura completa de campos dos expoentes.

Metodologia
Os autores propõem um procedimento de semidecisão para verificar propriedades de segurança para protocolos que utilizam a estrutura completa do grupo DH. A abordagem integra o raciocínio simbólico com métodos algébricos, implementados como uma extensão ao provador Tamarin.

Fundamentação Teórica: O trabalho baseia-se no sistema de reescrita proposto por Dougherty e Guttman, que aproxima campos usando um sistema de reescrita convergente ( $\to_{DH}$ ) módulo associatividade e comutatividade (AC). Este sistema permite a definição de formas normais para termos.
Suposição de Não-Cancelamento: A abordagem baseia-se em duas condições primárias:
- C1: Todos os elementos de grupo pertencem a um único grupo fixo com um gerador comum.
- C2 (Não-Cancelamento): As propriedades de segurança envolvem termos onde os subtermos não se cancelam mutuamente (ou seja, não podem ser reduzidos ao elemento identidade 1 ou 0). Se esta condição falhar, a ferramenta ainda poderá encontrar ataques válidos, mas uma prova de segurança exige verificação manual de que os termos específicos não se cancelam.
Resolução de Restrições Híbrida: A inovação central é um algoritmo de resolução de restrições modificado que evita a unificação direta para termos DH. Em vez disso, emprega um processo de duas etapas:
- Unificação Simbólica (Teoria Simplificada): O algoritmo primeiro unifica termos dentro de uma teoria equacional simplificada ( $\varepsilon_{simp}$ ) que exclui o operador de multiplicação de grupo. Isso permite o uso dos algoritmos de unificação existentes do Tamarin para combinar termos raiz.
- Reconstrução Algébrica: Uma vez que os termos raiz são combinados, o algoritmo interpreta os termos simbólicos como objetos algébricos (polinômios sobre um campo). Ele classifica os expoentes como "vazados" (conhecidos pelo adversário) ou "secretos". Usando eliminação Gaussiana (ou potencialmente o algoritmo de Buchberger para casos não lineares), o sistema resolve se os expoentes secretos podem ser combinados com os vazados para reconstruir o termo alvo.
Função Indicadora: Para determinar se um termo é dedutível, os autores definem uma função "indicadora". Esta identifica os componentes secretos mínimos necessários para construir um termo. Se qualquer indicador não puder ser reconstruído a partir do conhecimento do adversário, o termo é considerado indedutível.
Modelagem Adversária: A extensão suporta um adversário Dolev-Yao ativo capaz de aplicar todos os operadores DH. O resolvedor de restrições lida com a dedução adversária verificando se o adversário pode satisfazer as equações lineares derivadas da interpretação polinomial dos termos.

Principais Contribuições

Primeira Ferramenta Automatizada para Teoria DH Completa: Este trabalho apresenta a primeira implementação de uma ferramenta de verificação automatizada capaz de modelar e raciocinar sobre protocolos que utilizam a estrutura completa do grupo Diffie-Hellman, incluindo a multiplicação de elementos de grupo.
Correção e Completude: Os autores provam que a relação de resolução de restrições estendida é correta (sound) e completa (sob a suposição de não-cancelamento). Se o Tamarin encontrar um ataque, é uma execução válida; se ele provar a segurança, não existe execução violadora dentro do modelo simbólico.
Integração com Tamarin: A abordagem é implementada modificando o algoritmo de resolução de restrições do Tamarin, adicionando novas regras ( $C@, C_{Prem}, C=, C_{var}$ ) que substituem as regras de unificação padrão para termos ordenados por DH por etapas de resolução algébrica.
Tratamento de Teorias Mistas: O método suporta a combinação da teoria DH completa com outras teorias equacionais definidas pelo usuário (ex: criptografia simétrica, pares) através da "limpeza" de termos combinados — substituindo subtermos DH por variáveis frescas para unificação e, em seguida, reintroduzindo restrições DH para resolução algébrica.

Resultos e Estudos de Caso
Os autores avaliaram a implementação em vários protocolos:

Criptografia ElGamal: A ferramenta provou com sucesso a executabilidade e o segredo do esquema de criptografia ElGamal. Notavelmente, esta é a primeira vez que o ElGamal foi verificado automaticamente no modelo simbólico com suporte total a DH. A ferramenta também identificou corretamente a falta de segredo quando o iniciador não é autenticado.
Troca de Chaves MQV: A ferramenta foi utilizada para analisar o protocolo MQV. Ela redescobriu com sucesso o conhecido ataque de "chave desconhecida compartilhada" (unknown key-share) de Kaliski, demonstrando a capacidade da ferramenta de encontrar ataques complexos envolvendo elementos de grupo compostos.
Avaliação de Benchmark: A extensão foi testada em 20 modelos existentes do Tamarin (incluindo WireGuard e vários protocolos de troca de chaves) que anteriormente utilizavam uma teoria DH restrita. Os resultados mostraram que a extensão produz os mesmos vereditos de segurança que a teoria restrita para esses protocolos, embora com um tempo de execução aumentado devido à complexidade do espaço de busca estendido.

Significância
O artigo afirma que este trabalho representa um avanço significativo na verificação de protocolos simbólicos. Ao superar a indecidibilidade da unificação em teorias DH completas, os autores permitem a verificação automatizada de uma classe mais ampla de protocolos criptográficos que dependem da estrutura algébrica completa dos grupos Diffie-Hellman. A capacidade de verificar automaticamente o ElGamal e redescobrir ataques de MQV em poucos minutos demonstra a viabilidade, escalabilidade e eficiência da abordagem, preenchendo a lacuna entre propriedades algébricas teóricas e análise de segurança automatizada prática.

1. O Problema: O "Quebra-Cabeça Irresolúvel"

2. A Solução: Uma Estratégia de Detetive de Duas Etapas

3. A Regra de "Não-Cancelamento"

4. O Que Eles Alcançaram

Resumo

Mais como este