Uma pergunta aberta desde 2000
A Anthropic anunciou em 16 de outubro que um modelo interno de pesquisa do Claude reconstituiu, em menos de meia hora, o método usado para gerar as sementes de cinco curvas elípticas do NIST: P-192, P-224, P-256, P-384 e P-521. As sementes não são saídas de uma função de hash, como dizia a explicação mais conhecida. Segundo a publicação da Anthropic, elas vêm do lrand48, o gerador de números aleatórios da biblioteca padrão do C, iniciado com uma marca de tempo Unix.
As sementes importam porque as curvas construídas a partir delas sustentam o ECDSA, o esquema de assinatura usado em TLS, na assinatura de código e nas carteiras de criptomoedas. O NIST adotou o ECDSA em 2000 com o FIPS 186-2 e publicou para cada curva uma semente cujo hash fixa um dos coeficientes. A NSA entregou essas sementes sem explicar de onde vinham, o que deixou espaço para a suspeita de que alguém tivesse procurado até achar uma curva com uma fraqueza que só ele conhecia.
O que o modelo fez
A Anthropic conta que o modelo começou verificando se as sementes pareciam a saída de geradores disponíveis nos anos 1990. Algumas tinham todos os bits mais altos em zero, uma assinatura do lrand48. Depois recuperou o estado interno do gerador para as sementes das curvas primas por meio de redução de reticulados.
Os estados iniciais recuperados são leituras de relógio. P-192 e duas curvas próximas remetem a 18-05-1997 às 14:45:34; P-521 a 08-08-1997 à 01:12:04; P-256 a 16-08-1997 à 01:52:34, o candidato 1.842 daquela execução; P-384 a 30-08-1997 às 14:50:08; e P-224 a 03-04-1998 às 12:52:07. As quatro curvas binárias do NIST caem em 17 de abril de 1998, mas só quando a marca de tempo é dividida por dois, o que sugere que o programa que as produziu cortava o valor do relógio.
O modelo também localizou a origem de seis pontos base, o de P-192 e de cinco curvas próximas, no gerador de números aleatórios do FreeLIP, o pacote de aritmética de inteiros longos de Arjen Lenstra, com as sementes 20000, 20420, 20507, 20509, 20512 e 20517.
O que dizia a explicação antiga
A teoria dominante vinha de Jerry Solinas, o matemático da NSA que trabalhou nas curvas. Em 2015 ele disse que as sementes eram hashes de uma frase jocosa, algo como “dêem um aumento a Bob e a Jerry”, e que um colega havia escrito o código. Nenhum arquivo da época foi encontrado, e Solinas morreu em 2023. A Anthropic afirma que seus próprios funcionários seguiram essa pista sem sucesso antes de passar o problema a um modelo.
O que continua em aberto
A publicação da Anthropic lista o que o modelo não resolveu: os pontos base de P-224, P-256, P-384, P-521 e das curvas binárias do NIST; a quinta semente binária, B-163; e por que alguns candidatos válidos foram descartados, entre eles o candidato 876 de P-256.
A empresa é explícita: isto “não é uma quebra criptográfica, um ataque novo nem uma fraqueza das curvas ECDSA”, e diz que ninguém precisa fazer nada. Sustenta que o resultado torna uma porta dos fundos deliberada bem menos plausível, porque as sementes foram produzidas de forma muito simples e poucos candidatos foram descartados, embora acrescente que não pode descartar que marcas de tempo específicas tenham sido escolhidas por alguma propriedade da curva resultante.
O que observar
A Anthropic publicou código em Python que reproduz as sementes e os seis pontos base, sob licença CC0, de modo que a afirmação pode ser checada por quem quiser executá-la. A publicação não descreve nenhuma verificação independente. A recompensa de 36.864 dólares pela resposta, organizada por Filippo Valsorda, vai para o Internet Security Research Group. Os pontos base restantes e a semente B-163 são a próxima coisa a cair, ou não.
