Padrões de criptografia pós-quântica do NIST

A computação quântica é um paradigma completamente novo para computadores. Um computador quântico usa propriedades quânticas como a superposição, que permite que um qubit (um bit quântico) não seja nem 0 nem 1, mas algo muito mais complicado. Em teoria, tal computador pode resolver problemas muito complexos para computadores convencionais.

Os computadores quânticos atuais ainda são protótipos de brinquedo, e os avanços de engenharia necessários para construir um computador quântico funcionalmente útil estão em algum lugar entre alguns anos de distância e são impossíveis. Mesmo assim, já sabemos que esse computador poderia fatorar grandes números e computar logs discretos e quebrar os algoritmos de chave pública RSA e Diffie-Hellman em todos os tamanhos de chave úteis.

Os criptógrafos odeiam ser apressados, e é por isso que o NIST iniciou uma competição para criar um padrão criptográfico pós-quântico em 2016. A ideia é padronizar tanto uma criptografia de chave pública quanto um algoritmo de assinatura digital que seja resistente à computação quântica, bem antes qualquer um constrói um computador quântico útil.

O NIST é um veterano nesse processo competitivo, tendo feito isso anteriormente com algoritmos simétricos (AES em 2001) e funções de hash (SHA-3 em 2015). Participei de ambas as competições e as comparei a derbies de demolição. A ideia é que os participantes coloquem seus algoritmos no ringue, e então todos nós passamos alguns anos batendo nas submissões uns dos outros. Então, com a contribuição da comunidade criptográfica, o NIST coroa um vencedor. É um bom processo, principalmente porque o NIST é confiável e confiável.

Em 2017, o NIST recebeu oitenta e duas submissões de algoritmos pós-quânticos de todo o mundo. Sessenta e nove foram considerados completos o suficiente para serem candidatos da Rodada 1. Vinte e seis avançaram para a Rodada 2 em 2019, e sete (mais outros oito suplentes) foram anunciados como finalistas da Rodada 3 em 2020 . O NIST estava pronto para fazer as seleções finais do algoritmo em 2022, com um plano de ter um rascunho do padrão disponível para comentários públicos em 2023.

Criptanálise sobre a competição foi brutal. Vinte e cinco dos algoritmos da primeira rodada foram atacados o suficiente para removê-los da competição. Outros oito foram igualmente atacados na Rodada 2. Mas aqui está a verdadeira surpresa: houve resultados de criptoanálise recentemente publicados contra pelo menos quatro dos finalistas da Rodada 3 apenas alguns meses atrás – momentos antes do NIST tomar sua decisão final.

Descobriu-se que um dos algoritmos mais populares, Rainbow, estava completamente quebrado . Não que teoricamente possa ser quebrado com um computador quântico, mas que pode ser quebrado hoje – com um laptop de prateleira em pouco mais de dois dias. Três outros finalistas, Kyber, Saber e Dilithium, foram enfraquecidos com novas técnicas que provavelmente funcionarão contra alguns dos outros algoritmos também. (Curiosidade: esses três algoritmos foram quebrados pelo Centro de Criptografia e Segurança da Informação, parte da Força de Defesa de Israel. Isso representa a primeira vez que uma organização nacional de inteligência publicou um resultado de criptoanálise na literatura aberta. E eles tiveram muito problemas de publicação, pois os autores queriam permanecer anônimos.)

Foi por pouco, mas demonstrou que o processo está funcionando corretamente . Lembre-se, este é um derby de demolição. O objetivo é trazer à tona esses resultados criptoanalíticos antes da padronização, que foi exatamente o que aconteceu. Neste momento, o NIST escolheu um único algoritmo para criptografia geral e três algoritmos de assinatura digital. Ele não escolheu um algoritmo de criptografia de chave pública e ainda há quatro finalistas. Verifique a página do NIST sobre o projeto para obter as informações mais recentes.

Ian Cassels, matemático britânico e criptoanalista da Segunda Guerra Mundial, disse uma vez que “a criptografia é uma mistura de matemática e confusão, e sem a confusão a matemática pode ser usada contra você”. Essa mistura é particularmente difícil de alcançar com algoritmos de chave pública, que dependem da matemática para sua segurança de uma forma que os algoritmos simétricos não. Tivemos sorte com RSA e algoritmos relacionados: sua matemática depende do problema da fatoração, que acabou sendo extremamente difícil. Os algoritmos pós-quânticos dependem de outras disciplinas e problemas matemáticos – criptografia baseada em código, criptografia baseada em hash, criptografia baseada em rede, criptografia multivariada e assim por diante – cuja matemática é mais complicada e menos compreendida.

A moral é a necessidade de agilidade criptográfica. Não basta implementar um único padrão; é vital que nossos sistemas sejam capazes de trocar facilmente novos algoritmos quando necessário. Aprendemos da maneira mais difícil como os algoritmos podem ficar tão arraigados nos sistemas que podem levar muitos anos para atualizá-los: na transição de DES para AES e na transição de MD4 e MD5 para SHA, SHA-1 e depois SHA -3.

Nós precisamos fazer melhor. Nos próximos anos estaremos diante de uma dupla incerteza. A primeira é a computação quântica. Quando e se a computação quântica se tornar uma realidade prática, aprenderemos muito sobre seus pontos fortes e limitações. Levou algumas décadas para entender completamente a arquitetura de computador de von Neumann; esperar a mesma curva de aprendizado com a computação quântica. Nossa compreensão atual da arquitetura de computação quântica mudará, e isso pode facilmente resultar em novas técnicas criptoanalíticas.

A segunda incerta está nos próprios algoritmos. Como os novos resultados criptoanalíticos demonstram, ainda estamos aprendendo muito sobre como transformar problemas matemáticos difíceis em sistemas criptográficos de chave pública. Temos muita matemática e uma incapacidade de adicionar mais confusão, e isso resulta em algoritmos vulneráveis ​​aos avanços da matemática. Mais resultados criptoanalíticos estão chegando e mais algoritmos serão quebrados.

Não podemos parar o desenvolvimento da computação quântica. Talvez os desafios de engenharia se tornem impossíveis, mas não é a maneira de apostar. Diante de toda essa incerteza, a agilidade é a única maneira de manter a segurança.

Este ensaio foi publicado originalmente em IEEE Security & Privacy .