- O ponto central da crítica é que, no processo de promover o Kyber-512 como padrão de criptografia pós-quântica, o NIST teria calculado errado o custo dos ataques e inflado seu nível de segurança
- A controvérsia é que o custo computacional e o custo de acesso à memória por iteração deveriam ser somados, mas o NIST os tratou como se tivessem sido multiplicados, adicionando “40 bits extras de segurança” à estimativa de 2^137 de Matzov
- O Kyber-512 foi apresentado com nível de cerca de 2^118 pelo critério Core-SVP, e o NIST tentou alinhá-lo ao patamar do AES-128, de aproximadamente 2^143 bit operations, mas é criticado por combinar números cujas unidades e significados não batem
- Enquanto o Kyber oferece apenas opções limitadas de parâmetros, como Kyber-512, Kyber-768 e Kyber-1024, NTRU e NTRU Prime são comparados como alternativas com escolhas mais granulares de tamanho e nível de segurança
- A padronização do Kyber-512 carrega incertezas na análise de ataques, falta de quantificação do modelo de custo de memória e pouca revisão pública; o autor pede a remoção do Kyber-512 e a divulgação do erro de cálculo do NIST
O núcleo do erro de cálculo
- O ponto de partida é o exemplo simples de que “2^40 + 2^40 não é 2^80, mas 2^41”
- Confundir números que devem ser multiplicados com números que devem ser somados pode inflar enormemente o nível de segurança
- Na discussão sobre o nível de segurança do Kyber-512, a estrutura do problema é a seguinte
- O ataque é composto de muitas iterações (iterations)
- Cada iteração tem custo computacional e custo de acesso à memória
- O custo total deve ser calculado como
número de iterações × custo por iteração - Dentro do custo por iteração, o custo computacional e o custo de acesso à memória devem ser somados
- A crítica central é que o NIST produziu o efeito de multiplicar o custo computacional pelo custo de acesso à memória, em vez de somá-los
- Por exemplo, 2^25 bit operations/iteration e 2^35 bit operations/iteration devem ser somados
- Se forem multiplicados, a unidade vira
bitops^2/iter^2, que não é uma unidade de custo de ataque - Essa multiplicação pode inflar o custo do ataque em milhões de vezes ou mais
Contexto do NISTPQC e do Kyber-512
- O NIST anunciou em 2022 o plano de padronizar o Kyber-512 e publicou em 2023 um rascunho do padrão para o Kyber-512
- O foco da crítica é que o NIST teria cometido um erro grave de cálculo ao justificar o nível de segurança do Kyber-512
- Em março de 2022 foi feito um pedido FOIA para NSA, NIST, and post-quantum cryptography, e depois parte de documentos internos do NIST foi revelada por meio de processo judicial
- Pela comparação entre documentos públicos e não públicos, o texto sustenta que a participação da NSA no processo NISTPQC foi maior do que o NIST explicou publicamente
- A lista da equipe
pqc@nist.govde 2016 teria mais pessoas da NSA do que do próprio NIST - Em material público de 2020, o NIST havia afirmado que o feedback da NSA não influenciava as decisões e que apenas o NIST decidia com base em informação pública
- Em janeiro de 2023 foi apresentado um novo pedido FOIA sobre as alegações de segurança do Kyber-512, e o texto afirma que o NIST voltou a atrasar a resposta, gerando novo processo
A escolha limitada de parâmetros do Kyber
- O texto aponta que o Kyber, ao contrário de RSA, ECC, McEliece e NTRU, não permite elevar gradualmente o nível de segurança para o tamanho desejado
- Não existe Kyber-576; a próxima opção acima do Kyber-512 é o Kyber-768, exigindo aumento de 50% na dimensão
- A próxima opção acima do Kyber-768 é o Kyber-1024
- Não há opção acima do Kyber-1024
- A documentação oficial do Kyber apresentava como vantagem o fato de todos os conjuntos de parâmetros poderem ser tratados com uma “dimension-256 NTT”, mas nessa estrutura dimensões que não sejam múltiplos de 256 exigem mudanças centrais de projeto
- Em aplicações com limite de 1 KB, é difícil usar o Kyber-768, e o Kyber-512 vira a opção mais segura dentro da linha Kyber
- O Kyber-768 usa public key de 1184 bytes e ciphertext de 1088 bytes
- O Kyber-512 usa key de 800 bytes e ciphertext de 768 bytes
- No mesmo limite de 1 KB, a família NTRU é comparada como oferecendo estimativas Core-SVP mais altas
sntrup653: key de 994 bytes, ciphertext de 897 bytes, Core-SVP 2^129- NTRU-677 (
ntruhps2048677): key de 931 bytes, ciphertext de 931 bytes, Core-SVP 2^145 - A versão round-3 do Kyber-512 foi apresentada com Core-SVP 2^118
- Core-SVP é o mecanismo que a equipe do Kyber usou para estimar o nível de segurança nas submissões round-1 e round-2, e o relatório round-2 do NIST de 2020 também o usou nas comparações
Critérios de avaliação do NIST e comparação com o NTRU
- O pedido oficial de submissões do NIST de 2016 incluía flexibilidade (flexibility) entre os critérios de avaliação
- Partindo da premissa de “boa segurança geral e desempenho”, o NIST considerava que esquemas com mais flexibilidade poderiam atender melhor a diferentes necessidades de usuários
- O texto oficial dizia também que, dentro da mesma categoria, vários conjuntos de parâmetros poderiam ser oferecidos para ajustar desempenho ou margem de segurança
- Em 2020, ao eliminar o NewHope, o NIST citou como um dos motivos o fato de o Kyber suportar naturalmente um conjunto de parâmetros de categoria 3
- Se o Kyber-512 não atingir o nível mínimo de segurança, restariam ao Kyber apenas o Kyber-768 e o Kyber-1024, ampliando a desvantagem de flexibilidade frente ao NTRU
- O selection report de 2022 do NIST afirmou ter confiança tanto na segurança do Kyber quanto na do NTRU, e avaliou o desempenho geral dos KEMs como aceitável para aplicações de uso geral
- Nessa condição, o argumento é que, sem o Kyber-512, o NTRU ficaria em melhor posição por oferecer opção menor, opção de segurança mais alta e trade-offs mais granulares entre tamanho e segurança
Quatro críticas de que o NIST inclinou a competição
-
1. Ignorar a flexibilidade adicional do NTRU
- O texto diz que a literatura do NTRU já mostrava há muito tempo a possibilidade de oferecer várias combinações de nível de segurança e tamanho
- Em 2020, o NIST afirmou que “parameter sets demais dificultam a avaliação e a análise”
- A crítica é que os critérios oficiais apresentavam flexibilidade como algo positivo, mas no meio do processo surgiu a objeção de “too many”, sem que o NIST respondesse claramente onde estaria o limite
-
2. Exagero no custo de geração de chave
- Em benchmark com Golden Cove, o Kyber-512 teria encapsulation de 25829 cycles e decapsulation de 20847 cycles
- O NTRU-509 teria encapsulation de 15759 cycles e decapsulation de 25134 cycles, totalizando processamento de ciphertext 13% menor que o do Kyber-512
- Já a key generation do NTRU-509 seria de 112866 cycles, acima dos 17777 cycles do Kyber-512
- Mas o argumento é que, em KEM, a chave pode ser reutilizada para vários ciphertexts, o custo de transmitir bytes é muito mais importante que cycles, e a Montgomery trick pode acelerar a key generation do NTRU
-
3. Ocultar o nível de segurança mais alto do NTRU
- No relatório round-2 de 2020, o NIST passou a recomendar fortemente conjuntos de parâmetros de categoria 5
- O NTRU apresentou NTRU-1229 e NTRU-HRSS-1373, com Core-SVP 2^301 e 2^310, respectivamente, acima dos 2^254 do Kyber-1024
- O NTRU Prime também apresentou opções como
sntrup1277entrulpr1277, com Core-SVP 2^270 e 2^271 - A crítica é que os gráficos do NIST não evidenciaram adequadamente essas opções NTRU de segurança mais alta
-
4. Exclusão do NTRU-509, a opção de melhor desempenho
- O texto afirma que o NIST retirou o NTRU-509 de um gráfico grande e também de figuras e tabelas posteriores do selection report
- O NTRU-509 oferece key e ciphertext menores que os do Kyber-512, o que entraria em conflito com a descrição do NIST de que o NTRU teria public key e ciphertext “somewhat larger” que o Kyber
- Para excluir o NTRU-509, seria preciso dizer que ele fica abaixo do nível mínimo de segurança do AES-128, mas manter o Kyber-512 pelo mesmo critério seria, segundo a crítica, uma distinção muito frágil
Incertezas além do Core-SVP
- O Core-SVP do Kyber-512 é 2^118, enquanto o custo de ataque ao AES-128 é colocado um pouco acima de 2^140 bit operations
- Os documentos de submissão do Kyber de 2017 e 2019 afirmavam que ele era pelo menos 30 bits mais seguro que o Core-SVP, mas parte dessa justificativa é criticada como errada ou insuficiente
- O rounding noise não se aplicaria a ataques à key, então não serviria como base para aumento de segurança
- A alegação de aumento subexponencial no custo do sieving seria sem fundamento, e a assíntota real poderia até ser mais rápida que o Core-SVP
- O número de chamadas ao oráculo de SVP e o gate count podem ter algum mérito, mas não pareceriam suficientes para salvar o Kyber-512
- O custo de acesso à memória pode ser importante no custo real do ataque, mas os critérios oficiais do NIST exigiam 2^143 “classical gates”, então isso não serviria diretamente como justificativa de resgate do Kyber-512
- A submissão round-3 do Kyber teria mudado o Kyber-512 e redefinido o Core-SVP, obtendo 2^118 em vez de 2^112
- Essa submissão apresentou a segurança do Kyber-512 como 151 bits ±16 e argumentou que, mesmo caindo até 135, isso não seria “catastrophic” por causa dos requisitos de memória
- Depois surgiram várias análises de ataques de lattice, como a de Matzov, tornando a estimativa de segurança do Kyber-512 mais complexa e instável
A lógica do NIST para salvar o Kyber-512
- O call oficial do NIST afirma que cada categoria de segurança usa primitives de referência como o AES-128 como piso em várias métricas “potentially relevant”
- Ou seja, qualquer ataque precisaria exigir recursos acima da referência em todas as métricas que o NIST considere potencialmente relevantes para a segurança prática
- O NIST evitou por muito tempo definir claramente “classical gates” e, no selection report de 2022, explicou que aceitava leitura/escrita de memória de um bit como gate de custo 1
- A crítica é que, ao excluir o NTRU-509, o NIST usou um “non-local cost model”, isto é, um critério que trata custo de acesso à memória como praticamente grátis
- Em contrapartida, para manter o Kyber-512 na categoria 1, o NIST considerou que “realistic memory access costs” fariam o esquema satisfazer a categoria 1
- O resultado, segundo a crítica, é que foi aplicado um critério de memória grátis ao NTRU-509 e um critério de memória cara ao Kyber-512
NISTBS: contestação à explicação de 7 de dezembro de 2022
- Em 7 de dezembro de 2022, o NIST explicou por que considerava que o Kyber-512 satisfazia a categoria I do NIST, e este texto chama essa explicação de “NISTBS”
- O NISTBS parte da estimativa do relatório de Matzov de que o custo do ataque ao Kyber-512 seria 2^137 bit operations
- O custo do ataque clássico ao AES-128 é estimado em cerca de 2^143 bit operations
- Portanto, faltariam 6 bits
- O NISTBS explica que ataques de lattice sieving exigem acesso não estruturado a grandes memórias, e que o modelo RAM ignora esse custo
- Em seguida, cita avaliações das submissões NTRU e NTRU Prime para dizer que, ao considerar o custo de acesso à memória em ataques de sieving da categoria 1, o valor poderia ser “20~40 bits” maior que no modelo RAM
- O problema, segundo a crítica, é que o NIST parece ter somado esses 40 bits do NTRU Prime aos 2^137 de Matzov, interpretando isso como algo no nível de 2^177
- Os 40 bits do NTRU Prime parecem vir da diferença entre “real” 2^169 e “free” 2^129 em
sntrup653 - O 2^129 é o Core-SVP, isto é, uma estimativa aproximada do número de iterações, e não o gate count do modelo RAM mencionado pelo NIST
- O custo de acesso à memória deve ser somado ao custo por iteração; ele não pode ser multiplicado pelo custo computacional total já agregado em bit operations nem adicionado diretamente ao expoente dessa forma
- Os 40 bits do NTRU Prime parecem vir da diferença entre “real” 2^169 e “free” 2^129 em
O significado real dos números
- O documento do NTRU Prime informa Core-SVP 2^129 para
sntrup653- Isso é uma estimativa aproximada do número de iterações
- O mesmo documento estima o custo total de acesso à memória como equivalente a 2^169 bit operations
- O Kyber-512 é apresentado com Core-SVP 2^118
- Fazendo uma estimativa grosseira do custo de acesso à memória da mesma forma, o texto diz que o valor seria equivalente a 2^154 bit operations
- A estimativa de 2^151 “gates” do documento do Kyber não é uma estimativa de custo de acesso à memória
- Ela estima a quantidade de bit operations dentro do cálculo do ataque
- Considerando “known unknowns”, o intervalo apresentado é de 2^135~2^167
- Portanto, a estimativa de custo computacional 2^151 e a estimativa de custo de acesso à memória não são fatores a serem multiplicados entre si; são termos que precisam ser somados de forma compatível dentro do custo por iteração
Por que o erro seria fácil de detectar
- Um sanity check simples seria o seguinte
- O documento do Kyber estima o custo computacional do ataque ao Kyber-512 em 2^135~2^167 bit operations
- O NTRU Prime estima o custo de acesso à memória em algo equivalente a 2^169 bit operations para
sntrup653, que pareceria mais difícil que o Kyber-512 - Se o ataque melhorou em 2^14, então calcular o custo do ataque ao Kyber-512 como 2^177, como o NIST teria feito, soa estranho
- O NISTBS escreveu que o documento do NTRU Prime estimava “40 bits de segurança extra em relação ao modelo RAM”, mas a Seção 6.11 desse documento não traz diretamente as expressões “40” nem “RAM model”
- A crítica é que, para uma revisão clara, o NIST deveria ter explicado exatamente de onde veio esse 40, a que valor ele se refere e em qual métrica
- Depois de dezembro de 2022, foi feita a pergunta direta sobre um cenário específico: “o cálculo foi mesmo 137+40=177?”; segundo o texto, o NIST não respondeu
- Depois, o NIST teria dito apenas que o e-mail “speaks for itself”, sem confirmar uma interpretação específica do cálculo nem oferecer interpretação alternativa
A pesquisa necessária para o cálculo correto
- Um cálculo correto precisa separar dois efeitos
- Parte do aumento da estimativa de segurança acima do Core-SVP vem do custo em bit operations do cálculo interno de cada iteração
- Outra parte vem do aumento no próprio número de iterações no loop externo em relação ao Core-SVP
- O efeito de aumento no número de iterações pode ser multiplicado pelo custo de acesso à memória
- Já o custo computacional interno da iteração e o custo interno de acesso à memória devem ser somados; multiplicá-los é o erro central
- Um cálculo preciso exigiria reotimizar toda a pilha de ataques à luz da literatura mais recente sobre lattice attacks, incorporando o custo de acesso à memória
- Por exemplo, mesmo dentro do BKZ, seria necessário recalcular o que é mais vantajoso entre low-memory enumeration e high-memory sieving quando se considera o custo de memória
Rascunho do padrão e questão de responsabilidade
- Em agosto de 2023, o NIST publicou o rascunho do padrão Kyber, o ML-KEM
- ML-KEM-512 é security category 1
- ML-KEM-768 é category 3
- ML-KEM-1024 é descrito como “claimed” category 5
- O problema é que não está claro quem é o sujeito de “claimed”
- A crítica pergunta se a alegação é do NIST, dos projetistas ou de outra parte
- O Apêndice A do rascunho reafirma o critério de que as categorias devem superar AES-128, AES-192 e AES-256 em todas as métricas potentially relevant
- A análise mais recente dos documentos do Kyber sugere que o custo do ataque ao Kyber-512 pode cair até 2^135 “classical gates”, abaixo da estimativa do NIST de 2^143 gates para o AES-128
- Por isso, a crítica pede uma análise pública explicando como o NIST justifica a afirmação de que o Kyber-512 está acima do AES-128 em todas as métricas relevantes
Conclusão e proposta
- A conclusão é que a superfície de ataques de lattice é instável e ainda insuficientemente compreendida, então padronizar o Kyber-512 seria imprudente
- O Kyber-512 pode ser muito mais fácil de quebrar que o AES-128 mesmo considerando os ataques já publicados e o custo de acesso à memória, embora também exista a possibilidade contrária; esclarecer o estado real exigiria pesquisa difícil
- O próprio AES-128, em ataques multi-target, pode cair para algo como 2^88 computations para quebrar uma entre 1 trilhão de chaves, então uma perda de 10 a 30 bits não seria desprezível
- Se o Kyber-512 permanecer como opção padrão, o texto considera provável que aplicações capazes de suportar Kyber-1024 ou NTRU-1229 ainda escolham a opção mais rápida
- A recomendação final é remover o Kyber-512 e que o NIST reconheça publicamente o erro de cálculo no nível de segurança do Kyber-512 e a seleção opaca de dados na comparação com o NTRU
1 comentários
Comentários do Hacker News
O ponto que é essencial saber antes de ler este texto é que não foram o NIST e a NSA que criaram este algoritmo, eles avaliaram a competição
A maior parte da análise foi conduzida pelos concorrentes e pela academia, e a equipe do Kyber inclui Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, Damien Stehlé, além de Peter Schwabe, colaborador de Bernstein
Historicamente, muitas vezes só o vencedor acaba sendo adotado. Basta olhar para a competição do AES e pensar em quão frequentemente o Serpent, avaliado como tendo uma margem de segurança maior que a do Rijndael, é mencionado
Não parece que o NIST faça recomendações com base em alguma análise secreta
A realidade lamentável é que Bernstein pode estar certo, mas é difícil distinguir se a resposta — ou a falta de resposta — do NIST deve ser vista como enganação, ou se eles simplesmente não queriam se envolver com alguém que chega com uma postura muito agressiva.
No NIST também trabalham pessoas comuns, e é bem provável que tenham recebido essas exigências ríspidas de explicação de forma parecida com a maneira como a maioria de nós recebe relatórios de bugs agressivos.
Acusações exageradas como “vocês expuseram 3 anos de dados de usuários a atacantes ao mandar usar Kyber a partir de quando a licença de patente for ativada em 2024, e não mandaram usar NTRU desde 2021” não ajudam. Provavelmente ninguém vai implantar criptografia pós-quântica independente de imediato por um bom tempo, e em 2021 havia várias alternativas que o NIST poderia ter sugerido. SIKE parecia bastante promissor até ser quebrado no ano passado.
O NIST não tem uma reputação impecável nessa área, mas, para criticar o algoritmo e o processo, seria bom ter um resumo conciso do porquê e uma ou duas provas decisivas. Análises de inúmeros e-mails, comparação com apenas uma submissão e acusações de que todos estavam ganhando tempo para sugar dados tornam difícil levar isso a sério. Se Kyber-512 é de fato tão perigoso assim, isso precisa ser comunicado com mais clareza.
O fato de a página ter 17.000 palavras também pesa. Mesmo pelos padrões de Harry Potter, é um volume que levaria 70 minutos para um leitor médio ler, e este texto não é um romance: está cheio de números, ressalvas e frases cuja escolha de palavras precisa ser examinada, como citações do NIST. Mesmo com a base necessária para entender criptografia pós-quântica, é difícil ler rápido como um livro comum.
No começo, cliquei em “That lawsuit has been gradually secret NIST documents, shedding some light on what was actually going on behind the scenes” e acabei sugado para outro texto; a página linkada tinha mais 54.000 palavras. No celular, sem barra de rolagem, eu não sabia o tamanho e fui passando de forma linear, até que em algum momento senti como se tivesse me matriculado em um projeto de pesquisa de doutorado, fechei a aba e voltei ao texto original.
Os leitores do HN são inteligentes e muitos são técnicos, mas vêm de áreas variadas, então é difícil avaliar racionalmente provas cheias de jargão especializado que supostamente sustentam “NIST = ruim”. Por estar em uma área adjacente, acho que entendo mais do que o leitor médio, mas não sinto que tenho legitimidade para julgar sem ler direito. O texto até explica contexto e siglas, mas o volume é tão grande que não sei se alguém que já não conheça o assunto teria vontade de ler. Nem toda submissão precisa ser compreensível para todo mundo, mas, como esta contém acusações, fico em dúvida se é um texto adequado para o HN.
Então talvez eu recue um pouco do que disse abaixo e, no mínimo, acho mais compreensível o tom agressivo de djb considerando o histórico dele com recomendações do NIST. Há informações relacionadas em https://en.wikipedia.org/wiki/Daniel_J._Bernstein#Cryptograp....
Não gosto de focar demais na forma em detrimento do conteúdo, mas, neste caso, o formato do post do blog era tão ruim que ficou difícil avaliar se o conteúdo tinha valor. Como não sou da área de criptografia, não consigo avaliar o mérito, mas o sarcasmo e as depreciações desnecessárias tornaram a mensagem muito suspeita. Mesmo quando parecia apontar bons pontos, o tom geral lembrava um vídeo do YouTube do tipo “WhaT ThE ElITe DoN'T WanT YoU TO KnoW!!”, e, mesmo que esteja certo, o autor soa bastante desagradável.
Também fico curioso se alguém realmente leu isso até o fim. Talvez seja verdade que a internet matou nossa capacidade de concentração, mas, por outro lado, hoje há informação demais e acabamos escolhendo com muito rigor onde gastar nosso tempo. Se for um post de blog, os detalhes relevantes e um resumo deveriam estar nos primeiros parágrafos, deixando o diário longo e errante para depois. Se as partes importantes estão escondidas como um Where's Waldo dentro de um diário prolixo, é difícil esperar que as pessoas leiam tudo.
O ponto central que ele pergunta repetidamente é por que os critérios de avaliação foram mudados várias vezes depois do fato, por que os resultados foram apresentados de forma enganosa e por que houve erros básicos de cálculo. Essas pessoas são especialistas, e todas essas coisas favoreceram um único algoritmo.
Aos meus olhos, isso parece um sinal de que queriam transformar aquele algoritmo em padrão. Some-se a isso o fato de que o envolvimento da NSA foi muito maior do que se sabia e que tentaram ocultá-lo, e eu passo a desconfiar extremamente desse padrão.
Isso é um problema porque esses algoritmos em breve serão incorporados ao hardware.
Uma vez definida a implementação que será padronizada, é provável que fabricantes de hardware comecem a projetar blocos para calcular o padrão FIPS 203 de forma mais eficiente. Talvez alguns já tenham sido projetados.
Considerando que a publicação do padrão é esperada para 2024 e que a análise do NIST CMVP para módulos FIPS leva de 1 a 2 anos, não seria surpreendente ver, por volta de meados de 2026, módulos de hardware FIPS 140-3 contendo ML-KEM (Kyber etc.).
O ponto central parece ser a frase de [1]: “No entanto, o NIST não fez uma declaração clara de ponta a ponta de que Kyber-512 tem uma margem de segurança de N bits no cenário X para (N,X) claramente especificados”.
Em [2], djb resumiu de forma concisa o que chama de “cenário X” e diz que só precisa de uma resposta sim/não. Ele está perguntando a pessoas que de fato precisam saber disso e têm a base técnica para discutir o assunto. Como não recebeu resposta, publicou [1].
A resposta do NIST em [3] descartou [1] sem discutir a segurança em si. O segundo parágrafo, em especial, foi frustrante. “O e-mail citado (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...) fala por si só. O NIST continua interessado nas opiniões das pessoas sobre se o plano atual de padronizar o Kyber512 é bom. Revisores têm a liberdade de, por diversão, tentar refutar aquilo que parece ser a alegação do NIST sobre margem de segurança, mas o resultado não será particularmente útil para o processo de padronização. As alegações anteriores do NIST e sua interpretação não têm relação com o fato de as pessoas acreditarem ou não que padronizar o Kyber512 seja uma boa ideia”
Se o NIST considera as alegações relacionadas à segurança feitas pelos revisores como “não particularmente úteis para o processo de padronização”, por que o público deveria confiar nesse padrão, considerando que esses revisores são criptógrafos?
É inevitável que não haja uma prova decisiva. O ponto em discussão agora é justamente a falta de uma explicação clara. Se fosse possível explicar como foi calculado o nível de segurança do Kyber-512, a situação seria outra.
Pelas estimativas atuais de terceiros, o valor um tanto ambíguo chamado nível de segurança do Kyber-512 fica abaixo dos requisitos originais, então parece necessária uma explicação ou justificativa.
[1]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[2]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
[3]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/4MBu...
Se este fosse um texto de alguém desconhecido, talvez eu concordasse, mas os autores são DJB ou Tanja Lange, e nenhum dos dois é desconhecido.
Esse tipo de coisa, até certo ponto, inevitavelmente acaba sendo adversarial. A criptoanálise às vezes exige essa postura, e também houve várias situações suspeitas no passado. Faz parte da área e da política, então é difícil evitar.
Isto está mais para um diário do que para um artigo. Tem muito jargão, não está bem organizado, fica dando voltas no mesmo ponto e é muito difícil de acompanhar
Ainda assim, a informação em si pode ser importante. Há uma forte insinuação de que o NIST, com ajuda da NSA, padronizou de propósito um algoritmo fraco
Todos sabemos que isso é possível
Mas, se houver alguém que acompanhe essa área mais de perto, gostaria que explicasse o que significam esses números aqui. Sempre achei que enfraquecer criptografia pública desse jeito é uma aposta arriscada, porque não dá para garantir que um atacante não descubra o mesmo fato de forma independente. Uma chave secreta de backdoor pode ser escondida. Eram essas as suspeitas quando surgiu o Dual_EC_DRBG. Mas resultados matemáticos são realmente difíceis de esconder
Por que eles teriam querido correr esse risco aqui?
A esta altura, nem sei por que essa discussão é necessária. Não precisamos mais deles. As restrições de exportação também acabaram
O que precisamos é de um consórcio que chame a atenção dos fabricantes de hardware e limite o NIST e a NSA ao status de simples participantes. Assim, mesmo que o governo adote um padrão com backdoor, só eles o usariam
Por que eles se importariam com isso?
A estimativa atual sobre o que pode ter acontecido nas curvas elípticas do NIST vai nessa direção
Nesse caso, poderia ser, por muito tempo, um backdoor praticamente exclusivo dos EUA
A ideia era que eles poderiam se manter à frente nos ataques e que, quando chaves de 56 bits ficassem fracas demais em geral, o DES já teria sido substituído por outra coisa. Foi arriscado? Sim. Mas, em certo sentido, “funcionou”. Então eu não assumiria que algo parecido jamais voltará a acontecer
A teoria por trás disso é chamada de kleptografia (kleptography). Isso também significa que a NSA é paranoica o suficiente para achar que consegue roubar informações de forma “segura”
No ano passado houve uma thread relacionada com 443 comentários
https://news.ycombinator.com/item?id=32360533 ("NSA, NIST, and post-quantum crypto: my second lawsuit against the US government (cr.yp.to)")
“Descobrir como o NISTPQC funciona em segredo. Em março de 2022, fiz um pedido via FOIA chamado ‘NSA, NIST, and post-quantum cryptography’. O NIST violou a lei e ficou ganhando tempo. O escritório de direitos civis Loevy & Loevy entrou com uma ação em meu nome”
Pessoalmente, em geral não gosto do djb, mas profissionalmente ele tem pressionado o governo federal nos tribunais de forma consistente, então sempre o apoio. Fico muito feliz em ver que ele ainda continua fazendo isso
Independentemente de DJB ser uma figura importante na criptografia, e de eu desconhecer boa parte dos detalhes aqui, houve um ponto em que a credibilidade caiu bastante
Especialmente na parte dos gráficos, ele diz que “o NIST decidiu usar barras vermelhas mais finas no gráfico de largura de banda para dar menos destaque”, mas as evidências não demonstram isso de forma alguma. Há uma explicação muito mais plausível. O gráfico com barras mais finas é um gráfico de barras com mais pontos de dados do que os outros. Abra qualquer ferramenta de gráficos e compare um gráfico com 12 pontos de dados com outro de 9; é natural que as linhas do de 12 fiquem mais finas. Nesse ponto, tive uma forte impressão de que ele estava tentando interpretar todas as ações da forma mais maliciosa possível
No item seguinte, ele reclama que não usaram escala logarítmica, embora os valores estejam na mesma ordem de grandeza. Não parece um bom caso para usar escala logarítmica, e não sei bem por que isso seria justificável aqui
Sabendo que DJB esteve envolvido com o NTRU, é difícil afastar a sensação de que boa parte disso é uma reação amarga por ter perdido a competição
Qualquer outra suposição me parece, no mínimo, bastante ingênua
Há motivos suficientes para suspeitar
É natural que concorrentes da área acabem revisando o trabalho uns dos outros
O que aprendi observando profissionalmente brigas incendiárias entre criptógrafos: não aposte contra Bernstein e não confie no NIST
O NIST respondeu: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/W2VO...
Não sei se ainda resta alguma confiança no N(IST)SA
É encorajador que curve25519 seja mais usado do que as curvas P deles, e espero que a comunidade continue nessa direção e passe, em grande parte, a ignorá-los no futuro
O governo não deve liderar nem decidir. Para FIPS, regulações etc., seria melhor estruturar o processo em torno de reunir e seguir o consenso atual