Claude decifrou o mistério da curva da NSA

A criptografia de curva elíptica (ECC) sustenta as conexões seguras que os navegadores estabelecem com sites, permitindo a troca crucial de uma chave secreta compartilhada à vista de todos. Essa façanha matemática baseia-se em elliptic curves, onde operações específicas são computacionalmente triviais de realizar, mas praticamente impossíveis de reverter. A curva P-256, um padrão publicado pelo NIST em 2000, tornou-se a pedra angular do TLS 1.3 e do HTTPS, exigida para praticamente todas as aplicações.

Por mais de duas décadas, os criptógrafos nutriram um profundo desconforto em relação a essas curvas do NIST. Os parâmetros que definem sua forma incorporavam "sementes" arbitrárias fornecidas pela NSA, sem qualquer explicação pública para sua gênese. Essa falta de transparência alimentou especulações: a NSA poderia ter escolhido deliberadamente essas sementes para incorporar uma porta dos fundos secreta, permitindo-lhes acesso exclusivo a comunicações criptografadas?

As infames revelações de Snowden sobre o gerador de números aleatórios Dual_EC_DRBG amplificaram essas suspeitas, mostrando que um padrão separado influenciado pela NSA estava, de fato, comprometido. No entanto, é fundamental distinguir o Dual_EC_DRBG das curvas elípticas do NIST. Embora o incidente anterior tenha tornado compreensível uma teoria da conspiração sobre a P-256, ele nunca constituiu prova de uma porta dos fundos nas próprias curvas elípticas.

Por décadas, um boato tentador, atribuído ao matemático da NSA Jerry Solinas, sugeriu que a semente da P-256 originou-se do hash de uma frase memorável. Essa explicação, embora nunca totalmente corroborada, direcionou os pesquisadores para buscas infrutíferas pela "frase de piada" que Solinas mencionou, como "dê um aumento a Bob Reiter e Jerry Solinas", que ele não conseguiu recordar antes de seu falecimento em 2023. Isso levou a uma recompensa de longa data pela solução, alimentando especulações.

Claude, no entanto, ignorou essa pista famosa. Em vez de perseguir uma frase esquecida, o modelo da Anthropic explorou padrões comuns de geradores de números pseudoaleatórios (PRNG). Ele identificou artefatos estatísticos, como um bit superior consistentemente zerado, característicos de geradores legados específicos. Usando algoritmos de redução de rede, Claude trabalhou de trás para frente a partir dessas "impressões digitais" para reconstruir o estado interno do gerador.

O resultado principal: as sementes para várias curvas primas do NIST, incluindo a P-256, corresponderam às saídas do lrand48. Este gerador familiar da biblioteca C da era Unix, amplamente utilizado na década de 1990, foi inicializado a partir de carimbos de data/hora simples do Unix. Para a P-256 especificamente, a reconstrução aponta para o lrand48 sendo semeado em 16 de agosto de 1997, às 01:52:34 UTC, com a semente oficial da P-256 correspondendo ao seu 1.842º número gerado. Outras curvas do NIST, como a P-192, também se alinharam com as saídas do lrand48 a partir de carimbos de data/hora entre maio de 1997 e abril de 1998.

O avanço de Claude dependeu do reconhecimento de sutis "impressões digitais" estatísticas dentro dos valores das sementes. Ele identificou que as sementes fornecidas pelo NIST exibiam características consistentes com o lrand48, um gerador de números pseudoaleatórios (PRNG) comum das bibliotecas C da década de 1990. Especificamente, Claude observou um comportamento restrito do bit superior nas saídas geradas.

A partir dessas saídas truncadas, o Claude reconstruiu engenhosamente o estado interno do PRNG. Ele empregou lattice-reduction methods — uma técnica sofisticada para encontrar vetores curtos em redes de alta dimensão — para fazer a engenharia reversa do estado do gerador, mesmo com informações incompletas. Isso permitiu rastrear os números aleatórios até suas condições iniciais.

A velocidade dessa reconstrução foi notável: menos de meia hora para cinco curvas NIST. O bloco de notas interno do Claude até mostrou que ele expressou surpresa, questionando se estava em um ambiente de teste simulado dado o sucesso rápido. Para a P-256, o gerador começou em 16 de agosto de 1997, às 01:52:34 UTC, e a semente oficial foi o 1.842º número que ele produziu.

A Anthropic verificou rigorosamente essas descobertas, publicando código reprodutível que permitiu a pesquisadores independentes regenerar as sementes relatadas caractere por caractere em segundos. Esse processo também resolveu as origens de vários pontos base ANSI X9.62 e NIST, vinculando-os à biblioteca FreeLIP de Arjen Lenstra. A Anthropic reivindicou uma recompensa de longa data de US$ 36.864 por essa descoberta e a doou para o Internet Security Research Group (ISRG). Mais detalhes, incluindo o artigo de pesquisa, estão disponíveis em Anthropic Research: ECDSA Curve Origins.

Revelar as origens do timestamp oferece uma tranquilidade significativa, não uma crise criptográfica. Um timestamp Unix, fornecendo cerca de 30 bits de escolha, apresenta um espaço de busca drasticamente menor do que o que seria necessário para um backdoor deliberadamente projetado. Essa liberdade limitada significa que uma fraqueza oculta é altamente improvável.

Crucialmente, essa descoberta não quebra o TLS, não revela chaves privadas nem falsifica assinaturas. A P-256 permanece segura, não exigindo nenhum patch urgente ou revisão de protocolo. A análise da Anthropic, e a subsequente verificação independente, confirmaram que as curvas são mais limpas, não mais fracas.

No entanto, restam perguntas pendentes. A semente da curva binária B-163, por exemplo, ainda carece de uma explicação completa. As origens precisas de certos base points — as coordenadas iniciais na curva elíptica — também aguardam elucidação completa, embora alguns tenham sido vinculados à biblioteca FreeLIP de Arjen Lenstra.

Além disso, os criptógrafos ainda ponderam por que um candidato qualificado para a P-256 foi selecionado em detrimento de outros que também atendiam aos critérios. Embora o trabalho do Claude tenha reduzido drasticamente a suspeita em torno das curvas NIST, ele fornece um capítulo crucial em sua história, não um relato definitivo de cada escolha de design.

O que o Claude descobriu sobre as sementes das curvas NIST?

O Claude da Anthropic rastreou várias sementes de curvas NIST até saídas do gerador de números pseudoaleatórios lrand48, inicializado com timestamps Unix.

A descoberta significa que a P-256 tinha um backdoor?

Não. O processo baseado em timestamp deixa pouca liberdade para tornar um backdoor intencional plausível, e a descoberta não permite ataques à P-256.

Como o Claude reconstruiu as sementes?

Ele reconheceu padrões estatísticos nas saídas do lrand48 e usou técnicas matemáticas, incluindo lattice reduction, para recuperar os estados prováveis do gerador.

Todas as origens das curvas foram explicadas agora?

Não. Algumas origens de sementes e escolhas de pontos base permanecem sem solução, incluindo a semente da curva binária B-163 e a seleção de um candidato para a P-256.