Recompensa pela seed das curvas elípticas do NIST
(words.filippo.io)- As 5 curvas elípticas do NIST amplamente usadas na criptografia moderna tiveram suas seeds derivadas de valores fornecidos pela NSA nos anos 1990, e há uma recompensa de US$ 12.288 para encontrar o texto original
- O alvo são as curvas P-192, P-224, P-256, P-384 e P-521 da FIPS 186-2, e o valor sobe para US$ 36.864 se o vencedor optar por doação para uma entidade beneficente americana 501(c)(3)
- A seed teria sido criada por Jerry Solinas em 1997, possivelmente a partir do hash SHA-1 de uma frase em inglês, mas a formulação exata se perdeu após troca ou atualização de equipamentos
- O formato da frase é incerto — incluindo ponto final, quebra de linha, posição e formato do contador e até a inclusão do nome da curva — então uma lista inicial de cerca de 12 mil hashes foi definida como alvo prioritário
- Quem enviar pela primeira vez ao menos 1 pre-seed recebe US$ 6.144, e quem enviar pela primeira vez o conjunto completo das 5 recebe os US$ 6.144 restantes; a ordem é determinada pelo cabeçalho
Receiveddo servidor de e-mail
Alvo da recompensa e valor pago
- O objetivo da recompensa pública é encontrar o valor de entrada do hash (pre-seed) que gerou as seeds das 5 curvas elípticas do NIST
- A recompensa total é de US$ 12.288, ou 12 Ki$
- Se o vencedor escolher doação, em vez de dinheiro, para uma entidade beneficente americana 501(c)(3), o total sobe para US$ 36.864
- Os hashes a serem quebrados são estes 5:
3045AE6FC8422F64ED579528D38120EAE12196D5BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5C49D360886E704936A6678E1139D26B7819F7E90A335926AA319A27A1D00896A6773A4827ACDAC73D09E8800291CB85396CC6717393284AAA0DA64BA
Por que as seeds das curvas do NIST geraram suspeitas
- As curvas do NIST P-192, P-224, P-256, P-384 e P-521 foram publicadas na FIPS 186-2 em 2000 e, seguindo o método da ANSI X9.62, derivam parte dos parâmetros a partir da saída de um SHA-1 aplicado a uma seed arbitrária
- Muitos sistemas criptográficos usam curvas do NIST, especialmente P-256 e P-384
- Essas duas curvas fazem parte da Commercial National Security Algorithm Suite
- Também são usadas em certificados ECDSA X.509 que protegem grande parte da web
- O texto NIST curve seed origins, de Steve Weis, resume o que se sabe sobre as seeds arbitrárias incluídas na especificação FIPS 186
- As seeds parecem ter sido fornecidas pela NSA
- Elas teriam sido geradas por Jerry Solinas em 1997
- É possível que tenham sido produzidas aplicando SHA-1 a uma frase em inglês
- Jerry Solinas já mencionou, como exemplo, uma seed no estilo
SHA1("Jerry deserves a raise."), mas a frase real se perdeu, e formulações parecidas não bateram com os hashes
Como encontrar o pre-seed pode reduzir a desconfiança
- Em avaliações recentes, as curvas do NIST passaram a ser vistas de forma mais positiva em alguns aspectos
- complete addition formulas mitigam um dos principais footguns
- Formas mais seguras de projetar interfaces já são conhecidas
- O valor de curvas de ordem prima imunes a ataques por cofactor também ficou mais claro
- Ainda existe, entre alguns não praticantes, a preocupação de que a NSA possa ter escolhido intencionalmente as seeds para selecionar curvas fracas
- A riddle wrapped in an enigma, de Koblitz e Menezes, argumenta que, mesmo que a NSA tivesse controle total sobre as seeds, esse tipo de ataque é pouco convincente
- Isso exigiria uma classe grande de curvas fracas que academia e indústria não tivessem detectado em 25 anos
- Embora essa preocupação não pareça muito bem fundamentada, encontrar o pre-seed pode ajudar a reduzir o FUD em torno das curvas do NIST
- Encontrar a preimage em inglês não garante completamente a rigidity, mas preencheria uma peça que falta na história da criptografia
Pistas conhecidas sobre o valor de entrada do hash
- O valor de entrada provavelmente é uma frase em inglês mencionando Jerry Solinas, possivelmente com nomes de outras pessoas e um contador
- Um contador provavelmente foi necessário porque, dependendo do tamanho em bits da curva, apenas cerca de 1 entre 192 e 521 hashes serviria para gerar uma curva válida
- Para a maior curva, a probabilidade de o contador ficar abaixo de 2400 é de 99%
- Para a P-256, há probabilidade de o contador ficar abaixo de 1175
- As seeds de P-192 e P-256 já apareciam como exemplo no padrão ANSI X9.62 anterior, enquanto as demais surgiram pela primeira vez na FIPS 186-2, então a estrutura das frases pode ser diferente
- A recompensa cobre apenas as 5 curvas do NIST de ordem prima, mas, se o custo de teste for baixo, também vale tentar outros exemplos da ANSI X9.62 e as seeds de binary curves da FIPS 186-2
- ANSI prime192v2, prime192v3, prime239v1, prime239v2 e prime239v3 não entram na recompensa
- NIST B-163, B-233, B-283, B-409 e B-571 não entram na recompensa
Formatos possíveis das strings e lista de ataque
- O formato exato da string continua sendo um mistério
- A frase pode terminar com ponto final ou não
- Pode haver quebra de linha ou não
- O contador pode estar em decimal, com leading zeros, ou em binário de 16 ou 32 bits
- O contador pode vir depois do ponto final ou ser anexado com outro tipo de separação
- Todas as seeds podem ter sido geradas com a mesma frase mais contadores diferentes, ou cada seed pode ter usado uma frase diferente
- O nome ou o tamanho da curva pode ter sido incluído na frase
- Como a memória humana falha bastante, continua aberta a possibilidade de que alguns detalhes dos relatos indiretos estejam errados
- Em vez de contador, também pode ter sido usado hashing repetido, como
SHA-1(s)ouSHA-1(SHA-1(s)) - Outra possibilidade é começar de
SHA-1(s)e então incrementar o valor do hash, como na Section A.3.3.1 da ANSI X9.62 - Foi fornecida uma lista de ataque com cerca de 12 mil hashes em nist-and-ansi-prime-order-seeds-increments-99-percent.txt
- A lista cobre o espaço de probabilidade de 99% para cada seed de curva de ordem prima da FIPS 186-2 e da ANSI X9.62
- Se o custo de verificar muitos hashes for baixo, recomenda-se usar essa lista como alvo principal
- Se possível, comparar apenas os primeiros 16 bytes do hash também produz o mesmo resultado
- SHA-1 é extremamente rápido para brute force, então este é um problema adequado para quem tem experiência com quebra de passphrases e brute force de brainwallets
Forma de envio e condições de pagamento
- A recompensa vai para quem enviar primeiro por e-mail, para
seeds@filippo.io, os pre-seeds das 5 curvas do NIST de ordem prima - A estrutura de pagamento tem duas etapas
- Quem enviar primeiro pelo menos 1 pre-seed recebe metade: US$ 6.144
- Quem enviar primeiro os 5 pre-seeds completos recebe os US$ 6.144 restantes
- A mesma pessoa pode receber os dois pagamentos, então não é preciso esperar encontrar as 5 de uma vez
- É possível escolher entre receber em dinheiro ou fazer doação para uma entidade beneficente americana 501(c)(3)
- Se optar por doação, o valor é triplicado
- Pode haver recusa se a entidade escolhida conflitar de forma extrema com os valores do ofertante
- Se a legislação impedir o envio de dinheiro para americanos ou cidadãos italianos, será preciso escolher a opção de doação
- Os impostos sobre a recompensa em dinheiro são responsabilidade de quem a recebe
- O assunto do e-mail deve incluir
ANTISPAMpara passar pelas regras de allowlisting - A ordem de envio será determinada em definitivo pelo cabeçalho
Receiveddo host de e-mail - A recompensa expira se as seeds se tornarem publicamente conhecidas; caso contrário, permanece válida até novo aviso nesta página
- Se a recompensa for cancelada ou reduzida, haverá aviso com 6 meses de antecedência
- Não há restrições sobre o método usado para encontrar as seeds
- Vale brute force, palpites engenhosos, investigação, recuperação de backups antigos do NIST ou qualquer outro método
- Também há a condição de que, se a pessoa não quiser, não será perguntado como chegou ao resultado
1 comentários
Opiniões no Hacker News
O contexto aqui é bem engraçado: anda circulando recentemente a história de que as sementes “aleatórias” das NIST P-curves, criadas por Jerry Solinas, da NSA, nos anos 1990, eram na verdade valores obtidos ao aplicar hash SHA1 a variações da string
"Give Jerry a raise"Na época, considerava-se que passar uma string pelo SHA1 fazia a estrutura da semente desaparecer, servindo como um mecanismo de confiança de que a NSA não poderia escolher intencionalmente uma semente fraca
Mas, nos anos 2000, quando o NIST/NSA arruinou a própria reputação, essa explicação deixou de ser suficiente para acalmar teorias da conspiração; mais tarde, quando o NIST tentou mostrar que a semente era benign, Jerry Solinas tentou reconstruí-la, mas teria esquecido a string que usou
Um conspiracionista de verdade diria que ninguém jamais encontrará a string que gera essa semente, mas, se alguém a encontrar, isso pode ser um golpe considerável na teoria de que as NIST P-curves foram geradas de forma maliciosa, então é um bounty interessante
"Give Jerry a raise of $100000 dollars now!!!"cujo hash bata com a semente, não vejo isso como prova de ausência de malíciaAfinal, se soubessem quais propriedades especiais uma curva fraca deveria ter, poderiam ter testado por hash um número enorme de variações semelhantes da string até escolher uma constante com a propriedade desejada
SSLv2 e SSLv3 são bons exemplos, e, embora o tamanho da saída corresponda ao SHA1, não seria tão surpreendente se tivesse sido um pipeline como
echo "$string" | md5sum | sha1sumhttps://eprint.iacr.org/2015/1018
https://eprint.iacr.org/2015/1018.pdf
Suspeitas semelhantes de backdoor também existiram em relação ao (EC)DSA, e defensores do RSA afirmavam que a NSA o promovia porque havia colocado um backdoor no DSA, mas não havia evidências, e diz-se que em 20 anos não foi descoberta nenhuma forma de inserir um backdoor no DSA ou no ECDSA
Há também a anedota de que, em uma reunião de padronização, um representante da NSA voltou após uma ligação telefônica e disse que a NSA acreditava que ECC era suficiente para comunicações seguras de todas as agências do governo dos EUA, incluindo o Federal Reserve, deixando todos surpresos
Assim como os ajustes no DES depois se revelaram uma defesa contra criptoanálise diferencial, e a fraqueza do SHA original, o SHA-0, não estava presente no SHA-1 final, outras ações da NSA também foram recebidas com suspeita
Em ambas as curvas, a escolha de G é o dobro de um ponto com uma coordenada x de tamanho suspeitosamente adequado, e essa característica é igual nas duas curvas
Nessas curvas, a escolha de G é a única entrada com muita entropia, mas é possível provar que, na prática, ela é quase irrelevante; no máximo, quem a escolheu passa a conhecer um logaritmo discreto arbitrário específico
Em um protocolo forçado, isso poderia virar um backdoor, mas seria algo muito artificial; ainda assim, por ser o único parâmetro desconhecido, achei que valia a pena procurar
Se a semente das P-curves for encontrada, ela talvez seja parecida com a semente usada nos pontos geradores de outras curvas, o que também poderia resolver esse pequeno mistério
Uma frase poderia, em teoria, ser escolhida para produzir o hash desejado
O GCHQ do Reino Unido emprega mais matemáticos do que qualquer laboratório ou universidade do país. Imagino que a instituição equivalente dos EUA seja parecida
A troca de chaves Diffie-Hellman também já era conhecida pelo GCHQ e pela NSA antes de Diffie e Hellman a redescobrirem
É difícil afirmar algo categórico sobre as capacidades fundamentais das agências de inteligência, e não estou dizendo que elas de fato conheçam essa família de curvas fracas, mas também é difícil considerar impossível. Essa área é o trabalho principal delas
Em geral, diz-se que a academia é tão competente que, se a NSA tivesse feito algo, isso já teria sido descoberto; e quem discorda é tratado como alguém espalhando FUD sem entender do assunto. Este texto também repete essa linha, mas é bom que a questão seja tratada com mais seriedade por meio de um bounty organizado
Trabalhei com criptografia no passado e, por alguns anos, revisei regularmente artigos de cripto como parte do meu trabalho, participei de conferências e conversei com pesquisadores, além de ter implementado várias criptografias de curva elíptica “incomuns”. Não sou totalmente de dentro, mas também não sou totalmente de fora; dessa posição, esse senso comum me parece perigoso
Os argumentos centrais são dois: a alegação de que, se tivesse sido possível um ataque de cleptografia na padronização das curvas do NIST, a academia ou a indústria já o teriam encontrado; e a alegação de que, como o Dual_EC_DRBG foi imediatamente considerado suspeito, a comunidade pública de criptografia é boa em detectar backdoors
O primeiro é pouco convincente. Na academia há o problema da gaveta de arquivos e os incentivos de “publique ou desapareça”; é óbvio o que é mais vantajoso para um pesquisador jovem: criar um novo algoritmo de prova de conhecimento zero e publicar um artigo que será citado, ou atacar um algoritmo que todos acreditam ser forte e talvez não obter nada
A base é um consenso de especialistas de que “muitas pessoas inteligentes estudaram isso a fundo e não encontraram nada”, mas, como na academia é difícil publicar resultados negativos, não há como saber quanto esforço de fato foi investido
A cleptografia, isto é, a própria técnica de inserir backdoors em padrões, também quase não tem utilidade se você não for a NSA, então não é um bom caminho de carreira, e é desfavorável tanto para transição à indústria quanto para citações
Por outro lado, a NSA pode pagar salários maiores que a academia, empregar mais pesquisadores do que toda a academia para se dedicarem a pesquisas com alta probabilidade de fracasso ou úteis apenas para backdoors em padrões, e, graças ao orçamento de hardware, pode realizar por décadas pesquisas multidisciplinares que a pesquisa acadêmica em criptografia não consegue fazer
Se eu tivesse de apostar sobre quem entende mais de ECC, a NSA ou a academia, o poder de fogo está do lado do governo, e a comparação nem é equilibrada. Dá para estimar aproximadamente quantos doutores em matemática o governo emprega, mas não sabemos quanto poder de fogo a academia de fato aplicou a esse espaço de problemas
O segundo argumento também não é ideal. As pessoas levantaram preocupações imediatamente não só sobre o Dual_EC_DRBG, mas também sobre as curvas do NIST. A diferença é apenas que, no primeiro caso, havia um algoritmo conhecido capaz de executar o ataque necessário; no segundo, não havia
O método para tornar essa discussão desnecessária era conhecido havia décadas, e foi por isso que as curvas do NIST foram geradas a partir da saída do SHA1. O melhor momento para eliminar gradualmente as curvas do NIST foi décadas atrás; o segundo melhor momento é agora
O motivo para contribuir com este bounty é que, se for mesmo uma frase possível de quebrar por cracking de senha, descobrir isso teria grande importância histórica
É bastante inquietante que as curvas elípticas do NIST tenham sido criadas fazendo hash de seeds fornecidas pela NSA
Soa como: “não se preocupe, foi feito aplicando hash a uma frase qualquer sem importância. Hoje esquecemos qual era, mas era só o Jerry fazendo uma piada sobre aumento de salário”
É difícil acreditar que isso não tenha passado antes por uma validação forte, e que não tenham feito uma seleção de seed mais razoável, como misturar seeds aleatórias de várias partes com interesses diferentes, geradores de números aleatórios por hardware etc.
Esse método teria sido bom, mas na época provavelmente não havia muita gente que visse essa necessidade
https://en.wikipedia.org/wiki/Utah_Data_Center
Há um vídeo em que o professor Dan Boneh explica o contexto: https://youtu.be/8WDOpzxpnTE?t=892
Se entendi corretamente, a comunidade aceitou strings suspeitas de origem desconhecida, e teria sido muito fácil substituí-las por strings de origem clara colocando outra entrada conhecida no hash?
Infelizmente, até onde sei, esse é o único caso em que se fala em incompetência envolvendo a NSA e padrões criptográficos; normalmente as histórias apontam na direção oposta
O problema ainda maior é que o NIST já tinha um histórico de inserir backdoors em padrões relacionados a curvas elípticas, e também foi apontado imediatamente que esse mecanismo não criava confiança, mas nem o NIST nem a NSA tomaram qualquer providência. Igual ao caso do Dual_EC_DRBG
O problema ainda maior é que, em 2015, a NSA disse explicitamente para não fazer upgrade das curvas do NIST para outras curvas posteriores. A justificativa foi que os computadores quânticos logo ficariam bons o bastante para quebrar toda a ECC, então todos deveriam migrar para criptografia pós-quântica
Se a ECC funcionasse bem, os computadores quânticos estivessem distantes e você quisesse manter as pessoas presas às curvas do NIST pelo maior tempo possível, era exatamente isso que você diria
A comunidade de criptografia dificilmente sai honrada dessa situação. Já se passaram quase 25 anos e existem curvas mais novas que não têm esse problema; então por que as curvas do NIST ainda são usadas? Onde está o esforço para aposentá-las gradualmente, como aconteceu com o SHA1? Este texto, na verdade, parece estar promovendo essas curvas
Se você estiver se sentindo com sorte, pode tentar adivinhar o hash SHA1 aqui: https://wending.dev/hash_guessing/
Se o gerador de seeds da NSA entendesse ao menos um pouco de criptografia e computadores, não teria ficado inserindo manualmente 500 frases diferentes até sair uma boa curva
Mesmo que tenha feito isso, as variações possíveis são infinitas: colocar um ponto no fim, mudar maiúsculas e minúsculas, usar capitalização de título etc.
Uma lista de variações plausíveis a tentar dificilmente será completa; mas, se a página apenas gera hashes SHA1, como esta, mesmo que você adivinhe a string acertando até a pontuação e as maiúsculas/minúsculas, encontrar o hash real é praticamente impossível
No mínimo, para verificar se o hash resultante é um valor incrementado, seria preciso conseguir checar se os 10 bytes iniciais ou finais batem. Ainda assim, na maior parte das vezes isso só faria as pessoas perderem tempo, e o autor também deve saber que não levará a lugar nenhum
A página deveria dizer que é apenas um brinquedo de demonstração e que, mesmo que você adivinhe corretamente, ela não permitirá encontrar a seed real
Depois de acompanhar por muito tempo debates inflamados entre criptógrafos, o que aprendi foi: “não aposte contra Bernstein e não confie no NIST”
Agora acho que preciso corrigir para: “não aposte contra Bernstein nem contra Filippo e não confie no NIST. Se essas duas regras entrarem em conflito, ainda assim não confie no NIST”
É verdade que o SHA-1 foi quebrado, mas eu achava que os problemas eram principalmente colisões por ataques de extensão de comprimento ou ataques de texto claro conhecido
Dado apenas o hash, eu via encontrar a frase secreta como algo ainda difícil de tratar na prática
Mas, se a hipótese sobre a estrutura da seed estiver certa, a resistência à pré-imagem não importa tanto aqui. O SHA-1 é muito rápido e fácil de paralelizar, então há uma chance considerável de que alguém que vasculhe obstinadamente o espaço de variações de
"Jerry needs a raise"descubra a entrada originalNão tem muita relação com o SHA1 em si