SIDH e SIKE: Design e Criptoanálise

O Diffie-Hellman de isogenias supersingulares (SIDH), proposto por Jao e De Feo em 2011, é um protocolo de troca de chaves públicas análogo ao Diffie-Hellman, mas que usa isogenias em curvas elípticas supersingulares. Ambas as partes começam com a mesma curva supersingular E sobre Fp2. Alice calcula uma isogenia secreta phi_A: E -> E_A (núcleo aleatório no grupo de torção 2^a), publica E_A e as imagens dos geradores de torção de Bob sob phi_A. Bob calcula phi_B: E -> E_B (núcleo aleatório no grupo de torção 3^b), publica E_B e as imagens dos geradores de torção de Alice sob phi_B. Alice usa os dados publicados por Bob para calcular phi_A': E_B -> E_AB; Bob calcula phi_B': E_A -> E_AB. Ambos chegam a j(E_AB) como segredo compartilhado.

A forma especial do primo do SIDH, p = 2^a * 3^b * f - 1 (f é um cofator pequeno para garantir a primalidade), assegura que a curva E sobre Fp2 tenha a estrutura de torção necessária. Para SIKEp434 (Nível 1 do NIST, segurança pós-quântica de 128 bits): p = 2^216 * 3^137 - 1, a = 216, b = 137. Isso significa que Alice percorre 216 etapas de 2-isogenias, enquanto Bob percorre 137 etapas de 3-isogenias. Tamanhos das chaves: a chave pública de Alice é E_A mais dois pontos de Fp2 (phi_A(P_B), phi_A(Q_B)) = 3 * 2 * 54 = 324 bytes. SIKEp751 visa segurança clássica de 192 bits e quântica de 128 bits e tem chaves públicas de 564 bytes. Estas são as menores chaves públicas entre todos os candidatos a PQC do NIST — ao custo de serem de 100 a 1000 vezes mais lentas.

SIKE (encapsulamento de chaves por isogenias supersingulares) é um KEM seguro contra IND-CCA2, construído a partir do SIDH usando a transformação de Fujisaki-Okamoto. SIKE.Encaps: escolha uma mensagem aleatória m, calcule (c0 = chave pública do SIDH com a semente m, c1 = H2(m) XOR pk) e envie (c0, c1). SIKE.Decaps: recupere m de c0 usando a chave secreta, verifique c1, recalcule (c0, c1) para verificar a consistência e produza K = H3(m, c0). A transformação FO converte a troca segura contra CPA do SIDH em um KEM seguro contra CCA2. SIKE participou de todas as quatro rodadas do PQC do NIST (2017–2022), sobrevivendo a uma extensa criptoanálise — até que um ataque clássico devastador surgiu em julho de 2022.

De 2011 a 2022, o SIDH resistiu a esforços significativos de criptoanálise. Os melhores ataques conhecidos contra o SIDH eram: (1) Algoritmo SSIP genérico: O(p^{1/4}) classicamente, O(p^{1/6}) quanticamente usando o algoritmo de Tani. (2) Ataque de encontro no meio sobre o caminho de isogenias: O(p^{1/4}) classicamente, igual ao SSIP. (3) Algoritmos em tempo polinomial para ataques estruturais específicos (van Oorschot-Wiener): não aplicáveis ao SIDH. Dezenas de artigos analisaram a segurança do SIDH, e nenhum ataque clássico ou quântico em tempo polinomial foi encontrado em 11 anos. Esse histórico tornou o SIKE um finalista confiável do NIST. A quebra final não veio de um ataque direto ao SSIP, mas da exploração das informações auxiliares dos pontos de torção do SIDH.

Em 30 de julho de 2022, Wouter Castryck e Thomas Decru publicaram uma prepublicação mostrando um ataque clássico em tempo polinomial contra o SIDH. O ataque usa as informações extras nos pontos auxiliares de torção do SIDH phi_A(P_B), phi_A(Q_B): essas informações essencialmente revelam a ação de phi_A sobre o subgrupo de torção 3^b. Combinadas com a curva imagem E_A, elas permitem reconstruir o núcleo de phi_A (e, portanto, a própria phi_A) usando técnicas da teoria de curvas elípticas com multiplicação complexa e isogenias de Richelot. O ataque foi executado em 62 minutos em um notebook para SIKEp434 — um conjunto de parâmetros que deveria oferecer segurança pós-quântica de 128 bits. Em poucos dias, pesquisadores independentes confirmaram e ampliaram o ataque para todos os parâmetros do SIDH.

O projeto do SIDH exigia que ambas as partes publicassem as imagens dos pontos da base de torção da outra parte sob sua isogenia secreta. Isso era necessário para o funcionamento do protocolo: sem phi_A(P_B) e phi_A(Q_B), Bob não poderia transportar sua isogenia para a curva de Alice e calcular o segredo compartilhado. Porém, essas informações extras — que revelam a ação de phi_A restrita à torção 3^b — acabaram revelando uma quantidade catastrófica de informações a mais do que se esperava. O ataque de Castryck-Decru usa curvas de gênero 2 (isogenias de Richelot) para elevar o problema a objetos de gênero superior, nos quais a ação restrita determina completamente phi_A. Esse vazamento é estrutural no SIDH e não pode ser corrigido sem alterar o projeto fundamental do protocolo.

