Sementes das Curvas NIST Resolvidas: 5 Mitos sobre ECDSA

Por vinte e cinco anos, as sementes das curvas ECDSA da NIST foram o mais perto que a criptografia aplicada chegou de um caso arquivado sem solução. Cinco valores de 160 bits aparentemente aleatórios, entregues à NIST pela NSA sem nenhuma explicação, sustentavam assinaturas de tudo, desde suas conexões TLS até transações Bitcoin. Esta semana o caso foi fechado, e a resposta é quase constrangedora: as sementes eram saída do gerador lrand48() da biblioteca C, inicializado com timestamps Unix de 1997 e 1998. Só isso. Nada de hash de uma frase secreta, nenhuma maquinaria exótica — srand48(time(NULL)), exatamente o padrão que todo curso de segurança manda nunca usar.

A descoberta veio de um modelo de pesquisa da Anthropic, apontado para o problema por um funcionário curioso, que reconheceu a assinatura estatística de um gerador congruencial linear dos anos 1990 nas constantes publicadas e rodou o estado para trás até cair em datas de calendário. Passei anos auditando sistemas criptográficos o suficiente para saber que isso importa — não porque as curvas estejam quebradas (não estão), mas porque derruba várias coisas que nossa indústria acreditava com confiança. Vamos aos mitos, um de cada vez.

Mito 1: Constantes Não Explicadas Significam um Backdoor Escondido

A desconfiança nunca foi absurda. Quando a NIST publicou as curvas FIPS 186-2 em 2000, cada uma veio com uma semente cujo hash determina o coeficiente b da curva. A NIST disse que as sementes garantiam que as curvas eram “verificavelmente aleatórias” — mas não conseguiu, ou não quis, explicar como as próprias sementes foram geradas. Koblitz e Menezes escreveram um artigo inteiro sobre a polêmica, com o título certeiro “A Riddle Wrapped in an Enigma”. A melhor pista da comunidade veio de Jerry Solinas, na NSA, que lembrou em 2015 que a entrada era o hash de uma frase bem-humorada, algo como “Give Bob and Jerry a raise”. Ele morreu em 2023 sem que ninguém recuperasse os detalhes.

Aqui está a verdade incômoda para quem gosta de teorias da conspiração, e eu mesmo já fui assim em alguns momentos: não explicado geralmente significa não documentado, não malicioso. O processo real de geração foi um desenvolvedor rodando um pequeno programa em C, deixando o PRNG padrão se semear pelo relógio de parede e pegando o primeiro candidato que produzisse uma curva utilizável. A semente publicada da P-256 foi o candidato número 1.842 de uma execução iniciada às 1:52 da manhã de 16 de agosto de 1997. Isso não é o fluxo de trabalho de uma agência plantando uma armadilha teórica de números. É um engenheiro à uma da manhã rodando um loop até imprimir algo válido.

Já vi esse padrão em revisões de incidentes mais vezes do que consigo contar. Um valor de configuração misterioso, uma constante mágica sem documentação, um passo de deploy que ninguém consegue explicar — e o postmortem revela que era um atalho razoável na hora, tomado por um engenheiro cansado e nunca registrado. O pecado real da NSA aqui não foi colocar backdoor nas curvas. Foi distribuir constantes criptográficas para o mundo inteiro sem um README.

Mito 2: O Método de Geração Prova que a Seleção Foi Honesta

Agora, a correção exagerada. Muitos comentários desta semana tratam o “são só timestamps” como absolvição total. Não é, e os pesquisadores por trás do trabalho têm o cuidado de dizer isso. Saber como os candidatos foram gerados não diz nada sobre como as curvas finais foram selecionadas — e a seleção aconteceu ao longo de meses, de maio de 1997 a abril de 1998.

As evidências vão nos dois sentidos. Na execução da P-256, o candidato 876 também produziu uma curva de ordem prima com o tamanho certo, construída com as mesmas convenções de parâmetros — e foi descartado. A curva publicada foi o candidato 1.842. A execução da P-224 deixou de lado três curvas viáveis; as execuções da ANSI X9.62 descartaram mais sete. Não conseguimos ver o histórico completo dos candidatos descartados, só os alcançáveis nas execuções registradas. Se alguém quisesse uma curva com uma propriedade rara específica, poderia, em princípio, ter buscado sobre timestamps até encontrar uma, e depois ficar em silêncio sobre o timestamp. “Fazer e não dizer nada” sempre foi uma opção.

