Se os protocolos de criptografia atuais falhassem, seria impossível proteger as conexões online — enviar mensagens confidenciais, fazer transações financeiras seguras ou autenticar dados. Qualquer um podia acessar qualquer coisa; qualquer um podia fingir ser qualquer um. A economia digital entraria em colapso.
Quando (ou if) um computador quântico totalmente funcional se torna disponível, é exatamente isso que pode acontecer. Como resultado, em 2017, o Instituto Nacional de Padrões e Tecnologia (NIST) do governo dos EUA lançou uma competição internacional para encontrar as melhores maneiras de alcançar a criptografia “pós-quântica”.
No mês passado, a agência selecionou seu primeiro grupo de vencedores: quatro protocolos que, com alguma revisão, serão implantados como um escudo quântico. Também anunciou quatro candidatos adicionais ainda em análise.
Então, em 30 de julho, dois pesquisadores revelaram que tinham quebrou um desses candidatos em uma hora em um laptop. (Desde então, outros fizeram o ataque ainda mais rápido, quebrando o protocolo em questão de minutos.) “Um ataque tão dramático e poderoso … foi um choque”, disse Steven Galbraith, matemático e cientista da computação da Universidade de Auckland, na Nova Zelândia. Não apenas a matemática subjacente ao ataque foi surpreendente, mas também reduziu a diversidade (muito necessária) da criptografia pós-quântica – eliminando um protocolo de criptografia que funcionava de maneira muito diferente da grande maioria dos esquemas da competição do NIST.
“É um pouco chato”, disse Christopher Peikert, um criptógrafo da Universidade de Michigan.
Os resultados deixaram a comunidade de criptografia pós-quântica abalada e encorajada. Abalado, porque esse ataque (e outro de uma rodada anterior da competição) de repente transformou o que parecia uma porta de aço digital em jornal molhado. “Veio do nada”, disse Dustin Moody, um dos matemáticos que lideram o esforço de padronização do NIST. Mas se um esquema criptográfico for quebrado, é melhor que isso aconteça bem antes de ser usado na natureza. "Há muitas emoções que passam por você", disse David Jao, um matemático da Universidade de Waterloo, no Canadá, que, junto com o pesquisador da IBM Lucas De Feo, propôs o protocolo em 2011. Certamente surpresa e decepção estão entre eles. “Mas também”, acrescentou Jao, “pelo menos quebrou agora”.
O segredo anda entre as curvas
Jao e De Feo viram uma oportunidade para um sistema criptográfico que fosse semelhante e adequadamente distinto de protocolos bem conhecidos. Seu esquema, chamado de protocolo Diffie-Hellman de isogenia supersingular (SIDH), lidava com curvas elípticas – os mesmos objetos matemáticos usados em um dos tipos mais difundidos de criptografia implantados hoje. Mas ele os usou de uma maneira completamente diferente. Era também o esquema mais compacto que o NIST estava considerando (com a desvantagem de ser mais lento do que muitos dos outros candidatos).
E “matematicamente, é muito elegante”, disse Jao. “Na época, parecia uma bela ideia.”
Digamos que duas partes, Alice e Bob, queiram trocar uma mensagem em segredo, mesmo sob o olhar atento de um possível invasor. Eles começam com uma coleção de pontos conectados por arestas chamado grafo. Cada ponto representa uma curva elíptica diferente. Se você puder transformar uma curva em outra de uma maneira específica (por meio de um mapa chamado isogenia), desenhe uma aresta entre o par de pontos. O gráfico resultante é enorme e fácil de se perder: se você der uma caminhada relativamente curta ao longo de suas bordas, acabará em algum lugar que parece completamente aleatório.
Os gráficos de Alice e Bob têm todos os mesmos pontos, mas as arestas são diferentes — eles são definidos por diferentes isogenias. Alice e Bob começam no mesmo ponto, e cada um salta ao longo de arestas aleatórias em seu próprio gráfico, acompanhando seu caminho de um ponto a outro. Cada um publica sua localização final, mas mantém seu caminho em segredo.
Agora eles trocam de lugar: Alice vai para o ponto final de Bob e Bob para o de Alice. Cada um repete sua caminhada secreta. Eles fazem isso de tal forma que ambos vão acabar no mesmo ponto.
Esse local foi encontrado em segredo, então Alice e Bob podem usá-lo como sua chave secreta — informações que lhes permitem criptografar e descriptografar as mensagens um do outro com segurança. Mesmo que um invasor veja os pontos intermediários que Alice e Bob enviam um ao outro, eles não conhecem a caminhada secreta de Alice ou Bob, portanto, não podem descobrir esse ponto final.
Mas para fazer o SIDH funcionar, Alice e Bob também precisam trocar algumas informações adicionais sobre suas caminhadas. Essa informação extra é o que levou à queda do SIDH.
Uma nova reviravolta na velha matemática
Thomas Decru não partiu para quebrar SIDH. Ele estava tentando construir sobre isso – generalizar o método para aprimorar outro tipo de criptografia. Isso não funcionou, mas gerou uma ideia: sua abordagem pode ser útil para atacar o SIDH. E assim ele se aproximou Wouter Castryck, seu colega na Universidade Católica de Leuven na Bélgica e um de seus ex-orientadores de doutorado, e os dois mergulharam na literatura relevante.
Eles se depararam com um artigo publicado pelo matemático Ernesto Kani em 1997. Nele havia um teorema que “era quase imediatamente aplicável ao SIDH”, disse Castryck. “Acho que quando percebemos isso… o ataque veio bem rápido, em um ou dois dias.”
Em última análise, para recuperar a caminhada secreta de Alice (e, portanto, a chave compartilhada), Castryck e Decru examinaram o produto de duas curvas elípticas — a curva inicial de Alice e a curva que ela enviou publicamente a Bob. Essa combinação produz um tipo de superfície chamada superfície abeliana. Eles então usaram essas superfícies abelianas, o teorema de Kani (que relaciona superfícies abelianas a curvas elípticas) e as informações extras que Alice deu a Bob para descobrir cada passo que Alice dava.
“É quase como um sinal de retorno que permite que você bloqueie [certas superfícies abelianas]”, disse Jao. “E esse sinal lhe diz que este é o caminho que você deve seguir para dar o próximo passo para encontrar a [caminhada secreta] correta.” O que os levou direto à chave compartilhada de Alice e Bob.
“É uma abordagem muito inesperada, indo para objetos mais complicados para obter resultados sobre o objeto mais simples”, disse Jao.
“Fiquei muito empolgado ao ver essa técnica sendo usada”, disse Cristina Lauter, um matemático e criptógrafo da Meta AI Research que não apenas ajudou a desenvolver criptografia baseada em isogenia, mas também trabalhou em superfícies abelianas. “Então, envergonhe-me por não pensar nisso como uma maneira de quebrá-lo.”
O ataque de Castryck e Decru quebrou a versão de segurança mais baixa do protocolo SIDH em 62 minutos e o nível de segurança mais alto em pouco menos de um dia. Então, pouco depois, outro especialista ajustou o ataque para que levasse apenas 10 minutos para quebrar a versão de baixa segurança e algumas horas para quebrar a de alta segurança. Ataques mais gerais postado nas últimas semanas tornam improvável que o SIDH possa ser recuperado.
“Foi um sentimento especial”, disse Castryck, embora agridoce. “Nós matamos um dos nossos sistemas favoritos.”
Um momento divisor de águas
É impossível garantir que um sistema seja incondicionalmente seguro. Em vez disso, os criptógrafos contam com tempo suficiente e pessoas suficientes tentando resolver o problema para se sentirem confiantes. “Isso não significa que você não acordará amanhã e descobrirá que alguém encontrou um novo algoritmo para fazer isso”, disse Jeffrey Hoffstein, um matemático da Brown University.
Daí porque competições como as do NIST são tão importantes. Na rodada anterior da competição NIST, Ward Beullens, um criptógrafo da IBM, concebeu um ataque que quebrou um esquema chamado Rainbow em um fim de semana. Como Castryck e Decru, ele só foi capaz de encenar seu ataque depois de ver o problema matemático subjacente de um ângulo diferente. E como o ataque ao SIDH, este quebrou um sistema que dependia de matemática diferente da maioria dos protocolos pós-quânticos propostos.
“Os recentes ataques foram um divisor de águas”, disse Thomas Prest, um criptógrafo da startup PQShield. Eles destacam o quão difícil é a criptografia pós-quântica e quanta análise pode ser necessária para estudar a segurança de vários sistemas. “Um objeto matemático pode não ter uma estrutura óbvia em uma perspectiva e ter uma estrutura explorável em outra”, disse ele. “A parte difícil é identificar a nova perspectiva certa.”
