A troca de chaves Diffie-Hellman por isogenia supersingular (do inglês, Supersingular isogeny Diffie–Hellman key exchange - SIDH ou SIKE) foi uma proposta insegura de um algoritmo criptográfico pós-quântico para estabelecer uma chave secreta entre duas partes através de um canal de comunicações não confiável. É análoga à troca de chaves Diffie–Hellman, mas é baseada em passeios em um grafo de isogenias supersingulares e foi projetada para resistir a ataques criptoanalíticos por um adversário em posse de um computador quântico. Antes de ser quebrado, o SIDH ostentava um dos menores tamanhos de chave de todas as trocas de chaves pós-quânticas; com compressão, o SIDH usava chaves públicas de 2688 bits em um nível de segurança quântica de 128 bits. O SIDH também se distinguia de sistemas similares como o NTRU e o Ring-LWE por suportar sigilo perfeito à frente (perfect forward secrecy), uma propriedade que impede que o comprometimento de chaves de longo prazo comprometa a confidencialidade de sessões de comunicação antigas. Estas propriedades pareciam fazer do SIDH um candidato natural para substituir o Diffie-Hellman (DHE) e o Diffie-Hellman de curva elíptica (ECDHE), que são amplamente utilizados em comunicações na Internet. No entanto, o SIDH é vulnerável a um devastador ataque de recuperação de chave publicado em julho de 2022 e é, portanto, inseguro. O ataque não requer um computador quântico.

Introdução

Para certas classes de problemas, os algoritmos executados em computadores quânticos são naturalmente capazes de alcançar uma complexidade de tempo menor do que em computadores clássicos. Isto é, os algoritmos quânticos podem resolver determinados problemas mais rapidamente do que o algoritmo mais eficiente em um computador tradicional. Por exemplo, o Algoritmo de Shor pode fatorar um inteiro em tempo polinomial, enquanto o algoritmo clássico de fatoração mais conhecido, o crivo geral do corpo de números, opera em tempo subexponencial. Isso é significativo para a criptografia de chave pública porque a segurança do RSA depende da inviabilidade de fatorar inteiros, o problema da fatoração de inteiros. O algoritmo de Shor também pode resolver de forma eficiente o problema do logaritmo discreto, que é a base para a segurança do Diffie-Hellman, Diffie-Hellman de curva elíptica, ECDSA, Curve25519, ed25519 e do esquema de assinatura ElGamal. Embora os computadores quânticos estejam atualmente na sua infância, o seu desenvolvimento contínuo e a sua capacidade teórica de comprometer protocolos criptográficos modernos (como o TLS/SSL) impulsionaram o desenvolvimento da criptografia pós-quântica.

O SIDH foi criado em 2011 por De Feo, Jao e Plut. Ele utiliza operações convencionais de curvas elípticas e não é patenteado.

Contexto Teórico

O invariante j de uma curva elíptica dada pela equação de Weierstrass é fornecido pela fórmula:

.

Curvas isomorfas possuem o mesmo invariante j; sobre um corpo algebricamente fechado, duas curvas com o mesmo invariante j são isomorfas.

O protocolo Diffie-Hellman por isogenia supersingular (SIDH) trabalha com o grafo cujos vértices são (classes de isomorfismo de) curvas elípticas supersingulares e cujas arestas são isogenias entre essas curvas. Uma isogenia entre as curvas elípticas e é uma aplicação racional que é também um homomorfismo de grupo. Se for separável, é determinada pelo seu núcleo a menos de um isomorfismo da curva de destino .

A configuração para o SIDH utiliza um primo da forma , para (pequenos) primos diferentes e , (grandes) expoentes e , e um pequeno cofator , juntamente com uma curva elíptica supersingular definida sobre . Tal curva possui dois grandes subgrupos de torção, e , que são atribuídos a Alice e Bob, respectivamente, como indicado pelos subscritos. Cada parte inicia o protocolo selecionando um subgrupo cíclico aleatório (secreto) do seu respectivo subgrupo de torção e computando a isogenia (secreta) correspondente. Em seguida, eles publicam, ou fornecem de outra forma à outra parte, a equação para a curva de destino de sua isogenia, juntamente com informações sobre a imagem do subgrupo de torção da outra parte sob essa isogenia. Isto permite que ambos computem privadamente novas isogenias a partir de cujos núcleos são gerados conjuntamente pelos dois subgrupos cíclicos secretos. Uma vez que os núcleos dessas duas novas isogenias coincidem, suas curvas de destino são isomorfas. O invariante j comum dessas curvas de destino pode então ser adotado como o segredo compartilhado necessário.

