💻 computer science

A Generalized PNE Framework: Taking ChaCha Further in Syncopated Rhythm

Este artigo introduz um framework generalizado de Expressões Neutras Probabilísticas (PNE) incorporando técnicas inovadoras como síncope e preservação de transporte para melhorar significativamente ataques de recuperação de chave em ChaCha com número reduzido de rodadas, alcançando o primeiro ataque de chave relacionada em ChaCha8 e quebrando 7,5 rodadas de ChaCha de 256 bits.

Autores originais: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

Publicado 2026-08-31

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Shichang Wang, Meicheng Liu, Shiqi Hou, Chengan Hou, Dongdai Lin

Artigo original sob licença CC BY 4.0 (https://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

Na vasta paisagem digital onde nossas mensagens privadas, transações financeiras e conexões seguras viajam, existe um guardião silencioso conhecido como cifra de fluxo. Pense nisso como uma máquina de alta velocidade que gera um fluxo longo e de aparência aleatória de números para embaralhar dados, garantindo que apenas alguém com a chave secreta correta possa desembaralhá-los e ler a mensagem original. Uma das máquinas mais confiáveis deste tipo é chamada ChaCha. Ela é o motor por trás da segurança de muitos protocolos de internet cotidianos, protegendo tudo, desde sua navegação na web até seus e-mails criptografados. Por ser tão amplamente utilizada, sua força é constantemente testada por criptoanalistas — especialistas que tentam quebrar esses códigos não para roubar segredos, mas para entender seus limites e garantir que permaneçam seguros. O desafio central ao quebrar uma cifra como a ChaCha é que ela é construída sobre uma estrutura que mistura operações simples, como somar números, rotacionar bits e inverter interruptores, de uma forma que rapidamente se torna incrivelmente complexa. Para encontrar uma fraqueza, os pesquisadores devem rastrear como uma pequena mudança na entrada reverbera através dessas operações para ver se ela cria um padrão previsível na saída.

Uma equipe de pesquisadores deu agora um passo significativo à frente no entendimento dos limites da ChaCha ao desenvolver um novo método para analisar como essas reverberações se comportam. Eles focaram em uma técnica específica chamada criptoanálise diferencial, que envolve alimentar a cifra com duas entradas ligeiramente diferentes e observar como as diferenças evoluem. Em tentativas anteriores de quebrar a ChaCha, os pesquisadores tinham que adivinhar um número massivo de chaves possíveis para ver qual delas se ajustava aos padrões observados, um processo que era frequentemente lento demais para ser prático. O novo estudo introduz uma abordagem refinada que utiliza um conceito chamado "sincopação". No contexto desta cifra, essa técnica permite que os pesquisadores identifiquem partes específicas da chave secreta que têm quase nenhuma influência na saída final embaralhada sob certas condições. Ao isolar essas partes não influentes, os pesquisadores podem efetivamente ignorá-las durante os estágios iniciais do ataque, reduzindo drasticamente o número de possibilidades que precisam testar. Isso é semelhante a resolver um quebra-cabeça complexo ao primeiro separar as peças que claramente não pertencem à imagem central, permitindo que você foque sua energia nas peças críticas que realmente importam.

Usando essa técnica de sincopação, combinada com uma nova estratégia para adivinhar os bits restantes da chave, os pesquisadores foram capazes de quebrar versões da ChaCha que anteriormente eram consideradas seguras contra tais ataques. Especificamente, eles demonstraram um ataque bem-sucedido em uma versão da cifra que possui 7,5 rodadas de processamento. Embora a versão completa e padrão da ChaCha utilize 20 rodadas, quebrar 7,5 rodadas é uma conquista notável porque é a primeira vez que um ataque de recuperação de chave foi realizado sobre este número específico de rodadas de forma mais rápida do que simplesmente adivinhar todas as chaves possíveis uma por uma. Os pesquisadores também mostraram que seus métodos poderiam melhorar ataques em versões de 7 rodadas da cifra, tornando-os significativamente mais eficientes do que tentativas anteriores. Além disso, eles aplicaram suas técnicas a uma versão relacionada da cifra chamada ChaCha8, que utiliza apenas 8 rodadas. Em um cenário onde um atacante tem permissão para usar duas chaves que são muito semelhantes entre si, eles encontraram uma maneira de quebrar a ChaCha8, sugerindo que esta variante específica pode não oferecer o nível total de segurança que seus designers pretendiam, caso tal condição venha a ocorrer.

O estudo também analisou uma versão mais curta da cifra que utiliza uma chave de 128 bits em vez da chave padrão de 256 bits. Aqui, os pesquisadores conseguiram quebrar uma versão de 7 rodadas desta cifra mais curta, desde que o último passo do processo de embaralhamento fosse removido. Estes resultados não significam que a versão completa de 20 rodadas da ChaCha usada em aplicações do mundo real, como o seu navegador de internet, esteja atualmente quebrada. A versão completa permanece segura. No entanto, estas descobertas são cruciais porque expandem os limites do que se conhece sobre a mecânica interna da cifra. Ao provar que a cifra pode ser enfraquecida sob condições específicas e controladas, os pesquisadores fornecem um feedback valioso para a comunidade criptográfica. Isso ajuda a garantir que os algoritmos que protegem nossas vidas digitais sejam robustos e que quaisquer vulnerabilidades potenciais sejam identificadas e endereçadas antes que possam ser exploradas no mundo real. O trabalho representa um passo pequeno, mas difícil, à frente no esforço contínuo para compreender e proteger os fundamentos matemáticos da nossa privacidade digital.

Resumo Técnico: Uma Estrutura PNE Generalizada: Levando o ChaCha Além com Ritmo Sincopado

1. Declaração do Problema

O cifrador de fluxo ChaCha, particularmente a variante de 256 bits, é amplamente implementado em protocolos do mundo real, como TLS, SSH e QUIC. Apesar de seu uso extensivo, a margem de segurança do ChaCha com número reduzido de rodadas tem sido objeto de intensa pesquisa criptanalítica. Antes deste trabalho, os ataques de recuperação de chave mais eficazes no ChaCha de 256 bits limitavam-se a 7 rodadas (com complexidades de tempo frequentemente superiores a $2^{220}$ ) ou 7,25 rodadas, e nenhum ataque mais rápido que a força bruta ( $2^{256}$ ) havia sido demonstrado com sucesso para 7,5 rodadas no cenário de chave única. Além disso, a segurança da variante de 8 rodadas (ChaCha8) no cenário de chave relacionada permaneceu amplamente inexplorada com ataques eficientes.

O desafio central na criptoanálise diferencial do ChaCha reside no compromisso entre o número de Bits Neutros Probabilísticos (PNBs) identificados e a correlação da aproximação reversa. Métodos tradicionais frequentemente lutam para encontrar um grande conjunto de PNBs que mantenha simultaneamente uma alta correlação, limitando a eficiência dos ataques de meet-in-the-middle. Adicionalmente, análises anteriores de "chaves fortes" (chaves para as quais não existe um IV adequado para satisfazer as características diferenciais) careciam de uma justificativa teórica abrangente para todos os casos.

2. Metodologia

O artigo introduz uma estrutura refinada para criptoanálise diferencial baseada em Bits Neutros Probabilísticos (PNBs) e a generaliza em uma estrutura baseada em Expressões Neutras Probabilísticas (PNEs). A metodologia consiste em três pilares técnicos primários:

2.1 Técnica de Sincopação para PNBs

Os autores introduzem a "sincopação" para abordar a contradição entre encontrar numerosos PNBs e manter uma alta correlação.

Conceito: A função de aproximação reversa $f$ é decomposta em $f = f_1 \circ f_0$ . A técnica aplica restrições a bits não-PNB específicos (bits restritos) para garantir que a saída da primeira parte ( $f_0$ ) se torne independente dos PNBs (bits de sincopação).
Mecanismo: Ao aproveitar as propriedades de adição e subtração modular em estruturas ARX, os autores derivam condições sob as quais a propagação do carry é controlada. Isso permite que a saída de segmentos específicos seja determinada exclusivamente por valores públicos conhecidos e não-PNBs, efetivamente "sincopando" a dependência dos PNBs desconhecidos.
Resultado: Esta técnica amplifica significativamente a correlação da aproximação reversa. Os autores também fornecem uma ferramenta (Algoritmo 1) para determinar sistematicamente segmentos sincopados lucrativos e um algoritmo guloso (Algoritmo 2) para construir conjuntos otimizados de PNBs Condicionais (CPNBs).

2.2 Estrutura PNE Generalizada

Para melhorar ainda mais a eficiência, o artigo generaliza o conceito de PNB para Expressões Neutras Probabilísticas (PNEs).

Estratégia de Adivinhação de Chave: Em vez de adivinhar diretamente os bits da chave original, o ataque adivinha uma chave equivalente $H(K)$ , onde $H$ é uma função invertível adaptada à estrutura do cifrador (por exemplo, combinações lineares envolvendo rotações e XORs).
Técnica de Preservação de Carry: Uma técnica inovadora é introduzida para adição modular. Ao impor condições lineares aos dados públicos, o vetor de carry da adição modular pode ser determinado sem conhecer os bits de chave desconhecidos (PNBs). Isso simplifica a operação não linear, permitindo que a aproximação ignore as partes desconhecidas da chave enquanto mantém uma alta correlação.
Integração: Esta estrutura permite a descoberta de elementos neutros adicionais (PNEs) em cenários onde PNBs tradicionais são escassos, particularmente nas rodadas tardias ou em diagonais específicas da matriz de estado.

2.3 Análise Diferencial Direta Refinada

O artigo fornece uma análise teórica mais profunda das equações diferenciais que governam a primeira rodada do ChaCha.

Análise de Chave Forte: Os autores oferecem uma explicação teórica abrangente para a existência de "chaves fortes" (chaves onde nenhum IV satisfaz o diferencial), cobrindo todos os oito casos das variáveis de estado interno, enquanto trabalhos anteriores cobriam apenas dois. Eles provam que aproximadamente 29,6875% das chaves são chaves fortes.
Geração de Pares Eficiente: Ao analisar as equações diferenciais, os autores identificam bits de IV específicos que podem ser invertidos para satisfazer as restrições diferenciais com alta probabilidade, reduzindo a complexidade de dados necessária para encontrar pares corretos.

3. Principais Contribuições

Técnica de Sincopação: Um novo método para amplificar as correlações de aproximação reversa explorando as propriedades estruturais de ARX, levando a uma seleção de PNB mais eficiente.
Estrutura PNE Generalizada: Uma extensão do método PNB usando expressões de chave equivalente e uma técnica de preservação de carry, permitindo ataques com menos bits adivinhados e maiores correlações.
Completude Teórica: Uma derivação teórica completa das probabilidades de chave forte para todos os casos diferenciais na primeira rodada, corrigindo e estendendo análises parciais anteriores.
Novos Resultados de Ataque:
- ChaCha256: O primeiro ataque de recuperação de chave em 7,5 rodadas que é mais rápido que a força bruta ( $2^{254,6}$ de complexidade de tempo). Ataques melhorados em 7 e 7,25 rodadas com complexidades reduzidas.
- ChaCha8 (Chave Relacionada): O primeiro ataque de chave relacionada no ChaCha8 de 256 bits (8 rodadas), demonstrando uma complexidade de tempo de $2^{253,3}$ quando um par de chaves com uma diferença fixa é utilizado.
- ChaCha128: Ataques melhorados em 6,5 rodadas e um novo ataque em 7 rodadas (excluindo a última rotação, denotado como $7\ll$ ).

4. Resultados

O artigo apresenta as seguintes complexidades de ataque (Tempo/Dados):

ChaCha256 7 rodadas:
- $2^{210,3}$ tempo / $2^{103,3}$ dados (usando 89 CPNBs).
- $2^{216,9}$ tempo / $2^{68,9}$ dados (usando 74 CPNBs).
- Melhorado para $2^{187,2}$ tempo / $2^{108,2}$ dados usando sincopação em um distinguidor de 5 rodadas (DL).
ChaCha256 7,25 rodadas:
- $2^{220,0}$ tempo / $2^{109}$ dados.
ChaCha256 7,5 rodadas:
- $2^{254,6}$ tempo / $2^{125,3}$ dados. Este é o primeiro ataque em 7,5 rodadas mais rápido que a força bruta ( $2^{256}$ ).
ChaCha256 8 rodadas (Chave Relacionada):
- $2^{253,3}$ tempo / $2^{99,2}$ dados. Isso quebra a afirmação de segurança de 256 bits do ChaCha8 sob o modelo de chave relacionada.
ChaCha128:
- ChaCha6,5: $2^{114,3}$ tempo / $2^{100,3}$ dados.
- ChaCha7 $\ll$ : $2^{122,9}$ tempo / $2^{108,8}$ dados.

A verificação experimental foi conduzida em ChaCha de 5 e 6 rodadas com 64 bits de chave desconhecidos, confirmando as melhorias teóricas de correlação e as probabilidades de sucesso (aprox. 70% para 5 rodadas e 62,5-71,4% para 6 rodadas).

5. Significância e Alegações

O artigo afirma dar um "passo pequeno, mas difícil, à frente" na análise de segurança do ChaCha. Sua principal significância reside em:

Quebrar a Barreira das 7,5 Rodadas: É a primeira vez que um ataque de recuperação de chave em 7,5 rodadas do ChaCha de 256 bits é demonstrado como sendo mais eficiente do que uma busca por força bruta.
Primeiro Ataque de Chave Relacionada no ChaCha8: Demonstra que o ChaCha8 falha em atingir a segurança de 256 bits se um par de chaves com uma diferença específica for permitido, desafiando as suposições de segurança prática da variante de 8 rodadas.
Avanço Metodológico: A introdução da técnica de Sincopação e da Estrutura PNE Generalizada (incluindo preservação de carry e novas estratégias de adivinhação de chave) fornece um conjunto de ferramentas mais poderoso para analisar cifras baseadas em ARX, potencialmente aplicável a outros designs como Salsa ou Chaskey.

Os autores declaram explicitamente que esses ataques não ameaçam o ChaCha de 20 rodadas completo usado em implementações reais, mas eles reduzem significativamente a margem de segurança para variantes de número reduzido de rodadas e destacam fraquezas teóricas no cenário de chave relacionada de 8 rodadas.