Em 5 de julho de 2022 (antes de Castryck-Decru), o NIST havia anunciado suas escolhas iniciais de padronização de PQC: ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+) e FN-DSA (Falcon) — o SIKE não estava entre elas (estava em uma segunda rodada de avaliação). O ataque de Castryck-Decru em julho de 2022 levou o NIST a eliminar formalmente o SIKE da avaliação. O NIST declarou: "O SIKE não está mais sendo considerado para padronização." Esse foi o desenvolvimento criptoanalítico mais dramático da competição de PQC do NIST, demonstrando que até mesmo um esquema que havia sobrevivido a 11 anos de análise poderia ser quebrado por uma nova descoberta matemática fundamental.

Dentro de uma semana após Castryck-Decru, Thomas Decru e Luciano Maino, de forma independente, e mais tarde Damien Robert publicaram outros aperfeiçoamentos. A variante de Robert usa a mesma ideia, mas calcula o anel de endomorfismos de E_A em vez de calcular diretamente o núcleo da isogenia, sendo possivelmente mais simples de descrever matematicamente. Essas redescobertas independentes e rápidas confirmaram que o ataque de Castryck-Decru havia identificado uma fraqueza estrutural fundamental, não um artifício obscuro. A velocidade dos artigos subsequentes também refletiu quantos pesquisadores vinham estudando o vazamento de pontos de torção do SIDH como um possível vetor de ataque, cientes de que se tratava de uma divulgação incomum de informações, mas incapazes de explorá-la até que Castryck e Decru encontrassem a ponte para o gênero 2.

FESTA (Criptografia rápida a partir de ataques de torção supersingulares, 2023) é um projeto de KEM inspirado no SIDH, mas que evita os dados auxiliares dos pontos de torção. O FESTA usa uma estrutura de protocolo diferente: a chave pública não inclui imagens da base de torção da contraparte — em vez disso, o compromisso com a isogenia secreta é feito apenas por meio da curva imagem (sem pontos auxiliares). O FESTA realiza a criptografia usando isogenias de uma forma que revela menos informações estruturais. As primeiras análises de segurança sugerem que o FESTA evita a estrutura do ataque de Castryck-Decru. No entanto, o FESTA é mais recente e recebeu menos análise minuciosa que o histórico de 11 anos do SIKE, e a comunidade de isogenias é cautelosa quanto à implantação de novos esquemas antes de uma análise extensa.

A quebra do SIKE oferece lições importantes. (1) A divulgação de informações auxiliares é perigosa: os dados extras dos pontos de torção do SIDH eram necessários para o protocolo, mas vazaram informações fatais. Os projetistas de protocolos devem analisar cada parte dos dados públicos, não apenas os valores principais. (2) Histórico não é prova de segurança: 11 anos sem um ataque conhecido são tranquilizadores, mas não constituem uma garantia. Provas criptográficas (redução a um problema difícil bem definido) são mais confiáveis que argumentos de autoridade ou o simples fato de um esquema ter sobrevivido à análise. (3) Ferramentas matemáticas novas criam riscos: o ataque de Castryck-Decru usou isogenias de Richelot de gênero 2 — uma ferramenta da matemática que não havia sido aplicada anteriormente à criptoanálise de isogenias. Os criptoanalistas que investigam novas primitivas devem considerar novos domínios matemáticos.

Apesar da quebra do SIKE, a criptografia baseada em isogenias continua como área de pesquisa. As assinaturas SQISign (177 bytes no Nível 1) continuam sendo as assinaturas de PQC mais compactas conhecidas e usam uma hipótese de dificuldade diferente (o problema do anel de endomorfismos), não afetada pelo ataque ao SIDH. Os protocolos baseados em CSIDH usam a estrutura de ação do grupo de classes (isogenias comutativas) sem vazamento de pontos de torção, embora o CSIDH enfrente seus próprios desafios (era mais lento que o SIDH, e a análise da segurança quântica continua em andamento). A comunidade de isogenias considera a quebra do SIKE uma experiência de aprendizado que aprimorou a compreensão sobre quais informações precisam ser ocultadas nos protocolos de isogenias — um conhecimento valioso para projetar esquemas futuros.

Que aspecto do projeto do SIDH permitiu o ataque de Castryck-Decru?

O SIDH usa cadeias alternadas de isogenias 2^a e 3^b entre duas partes, compartilhando imagens auxiliares de pontos de torção para possibilitar a troca de chaves. O SIKE envolve o SIDH com a transformação de Fujisaki-Okamoto para obter segurança contra CCA2. O SIKE tinha as menores chaves entre todos os candidatos a PQC do NIST (374 bytes), mas era de 100 a 1000 vezes mais lento. Após 11 anos de segurança, Castryck-Decru quebrou o SIKE em julho de 2022 usando isogenias de Richelot de gênero 2 para explorar o vazamento de pontos de torção. O NIST eliminou o SIKE. O FESTA evita a divulgação de pontos de torção. O SQISign continua usando a dificuldade do problema do anel de endomorfismos. A quebra do SIKE mostra que os dados públicos auxiliares precisam ser analisados com tanto cuidado quanto os valores primários do protocolo.