Criptografia pós-quântica – novo algoritmo “desapareceu em 60 minutos”

Escrevemos sobre PQC, abreviação de criptografia pós-quântica, várias vezes antes.

Caso você tenha perdido todo o entusiasmo da mídia nos últimos anos sobre a chamada computação quântica…

…é (com o perdão do que alguns especialistas provavelmente considerarão uma simplificação imprudente) uma forma de construir dispositivos de computação que possam acompanhar vários resultados possíveis de um cálculo ao mesmo tempo.

Com muito cuidado, e talvez um pouco de sorte, isso significa que você pode reescrever alguns tipos de algoritmo para encontrar a resposta certa ou, pelo menos, descartar corretamente uma série de respostas erradas, sem tentar e testar todos os resultados possíveis. um por um.

Duas acelerações criptoanalíticas interessantes são possíveis usando um dispositivo de computação quântica, assumindo que um dispositivo adequadamente poderoso e confiável possa realmente ser construído:

• Algoritmo de busca quântica de Grover. Normalmente, se você quiser pesquisar um conjunto de respostas ordenadas aleatoriamente para ver se a sua está na lista, você esperaria percorrer a lista inteira, na pior das hipóteses, antes de obter uma resposta definitiva. Por exemplo, se você quiser encontrar a chave de descriptografia AES de 128 bits para decodificar um documento, precisará pesquisar a lista de todas as chaves possíveis, começando em 000..001, ..2, ..3, e assim por diante, até FFF..FFF (16 bytes de FF), para ter certeza de completar o problema. Em outras palavras, você precisa fazer um orçamento para experimentar todos os 2¹²⁸ chaves possíveis antes de encontrar a chave certa ou determinar que não havia nenhuma. O algoritmo de Grover, no entanto, dado um computador quântico suficientemente grande e poderoso, afirma ser capaz de completar o mesmo feito com o raiz quadrada do esforço habitual, decifrando assim o código, em teoria, em apenas 2⁶⁴ em vez disso, tenta.
• Algoritmo de fatoração quântica de Shor. Vários algoritmos de criptografia contemporâneos baseiam-se no fato de que a multiplicação de dois grandes números primos pode ser feita rapidamente, ao passo que dividir seu produto novamente nos dois números com os quais você começou é praticamente impossível. Para ter uma ideia disso, tente multiplicar 59×87 usando papel e caneta. Pode levar um minuto ou mais para retirá-lo (5133 é a resposta), mas não é tão difícil. Agora tente o contrário. Divida, digamos, 4171 novamente em seus dois fatores. Muito mais dificil! (É 43×97.) Agora imagine fazer isso com um número de 600 dígitos. Falando livremente, você terá que tentar dividir o número de 600 dígitos por todos os números primos de 300 dígitos possíveis até tirar a sorte grande ou descobrir que não há uma resposta. O algoritmo de Shor, no entanto, promete resolver este problema com o logaritmo do esforço habitual. Assim, a fatoração de um número de 2048 dígitos binários deve levar apenas o dobro do tempo de fatoração de um número de 1024 bits, não o dobro do tempo de fatoração de um número de 2047 bits, representando uma enorme aceleração.

Combatendo a ameaça

A ameaça do algoritmo de Grover pode ser combatida simplesmente aumentando o tamanho dos números que você está usando, elevando-os ao quadrado, o que significa dobrar o número de bits em seu hash criptográfico ou em sua chave de criptografia simétrica. (Em outras palavras, se você acha que o SHA-256 está bem agora, usar o SHA-512 forneceria uma alternativa resistente ao PQC.)

Mas o algoritmo de Shor não pode ser combatido tão facilmente.

Uma chave pública de 2048 bits precisaria ter seu tamanho aumentado exponencialmente, não simplesmente por quadratura, de modo que, em vez de uma chave de 2 × 2048 = 4096 bits, você precisaria de uma nova chave com o tamanho impossível de 2.²⁰⁴⁸ pedaços…

…ou você teria que adotar um tipo completamente novo de sistema de criptografia pós-quântica ao qual o algoritmo de Shor não se aplicava.

Bem, o NIST, órgão de padronização dos EUA, vem realizando um “Competição” PQC desde o final de 2017.

O processo foi aberto a todos, com todos os participantes bem-vindos, todos os algoritmos publicados abertamente e o escrutínio público não apenas possível, mas encorajado ativamente:

Chamada de Propostas. [Fechado em 2017/11/30]. […] Pretende-se que os novos padrões de criptografia de chave pública especifiquem uma ou mais assinaturas digitais não classificadas e divulgadas publicamente, criptografia de chave pública e algoritmos de estabelecimento de chave que estão disponíveis em todo o mundo e são capazes de proteger informações governamentais confidenciais num futuro próximo, inclusive após o advento dos computadores quânticos.

Após três rodadas de submissões e discussões, NIST anunciado, em 2022/07/05, que escolheu quatro algoritmos que considerou “padrões” com efeito imediato, todos com nomes que soam deliciosos: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON e SPHINCS+.