Minha leitura, depois de acompanhar pesquisas sobre curvas fracas por anos: a hipótese do backdoor está gravemente ferida, mas não formalmente morta. Os candidatos descartados são poucos demais para que a escolha a dedo implique que curvas fracas são comuns e fáceis de encontrar — o que duas décadas de criptoanálise pública dizem que não são. Ninguém jamais publicou um distinguidor capaz de separar essas curvas de curvas aleatórias. Mas “nenhuma fraqueza conhecida” e “provadamente sem fraqueza” são afirmações diferentes, e a posição honesta é a primeira. Isso é exatamente a lacuna entre especificação e implementação se manifestando no nível dos padrões: a especificação dizia “verificavelmente aleatório”, e a implementação foi “o que o relógio marcasse”.

As sementes foram geradas do jeito que um estudante de pós faria: um PRNG padrão e o relógio do sistema. O escândalo nunca foi a matemática. Foi a falta de documentação.

Mito 3: PRNGs Antigos e Fracos São Inofensivos Se Você Usar Só Uma Vez

Este é o mito que deveria fazer sentar na cadeira todo engenheiro que já digitou srand(time(NULL)). O véu de mistério de vinte e cinco anos existiu por causa de uma propriedade de design do lrand48(): ele vaza a própria estrutura. O gerador devolve apenas os 31 bits superiores de um estado de 48 bits, então suas palavras de saída sempre têm o bit mais alto zerado. Escritas como palavras de 32 bits, quatro das dez sementes das curvas binárias mostram bits mais altos todos zerados em vinte palavras consecutivas — um evento com probabilidade em torno de uma em 58 mil sob distribuição uniforme. A assinatura estava visível a olho nu para quem pensasse em olhar.

A partir daí, o ataque é embaraçosamente barato. Para recuperar os estados das curvas binárias, você pega a primeira palavra de saída, força bruta sobre os 2^17 bits baixos ocultos e verifica se as próximas quatro palavras seguem. São alguns milissegundos de computação. Para as curvas primas, as sementes mantinham menos bits por saída, então recuperar o estado exigiu o clássico ataque de LCG truncado: modelar como problema de reticulado e atacar com a redução de base LLL. Coisa de livro-texto, literalmente. Uma vez com o estado em mãos, um LCG roda para trás tão facilmente quanto para frente, então você o retrocede até aparecer a forma de inicialização do srand48 — bits baixos iguais a 0x330E — e lê o timestamp com que foi semeado.

# The whole mystery, reproduced
from datetime import datetime, timezone
def unix(when):
return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())
def candidate(t, n, per, shift, width):
x, out = (t << 16) | 0x330E, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

A lição vai além dos órgãos de padronização. Qualquer valor “com cara de aleatório” que você emite — tokens de sessão, IDs de requisição, salts, nomes de arquivo — carrega a impressão digital do gerador que o produziu. Se esse gerador é um motor congruencial linear ou um Mersenne Twister, algumas poucas saídas reconstroem o estado interno, e tudo o que foi gerado antes e depois se torna previsível. Um único uso, vinte e cinco anos atrás, em um arquivo feito para parecer ruído, foi completamente invertido. Quando reviso código que usa RNGs não criptográficos para qualquer coisa que um atacante possa observar, essa é a história de guerra que passo a citar daqui em diante.

Mito 4: Os Números “Nothing-Up-My-Sleeve” Nunca Foram a Proteção Real

A ideia de “nothing-up-my-sleeve” — derivar constantes de algo obviamente inocente, como os dígitos de pi — existe para limitar os graus de liberdade do projetista. Se eu consigo mostrar que minha constante sai de um procedimento público e rígido, não tive espaço para contrabandear um backdoor. As sementes da NIST falharam nesse teste procedimentalmente: o procedimento era secreto, então o limite sobre os graus de liberdade era desconhecido. Mas o que este episódio realmente expõe é que o teste da manga é mais fraco do que fingíamos, mesmo quando funciona.

Considere o que “verificavelmente aleatório a partir de um timestamp” realmente oferece. Um timestamp tem cerca de 31 bits de entropia para uma janela plausível. Qualquer pessoa — inclusive o autor original — pode vasculhar milhões de timestamps, gerando milhões de curvas candidatas, e publicar apenas a que quer, junto com sua semente de aparência inocente. Se curvas com uma fraqueza secreta existissem na proporção de uma em um milhão, a busca por timestamps encontra uma em uma tarde. A semente prova de onde o número veio e diz quase nada sobre por que aquele foi escolhido. O mesmo vale para esquemas de hash de senha, e é por isso que o boato sobre a frase engraçada de Solinas nunca foi totalmente tranquilizador.

A prática moderna mais forte é a construção rígida de curvas: escolher o menor coeficiente que satisfaça uma lista pública de critérios de segurança, com as regras de seleção fixadas antes de a busca começar. Essa é a filosofia por trás da Curve25519 e por que os argumentos de rigidez de Dan Bernstein remodelaram a forma como a comunidade avalia curvas. A proteção real contra constantes maliciosas nunca foi uma história bonita de derivação. É minimizar o espaço de busca, publicar os critérios com antecedência e ter olhos independentes suficientes sobre a matemática para que uma propriedade oculta não possa continuar oculta. Auditar constantes significa auditar o processo que as filtrou — e é por isso que as perguntas sem resposta aqui (os candidatos descartados, os pontos base não explicados da P-256 e similares, a semente ainda não identificada da B-163) merecem continuar abertas no registro, em vez de serem varridas para debaixo do tapete pela comemoração.

