A Novel Memory-Efficient MitM Attack on Ascon-Hash

No mundo digital, a segurança muitas vezes depende de um equilíbrio delicado entre força e eficiência. Para os bilhões de pequenos dispositivos, alimentados por bateria, que compõem a Internet das Coisas — sensores em fábricas, medidores inteligentes e monitores médicos — o poder computacional é escasso, e a memória é ainda mais escassa. Esses dispositivos precisam de ferramentas criptográficas que sejam robustas o suficiente para manter os dados seguros, mas leves o suficiente para rodar sem esgotar uma bateria ou preencher um chip minúsculo. O Ascon é uma solução líder para esse desafio, uma família de métodos de criptografia e hashing projetados especificamente para esses ambientes de recursos limitados. Para garantir que o Ascon permaneça seguro, pesquisadores constantemente o testam contra ataques sofisticados, tentando encontrar o caminho mais curto para quebrar seu código. Uma das ferramentas mais poderosas nesse arsenal é o ataque de "encontro no meio" (meet-in-the-middle), uma estratégia onde um atacante trabalha de trás para frente a partir do resultado final e de frente para trás a partir do ponto inicial, esperando se encontrar no meio com uma correspondência. No entanto, essa estratégia tradicionalmente exigia uma quantidade massiva de memória para armazenar os milhões de etapas intermediárias, um requisito que frequentemente tornava o ataque impraticável para os próprios dispositivos que o Ascon visa proteger.

Uma equipe de pesquisadores desenvolveu agora uma nova maneira de executar esse ataque que reduz drasticamente a memória necessária, tornando o teste muito mais realista para sistemas leves. Em um estudo focado na função Ascon-Hash, os autores demonstraram que poderiam realizar o ataque em uma versão reduzida do sistema usando significamente menos espaço de armazenamento do que o anteriormente considerado possível, sem sacrificar a velocidade do cálculo. Ao tratar o problema como um quebra-cabeça complexo de restrições lógicas, eles encontraram uma maneira de filtrar dados desnecessários antes mesmo que precisassem ser armazenados. O trabalho deles mostra que, para uma versão de três rodadas do hash, a memória necessária pode ser reduzida de uma complexidade de 2^24 para 2^14. Para uma versão de quatro rodadas, a redução é ainda mais dramática, baixando o requisito de uma complexidade de 2^34 para 2^12. Essa conquista não apenas diminui o custo do ataque; ela fornece uma imagem mais nítida e precisa de quão seguro o Ascon realmente é ao enfrentar um adversário com recursos limitados.

Os pesquisadores começaram reconhecendo que tentativas anteriores de quebrar o Ascon usando ferramentas de busca automatizada haviam atingido um muro de uso de memória. Embora os computadores tivessem se tornado mais rápidos em encontrar o caminho certo através da criptografia, o processo ainda exigia que o atacante mantivesse uma vasta biblioteca de resultados intermediários na memória, muito parecido com tentar resolver um labirinto anotando cada curva que você faz em um pedaço de papel separado. Se o labirinto for grande o suficiente, você fica sem papel muito antes de encontrar a saída. A equipe percebeu que a chave para resolver isso não era apenas encontrar o caminho mais rápido, mas ser mais inteligente sobre o que anotar. Eles usaram um método chamado resolução de satisfatibilidade (satisfiability solving), que é essencialmente uma forma de pedir a um computador para encontrar um conjunto de condições que torne uma afirmação lógica complexa verdadeira. Isso permitiu que mapeassem os pontos específicos no processo de criptografia onde os cálculos de ida e volta poderiam potencialmente se encontrar.

Uma vez mapeados esses potenciais pontos de encontro, os pesquisadores aplicaram uma série de filtros algébricos para limpar os dados. Eles notaram que muitas das restrições que governam a criptografia podiam ser separadas em relações lineares simples e outras não lineares mais complexas. As partes lineares eram diretas; elas podiam ser simplificadas usando técnicas matemáticas padrão para remover informações redundantes, efetivamente encolhendo a lista de possibilidades que o computador precisava rastrear. As partes não lineares eram mais complicadas, mas a equipe desenvolveu um método para rearranjá-las em um formato triangular, permitindo resolver certas variáveis com base em outras. Esse processo eliminou a necessidade de calcular e armazenar explicitamente essas variáveis específicas, reduzindo ainda mais a pegada de memória.

A inovação mais significativa veio na forma como lidaram com as restrições complexas restantes que não podiam ser facilmente simplificadas. Em vez de armazenar cada resultado possível, os pesquisadores usaram essas restrições restantes para criar um "índice residual", uma espécie de etiqueta ou rótulo digital. À medida que geravam a lista de potenciais caminhos de ida, eles atribuíam a cada um uma etiqueta baseada em suas propriedades específicas. Crucialmente, eles perceberam que o caminho de volta só poderia corresponder a um caminho de ida se suas etiquetas fossem compatíveis. Isso significava que o computador não precisava manter todos os caminhos de ida na memória; ele só precisava manter aqueles que carregavam uma etiqueta que o caminho de volta pudesse possivelmente alcançar. Nas configurações específicas que testaram, esse filtro foi tão eficaz que reduziu toda a lista de caminhos de ida necessários a um único e minúsculo balde de dados.

Os resultados dessa nova abordagem foram impressionantes. Quando aplicada a uma versão de três rodadas do Ascon-Hash, o método manteve a mesma velocidade de ataques anteriores, mas reduziu o requisito de memória de uma complexidade de 2^24 para 2^14. Para a versão de quatro rodadas, a redução foi ainda mais profunda, cortando a necessidade de memória de uma complexidade de 2^34 para 2^12 em comparação ao melhor método anterior. Os pesquisadores verificaram que esse filtro agressivo não descartou acidentalmente soluções válidas; eles checaram que os dados restantes ainda satisfaziam todas as regras originais do sistema de criptografia. O estudo confirma que, ao analisar cuidadosamente a estrutura da criptografia e aplicar esses filtros lógicos, é possível realizar testes de segurança profundos com uma fração dos recursos anteriormente considerados necessários. Este trabalho sugere que a margem de segurança do Ascon em ambientes de recursos limitados está sendo avaliada com maior precisão, garantindo que os padrões criptográficos que protegem nosso mundo conectado sejam tão robustos quanto aparentam ser.