Como a segurança do esquema depende do subgrupo de torção menor, recomenda-se escolher .

Uma excelente referência para este assunto é o artigo de De Feo "Mathematics of Isogeny Based Cryptography".

Segurança

A forma mais direta de atacar o SIDH é resolver o problema de encontrar uma isogenia entre duas curvas elípticas supersingulares com o mesmo número de pontos. Na época da publicação original por De Feo, Jao e Plût, o melhor ataque conhecido contra o SIDH era baseado na resolução do problema relacionado de busca de garras (claw-finding problem), o que levava a uma complexidade de para computadores clássicos e para computadores quânticos. Isso sugeria que o SIDH com um primo () de 768 bits teria um nível de segurança de 128 bits. Um estudo de 2014 do problema da isogenia por Delfs e Galbraith confirmou a análise de segurança de para computadores clássicos. A segurança clássica permaneceu inalterada pelo trabalho criptoanalítico relacionado de Biasse, Jao e Sankar, bem como de Galbraith, Petit, Shani e Yan.

Uma estratégia de ataque mais complexa baseia-se na exploração dos pontos auxiliares da curva elíptica presentes nas chaves públicas do SIDH, que, em princípio, revelam muitas informações adicionais sobre as isogenias secretas, mas essa informação inicialmente não parecia ser computacionalmente útil para os atacantes. Petit, em 2017, demonstrou pela primeira vez uma técnica que faz uso desses pontos para atacar algumas variantes peculiares do SIDH. Apesar de trabalhos de acompanhamento que estenderam o ataque a instanciações de SIDH muito mais realistas, a estratégia de ataque ainda não conseguia quebrar o SIDH "padrão", como o empregado pela submissão SIKE no PQC do NIST.

Em julho de 2022, Castryck e Decru publicaram um ataque eficiente de recuperação de chave no SIKE que explora os pontos auxiliares. Usando um computador de núcleo único (single-core), o SIKEp434 foi quebrado em aproximadamente uma hora, o SIKEp503 em aproximadamente 2 horas, o SIKEp610 em aproximadamente 8 horas e o SIKEp751 em aproximadamente 21 horas. O ataque baseia-se em "colar" várias das curvas elípticas que aparecem na construção do SIDH, produzindo uma superfície abeliana (mais genericamente, uma variedade abeliana), e computar uma isogenia elaborada de modo especial definida pelos pontos auxiliares fornecidos sobre esse objeto de dimensão superior.

Deve ser destacado que o ataque depende crucialmente dos pontos auxiliares dados no SIDH, e não há forma conhecida de aplicar técnicas semelhantes ao problema geral de isogenias.

Eficiência

Durante uma troca de chaves, as entidades A e B transmitirão cada uma informações de 2 coeficientes módulo definindo uma curva elíptica e 2 pontos da curva elíptica. Cada coeficiente da curva elíptica requer bits. Cada ponto da curva elíptica pode ser transmitido em bits; portanto, a transmissão é de bits. Isso resulta em 6144 bits para um módulo de 768 bits (segurança de 128 bits). No entanto, isso pode ser reduzido pela metade, para 2640 bits (330 bytes), utilizando técnicas de compressão de chave, sendo a mais recente descrita no trabalho dos autores Costello, Jao, Longa, Naehrig, Renes e Urbanik. Com essas técnicas de compressão, o SIDH tem uma exigência de largura de banda semelhante às assinaturas tradicionais RSA de 3072 bits ou trocas de chaves Diffie-Hellman. Esta pequena exigência de espaço torna o SIDH aplicável em contextos que exigem estritamente pouco espaço, como o Bitcoin ou o Tor. As células de dados do Tor devem ter menos de 517 bytes de comprimento, portanto, elas podem conter chaves SIDH de 330 bytes. Em contraste, o NTRUEncrypt precisa trocar aproximadamente 600 bytes para obter uma segurança de 128 bits e não pode ser utilizado dentro do Tor sem aumentar o tamanho da célula.