Mito 5: LLMs Apenas Regurgitam — Não Conseguem Fazer Criptoanálise Original

Este é o mito que mais incomoda, porque eu acreditava em uma versão dele. O problema em aberto ficou sem solução por um quarto de século, apesar de uma recompensa pública de US$ 36.864 e de atenção séria de amadores habilidosos. Vários pesquisadores da Anthropic já tinham tentado por conta própria, seguindo a pista do “hash de uma frase engraçada”, e voltaram de mãos vazias. Então um modelo de pesquisa interno, questionado sem receber o boato, tentou um ângulo diferente em menos de meia hora: em vez de adivinhar a entrada de um hash, perguntou que software teria gerado as sementes, levantou a hipótese de um PRNG da biblioteca C dos anos 1990, escreveu um scanner que deslizava sobre cada semente testando 34 combinações de gerador e fatia de saída, identificou o padrão de bit mais alto zerado, rodou o ataque de reticulado sobre as saídas truncadas e voltou os estados até datas de calendário.

Repare no que esse fluxo de trabalho é. Não é recordação — nenhum documento de treinamento continha a resposta, porque a resposta não existia em lugar nenhum. É geração de hipóteses somada a uso de ferramentas e verificação, que é a forma real do trabalho de criptoanálise. O modelo até checou a própria sanidade no meio da execução: isto é um ambiente de teste simulado? Uma coisa tão óbvia realmente ficaria sem ser encontrada por 25 anos? Um casamento de 160 bits a partir de uma semente de 32 bits descarta a coincidência? Essa autocrítica é o que eu esperaria de um analista humano, e, sinceramente, alguns analistas humanos pulam essa etapa. Já vínhamos testando os mitos sobre o que esses modelos realmente fazem neste site há um tempo, e este é um dado limpo: LLMs agora conseguem executar raciocínio forense de múltiplas etapas sobre artefatos do mundo real, não apenas sobre benchmarks.

O contraponto justo de profissionais é sobre proveniência. O modelo não inventou a recuperação de estado de LCG nem o LLL — ele se apoia em décadas de criptoanálise publicada por pesquisadores nomeados e anônimos, e não consegue dizer de quais artigos vieram as influências de sua abordagem. Isso me incomoda menos do que incomoda alguns. O scanner, o código de verificação e o script de reprodução são públicos; as pessoas da equipe direcionaram a pergunta e validaram o resultado. Vamos dar crédito honesto à divisão de trabalho: a máquina forneceu busca incansável de hipóteses, os humanos forneceram julgamento e responsabilidade. Destinar os US$ 36.864 ao Internet Security Research Group foi uma forma elegante de encerrar o assunto.

O Que Isso Muda para Auditorias de Segurança

Então, onde isso deixa um engenheiro em atividade? Algumas mudanças concretas na forma como eu abordaria auditorias daqui em diante. Primeiro, trate toda constante mágica em um protocolo ou base de código como um artefato forense, não como um fato da natureza. Pergunte que gerador poderia tê-la produzido, procure assinaturas estruturais — bits superiores enviesados, palavras sucessivas correlacionadas por LCG, recuperações de estado plausíveis com timestamps — antes de aceitar “é aleatório” como resposta. As ferramentas para isso agora estão trivialmente disponíveis.

Segundo, se você publica constantes, publique o gerador. Código-fonte, entradas exatas, ambiente exato. “Verificavelmente aleatório” sem uma receita reproduzível garante vinte e cinco anos de desconfiança e uma recompensa sobre o seu legado. Terceiro, continue usando P-256 — a descoberta aumenta a confiança nas curvas em vez de diminuí-la, e o modelo de ameaça real para curvas elípticas é hardware quântico, não o relógio de uma estação de trabalho de 1997. Mas leia as perguntas em aberto com honestidade: pontos base não explicados e candidatos descartados são pontas soltas, e um trabalho de segurança maduro significa mantê-las nos registros.

A conclusão mais profunda é sobre memória institucional. Jerry Solinas lembrou de uma piada sobre aumentos salariais que acabou sendo errada. Os arquivos, nas palavras dele, provavelmente estavam em algum HD perto da Arca da Aliança. A única razão de conhecermos a verdade hoje é que a própria saída reteve estrutura suficiente para se confessar. Seus sistemas estão escrevendo suas próprias confissões agora mesmo, em cada ID, token e constante que você envia. Certifique-se de que elas confessem algo de que você se orgulhe.