Um novo ataque eliminou facilmente um potencial algoritmo de criptografia

Apr 14, 2023

Dan Goodin, Ars Technica

Na campanha contínua do governo dos EUA para proteger os dados na era dos computadores quânticos, um novo e poderoso ataque que usou um único computador tradicional para quebrar completamente um candidato da quarta rodada destaca os riscos envolvidos na padronização da próxima geração de algoritmos de criptografia.

Esta história apareceu originalmente no Ars Technica, uma fonte confiável de notícias de tecnologia, análise de políticas de tecnologia, análises e muito mais. A Ars é propriedade da empresa controladora da WIRED, a Condé Nast.

No mês passado, o Instituto Nacional de Padrões e Tecnologia (NIST) dos EUA selecionou quatro algoritmos de criptografia de computação pós-quântica para substituir algoritmos como RSA, Diffie-Hellman e curva elíptica Diffie-Hellman, que são incapazes de resistir a ataques de um quantum computador.

No mesmo movimento, o NIST avançou quatro algoritmos adicionais como possíveis substitutos pendentes de testes adicionais, na esperança de que um ou mais deles também possam ser alternativas de criptografia adequadas em um mundo pós-quântico. O novo ataque quebra o SIKE, que é um dos últimos quatro algoritmos adicionais. O ataque não tem impacto nos quatro algoritmos PQC selecionados pelo NIST como padrões aprovados, todos baseados em técnicas matemáticas completamente diferentes das do SIKE.

O SIKE - abreviação de encapsulamento de chave de isogenia supersingular - agora provavelmente está fora de disputa, graças à pesquisa publicada no fim de semana por pesquisadores do grupo de Segurança de Computadores e Criptografia Industrial da KU Leuven. O documento, intitulado "Um ataque eficiente de recuperação de chave no SIDH (versão preliminar)", descreveu uma técnica que usa matemática complexa e um único PC tradicional para recuperar as chaves de criptografia que protegem as transações protegidas pelo SIKE. Todo o processo requer apenas cerca de uma hora. A façanha torna os pesquisadores, Wouter Castryck e Thomas Decru, elegíveis para uma recompensa de $ 50.000 do NIST.

“A fraqueza recém-descoberta é claramente um grande golpe para o SIKE”, escreveu David Jao, professor da Universidade de Waterloo e co-inventor do SIKE, em um e-mail. "O ataque é realmente inesperado."

O advento da criptografia de chave pública na década de 1970 foi um grande avanço, porque permitiu que partes que nunca haviam se encontrado negociassem com segurança material criptografado que não poderia ser quebrado por um adversário. A criptografia de chave pública depende de chaves assimétricas, com uma chave privada usada para descriptografar mensagens e uma chave pública separada para criptografar. Os usuários tornam sua chave pública amplamente disponível. Enquanto sua chave privada permanecer secreta, o esquema permanecerá seguro.

Na prática, a criptografia de chave pública pode muitas vezes ser complicada, então muitos sistemas dependem de mecanismos de encapsulamento de chave, que permitem que partes que nunca se encontraram antes concordem em conjunto com uma chave simétrica em um meio público como a Internet. Em contraste com os algoritmos de chave simétrica, os mecanismos de encapsulamento de chave em uso hoje são facilmente quebrados por computadores quânticos. O SIKE, antes do novo ataque, foi pensado para evitar tais vulnerabilidades usando uma construção matemática complexa conhecida como gráfico de isogenia supersingular.

A pedra angular do SIKE é um protocolo chamado SIDH, abreviação de supersingular isogeny Diffie-Hellman. O trabalho de pesquisa publicado no fim de semana mostra como o SIDH é vulnerável a um teorema conhecido como "cola e divide" desenvolvido pelo matemático Ernst Kani em 1997, bem como ferramentas desenvolvidas pelos colegas matemáticos Everett W. Howe, Franck Leprévost e Bjorn Poonen em 2000. A nova técnica se baseia no que é conhecido como ataque adaptativo GPST, descrito em um artigo de 2016. A matemática por trás do último ataque é garantidamente impenetrável para a maioria dos não-matemáticos. Aqui está o mais perto que você vai chegar:

“O ataque explora o fato de que SIDH tem pontos auxiliares e que o grau da isogenia secreta é conhecido”, explicou Steven Galbraith, professor de matemática da Universidade de Auckland e o “G” no ataque adaptativo GPST, em um breve artigo. no novo ataque. "Os pontos auxiliares no SIDH sempre foram um aborrecimento e uma fraqueza potencial, e eles foram explorados para ataques de falha, ataque adaptativo GPST, ataques de ponto de torção, etc."