Por Natalie Wolchover
Publicado na Quanta Magazine
Em 11 de agosto, a Agência Nacional de Segurança atualizou uma página obscura em seu site com um anúncio de que planeja deslocalizar a criptografia de dados governamentais e militares de esquemas criptográficos atuais para novos, ainda por determinar, que podem resistir a um ataque de computadores quânticos.
“Agora está claro que as atuais medidas de segurança da Internet e a criptografia por trás delas não suportarão as novas capacidades computacionais que os computadores quânticos trarão”, declarou o porta-voz da NSA, Vanee ‘Vines, em um e-mail, confirmando a mudança. “A missão da NSA de proteger os sistemas críticos de segurança nacional exige que a agência antecipe tais desenvolvimentos”.
Os computadores quânticos, uma vez vistos como uma possibilidade teórica remota , agora são amplamente esperados para trabalhar dentro de cinco a 30 anos. Ao explorar as regras probabilísticas da física quântica, os dispositivos poderiam decifrar a maioria dos dados “seguros” do mundo, dos segredos da NSA aos registros bancários e às senhas de e-mail. Consciente dessa ameaça iminente, os criptógrafos têm corrido para desenvolver esquemas “resistentes ao quantum”, o que é suficiente para o uso generalizado.
Acredita-se que os esquemas mais promissores sejam aqueles baseados na matemática das redes — multidimensional, repetindo grades de pontos. Esses esquemas dependem de quão difícil é encontrar informações escondidas em uma rede com centenas de dimensões espaciais, a menos que você conheça a rota secreta.
Mas em outubro passado, os criptógrafos da sede de comunicação do governo (GCHQ), agência de vigilância eletrônica da Grã-Bretanha, publicaram um documento enigmático online que questionou a segurança de alguns dos esquemas mais eficientes em rede. As descobertas sugeriram que as vulnerabilidades penetraram durante um impulso de uma década para uma eficiência cada vez maior. À medida que os criptógrafos simplificavam as redes subjacentes nas quais seus esquemas se baseavam, eles tornaram os esquemas mais suscetíveis ao ataque.
Com base nas alegações do GCHQ, duas equipes de criptoanalistas passaram o ano passado a determinar quais esquemas baseados em rede podem ser quebrados por computadores quânticos e que são seguros — por enquanto.
“Esta é a encarnação moderna do clássico jogo de gato e rato entre o criptógrafo e o criptoanalista”, disse Ronald Cramer, do Instituto Nacional de Pesquisa em Matemática e Ciência da Computação (CWI) da Universidade de Leiden, na Holanda. Quando os criptoanalistas são silenciosos, os criptógrafos afrouxam os fundamentos de segurança dos esquemas para torná-los mais eficientes, disse ele. “Mas, em algum momento, uma linha vermelha pode ser cruzada. Foi o que aconteceu aqui. “Agora, os criptoanalistas estão falando.
Segredos abertos
Toda vez que você visita um site com uma URL que começa “HTTPS”, você envia ou recebe dados criptografados. As transações seguras da Internet são possíveis pela criptografia de chave pública, uma invenção revolucionária da década de 1970. Até então, a criptografia tinha sido principalmente um jogo para governos e espiões; Duas partes, como um espião e um manipulador, tiveram que concordar antecipadamente em uma cifra secreta ou “chave” para se comunicar em segredo. (A simples “cifra César”, por exemplo, desloca as letras do alfabeto por algum número de posições acordado). A criptografia de chave pública possibilita que alguém envie a qualquer pessoa uma mensagem criptografada que apenas o destinatário pode descriptografar, mesmo que as partes envolvidas nunca concordassem em nada e não importa quem estivesse ouvindo.
“A recepção da NSA foi apoplética”, Martin Hellman, um dos três pesquisadores da Universidade de Stanford que inventaram criptografia de chave pública, lembrou em 2004.
Na criptografia de chave pública, os dados são protegidos por problemas de matemática que são fáceis de resolver, mas difíceis de engenharia reversa. Por exemplo, enquanto é fácil para um computador multiplicar dois números primos para produzir um inteiro maior, como no cálculo 34,141 x 81,749 = 2,790,992,609, é difícil — isto é, leva um tempo impraticável em um computador — para fatorar um inteiro suficientemente grande em seus componentes primos. Em um esquema de criptografia baseado em fatoração primária, os primos servem como “chave privada” de uma pessoa, que não é compartilhada. O produto dos primos serve como a “chave pública”, que é distribuída publicamente. Quando alguém usa a chave pública para criptografar uma mensagem, somente a pessoa em posse da chave privada pode descriptografá-la.
Dois esquemas eficientes de criptografia de chave pública que surgiram no final da década de 1970 continuam sendo os mais usados atualmente: RSA (inventado por Ron Rivest, Adi Shamir e Leonard Adleman), baseado no principal problema de fatoração e na troca de chaves Diffie-Hellman (inventada por Whit Diffie e Hellman), com base no chamado problema de logaritmo discreto. Embora não houvesse nenhuma prova real de que fatores primos ou logaritmos discretos eram impossíveis de calcular em um prazo razoável, ninguém poderia encontrar algoritmos para computação eficiente deles.
“Com o tempo, as pessoas acumulam confiança na dureza de algum problema porque tantas pessoas tentaram pensar em como quebrá-lo e não pode”, disse Jill Pipher, um matemático e criptógrafo da Brown University.
Com os algoritmos existentes, leva anos para calcular os principais fatores associados a uma chave pública de comprimento típico. E assim, RSA e a troca de chaves Diffie-Hellman tornaram-se a armadura da Internet, e uma sensação de segurança reinou.
Essa segurança, então, veio com um prazo de validade.
Algoritmo de Shor
Hipóteses sobre quais problemas de matemática são difíceis para os computadores serem resolvidos em 1994, quando um pesquisador da AT & T chamado Peter Shor revelou o poder decodificador teórico dos futuros computadores quânticos.
Em um computador comum, a informação é armazenada em unidades chamadas bits que podem existir em qualquer um dos dois estados designados 0 ou 1. A capacidade computacional do computador é proporcional ao número de bits. Em computadores quânticos, no entanto, as unidades de armazenamento de informações, chamadas qubits, podem existir em ambos os estados 0 e 1 simultaneamente. (Qubits pode assumir a forma de partículas subatômicas girando tanto no sentido horário como anti-horário, ao mesmo tempo, por exemplo). Como um sistema de qubits muitos podem existir em todas as combinações possíveis de todos os seus possíveis estados individuais, a capacidade computacional de um computador quântico aumentar exponencialmente com o número de qubits.
Isso parece tornar os computadores quânticos mais poderosos solucionadores de problemas do que computadores clássicos. No entanto, na verdade, tocando seu potencial requer encontrar um algoritmo para malabarismos com suas realidades simultâneas, de modo que, no final, o caminho certo — ou seja, o estado do sistema que corresponde à resposta correta — emerge. Durante mais de uma década após a computação quântica ter sido concebida no início da década de 1980, nenhum algoritmo promissor surgiu, e o campo enfraqueceu. “Francamente, ninguém prestou atenção”, disse Seth Lloyd, um teórico da computação quântica no Massachusetts Institute of Technology.
Tudo isso mudou em 1994, quando Shor, que agora está no MIT, desenvolveu um algoritmo de computação quântica capaz de computar de forma eficiente tanto fatores primos como logaritmos discretos e, assim, quebrar a criptografia RSA e a troca de chaves Diffie-Hellman. “Nesse ponto, havia um aplicativo assassino para computação quântica — talvez você pudesse chamá-lo de quapp — e o interesse pela computação quântica cresceu”, disse Lloyd.
Com as capacidades computacionais superiores dos computadores quânticos revelados pelo algoritmo de Shor, os pesquisadores do mundo estão correndo para construí-los desde então. Paralelamente, os criptógrafos têm corrido para criar novos esquemas de que os computadores quânticos não conseguem quebrar. “Nós não sabíamos por onde procurar por muito tempo”, disse Chris Peikert, um criptógrafo do Georgia Institute of Technology em Atlanta. “Mas as redes parecem ser uma base muito boa”.
Perdido em Grades
Assim como a segurança da criptografia RSA baseia-se na ideia de que é fácil multiplicar primos, mas difícil de calcular fatores primos, a segurança dos esquemas de criptografia em rede baseia-se na facilidade de se perder em uma rede de 500 dimensões: você simplesmente comece em um ponto de rede e balanceie as coordenadas espaciais, terminando em algum local próximo. Mas é extremamente difícil encontrar o ponto de rede mais próximo, dado uma localização arbitrária em espaço de 500 dimensões. Em esquemas baseados em rede, a chave privada está associada ao ponto de rede e a chave pública está associada à localização arbitrária no espaço.
Apesar da promessa, a criptografia em rede foi iniciada lentamente. Na década de 1980, as chaves públicas baseadas em redes eram muito longas, exigindo megabytes de dados para transmitir. Os criptógrafos foram forçados a simplificar as redes subjacentes por uma questão de eficiência. Em uma rede genérica, os pontos de rede são gerados tomando todas as combinações lineares possíveis de algum conjunto de vetores (setas apontando em direções diferentes). Atribuir um padrão a esses vetores torna a rede resultante mais simples e as chaves associadas mais curtas. Invariavelmente, no entanto, a simplificação da rede também facilita a navegação, permitindo que as chaves privadas sejam deduzidas das chaves públicas, rompendo assim o esquema. “As redes tornaram-se sinônimo de desastre — com tentativas fracassadas de criptografar”, disse Jeff Hoffstein, um matemático da Brown.
Enquanto o resto do mundo continuava, alguns criptógrafos continuavam a mexer com redes. Em 1995, Hoffstein, com Pipher e outro colega da Brown, Joe Silverman, desenvolveu um esquema criptográfico baseado em redes “cíclicas”, que são geradas por vetores que podem rodar em qualquer direção e ainda aterrissem em outro ponto de rede. NTRU, como eles chamaram de esquema, foi extremamente eficiente — ainda mais do que os protocolos RSA e Diffie-Hellman. Embora não houvesse nenhuma prova de que as redes cíclicas subjacentes à NTRU eram difíceis de navegar pelos computadores, ou que a NTRU era segura, 20 anos se passaram e ninguém encontrou uma maneira de quebrá-lo, aumentando a confiança em sua segurança.
A promessa de cotas cresceu dramaticamente em 1997, quando os pesquisadores da IBM, Miklós Ajtai e Cynthia Dwork, criaram o primeiro esquema de criptografia em rede que foi provávelmente tão difícil de romper quanto o problema de rede subjacente é difícil de resolver. Com base nesse trabalho, Oded Regev, cientista teórico da Universidade de Nova York, Courant Institute of Mathematical Sciences, provou em 2005 que os esquemas criptográficos baseados em um problema chamado aprendizagem com erros (LWE) são seguros contra computadores quânticos, desde que O problema de encontrar o ponto mais próximo em uma rede genérica é difícil para computadores quânticos (como a maioria dos pesquisadores presumem). A LWE era ineficiente, mas Regev, Peikert e Vadim Lyubashevsky, que agora está na IBM Research na Suíça, logo desenvolveu esquemas análogos baseados em redes “ideais” (que estão intimamente relacionadas com redes cíclicas) e mostraram que esses esquemas mais eficientes, denominados Ring-LWE, são seguros, desde que subjacentes , o problema da rede ideal é difícil.
Mais uma vez, no entanto, parecia haver uma compensação entre segurança e eficiência, e uma impossibilidade incrivel de ter os dois. O Ring-LWE tinha melhores garantias de segurança que a NTRU e era muito mais versátil , mas não era tão eficiente. Alguns pesquisadores acreditavam que poderiam fazer melhor. Desde 2007, eles estão considerando esquemas criptográficos baseados em “redes ideais principais”, que são gerados por um único vetor, da mesma forma que o conjunto de inteiros {…, -6, -3, 0, 3, 6, 9, …} pode ser gerado por múltiplos do inteiro 3.
“Eles eram gananciosos; eles não estavam felizes com a eficiência existente”, disse Regev.
Aprender com erros
Em 2005, Oded Regev desenvolveu um esquema criptográfico baseado em um problema chamado “aprendendo com erros”, o que ele provou ser tão seguro quanto o problema da rede é difícil. Os esquemas baseados em LWE funcionam assim:
Escolha qualquer número ímpar, e não diga a ninguém o que é. Essa é a sua chave privada. Agora multiplique-o por qualquer outro número, e adicione um pequeno número par a ele. (Por exemplo, se o seu número original for 121, você pode multiplicá-lo por cinco e depois adicionar dois, obtendo 607. Na prática, os números são muito maiores.) Faça isso muitas vezes, produzindo uma lista de versões ampliadas e perturbadas da sua chave privada. Esta lista de números é a sua chave pública. Diga ao mundo.
Agora, diga que alguém quer enviar uma mensagem (por exemplo, 0 ou 1, ataque ou recuo, sim ou não). Primeiro, essa pessoa seleciona aleatoriamente metade dos números listados em sua chave pública e os adiciona juntos. Então, para enviar a mensagem “0”, seu correspondente simplesmente envia a soma para você. Para enviar a mensagem “1”, a pessoa adiciona um à soma e, em seguida, envia isso de volta para você. Agora, para decodificar a mensagem, você simplesmente divide a soma que recebeu pela sua chave privada. Se o restante for uniforme, a mensagem é “0.” Se o restante for estranho, a mensagem é “1.”
Gato e rato
À medida que os criptógrafos acadêmicos criavam esquemas criptográficos baseados em redes primárias ideais, as pessoas também estavam nos bastidores do GCHQ. Seu esquema secreto, chamado Soliloquy, empregou técnicas da teoria dos números para reduzir o tamanho da chave pública de uma matriz de números grandes para um único número primo. No problema da rede subjacente, isso equivale a gerar uma rede com um vetor único e muito curto. “Infelizmente, as construções usadas para fazer isso foram seu calcanhar de Aquiles”, disse um porta-voz do GCHQ em um e-mail.
Em seu artigo publicado em outubro passado, intitulado “Soliloquy: A Cautionary Tale”, os pesquisadores do GCHQ revelaram que haviam inventado o Soliloquy e depois abandonaram o trabalho em 2013 ao descobrir um ataque quântico que poderia quebrá-lo. O documento forneceu apenas um esboço vago do ataque, no entanto, deixando aberta a questão de como ele funcionou e quais outros esquemas baseados em rede podem ser afetados. Parecia que, na busca da eficiência, uma linha vermelha havia sido cruzada. Mas onde estava a linha?
“Havia essa ideia inicial de que esse ataque poderia ser mais amplo e talvez implicasse toda a criptografia baseada em rede”, disse Pipher. Outros ficaram céticos quanto ao ataque ter trabalhado.
Os criptógrafos passaram quase um ano a determinar o alcance do ataque Soliloquy. “As pessoas ficaram obcecadas”, disse Hoffstein. “Houve um frenesi.” Descobriu-se que a equipe do GCHQ não havia elaborado muitos detalhes, mas simplesmente tinha “evidências suficientemente fortes de que um ataque poderia ser desenvolvido e, portanto, que o Soliloquy não poderia ser recomendado para o uso do mundo real” como o porta-voz colocou em um e-mail. Em um artigo de março, Regev, Peikert, Cramer e Léo Ducas da CWI resolveram a parte do ataque que requeria apenas um computador comum; na semana passada, Jean-François Biasse e Fang Song, da Universidade de Waterloo, em Ontário, estabeleceram os passos quânticos.
Além do Soliloquy, os achados indicaram que outros esquemas baseados em redes principais geradas por um único vetor curto também são quebrados, enquanto que esquemas baseados em redes genéricas mais genéricas, como Ring-LWE e NTRU, não são afetados. “Parece haver alguns obstáculos técnicos iniciais na transferência dessas técnicas para outros esquemas importantes”, disse Cramer, acrescentando que isso merece mais estudos.
No contínuo de segurança e eficiência, os criptógrafos deslizaram muito longe para o lado da eficiência. Em sua disputa para encontrar os melhores esquemas quânticos para bancos, governos e o resto da internet segura, o ataque Soliloquy os forçou de volta, em direção a esquemas que são um pouco menos eficientes, mas mais firmemente baseados em problemas difíceis de rede. Ou seja, presumimos difíceis problemas de rede.
Não há provas de que os computadores quânticos não conseguem encontrar o caminho para as redes. “Pode ser que todos esses problemas sejam realmente fáceis”, disse Peikert. “Mas parece improvável, dado o que sabemos”.
Quanto ao porquê a extrema eficiência e a segurança perfeita parecem ser tão diametralmente opostas, Hoffstein disse: “O universo é um lugar irritante, e este é apenas mais um exemplo disso”.
Tradução fornecida por Elton Wade a partir de seu projeto de divulgação científica.
