Quando verificamos o e-mail, fazemos login em nossas contas bancárias ou trocamos mensagens no Signal — aplicativo de mensagens instantâneas —, nossas senhas e credenciais são protegidas por criptografia, um esquema de bloqueio que usa segredos para disfarçar nossos dados. Funciona como um cadeado cibernético: com a chave certa, alguém pode desbloquear esses dados. Sem ela, será necessário recorrer a métodos trabalhosos de força bruta, o equivalente digital de serras e maçaricos.
Nossa confiança na segurança on-line tem suas raízes na matemática. Os esquemas de criptografia são criados com base em famílias de problemas matemáticos chamados de funções unidirecionais — cálculos que são fáceis de realizar em uma direção, mas quase impossíveis de resolver de forma eficiente na outra, mesmo com um computador potente. Elas são uma espécie de equivalente computacional daquelas lombadas encontradas nas saídas das agências de aluguel de carros nos aeroportos. Dirija em uma direção e você mal perceberá. Dê ré e você não irá longe (e precisará de pneus novos).
No entanto, há um problema. Embora os matemáticos suspeitem que existam funções unidirecionais verdadeiras, eles ainda não conseguiram provar isso. Eles não provaram que os problemas espinhosos que usamos são impossíveis ou mesmo extremamente impraticáveis de resolver. Em vez disso, pode ser apenas que ainda não tenhamos encontrado os meios matemáticos apropriados para desmontar os problemas. Esse enigma assombra toda a criptografia. Nossos dados são protegidos pelo fato de que ninguém sabe como decifrar os esquemas que os protegem — pelo menos não ainda.
Não é apenas com os hackers de hoje que precisamos nos preocupar. Há muito tempo, os especialistas em segurança alertam sobre uma ameaça que ainda não se concretizou: os computadores quânticos. No futuro, essas máquinas poderão executar um programa que resolve rapidamente os problemas matemáticos por trás da criptografia de última geração atual. Essa ameaça coloca em risco informações pessoais, financeiras, médicas e outras. Os hackers poderiam roubar os dados criptografados de hoje e armazená-los, apenas esperando a chegada de novos artifícios tecnológicos.
Cientistas da computação, matemáticos e criptógrafos estão em uma busca para encontrar novos algoritmos de criptografia que possam resistir a ataques não apenas dos computadores convencionais de hoje, mas também das máquinas quânticas de amanhã. O que eles querem é um grande e persistente problema matemático — algo que seja robusto o suficiente para resistir a ataques de computadores clássicos e quânticos, mas que ainda possa ser facilmente implementado no espaço cibernético.
Infelizmente, ninguém ainda encontrou um único tipo de problema que seja comprovadamente difícil para os computadores — clássicos ou quânticos — resolverem. (No mundo da criptografia, “difícil” descreve um problema cuja solução exige um número irracional de etapas ou uma quantidade excessiva de poder de computação). Se as funções unidirecionais não existirem, então o processo de encontrar falhas e desenvolver esquemas cada vez mais fortes para bloquear hackers inteligentes persistirá indefinidamente.
“A questão da existência ou não de funções unidirecionais é realmente o problema mais importante”, diz Rafael Pass, cientista teórico da computação da Universidade de Tel Aviv, em Israel. É um enigma que remonta à década de 1970 e ao início de uma área de pesquisa hoje conhecida como teoria da complexidade computacional. Durante cinco décadas, teóricos e criptógrafos têm procurado maneiras de estabelecer se essas funções existem de fato. Talvez os problemas que esperamos ou suspeitamos que sejam unidirecionais sejam apenas problemas mais fáceis e quebráveis disfarçados.
Pass está explorando como as funções unidirecionais estão conectadas a uma série de outros problemas em aberto, uma linha de pesquisa promissora que atraiu outros teóricos para a busca. Ao mesmo tempo, as pessoas que se concentram no lado prático da criptografia estão avançando, buscando novos esquemas que sejam — se não comprovadamente difíceis — aparentemente fortes o suficiente para resistir aos computadores quânticos.
Os cientistas da computação se encontram em uma curiosa encruzilhada, sem saber se os algoritmos pós-quânticos são realmente inatacáveis — ou se apenas se acredita que sejam.
Nos últimos sete anos, o trabalho de encontrar os melhores candidatos foi liderado pelo National Institute of Standards and Technology (NIST), o órgão do governo dos EUA encarregado de coletar, testar e padronizar algoritmos criptográficos para uso público. O NIST vem executando dezenas de possíveis algoritmos “pós-quânticos” por meio de uma série de testes e disponibilizando-os para testes externos. O processo reduziu o campo a alguns finalistas e, em agosto, o NIST anunciou que um deles, chamado CRYSTALS-Kyber, que adota uma abordagem considerada robusta o suficiente para combater ataques quânticos, será o primeiro a ser oficialmente recomendado para uso público até 2024. Depois disso, empresas e governos adotarão o algoritmo para criptografar dados.
Será que ela se manterá? A resposta ajudará a determinar a trajetória da segurança cibernética no curto prazo. Mas a questão está longe de ser resolvida: a história sugere que nossa fé na inviolabilidade muitas vezes foi mal colocada e, ao longo dos anos, candidatos a criptografia aparentemente impenetráveis foram vítimas de ataques surpreendentemente simples. Os cientistas da computação se encontram em uma encruzilhada curiosa, sem saber se os algoritmos pós-quânticos são realmente inatacáveis — ou se apenas se acredita que sejam. Essa é uma distinção que está no centro da segurança da criptografia moderna.
O mito e a realidade da “inquebrabilidade”
A proteção de mensagens secretas nem sempre esteve vinculada a problemas matemáticos difíceis; até recentemente, a criptografia não tinha quase nada de matemática. Na Grécia antiga, os líderes militares codificavam mensagens usando uma foice, um dispositivo cilíndrico que revelava uma mensagem oculta quando uma tira de texto aparentemente confusa era enrolada em torno dele. Séculos mais tarde, historiadores romanos descreveram um código, geralmente atribuído a Júlio César, que envolvia o deslocamento de letras em uma mensagem três pontos acima no alfabeto; por exemplo, um d seria escrito como um a.
Tanto na história quanto em nosso mundo moderno, os códigos secretos eram frequentemente quebrados. No século XVI, durante as décadas em que passou presa por sua prima, a Rainha Elizabeth I, Mary, Rainha dos Escoceses, usou cifras elaboradas, baseadas em símbolos, para codificar centenas de cartas, a maioria delas com o objetivo de garantir sua liberdade e recuperar o trono. Ela não prevaleceu: a equipe de espiões e decifradores de Elizabeth I interceptou, decodificou e copiou as cartas. Na carta que selou seu destino, Mary aprovou um plano para assassinar Elizabeth com seis palavras: “Coloque os seis cavalheiros para trabalhar”. Em resposta, Elizabeth acabou ordenando que sua prima fosse decapitada em 1587.
Em 1932, os decifradores de códigos na Polônia decifraram o código da máquina Enigma da Alemanha, inventada no final da Primeira Guerra Mundial. Mais tarde, eles compartilharam suas informações com os decifradores de códigos britânicos, que decifraram uma versão mais avançada da Enigma durante a Segunda Guerra Mundial.
Pass, o cientista teórico da computação em Tel Aviv, refere-se, meio brincando, a todo o período anterior à década de 1970 como a “idade das trevas da criptografia”.
“A criptografia não era realmente um campo científico”, diz ele. “Era mais como um artista contra os agressores. Você precisava ter habilidades [artísticas] para inventar um esquema de criptografia. E então ele era implantado até que alguma pessoa inteligente descobrisse como quebrá-lo. E assim por diante.”
Isso mudou, diz Pass, em novembro de 1976, quando os criptógrafos Whitfield Diffie e Martin Hellman, em Stanford, descreveram uma nova maneira de duas pessoas criarem uma chave que somente elas conheciam — uma chave que poderia ser usada para passar mensagens secretas. O mais importante é que elas não precisariam se encontrar para fazer isso. Essa foi uma noção inovadora. Anteriormente, tanto o remetente quanto o destinatário precisavam possuir fisicamente uma chave para codificação e decodificação. Para descriptografar uma mensagem codificada com a máquina Enigma, por exemplo, o destinatário precisava de uma folha de chaves que revelasse as configurações iniciais de criptografia.
O segredo da estratégia Diffie-Hellman era que duas pessoas criassem a chave usando um problema matemático simples que é fácil de calcular em uma direção e trabalhoso na outra. Veja como funciona: as duas pessoas que desejam se comunicar secretamente, geralmente designadas Alice e Bob nessas configurações, escolhem um número secreto cada uma. Em seguida, juntas, elas concordam com um par de números que compartilham publicamente (um é um primo grande e o outro é chamado de base). Em seguida, cada um deles executa uma série de operações matemáticas para combinar esses números privados com o primo e a base.
Em seguida, eles trocam os resultados e cada um executa outra série de operações matemáticas com os novos números. No final, tanto Alice quanto Bob terão feito as mesmas operações com os mesmos números — mas não na mesma ordem — e chegarão à mesma resposta. Os dígitos dessa resposta se tornam a criptografia. E um espião que intercepta a transmissão — muitas vezes apelidado de Eve — não conseguirá desvendar facilmente a confusão matemática sem conhecer pelo menos um dos números privados. Ela poderia começar a testar os números em uma abordagem de força bruta, mas isso exigiria uma quantidade excessiva de cálculos.
O problema complicado que Eve teria que resolver é chamado de encontrar um logaritmo discreto. A abordagem Diffie-Hellman ainda é usada atualmente — para proteger algumas VPNs, por exemplo — e é parte integrante de alguns esquemas pós-quânticos.
Em seu artigo, Diffie e Hellman observaram que não havia nenhum algoritmo capaz de resolver o problema de log discreto em um período de tempo razoável. Ainda não há. Eles introduziram, pela primeira vez, a noção de funções unidirecionais como base para a criptografia segura.
Atualmente, as interações on-line seguras que envolvem autenticação ou assinaturas digitais, por exemplo, são baseadas nessa ideia geral. Mas sem a prova matemática de que os problemas nos quais eles se baseiam são funções unidirecionais, permanece a possibilidade de que alguém descubra um esquema eficiente para decifrá-las.
A ameaça quântica
Atualmente, as transações on-line começam com uma espécie de aperto de mão digital, e a segurança desse aperto de mão geralmente é garantida por outro problema matemático que se presume ser difícil. O esquema de criptografia mais popular usado atualmente foi introduzido em 1977 por um trio de jovens cientistas da computação que foram estimulados pelo artigo de 1976 de Diffie e Hellman. Eles chamaram sua abordagem de RSA, em homenagem aos sobrenomes dos cientistas (Ron Rivest, Adi Shamir e Leonard Adleman).
O RSA, que se baseia na dificuldade de encontrar fatores primos em relação à facilidade de multiplicá-los, é um pouco diferente da abordagem Diffie-Hellman. O Diffie-Hellman é um segredo compartilhado: ele permite que dois usuários criem uma chave por meio de um canal inseguro (como a Internet) e essa chave é usada para disfarçar mensagens. No RSA, Alice usa a chave de Bob — baseada em grandes números primos — para criptografar uma mensagem que somente ele pode desbloquear. O RSA pode proteger dados enviados de uma pessoa para outra.
Ele se tornou rapidamente um dos métodos de criptografia de chave pública mais populares. É fácil de usar e adaptar. Com o passar do tempo, à medida que surgiram novos algoritmos que podem ser fatorados mais rapidamente e os computadores se tornaram mais potentes, o NIST recomendou o uso de números cada vez maiores para a segurança. Os números são representados em formato binário com 1s e 0s, e esses dígitos binários são mais conhecidos como “bits”. O número 13, por exemplo, é escrito em binário como 1101, que tem quatro bits. Atualmente, o NIST recomenda o uso de uma chave representada por pelo menos 2.048 bits, o que corresponde a um número com mais de 600 dígitos. (Até o momento, o maior número que foi fatorado em dois primos era composto de 250 dígitos e o processo levou quase 3.000 horas de tempo de computação). Esse é um ponto forte do RSA: mesmo que não seja indecifrável, tem sido fácil continuar aumentando a aposta, tornando sua quebra computacionalmente impraticável.
Em 1994, no entanto, surgiu uma ameaça de um tipo diferente quando o matemático americano Peter Shor, então no Bell Labs, desenvolveu um algoritmo para computadores quânticos que poderia resolver o problema de fatoração em um período de tempo razoável. (Era uma ameaça dupla: sua abordagem também poderia resolver o problema do log discreto na abordagem Diffie-Hellman).
O artigo de Shor provocou entusiasmo e ansiedade entre aqueles que queriam construir computadores quânticos e aqueles que reconheciam a ameaça que isso representava para a segurança cibernética. Felizmente para os criptógrafos, não é qualquer computador quântico que serve.
As últimas três décadas de segurança cibernética têm se desenrolado como um jogo cada vez mais intrincado, com pesquisadores perpetuamente criando e quebrando — ou tentando quebrar — novos candidatos.
Há alguns anos, pesquisadores do Google e do KTH Royal Institute of Technology, na Suécia, estimaram que um computador quântico composto por 20 milhões de bits quânticos, ou qubits, levaria cerca de oito horas para quebrar a segurança RSA de 2.048 bits atual. As máquinas atuais de última geração não chegam nem perto desse tamanho: o maior computador quântico até hoje, construído pela IBM, foi lançado no ano passado com 433 qubits.
Se o RSA pode ou não ser considerado em risco imediato de um ataque quântico depende muito de quem você pergunta, diz o cientista da computação Ted Shorter, cofundador da empresa de segurança cibernética Keyfactor. Ele vê uma divisão cultural entre os teóricos que estudam a matemática da criptografia e os criptógrafos que trabalham na implementação.
Para alguns, o fim parece próximo. Você conversa com um cientista da computação teórico e ele diz: “sim, é o fim do RSA está, porque ele consegue imaginar isso”, diz Shorter. Para eles, acrescenta, a existência do algoritmo de Shor aponta para o fim da criptografia como a conhecemos.
Muitos criptógrafos que estão implementando sistemas de segurança no mundo real estão menos preocupados com o futuro quântico do que com os hackers mais espertos de hoje. Afinal de contas, as pessoas vêm tentando fatorar com eficiência há milhares de anos e agora o único método conhecido requer um computador que não existe.
Thomas Decru, criptógrafo da KU Leuven, na Bélgica, diz que a ameaça quântica deve ser levada a sério, mas é difícil saber se o RSA cairá nas mãos dos computadores quânticos em cinco anos ou mais — ou nunca. “Enquanto os computadores quânticos não existirem, tudo o que se diz sobre eles é especulativo, de certa forma”, diz ele. Pass tem mais certeza sobre a ameaça: “É seguro dizer que a existência desse algoritmo quântico significa que há brechas no problema, certo?”
Os espinhos da implementação
Mas precisamos estar preparados para tudo, diz Lily Chen, matemática que gerencia o Cryptographic Technology Group do NIST e trabalha no esforço contínuo para produzir padrões de criptografia pós-quântica. Quer cheguem em três anos ou em 30, os computadores quânticos estão no horizonte, e o RSA, o Diffie-Hellman e outros esquemas de criptografia podem ficar vulneráveis.
Encontrar um esquema criptográfico resistente ao quantum não é fácil. Sem um problema matemático que seja computacionalmente difícil, as últimas três décadas de segurança cibernética têm se desenrolado como um jogo cada vez mais intrincado, com os pesquisadores perpetuamente construindo e quebrando — ou tentando quebrar — novos candidatos.
Esse empurra-empurra já surgiu no programa pós-quântico do NIST. Em fevereiro de 2022, os criptógrafos encontraram uma falha fatal no Rainbow, um algoritmo que havia sobrevivido a três rodadas de análise do NIST. Alguns meses depois, após a lista do NIST ter sido reduzida novamente, Decru e seu colega da KU Leuven, Wouter Castryck, anunciaram que haviam quebrado outro finalista, um algoritmo chamado SIKE.
O SIKE, que foi desenvolvido há alguns anos, é fruto de uma colaboração entre pesquisadores e engenheiros da Amazon, Microsoft, Universidade de Versalhes e outros. Ele se baseia em um mapa matemático especial, chamado de isogenia, que é composto de conexões entre curvas elípticas. Esses mapas podem ser transformados em uma criptografia para comunicação e pessoas de fora não podem espionar sem conhecê-los.
Em Leuven, Decru e Castryck desenvolvem maneiras de usar essas chamadas isogenias para criar abordagens de criptografia novas e mais rápidas. Eles quebraram a versão mais difícil do SIKE em apenas algumas horas de tempo de execução usando um desktop comum. (Desde então, outros grupos encontraram maneiras de fazer isso ainda mais rápido.) Além disso, Decru e Castryck fizeram isso quase que acidentalmente, e apenas algumas semanas depois que o SIKE foi declarado finalista alternativo do NIST. “Não estávamos tentando quebrá-lo de forma alguma”, insiste Decru. “Apenas tentamos generalizá-lo.”
Chen diz que o caso do SIKE — e do Rainbow antes dele — ilustra uma tensão do mundo real que impulsiona os esforços para encontrar algoritmos à prova de quantum. Por um lado, diz ela, “você precisa encontrar um problema que seja difícil tanto para computadores quânticos quanto para computadores clássicos”. Por outro lado, está a implementação: transformar esse problema difícil em um problema que possa ser usado em um sistema criptográfico do mundo real. Mesmo com os problemas bem definidos de hoje, diz Shorter, é muito difícil prever e evitar todas as brechas em todos os sistemas operacionais e dispositivos disponíveis no mercado. “Além disso, há testes de interoperabilidade, certificações e outros testes”, diz ele, “para garantir que eles não sejam apenas implementados corretamente, mas também de forma segura”.
O problema matemático no qual o SIKE se baseia parece ser computacionalmente difícil porque há muitos mapas diferentes que poderiam ser construídos entre curvas. Pode até ser um problema unidirecional e, portanto, à prova de quantum. A falha estava no design, que revelava muito das informações transmitidas. Decru e Castryck descobriram o problema porque, inadvertidamente, encontraram uma maneira de expor pontos de conexão suficientes para revelar tudo.
Outros esquemas se saíram melhor. O primeiro algoritmo de criptografia pós-quântica a ser padronizado, o CRYSTALS-Kyber, oferece segurança por meio de uma abordagem que envolve problemas em redes, objetos matemáticos que podem ser modelados como matrizes de pontos. (Há cinco famílias principais de métodos criptográficos pós-quânticos. As abordagens de isogenia e de rede são duas delas).
O CRYSTALS-Kyber é um esquema de criptografia geral, como o RSA, que pode ser usado para tarefas como proteger a comunicação on-line. Três outros algoritmos aprovados são projetados para autenticar assinaturas digitais, garantindo que os documentos digitais não tenham sido assinados de forma fraudulenta. O NIST planeja padronizá-los até a primavera de 2024. Outros três (eram quatro até a quebra do SIKE) também poderão ser padronizados nos próximos anos, desde que sobrevivam a novas rodadas de análise.
Mas, a menos que os matemáticos consigam provar se existem funções unidirecionais, diz Pass, os padrões que sempre caracterizaram a criptografia continuarão. “Voltamos a esse jogo de gato e rato, em que os projetistas de algoritmos propõem novas construções candidatas e outros projetistas tentam quebrá-las”, diz ele. A menos, é claro, que ele – ou alguém de sua área – consiga criar uma função implementável e comprovadamente unidirecional para resolver a questão da criptografia para sempre.
Até lá, os criptógrafos permanecerão em um limbo confuso no qual esquemas de criptografia convincentemente robustos são confiáveis — mas somente até que não sejam mais.
O problema matemático perfeito poderia nos tirar desse limbo, mas não pode ser uma bagunça pegajosa elaborada por um algebrista de poltrona em um longo fim de semana. Ele deve encontrar um equilíbrio entre a matemática e a criptografia, com a dificuldade computacional de um lado e a facilidade de implementação do outro. Se você se afastar demais de qualquer uma dessas propriedades, ela se tornará vulnerável – se não agora, então no futuro. O que está em jogo é a segurança passada, presente e futura dos dados de todos, em qualquer lugar. Sem pressão.
Stephen Ornes é um escritor de ciência que mora em Nashville.
MIT Technology Review
