Pular para o conteúdo
Início » O contensor de criptografia pós-quantum é retirado por um PC de núcleo único e 1 hora

O contensor de criptografia pós-quantum é retirado por um PC de núcleo único e 1 hora

Publicidade

O contensor de criptografia pós-quantum

O contensor de criptografia pós-quantum – Deixar para os matemáticos o que parecia ser um novo e impressionante algoritmo.

Publicidade

Na campanha em andamento 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.

O contensor de criptografia pós-quantum
O contensor de criptografia pós-quantum

No mês passado, o Instituto Nacional de Padrões e Tecnologia do Departamento de Comércio dos EUA, ou NIST, 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 computador quântico.

No mesmo movimento, o NIST avançou quatro algoritmos adicionais como substitutos em potencial, aguardando mais testes, 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 quatro últimos algoritmos adicionais. O ataque não tem impacto nos quatro algoritmos PQC selecionados pelo NIST como padrões aprovados, os quais dependem de técnicas matemáticas completamente diferentes das do SIKE.

Ficando totalmente SIKE

SIKE – abreviação de Supersingular Isogeny Key Encapsulation – agora provavelmente está fora do mercado, graças a uma pesquisa publicada no fim de semana por pesquisadores do grupo Computer Security and Industrial Cryptography em KU Leuven. O artigo, intitulado An Efficient Key Recovery Attack on SIDH (Preliminary Version) , 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 fraqueza recém-descoberta é claramente um grande golpe para a SIKE”, escreveu David Jao, professor da Universidade de Waterloo e co-inventor da 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 criptografia. Os usuários tornam sua chave pública amplamente disponível. Enquanto sua chave privada permanecer secreta, o esquema permanece seguro.

O contensor de criptografia pós-quantum na prática

Na prática, a criptografia de chave pública muitas vezes pode ser complicada, de modo que muitos sistemas dependem de mecanismos de encapsulamento de chave, que permitem que partes que nunca se encontraram antes concordem em conjunto sobre uma chave simétrica em um meio público como a Internet. Em contraste com os algoritmos de chave simétrica, os principais mecanismos de encapsulamento 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 “colar e dividir” desenvolvido pelo matemático Ernst Kani em 1997, bem como ferramentas criadas 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 de GPSST”, descrito em um artigo de 2016 . A matemática por trás do último ataque certamente será impenetrável para a maioria dos não-matemáticos. Aqui está o mais próximo que você vai chegar:

Publicidade

O fato de que o SIDH tem pontos auxiliares

“O ataque explora o fato de que o 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 sobre o novo ataque. “Os pontos auxiliares no SIDH sempre foram um incômodo e uma potencial fraqueza, e foram explorados para ataques de falhas, ataque adaptativo GPST, ataques de pontos de torção, etc.

Ele continuou:

Seja E_0a curva base e deixe P_0, Q_0 \in E_0ter ordem 2^a. Seja E, P, Qdado tal que existe uma isogenia \phide grau 3^bcom \phi: E_0 \to E\phi(P_0) = P, e\phi(Q_0) = Q.

Um aspecto chave do SIDH é que não se computa \phidiretamente, mas como uma composição de isogenias de grau 3. Em outras palavras, há uma sequência de curvas E_0 \to E_1 \to E_2 \to \cdots\to Econectadas por 3-isogenias.

Essencialmente, como no GPST, o ataque determina as curvas intermediárias E_ie, portanto, eventualmente determina a chave privada. Na etapa euo ataque faz uma busca de força bruta de todos os possíveis E_i \to E_{i+1}, e o ingrediente mágico é um gadget que mostra qual é o correto.

(O acima é muito simplificado, as isogenias E_i \to E_{i+1}no ataque não são de grau 3, mas de grau uma pequena potência de 3.)

Mais importante do que entender a matemática, Jonathan Katz, membro do IEEE e professor do departamento de ciência da computação da Universidade de Maryland, escreveu em um e-mail: “o ataque é totalmente clássico e não requer computadores quânticos”.

Lições aprendidas

O SIKE é o segundo candidato a PQC designado pelo NIST a ser invalidado este ano. Em fevereiro, o pesquisador de pós-doutorado da IBM Ward Beullens publicou uma pesquisa que quebrou o Rainbow , um esquema de assinatura criptográfica com sua segurança, de acordo com a Cryptomathic , “dependendo da dureza do problema de resolver um grande sistema de equações quadráticas multivariadas sobre um campo finito. ”

A campanha de substituição de PQC do NIST está em execução há cinco anos. Segue um breve histórico:

Publicidade

Rainbow caiu durante o Round 3. A SIKE chegou até o Round 4.

O que é preocuopante

Katz continuou:

Talvez seja um pouco preocupante que este seja o segundo exemplo nos últimos seis meses de um esquema que chegou à 3ª rodada do processo de revisão do NIST antes de ser completamente quebrado usando um algoritmo clássico. (O exemplo anterior foi o Rainbow, que foi quebrado em fevereiro.) Três dos quatro esquemas de PQC dependem de suposições relativamente novas cuja dificuldade exata não é bem compreendida, então o que o último ataque indica é que talvez ainda precisemos ser cautelosos/conservadores com o processo de normalização a avançar.

Perguntei a Jao, o co-inventor da SIKE, por que a fraqueza só veio à tona agora, em um estágio relativamente posterior de seu desenvolvimento. Sua resposta foi perspicaz. 

Ele disse:

É verdade que o ataque usa matemática publicada nas décadas de 1990 e 2000. De certa forma, o ataque não requer matemática nova; poderia ter sido notado a qualquer momento. Uma faceta inesperada do ataque é que ele usa curvas de gênero 2 para atacar curvas elípticas (que são curvas de gênero 1). Uma conexão entre os dois tipos de curvas é bastante inesperada. Para dar um exemplo ilustrando o que quero dizer, há décadas as pessoas tentam atacar a criptografia de curva elíptica regular, incluindo alguns que tentaram usar abordagens baseadas em curvas de gênero 2. Nenhuma dessas tentativas deu certo. Portanto, para esta tentativa de sucesso no reino das isogenias é um desenvolvimento inesperado.

Em geral, há muita matemática profunda que foi publicada na literatura matemática, mas que não é bem compreendida pelos criptógrafos. Eu me coloco na categoria daqueles muitos pesquisadores que trabalham em criptografia, mas não entendem tanto de matemática quanto deveríamos. Então, às vezes, basta alguém que reconheça a aplicabilidade da matemática teórica existente a esses novos criptossistemas. Isso foi o que aconteceu aqui.

A versão do SIKE enviada ao NIST

A versão do SIKE enviada ao NIST usou uma única etapa para gerar a chave. Uma possível variante do SIKE poderia ser construída em duas etapas. Jao disse que é possível que esta última variante não seja suscetível à matemática que causa essa quebra. Por enquanto, porém, o SIKE está morto, pelo menos na execução atual. O cronograma para os três candidatos restantes é atualmente desconhecido.

Leia também:

OTT e IPTV, uma rede gerenciada é a resposta

Milagre da medicina

Temos uma visão vazada das futuras missões lunares da NASA

Microsoft tem falha no Dia 0

Cats: 30 gatos mais bonitos do mundo

Publicidade

Deixe um comentário

O seu endereço de e-mail não será publicado.