Dois matemáticos quebraram a criptografia pós-quântica SIKE em uma hora em um único PC

Em agosto de 2022, semanas depois de o NIST selecionar quatro algoritmos de criptografia pós-quântica para eventualmente substituir o RSA e o Diffie-Hellman, pesquisadores do grupo de Segurança Computacional e Criptografia Industrial da KU Leuven publicaram 'An Efficient Key Recovery Attack on SIDH' — uma técnica que recupera as chaves que protegem transações protegidas pelo SIKE usando matemática complexa e um único PC tradicional, em cerca de uma hora. Wouter Castryck e Thomas Decru, autores do artigo, tornaram-se elegíveis para uma recompensa de US$ 50.000 da Microsoft.

O SIKE — Supersingular Isogeny Key Encapsulation — era um dos quatro algoritmos adicionais que o NIST promoveu como possíveis reservas, e acreditava-se que resistisse a computadores quânticos ao codificar segredos em um grafo de isogenias supersingulares, uma construção há muito considerada elegantemente difícil. O novo ataque mostra que seu protocolo fundamental, o SIDH (Supersingular Isogeny Diffie-Hellman), é vulnerável ao glue-and-split, um teorema provado pelo matemático Ernst Kani em 1997, além de ferramentas de Howe, Leprévost e Poonen em 2000, com base no conhecido ataque adaptativo GPST.

O significado foi imediato: o SIKE provavelmente estava fora da disputa pela padronização, enquanto os quatro algoritmos que o NIST havia selecionado como padrões — construídos sobre matemática completamente diferente — não foram afetados. David Jao, professor da Universidade de Waterloo e coinventor do SIKE, chamou a fraqueza de 'claramente um grande golpe' e o ataque de 'realmente inesperado'.

O SIDH sempre enviava pontos auxiliares com um grau de isogenia conhecido; um teorema de 1997 (glue-and-split) transforma essa conveniência de projeto em uma máquina de recuperação de chaves.

O ataque reutilizou uma matemática de um quarto de século, escondida à vista de todos desde 1997.

Não precisou de computador quântico — a ameaça para a qual o SIKE foi projetado — apenas de um núcleo e uma hora.

A falha era estrutural: pontos auxiliares e um grau de isogenia conhecido estavam embutidos no projeto do protocolo.

O resultado reclassificou uma competição de padronização governamental em poucos dias após a publicação.

Conveniências projetadas em um protocolo são vulnerabilidades latentes: os dados auxiliares que um esquema expõe para usabilidade podem ser exatamente a alavanca de que um atacante precisa.

O SIKE, um candidato alternativo do NIST, foi efetivamente eliminado da consideração; os quatro padrões pós-quânticos já selecionados dependiam de matemática diferente e não foram afetados. Os pesquisadores podiam receber a recompensa de US$ 50.000 da Microsoft, e o coinventor do SIKE, David Jao, confirmou publicamente a gravidade do ataque.