O primeiro (CRYSTALS-KYBER) é usado como o que é chamado de Mecanismo Chave de Acordo (KEM), onde duas extremidades de um canal de comunicação público criam com segurança uma chave de criptografia privada única para a troca confidencial de dados de uma sessão. (Simplificando: bisbilhoteiros apenas pegam repolho picado, então não podem escutar a conversa.)

Os outros três algoritmos são usados ​​para Assinaturas digitais, por meio do qual você pode garantir que os dados que você obteve correspondem exatamente aos que o remetente inseriu no outro, evitando assim adulterações e garantindo a integridade. (Simplificando: se alguém tentar corromper ou mexer nos dados, você saberá.)

Mais algoritmos necessários

Ao mesmo tempo em que anunciava os novos padrões, o NIST também anunciou um quarta rodada de sua concorrência, apresentando mais quatro algoritmos como possíveis KEMs alternativos. (Lembre-se de que, no momento em que este artigo foi escrito, já tínhamos três algoritmos de assinatura digital aprovados para escolher, mas apenas um KEM oficial.)

Estes foram: BIKE, Classic McEliece, HQC e SIKE.

Curiosamente, o Algoritmo McEliece foi inventado na década de 1970 pelo criptógrafo americano Robert Mc Eliece, que morreu em 2019, bem depois do concurso do NIST já estar em andamento.

No entanto, nunca pegou porque exigia enormes quantidades de material chave em comparação com a alternativa popular da época, o algoritmo Diffie-Hellman-Merkle (DHM, ou às vezes apenas DH).

Infelizmente, um dos três algoritmos da Quarta Rodada, a saber SIKE, parece ter sido quebrado.

Em um artigo desafiador intitulado UM ATAQUE EFICIENTE DE RECUPERAÇÃO DE CHAVE NO SIDH (VERSÃO PRELIMINAR), os criptógrafos belgas Wouter Castryk e Thomas Decru parecem ter desferido um golpe mortal no algoritmo SIKE

Caso você esteja se perguntando, SIKE é a abreviatura de Encapsulamento de chave de isogenia supersingular, e SIDH significa Isogenia Supersingular Diffie-Hellman, um uso específico do Algoritmo SIKE por meio do qual duas extremidades de um canal de comunicação realizam uma “criptodança” semelhante ao DHM para trocar um monte de dados públicos que permite que cada extremidade obtenha um valor privado para usar como uma chave de criptografia secreta única.

Não vamos tentar explicar o ataque aqui; vamos apenas repetir o que o artigo afirma, a saber:

Em termos muito gerais, as entradas aqui incluem os dados públicos fornecidos por um dos participantes da principal criptodança do estabelecimento, juntamente com os parâmetros pré-determinados (e, portanto, publicamente conhecidos) utilizados no processo.

Mas o resultado extraído (as informações referidas como a isogenia φ acima) deveria ser a parte nunca revelada do processo – a chamada chave privada.

Em outras palavras, apenas a partir de informações públicas, como os dados trocados abertamente durante a configuração da chave, os criptógrafos afirmam ser capazes de recuperar a chave privada de um dos participantes.

E depois de saber minha chave privada, você pode fingir ser eu de maneira fácil e indetectável, para que o processo de criptografia seja interrompido.

Aparentemente, o algoritmo de quebra de chave leva cerca de uma hora para fazer seu trabalho, usando apenas um único núcleo de CPU com o tipo de poder de processamento que você encontraria em um laptop comum.

Isso vai contra o algoritmo SIKE quando configurado para atender ao Nível 1, o nível básico de segurança de criptografia do NIST.

O que fazer?

Nada!

(Essa é a boa notícia.)

Como sugerem os autores do artigo, após observarem que seu resultado ainda é preliminar, “com a situação atual, o SIDH parece estar totalmente quebrado para qualquer curva base gerada publicamente.”

(Essa é a má notícia.)

No entanto, dado que o algoritmo SIKE ainda não foi oficialmente aprovado, pode agora ser adaptado para impedir este ataque específico (algo que os autores admitem ser possível) ou simplesmente abandonado por completo.

Aconteça o que acontecer ao SIKE, este é um excelente lembrete de por que tentar inventar seus próprios algoritmos de criptografia é tão perigoso.

É também um exemplo claro de por que os sistemas de criptografia proprietários que dependem do sigilo do próprio algoritmo para manter a sua segurança são simplesmente inaceitáveis ​​em 2022.

Se um algoritmo PQC como o SIKE sobrevivesse a persuasões e sondagens por especialistas de todo o mundo durante mais de cinco anos, apesar de ter sido divulgado especificamente para que pudesse ser sujeito ao escrutínio público…

…então não há necessidade de se perguntar quão bem seus algoritmos de criptografia caseiros e ocultos provavelmente se sairão quando lançados na natureza!

---