Em 2014, investigadores da Universidade de Waterloo desenvolveram uma implementação em software do SIDH. Eles executaram seu código parcialmente otimizado em um processador x86-64 rodando a 2,4 GHz. Para um módulo de 768 bits, conseguiram concluir as computações de troca de chaves em 200 milissegundos, demonstrando que o SIDH é computacionalmente viável.

Em 2016, pesquisadores da Microsoft disponibilizaram um software para o SIDH que é executado em tempo constante (protegendo assim contra ataques de tempo) e é a implementação mais eficiente até o momento. Eles escreveram: "O tamanho das chaves públicas é de apenas 564 bytes, o que é significativamente menor do que a maioria das alternativas populares de troca de chaves pós-quânticas. Em última análise, o tamanho e a velocidade do nosso software ilustram o forte potencial do SIDH como candidato a troca de chaves pós-quântica, e esperamos que esses resultados incentivem um esforço criptoanalítico mais amplo." O código é de código aberto (licença MIT) e está disponível no GitHub.https://github.com/microsoft/PQCrypto-SIDH https://github.com/microsoft/PQCrypto-SIDH

Em 2016, pesquisadores da Universidade Atlântica da Flórida desenvolveram implementações ARM eficientes do SIDH e forneceram uma comparação de coordenadas afins e projetivas. Em 2017, pesquisadores da mesma universidade desenvolveram as primeiras implementações FPGA do SIDH.

O método de Diffie-Hellman por isogenia supersingular

Embora vários passos do SIDH envolvam cálculos de isogenia complexos, o fluxo geral do SIDH para as partes A e B é direto para aqueles familiarizados com uma troca de chaves Diffie-Hellman ou a sua variante de curva elíptica.

Configuração Inicial Estes são parâmetros públicos que podem ser compartilhados por todos na rede, ou podem ser negociados pelas partes A e B no início de uma sessão.

Um primo da forma Uma curva elíptica supersingular sobre . Pontos elípticos fixos em . A ordem de e é . A ordem de e é .

Troca de chaves Na troca de chaves, as partes A e B criarão cada uma uma isogenia a partir de uma curva elíptica comum . Cada qual fará isso criando um ponto aleatório no que será o núcleo de sua isogenia. O núcleo de sua isogenia será gerado por e , respectivamente. Os diferentes pares de pontos utilizados garantem que as partes A e B criem isogenias diferentes e não comutativas. Um ponto aleatório ( ou ) no núcleo das isogenias é criado como uma combinação linear aleatória dos pontos , e , .

Utilizando ou , as partes A e B então utilizam as Fórmulas de Vélu para criar as isogenias e , respectivamente. A partir disso, eles computam a imagem dos pares de pontos , ou , sob as isogenias e , respectivamente.

Como resultado, A e B agora terão dois pares de pontos, , e , , respectivamente. A e B então trocam esses pares de pontos através de um canal de comunicações.

A e B agora usam o par de pontos que recebem como base para o núcleo de uma nova isogenia. Eles usam os mesmos coeficientes lineares que usaram anteriormente junto aos pontos recebidos para formar um ponto no núcleo de uma isogenia que eles criarão. Eles computam os pontos e e utilizam as fórmulas de Vélu para construir as novas isogenias.

Para completar a troca de chaves, A e B computam os coeficientes de duas novas curvas elípticas sob essas duas novas isogenias. Eles então computam o invariante j dessas curvas. A menos que tenha havido erros na transmissão, o invariante j da curva criada por A será igual ao invariante j da curva criada por B.

Nocionalmente, a troca de chaves SIDH entre as partes A e B funciona da seguinte maneira: