Um modelo automatizado para ataques diferenciais meet-in-the-middle em cifras AndRX

Por que esta pesquisa importa

Cada vez que usamos um smartphone, pagamos online ou conectamos um dispositivo médico, pequenos cadeados digitais chamados cifras de bloco protegem nossos dados. Especialistas em segurança tentam constantemente quebrar esses cadeados para projetar outros mais seguros. Este artigo apresenta uma nova forma de automatizar um estilo poderoso de ataque a uma família popular de cifras leves, ajudando pesquisadores a testar quão fortes esses cadeados digitais realmente são.

Como funciona a criptoanálise moderna

Cifras de bloco modernas embaralham dados em muitos passos pequenos, ou rodadas, controlados por uma chave secreta. Para avaliar se uma cifra é segura, criptanalistas procuram por padrões que não deveriam existir se o sistema se comportasse como aleatoriedade pura. Duas ferramentas clássicas são a criptoanálise diferencial, que rastreia como pequenas mudanças na entrada se propagam até a saída, e ataques meet-in-the-middle, que calculam a partir de ambas as extremidades da cifra e buscam coincidências no meio. Cada ferramenta isolada tem limites, mas combiná‑las cria uma sonda mais precisa da estrutura da cifra.

Combinando duas ideias de ataque

O estudo foca numa técnica híbrida chamada ataque diferencial meet-in-the-middle. Aqui, a cifra é dividida em três partes: uma seção de entrada, uma seção intermediária e uma seção de saída. No meio, o atacante procura um “diferencial distinguível”, um padrão de diferenças de entrada e saída que ocorre com mais frequência do que o acaso através de várias rodadas. Em torno desse núcleo, o atacante parcialmente encripta desde o início e parcialmente decripta desde o fim, adivinhando apenas pedaços selecionados da chave. Quando as duas direções se encontram no mesmo estado interno, os palpites têm maior probabilidade de corresponder à chave real, o que reduz o espaço de busca.

Transformando um ofício manual em uma ferramenta automatizada

Projetar tais ataques combinados manualmente é extremamente complicado, especialmente para cifras orientadas a bits cujo estado interno pode ter 64, 96 ou 128 bits de largura. Os autores constroem um arcabouço automatizado que usa programação por restrições, um método para descrever condições lógicas complexas de modo que um resolvedor possa explorar todas as possibilidades válidas. Primeiro, eles codificam como diferenças se movem através dos blocos básicos de uma cifra baseados em operações AND, rotação e XOR, uma família conhecida como designs AndRX. Em seguida, modelam quais bits de chave influenciam cada estágio e quantos desses bits precisam de fato ser adivinhados. O resolvedor busca por muitas maneiras de cortar a cifra em seções de entrada, meio e saída, escolhendo o arranjo que minimiza o esforço total do ataque.

Truques extras para reduzir o espaço de chaves

Além do modelo base, o arcabouço acrescenta dois truques de otimização voltados a cifras AndRX no estilo Feistel, como SIMON e Simeck. O primeiro, chamado ideia de subchave equivalente, desloca matematicamente partes das chaves de rodada para frente ou para trás de modo que vários bits de chave diferentes se comportem como se fossem o mesmo. Isso reduz o número de bits independentes que o atacante precisa considerar. O segundo, adivinhação seletiva de chave, estuda como a operação NÃO linear AND usa suas entradas, e mostra que sob certas condições um bit adivinhado pode substituir dois. Os autores também descrevem, mas ainda não automatizam completamente, duas melhorias adicionais: particionamento paralelo, que pode adicionar uma rodada extra ao ataque sem tempo adicional, e um truque de redução de dados que diminui quantas mensagens escolhidas são necessárias.

O que a ferramenta revela sobre cifras reais

Para testar sua abordagem, os pesquisadores aplicam seu modelo automatizado a todas as versões padrão das cifras leves SIMON e Simeck, candidatas ao uso em dispositivos limitados como sensores e controladores embarcados. Para cada variante, a ferramenta encontra um ataque diferencial meet-in-the-middle e estima seus custos em dados, tempo e memória. Em muitos casos, esses ataques alcançam mais rodadas do que meet-in-the-middle anteriores ou técnicas relacionadas, e frequentemente também superam ataques diferenciais impossíveis e de correlação zero anteriores em termos do número de rodadas cobertas. Por exemplo, a ferramenta produz ataques em até 51 rodadas de uma versão de 128 bits do SIMON com chave de 256 bits, estendendo o alcance de métodos anteriores enquanto mantém o trabalho abaixo de uma busca exaustiva por todas as chaves.

Panorama geral para a criptografia futura

Para não especialistas, a mensagem principal não é que SIMON ou Simeck estejam “quebrados” em cenários práticos, mas que ferramentas automatizadas estão se tornando poderosas o suficiente para explorar fraquezas sutis que seriam muito difíceis de encontrar manualmente. O arcabouço introduzido aqui é genérico ao nível de bit e, em princípio, pode ser adaptado a outras famílias de cifras. Ao ajudar projetistas a testar rapidamente como novos algoritmos resistem a ataques combinados avançados, tais ferramentas apoiam o objetivo de longo prazo de construir criptografia que permaneça robusta mesmo à medida que as técnicas de análise se tornam mais sofisticadas.

Citação: Chakraborty, D., Sahoo, S., Nguyen, P.H. et al. An automated model for differential meet in the middle attacks on AndRX ciphers. Sci Rep 16, 14773 (2026). https://doi.org/10.1038/s41598-026-41390-w

Palavras-chave: cifragem de bloco criptanálise, differential meet in the middle, cifra SIMON, cifra Simeck, programação por restrições